速さ
どのくらいの速さかと言うと、1億行、10列のCSVファイルで、ディスク上10GBほどのデータ読込が4.3秒になった。世間的にどのくらいから速いと言えるのか知らないが、自分に必要な速度は出たのでヨシ。
C:\Programming\FastCsvLoad\x64\Release>FastCsvLoad.exe "C:\Programming\hoge\hoge\hoge.csv"
FastCsvLoad.exe
Read File: C:\Programming\hoge\hoge\hoge.csv
Max threads available: 32
FileSize: 10,889,996,035 byte
firstLineSize: 108 byte
estimatedLines: 101,841,628 line
Read Lines: 100,000,000
Data Size (bytes): 4,000,000,000 bytes
Processing Time: 4,358 msec
使用技術
- Fast Float
- OpenMP
- メモリマップドファイル読み込み
処理の流れ
- 指定されたCSVファイルを開き、ファイル全体をメモリにマッピング。これにより、ディスクからの読み込みを高速化。CPUが直接メモリ上のデータにアクセスできる状態になる。
- OpenMPで利用可能な最大スレッド数（この場合は32）に合わせて、ファイル全体を均等なチャンクに分割する。OpenMPの各スレッドは自分の担当範囲を受け取り、並列に処理。全スレッドがそれぞれの担当チャンクの処理を終えると、各スレッドで得られた行先頭オフセットを一つの大きな配列に統合。
- 統合された行オフセットを元に、各行ごとにCSVの文字列を抽出、各行に含まれるフィールド（数値）を解析。テキスト->浮動小数点にはfast_float ライブラリを使用。ここでもOpenMPで配列化。
要するに、まず行に分解して、そのあと一行ずつ処理して、構造体の要素に代入している。getline()でパーシングしているのと基本的な仕組みは同じ。改行とデリミタ(カンマ等)を同時に処理したほうがループが一つになって速そうな気もする。しかし、ループは減っても、繰返し処理の中身が複雑になると並列化やSIMDが非効率になるので、このままにしてある。
メモリマップドファイル
内部技術的なことを説明できるほどオジサンは詳しくない。実装方法はOSや処理系で異なるようだ。Windowsのページング機能(仮想メモリ)をそのまま使えるようにしたもの、と推測。ということは、中身はカリカリにチューンしてあるのだろう。メモリマップドファイルを使うと、ファイルの中身をそっくりvoid*型やchar*型のポインタで扱えるようになる。これによりファイルテータの分割処理が簡易になり、マルチスレッド処理が有効活用できる。SSDではほとんどオーバーヘッドを感じない。メモリ読込が省略されているのか? HDDだと最初にメモリへの読み込み処理をしているようでオーバーヘッドが大きくなった。
//エラー処理等は省略
// ファイルを開く (Windows API)
HANDLE hFile = CreateFileW(
filename.c_str(),
GENERIC_READ,
FILE_SHARE_READ,
NULL,
OPEN_EXISTING,
FILE_ATTRIBUTE_NORMAL,
NULL
);
// ファイルサイズを取得
LARGE_INTEGER fileSize;
GetFileSizeEx(hFile, &fileSize);
// ファイルをメモリにマップ
HANDLE hMap = CreateFileMappingW(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
// ファイル全体をマッピング
LPCVOID pData = MapViewOfFile(hMap, FILE_MAP_READ, 0, 0, 0);
// ファイル内容を文字列として扱う
const char* fileContent = static_cast<const char*>(pData);
参考
- [Micorsoft公式]メモリ マップト ファイル
https://learn.microsoft.com/ja-jp/dotnet/standard/io/memory-mapped-files - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E3%83%AA%E3%83%9E%E3%83%83%E3%83%97%E3%83%88%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB
効果
分かりにくいと叱られてしまった。反省。とはいっても備忘録的なものなので詳細はご勘弁。どんだけ効果があったか視覚化しておくのは興味があったのでやっておきたい。
一覧にするとこんな感じ。並列化アルアルだけど、OpenMPにしても、コンパイラでオプションにしても、単純に並列化しても速くならない。並列に処理できるようデータを分割するのが並列化のコツと思う。
表には書いてないが、高速化における常識テクニックとして、メモリの事前確保と条件分岐の簡略化はやってある。これらも地味に効果が大きい。
10GBのファイルを読み込む時間を表とグラフにするとこんな感じ。
読み取り速度でグラフにするとこんな感じ。最終的に2.24GB/秒になったので、SSDの速度を考えるとまだ伸び代があるのではないかと思う。手持ちの点群データを読み込むには十分なのでこれ以上最適化は不要と判断。
HDDだと遅くなる。キャッシュが効く二回目以降は速くなるが、こういうのは一回目が速くないと意味がないような気がする。100列1千万行とかもやってみたが大きな変化は無かった。
ソース
-
ソースはここ。
https://github.com/pipimaru1/FastCsvLoad
CSVのサンプルデータを作るコードも付けた。 -
必要ライブラリ
fast float
https://github.com/fastfloat/fast_float
余談 昭和のオジサンはOpenGL
仕事で点群ファイルを表示するソフトが必要になった。フリーソフトもあるのだが、後でアニメーション機能とかも必要になるので機能が足りない。有償ソフトはメチャ高い。使いたい機能はそんなにないし。Unityとかならやりたいことできそうなのだけど、昭和のオジサンの脳細胞はアルコールとコーヒーで既にカーボン凍結しているので新しいツールは覚えるのは無理無理ぜったい無理。なので昭和のオジサンが使うのはOpenGLなのだ。OpenGLは表示だけなので点群データの読取やデータのパースは自分で組まなけければならない。最初はifstringstreamのgetlineでジワジワ読んでいたのだが、2.5GBほどのデータで読取に10分ほどかかってしまう。と言うわけでいろいろ工夫して高速化した。結構速くなったので、備忘録を兼ねて汎用化したので晒した。コーディングにはだいぶChatGPTに手伝ってもらった。賢いなあコイツ。
githubは使い慣れていないので見難いと思うけど勘弁して頂戴。