Rのglobal string poolに溺れる

だいぶ昔にdplyrにこんなIssueを立てたことがあります。r-wakalangでの議論のスピンオフ企画みたいなものです。

この時に、Rの文字列型データがメモリ上でどのように保持されるかについてちらっとコメントがついていました。

dplyr should be taking advantage of R's global string cache for doing string matching when using in-memory objects.

global string cache。なんでしょうそれは。

advrks(R言語徹底解説を読めカス)

我らがバイブル、R言語徹底解説を開いてみましょう。まず、優しいところからいくと、こんな記述があります。

In early versions of R, there was a memory advantage to using factors instead of character vectors, but this is no longer the case. (Data structures · Advanced R.

「factor型がcharacter型に比べて優れている点は、メモリ使用量が少なくて済む点だ」。そう思っていた時代が私にもありました、と。

昔はそういう作りだったそうですが、今は違います。character型だと同じ文字列でも律儀にメモリを確保しまくるなんていうことはなく、factor型と同じく、同一の文字列はひとつの場所に格納されるだけです。この方式を「global string pool」とか、上にあったように「global string cache」とか呼ぶようです。

The same issue also comes up with strings, because R has a global string pool. This means that each unique string is only stored in one place, and therefore character vectors take up less memory than you might expect: (Memory usage · Advanced R.

下の実例でも、文字列が10個あったら1つの文字列の10倍のサイズになったりはしていません。文字列を指すポインタが増えるだけです。

pryr::object_size("banana")
#> 96 B
pryr::object_size(rep("banana", 10))
#> 216 B

でも現実は甘くない

でも、上のIssueではdplyrのコミッタ・Romain=サンがこんなコメントを返しています。

It's a bit more complicated than that actually. Sometimes two different pointers are the same strings but with different encodings, and we want the joins to consider them equal. (Joining by a character column is slow, compared to joining by a factor column. · Issue #1386 · hadley/dplyr · GitHub

同じ文字列でも文字コードが違うと別のポインタになるよ、と。

なっ、なんだってー!!!

もうちょっとIssueを漁ると、こんなのがありました。

ここで、SeqlというCの実装についてコメントされています。

it looks like R implements string comparison by:

  • first try direct pointer comparison (leveraging the cache)
  • otherwise convert both to utf-8 and compare that

まずはポインタを比較して、それが同じでなければどちらもをUTF-8に変換してから比較する、というのがRの文字列比較の実装になっているようです。でもなんか怖いことが書いてあるからSeqlは使えなさそう、と。

R 3.3.0での変更

match(x, table) is faster (sometimes by an order of magnitude) when x is of length one and incomparables is unchanged, thanks to Peter Haverty (PR#16491).

差分はGithubで見たほうが見やすいでしょう:speedup for match(<scalar>, table) - from Pete Haverty`s PR#16491 · wch/r-source@b23076e · GitHub

ここで、文字列の場合の実装はこんな感じになっています。長さが1の場合は別の処理になって高速化が図られます。

    // special case scalar x -- for speed only :
    if(LENGTH(x) == 1 && !incomp) {

(...snip...)

      case STRSXP: {
      SEXP x_val = STRING_ELT(x,0);
      for (int i=0; i < LENGTH(itable); i++) if (STRING_ELT(table,i) == x_val) {
          INTEGER(ans)[0] = i + 1; break;
          }
      break; }

STRING_ELT()という関数形式のマクロを使ってSEXPを取ってきて、それを比較しています。このSTRING_ELT()とは何者でしょう。R言語徹底解説によると、以下のように説明されています。

Use STRING_ELT(x, i) to extract the CHARSXP, and CHAR(STRING_ELT(x, i)) to get the actual const char* string.

STRING_ELT()は文字列のポインタを取ってくるもののようです。そして、そこから実際の文字列データを取得するにはCHAR()を使うようです。おそらく文字コードが違うデータを比較するにはCHAR()で持ってきた文字列を比較しないとだめですが、上の実装ではそうなっていません。

仕様?

これがバグなのか仕様なのか分からないなーという現象がr-wakalangで報告されて色々調べてたんですが、

match, pmatch, charmatch, duplicated and unique all match in UTF-8 if any of the elements are marked as UTF-8.

?Encodingのドキュメントには書かれているので、さすがにバグのような気がします。でも、match()自体のドキュメントの方には書かれていなくてよくわかりません。

むむむ…

感想

advrks、流行らせていきたいです。