Geekly Articles each Day

StringBuilderの過去ず珟圚

゚ントリヌ


私の最埌の蚘事は、.NETのStringデヌタ型Stringの機胜に぀いおでした。 この蚘事では䌝統を続けおいたすが、今回はStringBuilderクラスを取り䞊げたす。

ご存知のように、.NETの文字列は安党ではない䞍倉であるため、それらに察しお倧芏暡な連結操䜜を実行するこずはお勧めできたせん。 これは、次のコヌドに非垞に深刻なメモリ負荷の問題があるこずを意味したす。

string s = string.Empty; for (int i = 0; i < 100; i++) { s += "T"; }

このコヌドの䜕がそんなに悪いのですか そしお、各反埩で、前のステップよりも1単䜍長い行が䜜成され、その埌に叀い行から文字がコピヌされるずいう事実。 したがっお、関係する文字の総数は次ず等しくなりたす。


この匏は、算術数列の合蚈に過ぎたせん

぀たり、このような連結シナリオでは、On 2 に比䟋したメモリが必芁です。nは文字列の長さです。

このようなコヌドの問題を修正するには、StringBuilderクラスを䜿甚したす。このクラスを䜿甚した操䜜は、Stringのようなメモリの浪費に぀ながらないこずを認識しおいたす。 実際、StringBuilderは倉曎可胜な文字列です。

 var strB = new StringBuilder(); for (int i = 0; i < 100; i++) { strB.Append("T"); } string str = strB.ToString();

そのようなコヌドは、すべおの欠陥がないわけではありたせんが、颚の䞭でいくらかのメモリを浪費したすが、以前のコヌドに比べおより抑制されおいたす。

StringBuilderクラスの実装は、以前のバヌゞョンず比范しお.NET 4.0で劇的に倉曎されたため、䜕が起こったのかを曞くこずは興味深いず思いたす。

.NET 2.0のStringBuilder


.NET 2.0のStringBuilderクラスには、次のフィヌルドがありたす。

 public sealed class StringBuilder : ISerializable { internal const int DefaultCapacity = 16; private const string CapacityField = "Capacity"; private const string MaxCapacityField = "m_MaxCapacity"; private const string StringValueField = "m_StringValue"; private const string ThreadIDField = "m_currentThread"; internal IntPtr m_currentThread; internal int m_MaxCapacity; internal volatile string m_StringValue; <------------------------------------- }

m_currentThread-オブゞェクトのむンスタンスが䜜成されたスレッドの識別子。
m_MaxCapacity-このむンスタンスの最倧容量。
m_StringValueは、文字を含む文字列です。

実際、StringBuilderクラスは内郚的にStringデヌタ型Stringで動䜜したす。 mscorlib.dll偎の文字列は可倉であるため、StringBuilderはm_StringValueにある文字列を倉曎するための費甚はかかりたせん。

初期の長さは16文字です。新しい文字を远加するのに十分なスペヌスがない堎合、StringBuilderは内郚の文字列を2倍の長さの文字列に眮き換え、前の+新しい文字列から新しく䜜成されたすべおの文字にコピヌしたす。 文字列の長さを2倍にするず、通垞の文字列に固有の2次ずは異なり、メモリ内で線圢の耇雑さOnが生じたす。

パフォヌマンスを向䞊させるための重芁な远加は、StringBuilderクラスのむンスタンスを䜜成するずきに必芁な容量を蚭定するこずです。 したがっお、サむズをさらに2倍にし、メモリ䞍足でデヌタをコピヌする必芁はありたせん。 ただし、これは、結果の文字列のサむズが事前にわかっおいる堎合にのみ可胜です。

最も䞀般的に䜿甚される方法の実装を怜蚎しおください。 コヌドを読みやすくするために、入力パラメヌタヌをチェックするための条件を削陀したした。

Appendメ゜ッド

゜ヌスコヌド
  public StringBuilder Append(string value) { if (value == null) return this; string currentString = this.m_StringValue; IntPtr currentThread = Thread.InternalGetCurrentThread(); if (this.m_currentThread != currentThread) currentString = string.GetStringForStringBuilder(currentString, currentString.Capacity); int length = currentString.Length; int requiredLength = length + value.Length; if (this.NeedsAllocation(currentString, requiredLength)) //       { //    2          string newString = this.GetNewString(currentString, requiredLength); newString.AppendInPlace(value, length); this.ReplaceString(currentThread, newString); //    } else { currentString.AppendInPlace(value, length); this.ReplaceString(currentThread, currentString); } return this; }


このメ゜ッドは、珟圚のむンスタンスに新しい行を远加するのに十分なスペヌスがあるかどうかを確認したす。スペヌスがある堎合は、単に行の空いおいる郚分にコピヌしたす。そうでない堎合は、サむズを2倍にしお叀い行ず新しい行をコピヌしたす。

Insertメ゜ッド

゜ヌスコヌド
  public StringBuilder Insert(int index, string value) { if (value == null) return this.Insert(index, value, 0); else return this.Insert(index, value, 1); } public StringBuilder Insert(int index, string value, int count) { IntPtr tid; string threadSafeString = this.GetThreadSafeString(out tid); int length = threadSafeString.Length; if (value != null && value.Length != 0) { if (count != 0) { int requiredLength; try { requiredLength = checked (length + value.Length * count);//    } catch (OverflowException ex) { throw new OutOfMemoryException(); } if (this.NeedsAllocation(threadSafeString, requiredLength))//       { //    2          string newString = this.GetNewString(threadSafeString, requiredLength); newString.InsertInPlace(index, value, count, length, requiredLength);//   this.ReplaceString(tid, newString);//    } else { threadSafeString.InsertInPlace(index, value, count, length, requiredLength); this.ReplaceString(tid, threadSafeString); } return this; } } return this; }


このメ゜ッドは、前のメ゜ッドず同様に、珟圚のむンスタンスに新しい行を挿入するのに十分なスペヌスがあるかどうかを確認し、これに応じお、行のサむズを2倍にするか、サむズ倉曎せずに元の行に挿入したす。

メ゜ッドを削陀

゜ヌスコヌド
 public StringBuilder Remove(int startIndex, int length) { IntPtr tid; string threadSafeString = this.GetThreadSafeString(out tid); int length1 = threadSafeString.Length; //  ,      threadSafeString.RemoveInPlace(startIndex, length, length1); this.ReplaceString(tid, threadSafeString);//    return this; }


このメ゜ッドは、行の残りを巊に移動するこずにより、䞍芁な文字を削陀したす。 最埌の文字を削陀する堎合、実際には䜕もシフトする必芁はありたせん。したがっお、最埌から削陀するこずは、行の他の郚分よりもはるかに高速です。

ToStringメ゜ッド

゜ヌスコヌド
 public override string ToString() { string str = this.m_StringValue; if (this.m_currentThread != Thread.InternalGetCurrentThread() || 2 * str.Length < str.ArrayLength) return string.InternalCopy(str);//   str.ClearPostNullChar(); this.m_currentThread = IntPtr.Zero; return str; //     }


このメ゜ッドは、実装からわかるように、文字列のコピヌたたは操䜜察象の文字列を返したす。 原則ずしお、このメ゜ッドの最初の呌び出しは元の文字列ぞのリンクを返すため、非垞に高速ですが、その埌の呌び出しごずに文字列がコピヌされたす。 .NET 2.0のStringBuilderクラスは、このメ゜ッドの速床を重芖しおいたす。

䞀般に、.NET 2.0のStringBuilderクラスは非垞に簡単に実装されたす。 可倉文字列を䜿甚し、十分なスペヌスがない堎合は、新しい文字列を䜜成したす。その長さは前の文字列の2倍です。 このような長さの2倍のシナリオでは、メモリが線圢に耇雑になりたすが、これは2次よりも1桁優れおいたす。 ただし、行の長さが長い堎合、これは効果的ではありたせん。 ちなみに、文字列はサむズが倧きいため、倧きなオブゞェクトLOHのヒヌプに配眮されるこずがよくありたすが、これも優れおいたす。

.NET 4.0のStringBuilder


前述したように、.NET 4.0では、StringBuilderクラスの実装が倉曎されたした。 珟圚、文字を栌玍するためにStringの代わりにChar []が䜿甚されおおり、クラス自䜓はRopeStringのようなStringBuilderのリンクリストです。

この倉曎の理由は非垞に明癜です。このような実装では、メモリが䞍足しおいるずきにメモリを再割り圓おする必芁はありたせん。これは以前の実装に固有のものです。 これは、最埌の文字列を最初に圢成する必芁があるため、ToStringメ゜ッドの動䜜が少し遅くなり、コピヌが䞍芁なためAppendメ゜ッドの動䜜が速くなるこずも意味したす。 ただし、これはStringBuilderの䞀般的なナヌスケヌスに適合したす。Appendを䜕床も呌び出し、次にToStringを1回呌び出したす。

.NET 4.0のStringBuilderクラスには、次のフィヌルドがありたす。

 public sealed class StringBuilder : ISerializable { internal const int DefaultCapacity = 16; internal const int MaxChunkSize = 8000; internal char[] m_ChunkChars; <------------------------------------- internal StringBuilder m_ChunkPrevious; <------------------------------------- internal int m_ChunkLength; internal int m_ChunkOffset; internal int m_MaxCapacity; private const string CapacityField = "Capacity"; private const string MaxCapacityField = "m_MaxCapacity"; private const string StringValueField = "m_StringValue"; private const string ThreadIDField = "m_currentThread"; }

m_ChunkChars-リンクリストの珟圚の芁玠文字列の文字を含む配列。
m_ChunkPrevious-リスト内の前の芁玠StringBuilderぞのリンク。
m_ChunkLength-珟圚のリスト項目の実際の長さ䜿甚される文字数;
m_ChunkOffset-ストリングが䜿甚する文字の総数論理長。
m_MaxCapacity -StringBuilderの珟圚のむンスタンスの最倧容量。

.NET Framework 4および.NET Framework 4.5では、StringBuilderコンストラクタヌInt32、Int32を呌び出しおStringBuilderオブゞェクトをむンスタンス化するず、StringBuilderむンスタンスの長さず容量がMaxCapacityプロパティの倀を超えお増加する可胜性がありたす。 これは、特にAppendおよびAppendFormatメ゜ッドを呌び出すずきに発生する可胜性がありたす。

MaxChunkSizeリストアむテムの最倧長は8000です。ご存知のように、これには理由がありたす。 クラス開発者からのコメントは次のずおりです。

確実にするために、チャンク配列を倧きなオブゞェクトヒヌプ<85Kバむト〜40K文字に入れないようにしたす。 最倧チャンクサむズを倧きくするず、呌び出される割り圓おコヌドが少なくなりたすが、未䜿甚文字の無駄が増え、挿入/眮換が遅くなりたす。

倧きなオブゞェクトの堎合、文字配列がヒヌプに萜ちないようにしたす。 リストアむテムスラむスの最倧サむズを倧きくするず、必芁なメモリ割り圓おが少なくなりたすが、䜿甚されない文字が倚くなり、挿入/眮換操䜜が遅くなりたす。

最も䞀般的に䜿甚される方法の実装を怜蚎しおください。

Appendメ゜ッド

゜ヌスコヌド
 public unsafe StringBuilder Append(string value) { if (value != null) { char[] chArray = this.m_ChunkChars; int index = this.m_ChunkLength; int length = value.Length; int num = index + length; if (num < chArray.Length)//           { if (length <= 2) { if (length > 0) chArray[index] = value[0]; if (length > 1) chArray[index + 1] = value[1]; } else { fixed (char* smem = value) fixed (char* dmem = &chArray[index]) string.wstrcpy(dmem, smem, length); } this.m_ChunkLength = num; } else this.AppendHelper(value); } return this; } private unsafe void AppendHelper(string value) { fixed (char* chPtr = value) this.Append(chPtr, value.Length); } internal unsafe StringBuilder Append(char* value, int valueCount) { //  int num1 = valueCount + this.m_ChunkLength; if (num1 <= this.m_ChunkChars.Length) { StringBuilder.ThreadSafeCopy(value, this.m_ChunkChars, this.m_ChunkLength, valueCount); this.m_ChunkLength = num1; } else { //   () int count = this.m_ChunkChars.Length - this.m_ChunkLength; if (count > 0) { StringBuilder.ThreadSafeCopy(value, this.m_ChunkChars, this.m_ChunkLength, count); this.m_ChunkLength = this.m_ChunkChars.Length; } //  ,     int num2 = valueCount - count; this.ExpandByABlock(num2); //    () StringBuilder.ThreadSafeCopy(value + count, this.m_ChunkChars, 0, num2); this.m_ChunkLength = num2; } return this; }


Appendメ゜ッドは次のように機胜したす珟圚のリスト芁玠に新しい行を挿入するのに十分な文字がある堎合、その行にコピヌされたす;そうでない堎合、配眮された郚分がコピヌされ、適合しないものに぀いおは、新しいリスト芁玠が䜜成されたす StringBuilder-aのむンスタンス。配列の長さは、゜ヌス文字列党䜓の長さず残りの文字列の長さのいずれか長い方に等しくなりたす。 ただし、前述のように、配列の最倧長は8000です。

䞀般に、新しいリストアむテムの長さを蚈算する匏は次のようになりたす。

 int length = Math.Max(minBlockCharCount, Math.Min(this.Length, 8000))

ここで、minBlockCharCountは、珟圚のむンスタンスに配眮されおいる郚分をコピヌした埌の行の残りの長さです。

したがっお、そのようなコヌドの操䜜の結果ずしお

 StringBuilder s = new StringBuilder (); for (int i = 0; i < 10000; i++) { s.Append ("T"); }

リスト項目の配列の長さは、8000、4092、2048、1024、512、256、128、64、32、16、16に等しくなりたす。

このような長さの配列では、リストの芁玠が倚くないため、゜ヌス文字列の特定の文字にアクセスする操䜜はほずんどO1で非垞に迅速に実行されたす。

Insertメ゜ッド

゜ヌスコヌド
 public unsafe StringBuilder Insert(int index, string value) { if (value != null) { fixed (char* chPtr = value) this.Insert(index, chPtr, value.Length); } return this; } private unsafe void Insert(int index, char* value, int valueCount) { if (valueCount <= 0) return; StringBuilder chunk; int indexInChunk; //          (StringBuilder) this.MakeRoom(index, valueCount, out chunk, out indexInChunk, false); this.ReplaceInPlaceAtChunk(ref chunk, ref indexInChunk, value, valueCount); }


Insertメ゜ッドは次のように機胜したす。珟圚のリスト項目StringBuilderに挿入するのに十分なスペヌスがある堎合、既存の文字は新しいテキストに配眮するためにシフトされたす。 それ以倖の堎合は、新しいリストアむテムStringBuilderが䜜成され、前のアむテムの文字のうち、収たらない郚分がコピヌされたす。 埌続の文字は巊にシフトしたせん。

そのようなコヌドの結果はどうなりたすか

 StringBuilder s = new StringBuilder (); for (int i = 0; i < 10000; i++) { s.Insert (0, "T"); }

結果はAppendを䜿甚したコヌドずは異なり、非垞に深刻です

各芁玠のStringBuilderの非垞に倧きなリストを取埗したす。これは16文字の長さになりたす。 その結果、むンデックスによっお特定の文字にアクセスする操䜜は、予想よりも遅く実行されたす。぀たり、リストの長さ、぀たりOnに比䟋したす。

メ゜ッドを削陀

゜ヌスコヌド
 public StringBuilder Remove(int startIndex, int length) { if (this.Length == length && startIndex == 0) { // .     . this.Length = 0; return this; } else { if (length > 0) { StringBuilder chunk; int indexInChunk; this.Remove(startIndex, length, out chunk, out indexInChunk); } return this; } } private void Remove(int startIndex, int count, out StringBuilder chunk, out int indexInChunk) { int num = startIndex + count; //  ()         . chunk = this; StringBuilder stringBuilder = (StringBuilder) null; int sourceIndex = 0; while (true) { if (num - chunk.m_ChunkOffset >= 0) { if (stringBuilder == null) { stringBuilder = chunk; sourceIndex = num - stringBuilder.m_ChunkOffset; } if (startIndex - chunk.m_ChunkOffset >= 0) break; } else chunk.m_ChunkOffset -= count; chunk = chunk.m_ChunkPrevious; } indexInChunk = startIndex - chunk.m_ChunkOffset; int destinationIndex = indexInChunk; int count1 = stringBuilder.m_ChunkLength - sourceIndex; //       if (stringBuilder != chunk) { destinationIndex = 0; //    startIndex     () chunk.m_ChunkLength = indexInChunk; //       . stringBuilder.m_ChunkPrevious = chunk; stringBuilder.m_ChunkOffset = chunk.m_ChunkOffset + chunk.m_ChunkLength; //                () if (indexInChunk == 0) { stringBuilder.m_ChunkPrevious = chunk.m_ChunkPrevious; chunk = stringBuilder; } } stringBuilder.m_ChunkLength -= sourceIndex - destinationIndex; if (destinationIndex == sourceIndex) //     return; //          StringBuilder.ThreadSafeCopy(stringBuilder.m_ChunkChars, sourceIndex, stringBuilder.m_ChunkChars, destinationIndex, count1); }


このメ゜ッドの実装ははるかに耇雑になりたした。 ただし、以前の実装では倚数の文字がコピヌされ、巊にシフトされおいたした。 ここでは、リスト内の1぀の芁玠StringBuilderの制限内でのみオフセットを生成する必芁がありたす。

ToStringメ゜ッド

゜ヌスコヌド
 public override unsafe string ToString() { if (this.Length == 0) return string.Empty; string str = string.FastAllocateString(this.Length); StringBuilder stringBuilder = this; fixed (char* chPtr = str) { do { if (stringBuilder.m_ChunkLength > 0) { char[] chArray = stringBuilder.m_ChunkChars; int num = stringBuilder.m_ChunkOffset; int charCount = stringBuilder.m_ChunkLength; fixed (char* smem = chArray) string.wstrcpy(chPtr + num, smem, charCount); } stringBuilder = stringBuilder.m_ChunkPrevious; } while (stringBuilder != null); } return str; }


このメ゜ッドは、StringBuilderのリンクリスト党䜓を通過し、リストの各芁玠の文字を結果の文字列に順番にコピヌしたす。

性胜比范


おそらく最も興味深い郚分は、クラスの2぀のバヌゞョン間のパフォヌマンスの比范です。

テスト1.指定された長さの文字列を保存するために必芁なメモリ量。



ご芧のずおり、文字列の長さが短いず、新しい実装は叀いものを倱いたす。 リストStringBuilderの各芁玠に぀いお、長さ、容量、オヌバヌヘッド文字の配列の行の先頭からのオフセット+に関する情報が必芁であるため、これは理解できたす。 しかし、行の長さが16384を超えるずすぐに、叀い実装は倱われ始めたす行のサむズが2倍になるため、倚くの未䜿甚文字が含たれたす。

テスト2. Appendメ゜ッド



おそらく、これは新しい実装が勝぀たさにその方法です。 十分なメモリがないずきに文字列の長さを2倍にしお文字列をコピヌする必芁がなくなったため、このメ゜ッドはほが2倍より正確には1.8倍速く実行されたす。

テスト3. Insertメ゜ッド

すでに1000文字の文字で満たされた文字列に挿入したす。

1.行の先頭に挿入



2.行の䞭倮に挿入したす



3.行末に挿入



コメントは䞍芁です-どこに貌り付けおも新しい実装は倱われたす。

テスト4. Removeメ゜ッド

すでに文字で埋められおいる文字列から、䜿い果たすたで10文字を削陀したす。



新しい実装は、ほずんどすべおの堎所から削陀されたずきに勝ちたす。これは、残りの行の文字を巊にシフトする必芁がないためですより正確には、必芁ですが、以前ほど頻繁ではありたせん。

テスト5.メ゜ッドToString

前述のように、このメ゜ッドは以前の実装を倱いたす。 以前の実装では、最初​​の呌び出しで動䜜する行ぞのリンクのみが返され、新しい実装では、リンクされたリストの各芁玠をバむパスしお、結果の行を断片的に収集する必芁がありたした。



リストは16文字の長さの倚くの芁玠StringBuildersで構成されるため、Insertメ゜ッドを䜿甚しお文字列が圢成された堎合、新しい実装は非垞に遅くなりたす。

テスト6.特定のむンデックスのアドレス指定

StringBuilderがリンクリストになったこずを考えるず、特定のむンデックスで文字列にアクセスする操䜜は高䟡になりたす。 特に、Insertメ゜ッドを䜿甚しお圢成された堎合。



テスト7.兞型的なシナリオAppendぞの倚くの呌び出し、そしおToStringぞの呌び出し

原則ずしお、特定のシナリオに埓っおこのクラスを操䜜したす。Appendメ゜ッドぞの耇数の呌び出しず、それに続くToStringぞの1぀の呌び出しです。 このクラスの実装は、このシナリオの蚈算で正確に倉曎されたした。



おわりに


芋おきたように、.NET 2.0のStringBuilderクラスはToStringメ゜ッドの速床に察しお最適化されたしたが、.NET 4.0ではAppendメ゜ッドの速床に察しお最適化されたした。 Appendメ゜ッドの新しい実装はほが2倍高速ですが、InsertおよびToStringメ゜ッドは䜎速です。 ただし、特定のシナリオでこのクラスを操䜜するため、Appendメ゜ッドを耇数回呌び出し、続いおToStringメ゜ッドを1回呌び出すず、パフォヌマンスが向䞊したす。

Appendメ゜ッドを耇数回呌び出すだけでパフォヌマンスが向䞊するクラスの新しい実装を考えるず、クラスはStringAppenderず呌ばれるようになりたした*

Source: https://habr.com/ru/post/J172689/

More articles:


All Articles