[讀書筆記]Universal References in C++11 part 7: Small String Optimize(SSO) 與 move

什麼是SSO？用了這麼久的C++，還是第一次聽到這個名詞。其實，這個是標準庫對std::string所進行的一種優化：對於長度小的字串使用預先分配的stack storage(通常是16 Byte)，長字串就根據長度動態的new出free storage。──我們知道，stack storage的速度比free storage還要快出許多。

上一篇我們有談到，若是一個類別裡面沒有使用到free storage的話，那麼其實move就等同於從一個stack storage複制到另一個stack storage。當std::string滿足SSO啟動條件的時候，就是一個典型的例子。但其實我們並不需要擔心太多這個優化問題，因為這邊的成本小到我們可以忽視掉。

不過，多知道一些東西說不定什麼時候能夠派上用場，因此還是讓我們來看看這個優化的細節到底是怎麼進行的吧！

首先，建議先閱讀下面二篇文章：

http://stackoverflow.com/questions/10315041/meaning-of-acronym-sso-in-the-context-of-stdstring

https://akrzemi1.wordpress.com/2014/04/14/common-optimizations/

本篇文章接下來將會探討VC++的std::string的實作。

首先，先讓我們看看VC++裡面的SSO的宣告：

enum
{    // length of internal buffer, [1, 16]
    _BUF_SIZE = 16 / sizeof(value_type) < 1 ? 1
    : 16 / sizeof(value_type)
};   union _Bxty
{    // storage for small buffer or pointer to larger one
    value_type _Buf[_BUF_SIZE];
    pointer _Ptr;
    char _Alias[_BUF_SIZE];    // to permit aliasing

} _Bx;

我們可以看到_BUF_SIZE是16除上一個value_type的size，但其實這裡的value_type是char，對其取sizeof我們會得到1，因此_BUF_SIZE就被固定在16 Byte。下面的union _Bxty就是整個SSO的核心。當我們字串小於16 Byte的時候就會使用_Buf：

當超過的時候，我們就會使用動態宣告出來的_Ptr：

由於_Bx宣告成union，因此std::string避免掉了浪費記憶體空間的問題，只要在實作中保證二個空間的操作不會互相干擾就行。

在了解了SSO的機制之後，接下來，讓我們思考一個問題：下面這段code到底是test2_1還是test2_2的速度比較快？

std::string test = "small_string";   
std::string test2_1 = test;  // line 1  
std::string test2_2 = std::move(test); // line 2

嗯？由於是small string，所以這二個操作不是都用copy的概念在進行的嗎？所以二個操作的速度應該是一樣的。嗯，是基本上這個想法的思路沒有錯，但當我們進行追進去程式之後會發現，std::string在lvalue跟rvalue在底層所進行的copy操作使用的是不同的函式：對於lvalue，使用的是memcpy；對於rvalue，使用的是memmove。那麼這二個到底是誰快？理論上應該是使用memcpy的版本要快上一點，但結果似乎有點超出預期。

以下是我所進行的benchmark的程式：

#include "Timer.h"

int main(){
    {
        Timer t;
        for (int i = 0; i < 10000000; i++){
            char s[] = "small_string";
            char t[10];   memcpy(&t, &s, 10);
        }
       std::cout << "test, memcpy: " << t.elapsed() << " second" << std::endl;
    }
    {
        Timer t;
        for (int i = 0; i < 10000000; i++){
            char s[] = "small_string";
            char t[10];
            memmove(&t, &s, 10);
        }
     std::cout << "test, memmove: " << t.elapsed() << " second" << std::endl;
    }
    {
        Timer t;
        for (int i = 0; i < 10000000; i++){
        std::string test = "small_string";
            std::string test2_1 = test;   // line 1
        }
        std::cout << "test, str copy: " << t.elapsed() << " second" << std::endl;
    }
    {
        Timer t;
        for (int i = 0; i < 10000000; i++){
            std::string test = "small_string";
            std::string test2_2 = std::move(test); // line 2
        }
        std::cout << "test, str move: " << t.elapsed() << " second" << std::endl;
    }
    return 0;
}

結果如下：

VC++ debug build：

test, memcpy: 0.0090005 second

test, memmove: 0.0110006 second

test, str copy: 4.92528 second

test, str move: 4.52926 second

VC++ release build:

test, memcpy: 0 second

test, memmove: 0.0080004 second

test, str copy: 0.0330019 second

test, str move: 0.0290017 second

為什麼release build的memcpy變成了0秒？看來VC++似乎有什麼優化機制，在編譯期就把上面的程式給優化掉了。

換個平台再跑一次看看吧！

在mac下使用gcc -O2 -g再跑一次的結果如下：

test, memcpy: 3.424e-05 second

test, memmove: 2.786e-06 second

test, str copy: 0.220534 second

test, str move: 0.187405 second

恩，測了二個平台的結果都一樣，看來還是str move的版本還是要快上一點。

Leave a Reply Cancel reply