テキストエディタなど巨大な配列、具体的にいうと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と言ったほうが正確かもしれないです）
ベンチマーク
ブロックサイズデフォルト。100文字×100万行の操作を行ってみました。add lineやupdate lineと書いてあるのは行と桁からバイト数に変換するテーブルの操作です。Commit d31463b
benchmark start
Allocated GC Memory:60,752bytes
add time:1951 ms
Allocated GC Memory:356,543,720bytes
replace 1 time:7117 ms
Allocated GC Memory:356,581,504bytes
replace 2 time:7185 ms
Allocated GC Memory:393,075,936bytes
replace 3 time:6850 ms
Allocated GC Memory:393,076,416bytes
enumratotion time:1168 ms
Allocated GC Memory:393,076,560bytes
clear buffer
Allocated GC Memory:82,728bytes
add line time:366 ms
Allocated GC Memory:40,996,432bytes
update line time:75 ms
Allocated GC Memory:40,999,688bytes
clear buffer
Allocated GC Memory:82,984bytes
Finished.Hit Any Key
ブロックサイズ32768で、100文字×100万行の操作を行ってみました。Commit d31463b
benchmark start
Allocated GC Memory:60,752bytes
add time:1055 ms
Allocated GC Memory:199,622,776bytes
replace 1 time:6032 ms
Allocated GC Memory:199,636,920bytes
replace 2 time:8309 ms
Allocated GC Memory:369,227,696bytes
replace 3 time:6220 ms
Allocated GC Memory:369,227,696bytes
enumratotion time:1158 ms
Allocated GC Memory:369,227,840bytes
clear buffer
Allocated GC Memory:82,728bytes
add line time:357 ms
Allocated GC Memory:40,996,432bytes
update line time:75 ms
Allocated GC Memory:40,999,688bytes
clear buffer
Allocated GC Memory:82,984bytes
Finished.Hit Any Key
100文字×1000万行でも試してみました。Commit d31463b
benchmark start
Allocated GC Memory:60,752bytes
add time:8424 ms
Allocated GC Memory:1,995,627,784bytes
replace 1 time:63209 ms
Allocated GC Memory:1,995,641,952bytes
replace 2 time:90562 ms
Allocated GC Memory:3,691,910,160bytes
replace 3 time:70683 ms
Allocated GC Memory:3,691,910,160bytes
enumratotion time:9278 ms
Allocated GC Memory:3,691,910,304bytes
clear buffer
Allocated GC Memory:81,152bytes
add line time:2639 ms
Allocated GC Memory:409,252,480bytes
update line time:455 ms
Allocated GC Memory:409,249,712bytes
clear buffer
Allocated GC Memory:81,408bytes
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
と不穏なことが書いてあるので、商用利用は避けたほうがいいかもしれません。改変度合いによっては元のライセンスがそのまま引き継がれることがあるらしいです。それに再帰をつかって書いてあるので、あまりにも大きな配列だとスタックオーバーフローで落ちるかも…(2GBぐらいまでなら大丈夫だとは思います)
この手の用途で使いたい場合は最低でも知的財産法に詳しい、弁護士に聞くなり、調べるだけ調べたほうがいいです。調べる場合、Vマジック 司法書士 民事訴訟法、最高裁のウェブサイトにある民事裁判教室を要件事実や事実認定を読んだ上で知的財産法の本を読めばある程度はわかりますが、どのルートをとるにしても、絶対ではないです。
裁判官の頭の中にある物差しで予想とは違った事実認定がされることはあるし、どう考えても無理とわかっていても訴えてくる人や保険会社がいて、裁判はとにかくお金がかかり、法テラスや弁護士保険があまり役に立たないという現実に付け込んで泣き寝入りを狙ってくる奴もいます。
弁護士に裁判の対応を依頼した場合、着手金２０万円から４０万円やら実費（日当、郵便代、弁護士の出張料、文書作成代、翻訳代）、成功報酬として賠償額の１割は最低でもかかります。困難依頼者と弁護士に判定されたら、着手金５０万円もざらにあります。
あまりおかしな金額を弁護士がとろうとすると懲戒請求の対象になる可能性もあるのですが、懲戒請求の内容によっては弁護士の業務を妨害したという理由で損害賠償請求されることもあり、この手はなかなか使えません。余命三年歳時記が大量懲戒請求をしたせいで懲戒請求の手続き自体もハードルが高くなってます。
そんな事情もあり、基本的には弁護士の言い値を呑むしかありません。言い値通り、払うこともできず、様々な理由で弁護士からも断られた結果、弁護士が見つからず、本人訴訟で応じないといけないケースもありますが、本人訴訟は時間と手間がかかります。契約書など明確な証拠があり、契約書の文言や法令の条文が誰から見ても同じと解釈できれば、嘘つきだと裁判官に思われない限り勝てますが、そうでない場合の本人訴訟の勝率はあまり高くありません。
裁判に伴う手間とリスクと費用を考えると、Ropeを解説した論文を読むなり、「Rope Datastructor」でくぐると考え方がでてくるので、商用利用の場合は一から書いたほうが無難だとは思います。