OSSチャレンジPart4（敗北）
目的
学んだことを忘れないようにメモ！
間違えたことを書いている可能性あるので、注意してください！
あと、全部教えてもらいながらやったことを書いてるだけなので、自分の実力ではないです。
やってること
Apache Arrow の C++に、Unicode正規化の機能を追加したい。
頂いたレビューに関してメモ
outputにそのまま正規化後の文字列を挿入するべき
This is definitely non-performant as it allocates a heap area for every input string. Ideally, we should write directly into the output buffer output.
utf8proc/utf8proc.c at master · JuliaStrings/utf8proc · GitHub
utf8proc_map は、内部で以下のようにメモリを確保してる
utf8proc_int32_t *buffer; buffer = (utf8proc_int32_t *) malloc(((utf8proc_size_t)result) * sizeof(utf8proc_int32_t) + 1);
そのため、このutf8proc_mapを使っちゃうと、arrowの方でoutputの領域を確保してるのに、それに追加でbufferの領域を確保するという無駄なことをしている。
なので、utf8proc_mapを使うのでなく、utf8proc_decompose_customとutf8proc_reencode を使うのが良さそう。
こんな感じになるとのことだった。
const auto n_chars = utf8proc_decompose(input, input_string_ncodeunits, reinterpret_cast<utf8proc_int32_t*>(output), output_string_ncodeunits, option);
if (n_chars < 0) return output_string_ncodeunits;
const auto n_codepoints = utf8proc_normalize_utf32(reinterpret_cast<utf8proc_int32_t*>(output), n_chars, option);
if (n_codepoints < 0) return output_string_ncodeunits;
auto codepoints = reinterpret_cast<utf8proc_int32_t*>(output);
for (utf8proc_ssize_t i = 0; i < n_codepoints; ++i) {
auto codepoint = codepoints[i];
output = arrow::util::UTF8Encode(output, codepoint);
}
utf8proc_reencodeを使わない
utf8proc_reencode() has a warning message regarding its size and IIUC it creates a null-terminating string which you are writing into the output. AFAIK, Arrow stores strings contiguously without null-terminations.
Cの文字列は、最後に\0を置いて、区切りを表現するそうで、ヌル終端文字列と呼ばれる。
utf8proc_reencode は、下のように文字列の最後に 0 を入れてる。
utf8proc_ssize_t rpos, wpos = 0;
for (rpos = 0; rpos < length; rpos++) {
uc = buffer[rpos];
wpos += utf8proc_encode_char(uc, ((utf8proc_uint8_t *)buffer) + wpos);
}
((utf8proc_uint8_t *)buffer)[wpos] = 0;
しかし、Arrowで使う文字列は、ヌル終端文字列を扱う想定でないので、このutf8proc_reencodeを使ってはならない。
utf8proc_reencodeは、コードポイントからutf-8文字に変更しているので、arrow::util::UTF8Encodeを利用できるとのこと。
最初のメモリ割り当ての最適化
we're calling the normalization function twice: once here to compute the output size, once in Transform to actually output the data. It seems wasteful (especially as I don't think normalization is especially fast).
scalar_string.ccでの文字列の処理は、主にMaxCodeunitsとTransformで行われる。
MaxCodeunitsは、あらかじめ確保が必要なバイト数を計算する関数で、Transformは実際に与えられた文字列を処理後のものに変換する処理を行う。
今回、自分は最初MaxCodeunits時に、どのくらいのbyte数の確保を必要かをutf8proc_decomposeを一度実行して計算しておき、十分な領域を確保してから、Transformで実際にutf8proc_decomposeやutf8proc_normalize_utf32をもう一度実行し、次は実際に文字列処理を行なうようにしていた。
この方法だと、確実に2回utf8proc_decomposeを実行する必要がある。
だが、実際に多くの文字列はUnicode正規化を行なっても、必要なサイズが変わるわけでない。だから、与えられた文字数が分かれば、処理に必要な領域は大体分かる。
一方で、アラビア文字などは、正規化すると、「ﷺ」が 「صلى الله عليه وسلم」になるように、文字数が大幅に変わる。
これに対応するためには、以下の方法をとるのが良さそう。
MaxCodeunitsでは、与えられた文字数から、ざっくり必要そうな値を計算しとく。Transformで、一度utf8proc_decomposeを実行する。utf8proc_decomposeは、あらかじめ確保した領域が足りないと、If the number of written codepoints would be bigger than bufsize, the required buffer size is returned, while the buffer will be overwritten with undefined data.必要な領域を返してくれるので、足りないだけメモリ領域を再確保する。確保した後に、もう一度
utf8proc_decomposeを実行する。
こうすれば、必要な時だけutf8proc_decomposeが実行されるので、効率が良い。
ちなみに、1でざっくり必要な領域を計算する際は、多めに出した方が良いことが多いらしい。メモリの再確保は、コストがかかるらしく、再確保が走るぐらいなら、多めにメモリを確保した方が良いことが多いとのこと。
答えの実装
今回のPRについて最後まで実装出来なかった。
巻き取ろうかと、commiterの方にコメント頂いたので、お願いした。実力不足が否めない...
答えはこちら！ github.com
大きくは、須藤さんに教えてもらった実装方針と一緒だったが、既存のExec系の処理を継承するのでなく、新しく作成していた。
感想
開発に関して重要なことを学べた。
まず、答えが誰もわかってないこと。本音を言うと、コミッターの人はほとんど答えをわかってるんだと思ってた。
けど、実際は、どうやったらメモリ効率が良いかとか、パフォーマンスが良いかとかを、コミッター同士で議論しながら、何が一番最適かを話し合うフローを経て、リリースまで持っていってるんだと分かった。
そしてその議論に入るためには、自分の知識は全く足りていないことも分かった。
今の自分は完全に下のブログでいう、使う人になっているが、今回の経験で少し作る人の世界が見えた気がして、すごくいい経験だった。
