1. C++ 17 選擇述句與初始化述句

    C++ 98 程式語言標準將 if、switch、while 與 for 述句的文法依序定義為:

    if (condition) statement
    if (condition) statement else statement
    switch (condition) statement
    while (condition) statement
    for (for-init-statement conditionopt; expression) statement

    其中,我們能在 condition 宣告一個變數[1],並使用此變數的數值控制執行流程。例如:

    #include <cstdlib>
    #include <ctime>
    #include <iostream>
    
    int main() {
      std::srand(std::time(NULL));
    
      if …

    More

  2. C++ 17: 以 std::scoped_lock 避免 Dead Lock

    最佳化多執行緒程式時,為了減少非必要阻塞(Blocking),常見作法是將一個 Mutex 依照保護對象拆分為多個 Mutex。如此一來,一個執行緒只需鎖定它需要的 Mutex,不必等待它不需要的 Mutex。有時我們會進一步實作「並行資料結構(Concurrent Data Structure)」,將 Mutex 的保護對象縮小到資料結構的節點,讓多個執行緒能同時讀寫一個資料結構。

    然而,同時操作多個 Mutex 必需留意一些技術細節。舉例來說,以下程式碼有問題:

    #include <mutex>
    
    struct Node {
      std::mutex m;
      int data;
    };
    
    void swap(Node &lhs, Node &rhs) {
      if (&lhs == &rhs) return;
      std::lock_guard …

    More

  3. C++ 17 結構化綁定

    今天我想要介紹 C++ 17 新增的 Structured Binding(結構化綁定)。以 std::pair 為例,Structured Binding 能讓我們能直接將 std::pair 的內容綁定到我們指定的識別字:

    auto [a, b] = std::make_pair("str", 0);
    

    在這個例子𥚃,a 是型別為 const char *"str"b 是型別為 int0。換句話說,上面的程式碼相當於:

    const char *a = "str";
    int b = 0;
    

    這讓我們能簡化「接收 std::pair …

    More

  4. 漫談 C/C++ 巨集展開規則

    最近工作上遇到一個和 C/C++ 巨集有關的問題。我想要使用巨集將原本呼叫 bcopy 的程式碼導向另一個實作 __bionic_bcopy。所以我寫出以下的程式碼:

    #define bcopy __bionic_bcopy
    

    然而這段程式碼會使得部分程式無法被正常地編譯。如果我將上面的 #define 改為:

    #define bcopy(src, dst, size) __bionic_copy(src, dst, size)
    

    原本被第一個 #define 弄壞的程式就能被正常地編譯了。然而這兩個 #define 的差異是什麼呢?以下是引起錯誤的程式片段:

    builtin.def

    #ifndef BUILTIN_LIBC
    #define BUILTIN_LIBC(NAME) BUILTIN(NAME)
    #endif
    
    BUILTIN_LIBC(bcopy)
    

    builtin.cpp

    enum BuiltinFunction {
    #define BUILTIN …

    More

  5. 簡介 perf_events 與 Call Graph

    Call Graph 是幫助 Perf Events 使用者判讀效能瓶頸成因的重要工具。Call Graph 優雅地結合「花去最多執行時間的熱區」與「為什麼要執行熱區內的程式碼」進而讓使用者能快速判斷程式有沒有改進空間。本文會從 Call Graph 的基本概念著手,再介紹記錄 Stack Trace 的注意事項與判讀 Call Graph 的方式。最後,本文會以一個文字處理程式示範如何利用 Call Graph 找出效能問題。

    Call Graph 概論

    perf report 印出的 Call Graph(呼叫圖)是以各個樣本的 Stack Trace(堆疊回溯)為基礎繪製而成的樹狀圖。因此本節會依序介紹 Stack Trace 與兩種不同的 Call Graph。

    Stack …

    More

  6. 使用 perf_events 分析程式效能

    在最佳化程式之前,我們必須要先測量程式的執行狀況,如此我們才能對症下藥。本文要介紹 Linux 核心內建的系統效能分析工具——perf_events

    perf_events

    perf_events 是 Linux 核心內建的系統效能分析工具。perf_events 一開始的主要功能是存取硬體效能計數器,所以最早的名字是 Performance Counters for Linux (PCL)。隨著功能不斷擴充,perf_events 能處理的事件來源已經不限於硬體效能計數器,所以改名為 perf_events

    有時候 perf_events 也被簡稱為 Perf。然而因為 Perf 作為一個單字是難以搜尋的常見字𢑥,所以 Vince WeaverBrendan Gregg 前輩通常使用 perf_events 稱呼這套工具。

    perf_events 這套工具分為三個部分:

    • 在 User Space 的 perf 指令
    • 在 …

    More

  7. The Case of the Missing Supercomputer Performance 心得

    因為最近的工作需求,我開始學習與補強系統效能分析方面的知識。所以我把同事之前推薦的論文 The Case of the Missing Supercomputer Performance [Fabrizio Petrini et al. 2003] 拿出來仔細研究。

    摘要

    這篇論文提出一個重要觀察:背景程式(Daemon)的干擾有時會嚴重影響特定負載(Workload)的執行速度。如果能妥善處理這些干擾,有機會可以讓總執行時間減半。

    這個結論在當時是非常特別的。因為在分析程式效能的時候,直覺的作法是專注分析「程式本身」的問題。有時候會從理論分析演算法或計算流程有沒有改善空間。有時是對程式做 Profiling,尋找有沒有明顯的熱區或者效能瓶頸。有時是改進編譯器,讓編譯器可以產生比較好的機器碼。然而這些作法背後都隱含一個假設:執行程式時,這個程式可以完全享有整個系統的計算資源。這對現代「分時多工的計算系統」而言是不成立的。

    論文舉出需要「Fine-Grained Synchronization」的負載特別容易被背景程式影響。以下是用 OpenMP 編寫的示意程式碼:

    for …

    More

  8. 簡介 Sparse Set

    最近讀一些論文的時候,學到 Sparse Set 資料結構。我覺得這個資料結構的設計還蠻有趣的,所以花一點時間把他記錄下來。

    Sparse Set 是一個儲存非負整數集合 {0, 1, 2, ... n - 1} 的資料結構。

    • 初始化的時間複雜度是 O(M)。這個資料結構本身只需要 O(1) 的初始化時間。M 是記憶體分配器配罝大小為 2 * n * sizeof(unsigned) 位元組的未初始化空間所需的時間。對大多數記憶體分配器而言,O(M) 可以視同 O(1)。
    • 增加一個成員的時間複雜度為 O(1)
    • 刪除一個成員的時間複雜度為 O(1)
    • 刪除所有成員的時間複雜度為 O(1)
    • 列舉所有成員所需的時間複雜度為 O(k),其中 k …

    More

  9. Python3: 淺談 Python 3.3 的 Yield From 表達式

    我最近需要使用 Python 2.7 解開 zip 壓縮檔並分析檔案內容。所以我寫了下面的程式。然而這個程式是有問題的。它沒有辦法列出 zip 壓縮檔裡面的檔案。為什麼呢?

    #!/usr/bin/env python
    
    import os
    import shutil
    import sys
    import tempfile
    import zipfile
    
    def unzip(zip_file_path, out_dir):
        with zipfile.ZipFile(zip_file_path) as zip_file:
            zip_file.extractall(out_dir)
    
    def list_files(path):
        for base, _, filenames in os.walk …

    More

  10. Python: defaultdict 的陷阱

    最近壓力比較大,讓我出賣一下我的同事。

    我的同事 L 最近要用 Python 寫一個函式 lookup()。它會拿三個參數:

    • d:一個 strsetdict
    • x:當作 d 的鍵值的字串
    • y:字串或是 None

    它的功能是:

    • 如果 d 沒有 x,則 lookup() 應回傳 False
    • 如果 dxyNone,則 lookup() 應回傳 True。
    • 如果 dxy …

    More

« Prev Page 2 / 3 Next »