テキストエディタなど巨大な配列、具体的にいうと85000バイト以上の配列を扱う場合、LOH入りします。
むろん、LOH入りしたからといってそう困るものではなく、GCの対象にはめったにならず、ワーキングセットが中々解放されない程度のものなんですが、エンドユーザー目線だとあまりよろしくありません。メモリーリークとサポートに不具合報告を送ってくる人とかいます。
そこで色々漁ってみたのですが、大量の配列を扱う場合、Ropeというものを使うといいそうです。Ropeだとブロックサイズを85000バイト以下にすることで、LOH入りを回避することができます。ただ、1GBぐらいのファイルをRopeに放り込むと素の設定だとGCで20秒ぐらい固まってしまうので、
NativeMmeoryArrayを使うという手もあります。ただ、こいつは値型以外使えないという欠点があります。シリアライズでByte配列にしてしまえば、なんとでもなるとはいえ、それはそれで面倒ですし、シリアライズによるオーバーヘッドのもあります。
なので、Classなどの参照型を何も考えずに放り込みたい場合、調べた範囲だとRopeが今のところ最適なようです。
ただ、こいつには一つ欠点があります。置き換えを繰り返すとクソ遅くなります。結果は載せてませんが、100万行×100文字を追加したうえで３文字削除の４文字追加をすると40秒近くかかります。これはRopeの性質上、仕方ないことではあります。
そこで
を試してみたのですが、先ほどの実装よりは早いです（全列挙はスタックオーバーフローするので試せていません）。ベンチマークに使ったマシンはCPUがCore i5 10400F、Memoryが16GBです。ベンチマークの内容は100万行×100文字を追加したうえで、３文字削除の３文字挿入、３文字削除の４文字挿入、４文字削除の３文字追加を行っています。
benchmark start
Allocated GC Memory:60,392bytes
add time:1996 ms
Allocated GC Memory:440,048,840bytes
replace time:10779 ms
Allocated GC Memory:440,082,632bytes
replace time:10682 ms
Allocated GC Memory:440,082,656bytes
clear buffer
Allocated GC Memory:82,280bytes
さすが、BugList（内部的にRopeが使われてます）なだけあります。配列だと挿入はO(N)ですが、BigListだとO(Log N)で済んでます。ただ、全列挙が遅く、N O(Log N)もかかりますし、データー量によってはスタックオーバーフローで落ちます。
これだと用途によっては困るので、BigListを改良し、リーフノードをリンクドリストで繋いでみました。
この改造で全列挙がO(N)で済むようになりました。（その代わりImuutableではなくなってます。SumTreeや二分探索木版PeaceTableと言ったほうが正確かもしれないです）
ベンチマーク
使用したPC：Core i7 14700、DDR4 メモリー32GB、Nvme SSD 1TB、1TB HDD 5400rpm
ブロックサイズ32768で、100文字×100万行の操作を行ってみました。add lineやupdate lineと書いてあるのは行と桁からバイト数に変換するテーブルの操作です。Commit e795913
benchmark start
size:1000000
Allocated GC Memory:64,656bytes
add time:688 ms
Allocated GC Memory:199,684,816bytes
replace 1 time:3389 ms
Allocated GC Memory:199,700,584bytes
replace 2 time:4669 ms
Allocated GC Memory:345,444,168bytes
replace 3 time:3580 ms
Allocated GC Memory:345,444,192bytes
enumratotion time:699 ms
Allocated GC Memory:345,444,312bytes
clear buffer
Allocated GC Memory:84,368bytes
add line time:243 ms
Allocated GC Memory:41,046,464bytes
update line time:51 ms
Allocated GC Memory:41,050,104bytes
clear buffer
Allocated GC Memory:84,624bytes
Finished.Hit Any Key
ブロックサイズ32768、一時ファイルを作らないモード、100文字×4000万行でも試してみました。Commit 92991bb
benchmark start
Allocated GC Memory:61,088bytes
add time:18541 ms
Allocated GC Memory:7,984,576,768bytes
replace 1 time:146495 ms
Allocated GC Memory:7,984,593,376bytes
replace 2 time:837038 ms
Allocated GC Memory:13,814,137,216bytes
replace 3 time:621522 ms
Allocated GC Memory:13,814,137,912bytes
enumratotion time:88196 ms
Allocated GC Memory:13,814,138,056bytes
clear buffer
Allocated GC Memory:82,728bytes
add line time:10398 ms
Allocated GC Memory:1,638,728,376bytes
update line time:1423 ms
Allocated GC Memory:1,638,739,600bytes
clear buffer
Allocated GC Memory:82,984bytes
Finished.Hit Any Key
ブロックサイズ32768、一時ファイルを作るモードで、100文字×1.2億行の操作を行ってみました。Commit 612aa7f。一時ファイルはHDDに作成しています。文字列操作中のタスクマネージャーから見たメモリー使用量は500~900MB程度で、行テーブル操作中のメモリー使用量は140MB程度です。
benchmark start
size:120000000
Allocated GC Memory:66,304bytes
add time:173334 ms
Allocated GC Memory:101,257,168bytes
replace 1 time:816628 ms
Allocated GC Memory:101,247,232bytes
replace 2 time:1179279 ms
Allocated GC Memory:333,371,424bytes
replace 3 time:1886714 ms
Allocated GC Memory:333,257,000bytes
enumratotion time:1638579 ms
Allocated GC Memory:331,904,816bytes
clear buffer
Allocated GC Memory:66,304bytes
add line time:46649 ms
Allocated GC Memory:86,939,136bytes
update line time:77635 ms
Allocated GC Memory:87,272,912bytes
clear buffer
Allocated GC Memory:69,448bytes
Finished.Hit Any Key
ライセンスでの注意点
改良の元ネタに使ったBigListのライセンスに
- COMMERCIAL DISTRIBUTION
Commercial distrbiutors of software may accept certain responsibilities with respect to end users, business partners and the like. While this license is intended to facilitate the commercial use of the Program, the Contributor who includes the Program in a commercial product offering should do so in a manner which does not create potential liability for other Contributors. Therefore, if a Contributor includes the Program in a commercial product offering, such Contributor ("Commercial Contributor") hereby agrees to defend and indemnify every other Contributor ("Indemnified Contributor") against any losses, damages and costs (collectively "Losses") arising from claims, lawsuits and other legal actions brought by a third party against the Indemnified Contributor to the extent caused by the acts or omissions of such Commercial Contributor in connection with its distribution of the Program in a commercial product offering. The obligations in this section do not apply to any claims or Losses relating to any actual or alleged intellectual property infringement. In order to qualify, an Indemnified Contributor must: a) promptly notify the Commercial Contributor in writing of such claim, and b) allow the Commercial Contributor to control, and cooperate with the Commercial Contributor in, the defense and any related settlement negotiations. The Indemnified Contributor may participate in any such claim at its own expense.
For example, a Contributor might include the Program in a commercial product offering, Product X. That Contributor is then a Commercial Contributor. If that Commercial Contributor then makes performance claims, or offers warranties related to Product X, those performance claims and warranties are such Commercial Contributor's responsibility alone. Under this section, the Commercial Contributor would have to defend claims against the other Contributors related to those performance claims and warranties, and if a court requires any other Contributor to pay any damages as a result, the Commercial Contributor must pay those damages.
https://github.com/timdetering/Wintellect.PowerCollections/blob/master/Binaries/License.txt
と不穏なことが書いてあるので、商用利用は避けたほうがいいかもしれません。改変度合いによっては元のライセンスがそのまま引き継がれることがあるらしいです。それに再帰をつかって書いてあるので、あまりにも大きな配列だとスタックオーバーフローで落ちるかも…(7GBぐらいまでなら大丈夫だとは思います)
弁護士に聞くのもただではないし（5000円から1万円かかります）、対応を依頼するのは最低でも〇〇万円＋実費＋成功報酬がかかり、何でもかんでも弁護士がやってくれるわけではありません。ある程度はこちらで証拠を集め、答弁書などを書かないといけませんし、裁判所から当事者尋問の形で呼び出されることがあります。（じつは弁護士も最高裁が無料で公開してる要件事実の本、司法書士や司法試験の本、尋問マニュアル、知的財産法に関する本を読んで勉強したので、やろうと思えば、本人訴訟もやれると思いますが、こちらはこちらで茨の道です）
そんな茶番につきあわされるぐらいなら、
Ropeを解説した論文を読むなり、「Rope Datastructor」でくぐると考え方がでてくるので、商用利用の場合は一から書いたほうが無難だとは思います。なお、MODIFY_NODE_BY_NORECURSIVEで囲まれた部分は論文とwikipediaの解説を読みながら一から書いたので、そのままコピペしても問題はありません。BinRangeListなどの「Copy from～」が書かれていない部分も同様です。