2011年1月25日 星期二

Rvalue Reference 與 String 的實作

Rvalue ReferenceC++0x 當中,一個非常重要的新功能。有了 Rvalue Reference,我們就可以容易地寫出具有 Moving Semantics 的 class。如果善用它,我們可以寫出更有效率的 C++ 程式碼。目前比較有名的編譯器如 GCC 或者 Visual C++ 都已經有 Rvalue Reference。

說來說去,Rvalue Reference 究竟是什麼?

首先我們必須要介紹 Lvalue 與 Rvalue。C++ 程式語言之中,Rvalue 與 Lvalue 相反的概念,Rvalue 的定義是「不是 Lvalue 的 Object(或曰 Variable),就是 Rvalue」。那 Lvalue 又是什麼?所謂的 Lvalue 是指在記憶體上有固定位置可以取址,可以放在指派運算子左邊的值。例如:

int a, b, c;
a = 1; b = 2; c = 3;  // (1)
a = b + c;  // (2)

第一行當中 a、b、c 三個變數都是放在指派運算子的左邊,所以都是 Lvalue。而第二行當中,a 是 Lvalue,(b+c) 這個表達式是 Rvalue。下面的程式很明顯是不合法的:

b+c = 0; // X

因為 b+c 這個 Rvalue 在記憶體上沒有固定的位址(翻譯為機器碼後,b+c 通常會被儲存在暫存器),所以自然也不能把 0 指派給他。但是這和 Rvalue Reference 有什麼關係呢?我們看看這個例子:

string a("abc");
string b("def");
string c("ghi");

string all = a + b + c + a;  // (3)

第三行的 (a+b) 、((a+b)+c)、(((a+b)+c)+a) 都是 Rvalue。在 C++98 當中,我們只能把 Rvalue 綁定到 const 修飾過的 Reference,所以我們的 operator+ 通常會這樣寫:

string operator+(string const &lhs, string const &rhs)  {
  string result(lhs); // (4) copy lhs
  result += rhs; // (5) concat rhs
  return result;
}

每當我們呼叫 operator+,我們就要複製一份 lhs,然後再把 rhs 串接上去。我們仔細地看一下上述程式的執行過程:
  1. 首先執行 a+b 的時候,我們要先複製一份 a(稱為 result1),再把 b 串接到 result1 的後面,最後回傳 result1。
  2. 接著我們要計算 result1+c 的結果。我們必需先複製一份 result1(稱之為 result2),再把 c 串接到 result2 的後面,最後回傳 result2。
  3. 最後我們要計算 result2+a 的結果,我們必需要先複製一份 result2(稱之為 result3),再把 a 串接到 result3 的後面,最後回傳 result3。
這個程式非常沒有效率。它會複製一份 result1,一份 result2,可是複製完就忘掉 result1 與 result2!為了減少這樣的浪費,有人提出了 Move Semantics:

struct string_tmp {
  string *ptr;
  string_tmp(string *s) : ptr(s) { }
  ~string_tmp() { delete ptr; }
};

// Move Constructor
string::string(string_tmp rhs) {
  internal_move(rhs); 
}

// operator=
string &string::operator=(string_tmp rhs) {
  internal_move(rhs);
  return *this;
}

void string::internal_move(string_tmp with) {
  if (buf) {
    delete [] buf;
  }

  buf = with.ptr->buf;
  buf_size = with.ptr->buf_size;
  str_length = with.ptr->str_length;

  with.ptr->buf = NULL;
  with.ptr->buf_size = 0;
  with.ptr->str_length = 0; 
}

string_tmp operator+(string const &lhs, string const &rhs) {
  string_tmp result(new string(lhs));
  *(result.ptr) += rhs;
  return result;
}

string_tmp operator+(string_tmp lhs, string const &rhs) {
  *(lhs.ptr) += rhs;
  return lhs;
}

上面的程式碼最重要的概念:operator+ 回傳的型別變成 string_tmp。然後多載 operator+ 與 operator=。這二個 operator 如果看到 string_tmp,就會想辦法把裡面的東西偷出來用,從而避免無謂的複製!

雖然在 C++98 當中,我們可以模仿出 Move Semantics,不過寫起來即為痛苦,不但需要黑魔法(上面的程式碼並不完整,詳情請參閱 moving_string.hpp),而且難以維護,如果 C++ 可以讓我們把 Rvalue 偷出來用就好了!

這就是 Rvalue Reference 可以讓我們做的事!

Rvalue Reference 在 C++ 的 notation 如下:

T &&rref = ... ;

我們可以把 Rvalue 綁定到 Rvalue Reference 上,例如:

string &&rref = a + b;

但是我們沒有辦法直接把 Lvalue 綁定到 Rvalue Reference 上,下面這個 statement 是不合法的:

string a;
string &&rref = a; // X

這是為了防止我們錯誤地把 Lvalue 當成 Rvalue。還記得嗎?Lvalue 是在記憶體上有特定位置,程序員碰得到 Lvalue,因此我們不能偷  Lvalue 的東西。如果我想告訴編譯器:「沒關係,這個變數我不在乎你去偷東西,你把它當成 Rvalue 就可以了!」可以使用 std::move:

string &&rref = std::move(a);

說了這麼多,到底要怎麼用 Rvalue Reference?和前面的 string_tmp 一樣,我們必需要多載 operator+、operator=、move constructor:

// Move Constructor
string::string(string &&rhs)
  : buf(NULL), buf_size(0), str_length(0) {

  internal_move(rhs);
}

// operator=
string &string::operator=(string &&rhs) {
  if (this == &rhs) {
    return *this;
  }
  internal_move(rhs);
  return *this;
}

void string::internal_move(string &with) throw () {
  if (buf) {
    delete [] buf;
  }

  buf = with.buf;
  buf_size = with.buf_size;
  str_length = with.str_length;

  with.buf = nullptr;
  with.buf_size = 0;
  with.str_length = 0;
}

// operator+
string &&operator+(string &&lhs, string const &rhs) {
  lhs += rhs;
  return std::move(lhs); // convert lhs to r-value again
}

我們可以注意到:我們不再需要 string_tmp,編譯器可以幫我們分辨何者是 Rvalue,並告訴我們可不可以從該物件偷取資源!

結語:有了 Rvalue Reference,我們可以寫出更有效率的程式碼。到了 C++0x 的時代,一個好的 C++ 程序員應該要能掌握 Rvalue Reference 的威力!

完整的程式碼:test.cppsimple_string.hpp(一般的字串)、moving_string.hpp(有 move semantics 的字串)、rrefopt_string.hpp(使用 rvalue reference 的字串)。