作者 | Paul Cavallaro

譯者 | 蘇本如，責編 | 屠敏

出品 | CSDN（ID：CSDNnews）

以下為譯文：

本篇文章中，將會概述一些常用的優化技術和“系統編程”的一些妙招。不管今天的“系統編程”意味著什么，我們將介紹一些方法，以便你的代碼運行更快、更加高效，并能讓你從你得到的任何知識中收獲更多的好處。

這篇文章里討論的所有示例可以在GitHub的這個地方獲取：paulcavallaro/systems-programming。

緩存線和偽共享

在現代對稱多處理（SMP）系統上，“偽共享”（False sharing）是一個非常容易理解的多線程代碼優化的問題。對于這個問題的討論已經相當廣泛了。一個基本的思想是機器上的物理內存不是無限粒度的，也就是說，你不能僅僅讀取一個字節。相反，當你想要讀取一個字節的內存時，處理器不僅會讀入并緩存這個字節，而且會讀入并緩存該字節周圍的數據，因為它假設這些數據也可能被使用。這個被讀取和緩存的數據單元被稱為“緩存線”，本質上它是可以訪問的最小內存塊。

截至2019年，緩存線的大小都是2 的乘方，通常介于32到256個字節之間，其中最常見的大小是64個字節。

現在，為了支持一臺機器上的多個處理器以一致的方式從同一塊內存中讀和寫，這臺機器上必須只有一個處理器可以獨占地訪問給定的緩存線。

“偽共享”是指意外地將兩個不相關的數據塊放在同一緩存行中。當有兩個處理器分別更新這兩個不同的數據塊中的數據時，比如多個計數器的值，就會產生互相干擾，因為每個處理器都試圖以獨占的方式訪問包含這兩個數據塊的緩存線。

對“偽共享”這個名稱的解釋是，盡管這兩個計數器從理論上來講不應該互相影響，但它們沒有任何好的理由地“錯誤地共享”了一個緩存線。

一種解決方案是將強行將數據寫入到分開的緩存行上，在C/C++語言中，這可以通過強制結構體/類（struct/class）成員的對齊來實現。在這個示例examples/cache-lines.cc中，我們使用abseil（注：谷歌內部使用多年的 C++ 代碼庫，現已開源）宏ABSL_CACHELINE_ALIGNED來實現這一點。

為了證明實際效果，我們針對兩個不同的結構體NormalCounters和CacheLineAwareCounters 中的std::atomic<int64> 類型的計數器做了基準測試。

// NormalCounters is straight forward naive implementation of a struct of
// counters.
// Note: We also use ABSL_CACHELINE_ALIGNED on the NormalCounters struct, but
// not its members, so that the entire struct will be aligned to a cache line.
// Otherwise the struct might be placed towards the end of a cache line,
// accidentally straddling two cache lines, thereby improving its performance.
struct ABSL_CACHELINE_ALIGNED NormalCounters {
std::atomic<int64> success{0};
std::atomic<int64> failure{0};
std::atomic<int64> okay{0};
std::atomic<int64> meh{0};
};

// CacheLineAwareCounters forces each counter onto a separate cache line to
// avoid any false sharing between the counters.
// Note: We must use ABSL_CACHELINE_ALIGNED for each member, since we want to
// pad every single counter so it will be forced onto its own separate cache
// line.
struct ABSL_CACHELINE_ALIGNED CacheLineAwareCounters {
ABSL_CACHELINE_ALIGNED std::atomic<int64> success{0};
ABSL_CACHELINE_ALIGNED std::atomic<int64> failure{0};
ABSL_CACHELINE_ALIGNED std::atomic<int64> okay{0};
ABSL_CACHELINE_ALIGNED std::atomic<int64> meh{0};
};

這個基準測試分別測試了在運行1個，2個，3個和4個線程的情況。每個線程會觸發結構體內一個單獨的原子計數器65,536次。以下是在帶有Haswell處理器的2013 MacBook Pro計算機上的處理結果：

Executing tests from //examples:cache-lines
-----------------------------------------------------------------------------
Cache Line Size: 64
sizeof(NormalCounters)=64
sizeof(CacheLineAwareCounters)=256
2019-08-13 01:16:18
Run on (4 X 2800 MHz CPU s)
CPU Caches:
L1 Data 32K (x2)
L1 Instruction 32K (x2)
L2 Unified 262K (x2)
L3 Unified 4194K (x1)
---------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------
BM_NormalCounters/threads:1 389 us 387 us 1812
BM_NormalCounters/threads:2 1264 us 2517 us 234
BM_NormalCounters/threads:3 1286 us 3718 us 225
BM_NormalCounters/threads:4 1073 us 3660 us 204
BM_CacheLineAwareCounters/threads:1 386 us 385 us 1799
BM_CacheLineAwareCounters/threads:2 200 us 400 us 1658
BM_CacheLineAwareCounters/threads:3 208 us 581 us 1152
BM_CacheLineAwareCounters/threads:4 193 us 721 us 1008

對上述結果作個注釋：Time代表每個線程的從開始到結束的掛鐘時間(wall clock time)，而CPU則代表每個線程使用的CPU時間。

我們可以看到兩個結構體的大小是不同的，其中：sizeof(NormalCounters)=64 ，而 sizeof(CacheLineAwareCounters)=256。這是因為我們對單個字段施加了對齊約束，這樣每個成員都在自己的緩存線上。因此，它不是像往常的Int64那樣占用8個字節，而是占用一個完整的緩存線，在我的機器上是64個字節。

我們還看到對于單線程的情況，NormalCounters與CacheLineWareCounters的性能差別微乎其微。但是當我們添加更多線程時，CacheLineAwareCounters的表現要比那些易受“偽共享”錯誤影響的簡單的普通計數器的實現要好得多。

有趣的是，在單線程的情況下，CacheLineAwareCounters需要的掛鐘時間(wall clock time)比多線程情況下要長，這可能指向一些微妙的基準測試問題，或者可能有一個固定的延遲量，但是在多線程時這個延遲量被分散到多個線程中，因此每個線程的延遲量看上去更小了。

神奇的2的乘方（冪）

在當前的硬件中，除法是最昂貴的操作之一，這里的昂貴意味著“最長延遲”。Agner Fog的指令延遲列表列出了英特爾公司Skylake處理器的DIV指令在兩個64位寄存器上運行，其延遲為35-88個周期，而在相同的兩個64位寄存器上運行ADD指令的延遲只有1個周期。因此，在其它操作能夠完成相同工作的地方，我們應該盡量避免使用除法操作。

除了實際做除法外，除法操作常用的一個地方是取模運算（%）。而取模運算的一個常用的地方是hash表：要從一個hash表轉到一個存儲桶(bucket)，需要進行HASH % TABLE_SIZE這樣的取模運算。取模運算的另一個更加頻繁使用的地方是開放尋址算法，因為我們需要不斷地將值重新映射回hash表存儲桶空間。

那么，取模運算如何幫助我們從hash表轉到存儲桶呢？這就要講到有點無聊但是很神奇的2的乘方了！

首先，讓我透露答案：我們將強制所有hash表的大小為2的N次方（冪）。

我們可以利用這個特性用更快的位運算（bit twiddling）來代替除法運算。另外，這個特性很容易維護，每當我們需要增加hash表的大小以攤銷rehashing的成本時，我們都會將hash表的大小增加一倍，因此隨著hash表的增長，它的大小將保持為2的冪。

現在，我們使用除法運算或者取模運算，將hash值映射到hash表中的bucket索引上。bucket索引必須嚴格小于hash表的大小，并且這個映射的散列值應該是無序狀態。

為了不使用除法運算，我們將使用位掩碼（bitmask）來“屏蔽”所有的設置位,除了那些嚴格小于2的冪的設置位之外。這種方式可以將所有的entropy保持在最低有效位，就像取模運算一樣，但它要快得多。Agner Fog在相同的英特爾 Skylake體系結構中把這種運算放在1周期延遲的指令列表中。

作為關于位運算（bit twiddling）和解釋如何選擇位掩碼（bitmask）的一個簡單回顧，讓我們來看看一些位模式（bit patterns）。

因為數字是用二進制表示的，所以我們知道每一個2的冪（數值N）只有一個位集。例如：

Decimal | Binary
2 | 00 00 00 10
8 | 00 00 10 00
32 | 00 10 00 00
128 | 10 00 00 00

這意味著所有的N-1的值都比log2（N）的有效位低一位。例如：

Decimal | Binary
1 | 00 00 00 01
7 | 00 00 01 11
31 | 00 01 11 11
127 | 01 11 11 11

因此，為了在HASH % N計算中替代我們的取模運算符，我們使用“按位和（bitwise AND）”運算來計算HASH &(N-1)的值。這將只保留比我們的log_2(N)位低的設置位，將任何HASH值映射到一個[0，N]之間的數字。如果需要，我們甚至可以緩存這個位掩碼，這樣以后就不必重新計算它了。

為了展示使用“位掩碼”技巧比使用普通的取模運算的速度要快，我編寫了一個小基準測試來比較執行一百萬次取模運算和一百萬次“位掩碼”運算的結果。

Executing tests from //examples:power-of-two
-----------------------------------------------------------------------------
2019-08-13 02:24:03
Run on (4 X 2800 MHz CPU s)
CPU Caches:
L1 Data 32K (x2)
L1 Instruction 32K (x2)
L2 Unified 262K (x2)
L3 Unified 4194K (x1)
--------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------
BM_Mod 9261 us 9234 us 75
BM_BitMask 325 us 324 us 1984

從上面的測試結果我們可以看到，使用取模操作符執行DIV指令要比使用“位掩碼”大約慢28倍，這個結果接近Agner Fog的慢35倍的預測值。

因為這個技巧很容易做到，并且提供了一個很好的例子，它已經被許多高性能的hash表使用，比如abseil Swiss Tables的flat_hash_set和flat_hash_map，以及ConcurrencyKit’s ck_ht_map。

尋址空間高位(Top Bit)用途的調整

通常情況下，你想在一個指針上存儲一兩個額外的信息。事實上，這種做法非常常見，以至于維基百科有一篇專門關于它的文章。實現這一點的一種方法是利用許多64位系統（如Linux）上的虛擬內存地址空間只有48位的這個特性，盡管我們使用8個字節來存儲它們。

這意味著，我們可以把任何我們想要的舊東西放在前16位，當我們真正不想引用它時，就可以屏蔽掉它。下面是一些使用指針的高位(top bit)來存儲底層數據是否“臟了”的C++代碼示例。

constexpr uintptr_t kDirtyBit=0x8000000000000000;
constexpr uintptr_t kPtrMask=0x7fffffffffffffff;
static_assert(sizeof(uintptr_t)==8, "Only works on 64-bit systems");

template <typename T>
uintptr_t MarkDirty(T* t) {
return reinterpret_cast<uintptr_t>(t) | kDirtyBit;
}

template <typename T>
T* GetPointer(uintptr_t t) {
return reinterpret_cast<T*>(t & kPtrMask);
}

不過，有趣的是，由于這是Linux內存管理/虛擬地址空間的一個特性，所以它可能會發生變化，而且實際上已經發生了變化！

LWN（Linux Weekly News）在2017年發布了補丁集，實現了五級頁表，以支持更大數量的可尋址內存空間。如果啟用這個更改的話，Linux的虛擬內存尋址空間將從現在48位提高到57位，從而將虛擬內存尋址空間的大小從256 TiB增加到128 PiB，這對于每個人來說都足夠了。

默認情況下這個更改無法啟用。部分原因是各種高性能程序，特別是各種JavaScript引擎和 LuaJIT，對尋址空間高位用途的調整會導致一些額外的數據被打包到指針中。

鎖定條帶化(Lock Striping)

當你希望多個線程以獨占方式訪問共享數據時，鎖可以用于互斥。但缺點是，如果共享數據被頻繁訪問，而且這是系統的關鍵部分的話，那么線程可能會將大部分時間花在鎖的爭用上，而不是實際工作上。

解決這個問題的一個常見方法是引入更多的鎖。你說什么？等一下！

好吧，我想說的是：不是一個保護所有數據的鎖，而是有許多只負責一部分數據的鎖。通過這種方式，我們將數據分成獨立的、互不競爭的存儲桶。假設數據訪問方式都傾向于一致的，增加數據的切分會按比例減少爭用鎖的線程數。

下面是用C++寫的一個小例子，提供了線程安全的hash-set的兩種實現。第一個實現ThreadSafeHashSet使用單個鎖來保護單個基礎hash-set（absl::flat_hash_set）。第二個實現LockStripedHashSet有N個單獨的鎖，保護N個單獨的基礎hash-set（abs::flat_hash_sets）。

// Simple thread-safe single-lock hash set
class ThreadSafeHashSet {
public:
void Insert(uint64 i) {
absl::MutexLock lock(&mu_);
hash_set_.insert(i);
}

bool Contains(uint64 i) {
absl::MutexLock lock(&mu_);
return hash_set_.contains(i);
}

private:
absl::Mutex mu_;
absl::flat_hash_set<uint64> hash_set_;
};

// Chunk the data into `kNumChunks` separate hash sets, guarded by separate
// locks.
template <size_t kNumChunks>
class LockStripedHashSet {
public:
void Insert(uint64 i) {
// Mod the data to calculate which hash_set/lock to use
const size_t idx=i % kNumChunks;
absl::MutexLock lock(&mu_[idx]);
hash_set_[idx].insert(i);
}

bool Contains(uint64 i) {
const size_t idx=i % kNumChunks;
absl::MutexLock lock(&mu_[idx]);
return hash_set_[idx].contains(i);
}

private:
std::array<absl::Mutex, kNumChunks> mu_;
std::array<absl::flat_hash_set<uint64>, kNumChunks> hash_set_;
};

為了說明鎖定條帶化的好處，我們在多個線程存在的情況下對兩個線程安全的hash-set性能進行了基準測試，每個線程都插入了一百萬項。對于LockStripedHashSet，我們嘗試將數據拆分成4塊和8塊。結果如下：

Executing tests from //examples:lock-striping
-----------------------------------------------------------------------------
2019-08-24 22:24:37
Run on (4 X 2800 MHz CPU s)
CPU Caches:
L1 Data 32K (x2)
L1 Instruction 32K (x2)
L2 Unified 262K (x2)
L3 Unified 4194K (x1)
--------------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------------
BM_SingleLock/threads:1 65 ms 65 ms 11
BM_SingleLock/threads:2 140 ms 254 ms 2
BM_SingleLock/threads:3 140 ms 332 ms 3
BM_SingleLock/threads:4 142 ms 405 ms 4
BM_LockStriping_4_Chunks/threads:1 71 ms 69 ms 9
BM_LockStriping_4_Chunks/threads:2 90 ms 178 ms 4
BM_LockStriping_4_Chunks/threads:3 89 ms 248 ms 3
BM_LockStriping_4_Chunks/threads:4 82 ms 299 ms 4
BM_LockStriping_8_Chunks/threads:1 70 ms 69 ms 10
BM_LockStriping_8_Chunks/threads:2 74 ms 143 ms 4
BM_LockStriping_8_Chunks/threads:3 71 ms 198 ms 3
BM_LockStriping_8_Chunks/threads:4 60 ms 200 ms 4

同樣地，Time代表每個線程的掛鐘時間(wall clock time)，CPU代表每個線程使用的CPU時間。另外請注意，由于我的機器只有4個邏輯內核，所以這個測試最多只能運行4個線程，因為超出這個范圍的任何線程實際上都不會導致任何額外的爭用。

從上面我們可以看到，在單線程的情況下，LockStripedHashSet無論是分塊或不分塊，掛鐘時鐘和CPU時間上的表現都比簡單的ThreadSafeHashSet稍差。

然而，隨著線程數量的增加，對鎖的爭用增加，LockStripedHashSet在這種情況下性能要好得多。在線程數較高的情況下，將數據拆分成8塊優于拆分成4塊的情況。

雖然鎖定條帶化可以幫助減輕對鎖的爭用，但它的缺點是增加了鎖的存儲開銷。在我們的示例中，7個額外的鎖和額外的absl::flat_hash_set簿記的開銷對于我們的基準中的一個實例來說是很小的，但是如果你在一個應用程序中用一個8路條帶化的線程安全的hash-set替換所有這些散列集，那么你可能會使其內存使用量大大增加。

結束語

雖然以上還遠遠不是最常見的系統編程技巧的詳盡列表，但希望它能激發你進一步學習的欲望，掌握更多的工具來提高你自己的應用程序的性能，或者至少它能讓你更容易地理解為什么性能敏感的代碼在做它正在做的事情。

原文：https://paulcavallaro.com/blog/common-systems-programming-optimizations-tricks/

本文為 CSDN 翻譯，轉載請注明來源出處。

【End】

據下圖的三相交流電動機正反轉控制的主電路，設計一個PLC控制電動機正停反的控制系統。控制要求如下：

（1）正常情況下，按啟動按鈕SB1，電機正轉，按下反轉啟動按鈕SB2，電機反轉。

（2）電機啟動后，按下停止按鈕SB3并等待5秒鐘之后，才可以改變電動機的旋轉方向；

（3）如果SB1和SB2同時按下，電動機停止轉動，并且不起動，同時報警燈L1亮1秒暗1秒不斷閃爍。此時按SB3停止按鈕進行復位。

首先我們先確定一下按鈕、KM的使用輔助觸點情況，這里是正反轉的主回路，主回路必須有互鎖電路，其他的按鈕用常開觸點。

下面是PLC的輸入輸出點表：

根據題意（1）編程：這里根據題意1，只需2個自保持電路即可。

題意（2）要求按停止按鈕5秒后才能改變電機方向，所以這里需設置一個標志位，這里用M0.0。

并且加上程序互鎖電路，具體如下：

首先在2個自保持回路中加入互鎖電路——網絡1的Q0.1常閉點和網絡2的Q0.0常閉點。題意2說按下停止按鈕后5秒，才能按啟動按鈕，所以網絡3按下I0.2停止按鈕后，M0.0得電自保持，計時器T37計時5s后，將M0.0的自保持回路停掉。并且在網絡1和網絡2中加M0.0的常閉點，使M0.0得電時網絡1和網絡2即使按了正轉按鈕或者反轉按鈕也不會使Q0.0或Q0.1得電。

題意（3）要求SB1和SB2同時按下，電動機停止轉動，并且不起動，同時報警燈L1亮1秒暗1秒不斷閃爍。編程如下：

這次增加了網絡4/5/6，網絡5和6就是利用2個計時器產生一個一秒脈沖的小程序，SM0.0為特殊位，其功能為一直得電。網絡4就是利用M0.1將網絡1/2/3鎖死，也就是說M0.1得電網絡1.2.3是不起作用的。其原理與上一小結的M0.0一樣。

以上就是這個實例的全部編程。

正所謂萬丈高樓平地起，如果你叫小編一口氣編出來，小編也是很為難的。但是，將題意一點點拆分，一點點地把所需的功能寫入，最后一定可以合你心意。最后你看看編完的程序與最初的程序差了多少？

接下來，小編給大家介紹5種PLC編程方法：經驗法、解析法、圖解法、技巧法及計算機輔助設計法。

(1)經驗法 ：

運用已掌握的成功設計經驗，結合實際的情況，選擇與實際情況類似的一個或若干個成功的程序，或具有一些典型功能的標準程序作為“樣機”，對“樣機”逐一修改，直至滿足新的任務要求。在工作過程中，應多收集與積累這些“樣機”，從而不斷豐富自己的經驗。

(2)解析法 ：

PLC用于邏輯控制的編程方法可根據組合邏輯或時序邏輯的理論，并運用相應的解析方法，對其進行邏輯關系的求解。然后，再根據求解的結果，或畫成梯形圖，或直接編寫指令表。解析法比較嚴密，可以運用一定的標準，使程序優化與算法化，并可避免編程的盲目性，是一種比較有效的方法。

(3)圖解法：

圖解法是靠畫圖進行PLC程序設計。

常見的主要有3種方法：梯形圖法、波形圖法以及流程圖法。

梯形圖法是最基本的方法。無論是經驗法，還是解析法，若用梯形圖編寫PLC程序，就要用到梯形圖法。

波形圖法很適合于時序控制電路。它先把對應信號的波形畫出，再根據時間用邏輯關系去組合，就可以很容易地把電路設計出來。

流程圖法是用框圖來表示PLC程序的執行過程及輸入條件與輸出間的關系。在步進控制中，用它進行設計是很方便的。

(4)技巧法

技巧法是在經驗法及解析法的基礎上，運用技巧進行編程，以提高進行編程的質量。巧妙地使用PLC所提供的多種功能指令進行編程，是對已有經驗的“升華”，做到熟能生巧，實現創造性的編程。

(5)計算機輔助設計

PLC可通過上位連接單元與微型計算機連接，并運用微型機進行聯機輔助編程。計算機輔助編程，應有相應的軟件做支持。現有的編程軟件可把梯形圖翻譯成指令表。編程時，可先在計算機屏幕上設計梯形圖，然后再將該梯形圖轉換成對應的指令表。這種編程軟件有現成的，例如，日本三菱公司的MEDOC和GPP等

總結以上5種編程方法是不能截然分開的。如經驗法、解析法、技巧法都要用到圖解法，而技巧法又是經驗法的升華。

轉發是最大的鼓勵！謝謝您的支持！

小貼士

PLC專屬資料：含有從入門到高級所有PLC學習資料（三菱/西門子/歐姆龍），電氣經典18本大全書，歷年電氣考試真題、電氣必備實訓仿真軟件、電氣自動化行業各類型技術手冊！