Was verursacht diesen Zeitsprung der Stringverkettung?

Question

Also aus Neugier und Leerlauf Langeweile, habe ich mit Benchmarking Shlemiel the painter's algorithm herumalbern. Ich begann mit einer leeren Zeichenkette, erstellte eine weitere von 1000 Leerzeichen und fugte eine weitere hinzu, wobei ich eine einfache alte ineffiziente String-Verkettung verwendete, um zu bestimmen, wie lange es jedes Mal dauerte.

string s1 = ""; 
string s2 = ""; 
while (s2.Length < 1000) 
{ 
    s2 += " "; 
} 

while (true) 
{ 
    Stopwatch sw = Stopwatch.StartNew(); 
    s1 += s2; 
    sw.Stop(); 

    Console.WriteLine(" {0}| {1}", s1.Length, sw.ElapsedMilliseconds); 
} 

Wie erwartet, je länger die Zeichenfolge bekam, desto länger (es war eine viel geringere Auswirkungen als ich erwartet hatte, aber das ist eine andere Frage für einen anderen Tag) verketten nahm. Was war überraschend war jedoch konsistente Spikes in der Zeit, die es dauerte. Jede sechste Verkettung dauerte etwa zwei- bis dreimal so lange wie die fünf vorhergehenden Verkettungen.

Length  | Time (ms) 
----------------------- 
32250000 | 117 
32251000 | 44 
32252000 | 31 
32253000 | 30 
32254000 | 30 
32255000 | 32 
32256000 | 129 
32257000 | 35 
32258000 | 43 
32259000 | 34 
32260000 | 30 
32261000 | 29 
32262000 | 107 
32263000 | 47 
32264000 | 29 
32265000 | 30 
32266000 | 31 
32267000 | 29 
32268000 | 110 
32269000 | 46 
32270000 | 31 
32271000 | 30 
32272000 | 30 
32273000 | 30 
32274000 | 113 

Diese Samples stammen aus, sobald die Saite angefangen hat, signifikant groß zu werden, aber das Pattern hält von Anfang an. Weitgehend die ersten tausend oder so Proben sind zu klein, um das Muster zu bemerken, aber um die 1.8k Marke ist es erkennbar.

Meine erste Annahme war, dass hinter den Kulissen die Zeichen in einer Art ArrayList/Vektor-Art-Deal gespeichert wurden, die sich verdoppelt, sobald es voll ist, aber als ich darüber nachdachte, passt das nicht - Wenn das der Fall wäre, würde die Spitze in exponentiellen Perioden statt linear auftreten.

Also, kurz gesagt: Was zum Teufel geht hier vor?

Answer 1

Erstellen von Zeichenfolgen und Verwerfen von ihnen erstellt Müll. Sobald Sie eine bestimmte Speichermenge verwendet haben, werden Speicherbereinigungen durchgeführt und der Prozess angehalten. Da nichts anderes in Ihrem Prozess vor sich geht und Sie Ihre Strings immer gleich lang machen, geschieht GC immer zur selben Zeit (jeder 6. Durchlauf).

Um diesen Effekt auf Ihr Timing zu vermeiden, rufen Sie vor dem Start des Timers bei jedem Lauf GC.Collect auf.