Re: [問題] C語言列舉、指標、標準問題 (x6)

[PkmX (阿貓)]

推 EdisonX:謝謝您的細心講解,收穫很多,關於 Q6 我要補充一下,實作時
→ EdisonX:我會把它們弄成一份連續的記憶體,也就是malloc一次而非
→ EdisonX:(N+1) 次, 在此情況下做循序讀取差別還會很大嗎？ (只剩
→ EdisonX:pointer 多做一次索引動作)
舉個實際的例子來說好了，以這個陣列為例：

    int a[] = {4, 2, 1, 3};

它在記憶體裡面可能是長這樣的：

    address 0x100 0x104 0x108 0x10c
      value   4     2     1     3

我們把它sort以後，就會變成這樣：

    address 0x100 0x104 0x108 0x10c
      value   1     2     3     4

接下來我們存取的時候，就是循序的讀下去：0x100 -> 0x104 -> 0x108 -> 0x10c

這樣當然非常好，但是假設data不是int而是欄位很多的物件，一直複製效率就不好

    std::vector<int> v{4, 2, 1, 3};
    std::sort(v.begin(), v.end());

    for (const int x: v)
    {
        use(x); // 1 2 3 4
    }

------------------------------------------------------------------------------

你在文中提到的方法是這樣，假設malloc給的空間很爛：

    address 0x10000 0x00004 0x10004 0xffffc
      value    4       2       1       3

    address 0x00200 0x00204 0x00208 0x0020c
      value 0x10000 0x00004 0x10004 0xffffc

    int** arr = 0x00200;

我們sort完成以後，就變成了這樣：

    address 0x00200 0x00204 0x00208 0x0020c
      value 0x10004 0x00004 0xffffc 0x10000

於是我們存取的時候就變成了：0x10004 -> 0x00004 -> 0xffffc -> 0x10000，

這樣可視為隨機存取，造成大量cache miss也難以pre-fetch，效能不好，

當然優點是排序的時候我們只有移動pointer而已:)

    std::vector<std::unique_ptr<int>> v;
    v.emplace_back(new int(4));
    v.emplace_back(new int(2));
    v.emplace_back(new int(1));
    v.emplace_back(new int(3));

    std::sort(boost::make_indirect_iterator(v.begin()),
              boost::make_indirect_iterator(v.end()));

    for (const auto& p: v)
    {
        use(*p); // 1 2 3 4
    }

------------------------------------------------------------------------------

而你推文所述的方式是這樣的：

    address 0x100 0x104 0x108 0x10c
      value   4     2     1     3

    address 0x200 0x204 0x208 0x20c
      value 0x100 0x104 0x108 0x10c

    int** arr = 0x200;

因為{4, 2, 1, 3}的空間是一起分配連續的，所以不會有上面那種到處亂放的狀況，

而我們sort完了以後，就變成了：

    address 0x200 0x204 0x208 0x20c
      value 0x108 0x104 0x10c 0x100

access pattern是：0x108 -> 0x104 -> 0x10c -> 0x100，

一樣排序時我們只需要移動pointer，不用搬動真正的data，

原則上避免了多次malloc所造成的問題，但access pattern還是屬於隨機

    std::vector<int> v{4, 2, 1, 3};

    std::vector<decltype(v)::iterator> its;
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        its.push_back(it);
    }

    std::sort(its.begin(), its.end(), // write your own indirect_less
        [](decltype(its)::value_type lhs, decltype(its)::value_type rhs)
        {
                return *lhs < *rhs;
        });

    for (const auto it: its)
    {
        use(*it); // 1 2 3 4
    }

------------------------------------------------------------------------------

至於哪一個效能會最好就要看你的使用情況了，我只能稍微分析一下他們的差異，

另外第二種作法乍看之下好像沒啥用，但它有個特別之處：

它可以是polymorphic objects的容器(hetrogeneous container)，例如這樣：

    struct base
    {
        // base can even be an abstract class.
        virtual void pure_virtual() = 0;
    };

    struct derived : public base
    {
        virtual void pure_virtual() override
        {
        }
    };

    std::vector<std::unique_ptr<base>> bases;
    bases.emplace_back(new derived); // ok!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.252.42
推 EdisonX:這下真的懂了,謝謝您的細心回覆,感謝 !! :)
→ EdisonX:疑！換個角度講的話,若只要求「歷遍」，而不要求「循序」
→ EdisonX:推文中的碼效能應也不差？唯必須再記一筆起始位址便是..
→ PkmX:oh...我可能沒有表達清楚 我在兩篇文章中所用的"循序"指的是
→ PkmX:依照記憶體位置"sequential"的讀取 並不是依照資料排序的意思
→ BombCat:現在x86的cache都是讀一個block當單位，堆文中方法應該都
→ BombCat:在cache中，這樣就算是隨機存取還有差嗎? (不是本科請見諒
推 EdisonX:資料量大還是會被擠出cache,因讀取的記憶體順序會跳來跳去
→ BombCat:了解，我想也是這樣