不要使用短路邏輯編寫 stl sorter 多條件比較

前言

最近工期緊、任務多，沒有時間更新博客，就水一期吧。雖然是水，也不能太水，剛好最近工作中遇到一個 sorter 多條件排序的問題，花費了半天時間來定位解決，就說說它吧。

背景

公司產品是一個跨端的數據傳輸 sdk，當下載資源時，會先從服務器拉取一批 peer，每個 peer 是包含要下載資源分片的 p2p 端，每個節點有一個序號，sdk 根據這個值從小到大排序后依次選取 peer 進行連接，序號是由服務器決定的，主要根據地域、連通率、帶寬等決定的，可以簡化為下面的 demo：

#include <stdio.h> 
#include <vector>
#include <string>
#include <algorithm>

struct PeerInfo
{
    std::string peerid; 
    std::string ip; 
    short port; 
    int begin; 
    int end; 
    int seq; 

    void print(void); 
};

void PeerInfo::print(void)
{
    printf ("peer %s: %d, %s:%d, %d-%d\n", 
            peerid.c_str(), seq, 
            ip.c_str(), port, begin, end); 
}

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        return lhs.seq < rhs.seq; 
    }
};

int main (void)
{
    std::vector<PeerInfo> vpi; 
    // init this vector by server response
    // ...
    std::sort (vpi.begin(), vpi.end(), PeerInfoSorter()); 
    for (auto it = vpi.begin(); it != vpi.end(); ++ it)
    {
        it->print(); 
    }
}

在下載過程中會向服務器請求多次，每批返回的 peer 都放在一個容器中排序，但是序號是基于批的，多個批次之間的 peer 如果僅按照 seq 排序的話，就會將前面批次舊的  peer 排在前面，從而導致一些新 peer 沒有機會被用到，發生饑餓現象。

問題的產生

了解到這個情況后，采取了按批和序號同時排序的方案，即為 peer 增加一個  batch 字段用于記錄批號，在排序時只有 batch 相同時才去比較 seq，代碼類似下面這樣：

struct PeerInfo
{
    std::string peerid; 
    std::string ip; 
    short port; 
    int begin; 
    int end; 
    int seq; 
    int batch; 

    void print(void); 
};

void PeerInfo::print(void)
{
    printf ("peer %s: %d-%d, %s:%d, %d-%d\n", 
            peerid.c_str(), batch, seq, 
            ip.c_str(), port, begin, end); 
}

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        return lhs.batch < rhs.batch || lhs.seq < rhs.seq; 
    }
};

當時的想法比較直接，先比較 batch，如果 batch 已經小了就直接短路返回結果；再比較 seq。看著邏輯沒什么問題，但是運行起來后發現還是有舊批次的 peer 排在前面，以上面那個 demo 為例，制造一些測試數據：

    // ...
    vpi.push_back ({"1a2b", "10.0.1.29", 8001, 0, 16384, 1, 1}); 
    vpi.push_back ({"3c4d", "10.0.1.30", 8002, 16384, 32768, 2, 1}); 
    vpi.push_back ({"5e6f", "10.0.1.31", 8003, 8192, 24576, 1, 2}); 
    vpi.push_back ({"7a8b", "10.0.5.22", 8081, 32768, 49152, 2, 2}); 
    vpi.push_back ({"9c0d", "10.0.5.23", 8082, 49152, 65536, 1, 3}); 
    vpi.push_back ({"afec", "10.0.5.24", 8083, 0, 65536, 2, 3}); 

其中最后兩個字段分別是 seq 與 batch 的初始值。執行后輸出如下：

$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer afec: 3-2, 10.0.5.24:8083, 0-65536

 peer 1-2 排在 2-1 后面明顯不是我們想要的，那是哪里出了問題呢？

問題的解決

看起來是 sorter 寫的有問題，重新考察一下它的邏輯：

• lhs.batch < rhs.batch 時，直接返回 true 并短路后面的條件，這是正確的
• lhs.batch = rhs.batch 時，結果退化為 seq 之間的比較，也是正確的
• lhs.batch > rhs.batch 時，結果退化為 seq 之間的比較，問題出在這里，此時應當直接返回 false

因此 sorter 正確的寫法應該是這樣：

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        if (lhs.batch != rhs.batch)
           return lhs.batch < rhs.batch; 

        return lhs.seq < rhs.seq; 
    }
};

前面的條件只要不相等就直接短路了，更正后輸出正常了：

$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer afec: 3-2, 10.0.5.24:8083, 0-65536

現在回過頭來看前面錯誤的代碼，看上去它至少保證了 batch 的順序，那么這是真的嗎？稍微調整一下容器數據的初始順序：

    vpi.push_back ({"9c0d", "10.0.5.23", 8082, 49152, 65536, 1, 3}); 
    vpi.push_back ({"afec", "10.0.5.24", 8083, 0, 65536, 2, 3}); 
    vpi.push_back ({"1a2b", "10.0.1.29", 8001, 0, 16384, 1, 1}); 
    vpi.push_back ({"3c4d", "10.0.1.30", 8002, 16384, 32768, 2, 1}); 
    vpi.push_back ({"5e6f", "10.0.1.31", 8003, 8192, 24576, 1, 2}); 
    vpi.push_back ({"7a8b", "10.0.5.22", 8081, 32768, 49152, 2, 2}); 

得到的輸出打破了這一"幻覺"：

$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer afec: 3-2, 10.0.5.24:8083, 0-65536

很顯然 1-2  排在了 2-1 之后。再分析之前的邏輯，當 lhs.batch > rhs.batch 時，結果是由 seq 決定的，所以完全可能出現上面的場景。而到底對哪些元素進行對比完全是由輸入序列和對比算法決定的，怎么構造反例還真不好設計，只有當數據量大時才會表現的比較明顯。

總結

再回頭來看邏輯短路操作，如果寫成下面形式：

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        return lhs.batch < rhs.batch || lhs.seq < rhs.seq; 
    }
};

則當 lhs.batch > rhs.batch 時不會短路，從而引發錯誤。如果寫成下面的形式：

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        return lhs.batch < rhs.batch && lhs.seq < rhs.seq; 
    }
};

則當 lhs.batch < rhs.batch 時不會短路，也引發錯誤。

總結一下就是，我們需要返回 batch 或 seq 的 operator < 結果來作為比較結果，但是這個條件對于 || 和 &&  在一半的情況下是不會短路的，具體而言就是：

• 使用 ||  邏輯短路時，lhs.batch < rhs.batch 得到滿足，lhs.batch > rhs.batch 沒有得到滿足
• 使用 && 邏輯短路時， lhs.batch > rhs.batch 得到滿足，lhs.batch < rhs.batch 沒有得到滿足

那它們能得到全部滿足嗎？當短路發生時，lhs.batch < rhs.batch 這一條件有 true 和 false 兩種情況需要返回，而短路邏輯 || 和 && 只能允許其中一種通過，所以答案是不能。除非可以預判只有其中一種條件發生 (只返回 true 或 false)，然后有針對性的寫 || 或 && 語句，不過那樣的話這個字段也就沒有參與比較的意義了。

最終結論就是，不要使用短路邏輯處理 sorter 多條件之間的判斷。

后記

回到前面項目中，再給它加一點需求：服務器返回不同批次的 peer 可能重復，通過 peerid 可以去重，但當新 batch 中的 peer 在之前出現并連接過時，我們希望它的優先級變低，以保證未連接過的 peer 不發生饑餓現象。對于這樣的需求，怎么改呢？想必大家心中已經有了答案，現在和正確答案對比一下吧：

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        if (lhs.connect_cnt != rhs.connect_cnt)
            return lhs.connect_cnt < rhs.connect_cnt;

        if (lhs.batch != rhs.batch)
           return lhs.batch < rhs.batch; 

        return lhs.seq < rhs.seq; 
    }
};

其中 connect_cnt 新字段表示連接的次數，每連接一次增加一個計數，將這個條件放在最前面以便保證連接次數最少的 peer 排在最前面，只有當連接次數相同時 (新 peer 的 connect_cnt == 0)，才對比 batch 與 seq。

舉這個例子的目的是為了說明，sorter 多條件對比時，只要按重要性一個個排就可以了，你學會了嗎？