[讀書筆記]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:

image

 

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

image

 

由於_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的版本還是要快上一點。

dorgon

dorgon

職業:LV3遊戲軟體工程師 為了追尋小時候玩遊戲的感動,而一頭栽入遊戲業界。 本來以撰寫遊戲劇本為主要志向,但回過神來才發現已經踏入程序猿的不歸路。 專長為client端跨平台遊戲開發架構與自動建置流程,主要使用引擎為cocos2d-x與UnrealEngine4。

More Posts - Website

Follow Me:
FacebookLinkedIn

有什麼想法嗎?請發表你的看法