Hi,
ich bin auf der Suche nach einem schnellen und performanten Weg um in einem Byte Array ein anderes Byte Array zu suchen.
Aktuell nutze ich folgende Funktion:
private int IndexOf(int index, byte[] AllBytes, byte[] searchByteArray)
{
for (int i = index; i <= AllBytes.Length - 1 - searchByteArray.Length - 1; i++)
{
for (int j = 0; j <= searchByteArray.Length - 1; j++)
{
if (AllBytes[i + j] == searchByteArray[j])
{
if (j + 1 == searchByteArray.Length)
return i;
}
else
break;
}
}
return -1;
}
Funktioniert gut, gibt mir den Index des ersten Bytes dann wieder.
Nur hat mein großes Array nun ca 900000000 Bytes. Und das suchArray besteht aus 10-15 Bytes. Das ganze dauert dann ewig.
Hat jemand von euch eine Abhilfe?
Die Frage ist, was das Ziel dieser Suche ist.
Und auch warum du 900MB nach 10-15 Bytes absuchen willst.
Mich würde der Grund für diese Umsetzung interessieren, da es irgenwie nicht sinnvoll klingt sowas umzusetzen.
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Was haste denn bisher versucht oder recherchiert??
Bisher hast ja einfach nur zwei simple Schleifen.
Allgemeine Tipps:
Span
vermieden werden- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
Ich habe mal einen Code genommen und etwas umgebaut, da die Schleife etwas sperrig war und scheinbar nie bis zum Ende durchläuft.
Aber um in den 900 MB dann 15 Bytes sogar am Ende zu finden, brauche ich hier gerade mal 3,8 Sek.
Wenn du also nicht X mal pro Sekunde damit in dem Array suchen musst, ist das noch recht schnell.
Nachtrag:
Hier der Code von mir, mit entfernen des if/else zu einem einfachem if mit break, habe ich sogar nochmal 0,3 Sek. gespart.
private int IndexOf(byte[] bytes, byte[] searchBytes, int index = 0)
{
for (int i = index; i <= bytes.Length - searchBytes.Length; i++)
{
for (int j = 0; j < searchBytes.Length; j++)
{
if (bytes[i + j] != searchBytes[j])
break;
if (j + 1 == searchBytes.Length)
return i;
}
}
return -1;
}
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Danke. Das problem ist, das ich die 900MB mehrfach durchsuchen muss, daher auch der Index.
Nehmen wir an ich suche 0x10, 0x11, 0x12, 0x13, 0x14,...., 0x50 (eben 10-15Bytes) dann kommen die evtl. 50x in den 900MB vor. Ich möchte dann von jeder Stelle den Index wissen, das mache ich über eine Schleife:
for (int i = (IndexOf(0, allData, suchBytes) - 1); i < allData.Length; i++)
{
Debug.WriteLine(i);
tmpIndex = IndexOf(i, allData, suchBytes);
if (tmpIndex > -1)
{
Byte1_Index.Add(tmpIndex + suchBytes.Length);
Debug.WriteLine("Counter: " + Byte_Index_Counter);
i = tmpIndex;
Byte_Index_Counter++;
}
}
Das Dauert dann wirklich ewig. Ein Hex Editor macht das allerdings in ca 8-10 Sek, also muss es ja möglich sein.
Dann würde ich genau für den Fall, wie auch Abt schon vorgeschlagen hat, die Suchläufe auch parallel laufen lassen.
Dann kannst du deine Methode auch als async umsetzen und per Tasks die parallelen Suchen laufen lassen.
Dein Hexeditor hat nur den Voteil, dass er die Daten als Text darstellt.
Hier ist es dann auch einfacher zu suchen, da er lediglich im Text nach den Muster suchen muss.
Ist also nicht direkt vergleichbar mit der Suche einer Elementen Kette in einem Array.
Nachtrag:
Dein aktueller Ansatz prüft aber nicht ob der Eintrag überhaupt vorkommt.
Entsprechend startet deine äußere Schleife immer bei -1 und würde alle Einträge durchlaufen.
Diesen Fall solltest du abfangen, da du dann die ganze Schleife überspringen könntest.
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Dein Hexeditor hat nur den Voteil, dass er die Daten als Text darstellt.
Hier ist es dann auch einfacher zu suchen, da er lediglich im Text nach den Muster suchen muss.
Ist also nicht direkt vergleichbar mit der Suche einer Elementen Kette in einem Array.
Wäre es dann hier sinnvoll beide Arrays in Strings umzuwandeln und dann zu suchen? Ich hab sowas mal gelesen...
Dein aktueller Ansatz prüft aber nicht ob der Eintrag überhaupt vorkommt.
Entsprechend startet deine äußere Schleife immer bei -1 und würde alle Einträge durchlaufen.
Diesen Fall solltest du abfangen, da du dann die ganze Schleife überspringen könntest.
Stimmt! Wird in der Praxis bei mir vermutlich nicht passieren, aber es einzubauen schadet nicht.
Dann würde ich genau für den Fall, wie auch Abt schon vorgeschlagen hat, die Suchläufe auch parallel laufen lassen.
Dann kannst du deine Methode auch als async umsetzen und per Tasks die parallelen Suchen laufen lassen.
Gearbeitet habe ich damit noch nie. Wie funktioniert das dann mit dem Index? Starten die Suchen ja dann vermutlich mit einem unterschiedlichen Index? - Wie bekomme ich das dynamisch aufgeteilt?
Dann müsstest du am Ende auch mehrfach per IndexOf im String nach den Byte String samt Index suchen.
Somit verlagerst du das Problem anur von Byte Array Suche zu String Muster Suche.
Und dann musst du die String Positionen noch auf die Byte Array Positionen zurück mappen.
Am Ende dürftest du vermutlich mit einer parallelen Suche besser arbeiten können.
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Dann müsstest du am Ende auch mehrfach per IndexOf im String nach den Byte String samt Index suchen.
Somit verlagerst du das Problem anur von Byte Array Suche zu String Muster Suche.
Und dann musst du die String Positionen noch auf die Byte Array Positionen zurück mappen.
Ja, hab ich befürchtet.
Am Ende dürftest du vermutlich mit einer parallelen Suche besser arbeiten können.
Hast Du da etwas weitereführende Doku oder Code für mich? Ich habe tatsächlich noch nie mit parallalen Prozessen gearbeitet.
Die passenden Begriffe zur Suche sind async/Task und die Klasse Parallell.
Ansonsten hilft auch ein Blick in die Doku.
Code habe ich keinen für dich, da kannst du dich auch dran versuchen 😃
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Danke! Sieht jetzt gar nicht so wild aus.
Wie passe ich das denn mit dem Index an, wenn ich mehrere Suchen gleichzeitig starte? Teile ich die Gesamtbytes durch die Anzahl der Suchen die ich parallel starte?
Ich hab noch das hier gefunden: https://coders-corner.net/2013/02/17/multithreading-in-c-teil-5-parallele-schleifen-mit-parallel-for-und-parallel-foreach-entwickeln/
Sieht super simpel aus, weiß eben nur nicht wie ich den Index aufteile damit ich alle Schleifen von vorn suchen und somit ja keine Zeitersparniss da ist.
Prinzipiell _kannst _Du, _musst _aber nicht selbst skalieren; das übernimmt alles TPL für Dich.
Wichtig sind die Pitfalls zu beachten: Potential Pitfalls in Data and Task Parallelism
async
wäre in diesem Fall kontraproduktiv, wenn bereits alle Informationen im Speicher direkt zugegriffen werden können.
Würde sich lohnen, wenn die Daten dynamisch geladen werden müssen.
PS: schau Dir auch Span<T> an. Gibt i.d.R. bei sowas einen deutlichen Performance Boost.
https://adamsitnik.com/Span/
- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
Ich komme in Gedanken nicht so richtig weiter. Wenn man nun das einfache Beispiel nimmt:
Parallel.For(1, 10, i => DoWork(i));
static void DoWork(int i)
{
Console.Write(i + " ");
}
Dann müsste mein Code so (ähnlich) aussehen:
Parallel.For((IndexOf(0, allData, suchBytes) - 1), allData.Length, i => DoWork(i));
static void DoWork(int i)
{
Debug.WriteLine(i);
tmpIndex = IndexOf(i, allData, suchBytes);
if (tmpIndex > -1)
{
Byte1_Index.Add(tmpIndex + suchBytes.Length);
Debug.WriteLine("Counter: " + Byte_Index_Counter);
i = tmpIndex;
Byte_Index_Counter++;
}
}
Aber dann würden doch mehrere Prozesse das gleiche machen oder nicht?
Aber dann würden doch mehrere Prozesse das gleiche machen oder nicht?
Tasks sind keine Prozesse!
Tasks sind abstraktionen von Threads, und Threads wiederum sind Betriebssystem-Features und teil eines Prozesses.
Tasks sind jedoch .NET managed, benötigen weniger Ressourcen (.. paar andere Dinge hier..) und lassen sich in .NET viel einfacher nutzen als Threads.
Du musst das schon richtig einsetzen, ansonsten ist Paralellelität kontraproduktiv.
Insgesamt hast Du 3 Schleifen, wobei die zweite Schleife (innerhalb von IndexOf) die eigentlichen Durchlauf durch die Bytes durchführt.
I.d.R. lassen sich solche "Suchschleifen" meist sehr gut parallelisieren; aber nicht mit dem aktuellen Codeaufbau.
Du callst IndexOf mehrmals, was dazu führt, dass jedes mal alles durchsucht wird.
Das solltest Du minimieren.
PS: bitte nich immer alles zitieren.
[Hinweis] Wie poste ich richtig? Punkt 2.3
- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
@Abt
Kann ich bestätigen, dass sich die Suchschleife deutlich performanter lösen lässt 😃
Ich habe mal meinen Code angepasst und einen Mix aus einem Span<byte> Suchblock sowie der Parallel.For gebaut.
Laut VS Profiler ist er nach gerade mal 206ms durch und liefert mir auch den richtigen Index am Ende des Blocks.
Ich habe hierbei die Schleife vereinfacht, da ich per Span jeweils einen Block mit der länge der Such Bytes baue und nur noch den Block gegen die Suchbytes prüfe, was die gesamten Interationen erheblich verkürzt.
Den Code poste ich aber nicht sofort, hier sollte der TE ja auch was lernen und ein wenige testen 😉
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Ich komme nicht weiter. Ich glaube das ich ja für meinen Fall eine verschachtelte Schleife brauche wie zb:
static void Main(string[] args)
{
Parallel.For(1, 5, i =>
{
for (int k = 1; k < 10; k++)
{
DoWork(i, k);
}
});
Console.ReadKey();
}
static void DoWork(int i, int k)
{
Console.Write(i + "," + k + " ");
}
Aber ich verstehe es nicht so ganz wie ich ein return hinbekomme dann.
Folgendeen Code habe ich probiert:
private int IndexOf(int index, byte[] AlleBytes, byte[] suchByteArray)
{
for (int ix = index; ix <= AlleBytes.Length - 1 - suchByteArray.Length - 1; ix++)
{
Parallel.For(0, suchByteArray.Length - 1, i => DoWork(i, index, AlleBytes, suchByteArray));
}
return -1;
}
static int DoWork(int i, int index, byte[] AlleBytes, byte[] suchByteArray)
{
Debug.WriteLine("Loop: " + i);
if (AlleBytes[index + i] == suchByteArray[i])
{
if (index + 1 == suchByteArray.Length)
return i;
return -1;
}
else
{
return -1;
}
}
Aber die Ausgabe gibt nun zufällige Werte von 0-23 aus. Ich glaube ich bin auf dem falschen Weg.
Mit deinem Code wirst du nicht sinnvoll mit Parallel.For arbeiten können.
Ich habe es wie folgt gelöst.
Ich habe eine Methode AnyIndexOf angelegt.
Diese bekommt dann das ursprüngliche Array und das Array mit dem Suchmuster.
Als Rückgabe Wert gibt es dann dort ein int Array mit den Indizies der Positionen.
Die eigentliche äußere Schleife wird durch die Parallel.For Methode abgebildet.
Diese ruft dann im Action Parameter eine Methde AddIndex auf.
Diese bekommt dann ebenfalls das Array, das Suchmuster und den aktuellen Index.
Intern ruft diese dann die Suchmethode auf.
Die Suchmethode baut dann über Span<byte> einfach den Datenabschnitt zur Prüfung auf.
Somit braucht jede Interation nur durch die Byte Anzahl des Suchmuster durchlaufen.
Ggf. kann man hier auch auf das Span verzichten und direkt durch die Bytes ab dem Index laufen.
Habe ich aber noch nicht getestet, da ich Span<byte> mal verwenden wollte 😃
Hier zur Hilfe mein Ansatz ohne die eigentliche IndexOf Implementierung, die solltest du dann hinbekommen.
Für Verbesserungsvorschläge bin ich offen 😃
int[] indizies = AnyIndexOf(bytes, searchBytes);
foreach(int idx in indizies)
Console.WriteLine(idx);
private static int[] AnyIndexOf(byte[] bytes, byte[] searchBytes)
{
ConcurrentBag<int> indizies = new ConcurrentBag<int>();
Parallel.For(0,
bytes.Length - searchBytes.Length + 1,
i => AddIndex(indizies, bytes, searchBytes, i));
return indizies.ToArray();
}
private static void AddIndex(ConcurrentBag<int> indizies, byte[] bytes, byte[] searchBytes, int index)
{
// Wenn der aktuelle Index kein Treffer ist, dann abbruch
if(IsMatch(bytes, searchBytes, index) == false)
return;
indizies.Add(index);
}
private static bool IsMatch(byte[] bytes, byte[] searchBytes, int index)
{
for (int i = 0; i < searchBytes.Length; i++)
{
if (bytes[index + i] != searchBytes[i])
return false;
}
return true;
}
Nachtrag:
Die Methoden sind bei mir static, da ich den Code aktuell in einer Test Konsolenanwendung habe.
Den Code sollte man in eine eigene Klasse überführen, dann kann diese auch immer wieder verwendet werden.
Nachtrag 2:
Ich habe den Code noch weiter optimiert und durch sinnvollere interne Verarbeitung mit IsMatch Methode ersetzt.
Contains kann ich mir auch sparen, da jeder Index ja eindeutig ist!
Hat die Ursprüngliche Suchzeit nochmals verkürzt.
Also noch optimierter geht es kaum 😃
Man kann noch das HashSet durch eine Liste<int> ersetzen, da die Prüfung auf doppelte Indexe entfällt!
Was aber nicht gemacht wird, falls es den Fall gibt, dass dein Suchmuster und der Byte Block mehrere gleiche Bytes hat, dann bekommst du ggf. auch mehrere angereihte Indexe, was du ggf. abfangen müsstest.
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Danke. Werde mir jetzt Span ansehen.
Wie lang dauert der komplette Scan der 900MB inkl. Finden von ca 50 Einträgen bei Dir ca?
Bisher habe ich nur ein 900 MB Byte Array mit den letzten 15 Stellen als 0x01 Bytes geprüft mit 15 0x01 Bytes als Suchmuster.
Müsste mir hier noch Testfälle anlegen um das zu prüfen.
Aber die Laufzeit dürfte hier bei allen Durchläufen gleich sein, da die Laufzeit nur von der Größe des Byte Array sowie der Länge des Suchmusters abhängig ist.
Der Rest wird dann so oder so durch die parallele Verarbeitung erledigt.
Je nach Kernzahl deiner CPU kann dann die Ausführungsdauer nochmals abnehmen/steigen.
Ansonsten sollte die Methode nun aber schnell genug sein, würde mich überraschen wenn es immer noch nicht reich 😃
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Hallo peterpan4711,
auf TPL würde ich hier verzichten, stattdessen Span IndexOf verwenden. Das ist (zumindest) in der .NET Core 3.0 Version vektorisiert und wird sicher gute Ergebnisse erzielen.
Sollte dennoch die TPL (Parallel.ForEach) verwendet werden wollen, so die Überladung welche Ranges erzeugt und dann jede Range per Span IndexOf durchsuchen und im Post-Schritt das Ergebnis zusammenbauen.
public static int IndexOf(byte[] source, int startIndex, byte[] searchPattern)
=> source.AsSpan(startIndex).IndexOf(searchPattern);
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Threading;
using System.Threading.Tasks;
namespace ConsoleApp4
{
class Program
{
static void Main(string[] args)
{
byte[] source = new byte[150_000];
byte[] searchPattern = { 0xde, 0xad, 0xbe, 0xef };
var rnd = new Random();
rnd.NextBytes(source);
searchPattern.AsSpan().CopyTo(source.AsSpan(75_000));
int index = IndexOf(source, 10, searchPattern);
bool success = index == 75_000;
// "poor man's unit tests" ;-)
// Richtige Unit-Tests wären besser
Console.ForegroundColor = success ? ConsoleColor.Green : ConsoleColor.Red;
Console.WriteLine($"actual: {index}, expected: 75000 -> {(success ? "ok" : "fail")}");
Console.ResetColor();
}
// Sollte empirisch ermittelt werden, mehr geht nicht auf die einfache Art und Weise
// Könnte z.B. während der Installation durch einen Ermittlungs-Lauf auf dem Ziel-System
// ermittelt werden, aber der Aufwand dafür steigt.
// Der tatsächliche Wert wird vermutlich bei ein paar Millionen liegen -- ich habs nicht geprüft.
private const int ThreshouldForParallel = 100_000;
public static int IndexOf(byte[] source, int startIndex, byte[] searchPattern)
{
if (source.Length - startIndex < ThreshouldForParallel)
{
return IndexOf(source.AsSpan(startIndex), searchPattern) + startIndex;
}
int index = int.MaxValue;
Parallel.ForEach(
Partitioner.Create(startIndex, source.Length),
() => int.MaxValue,
(range, loopState, localIndex) =>
{
// Die Range-Schreibweie benötigt C#8
int tmp = source.AsSpan(range.Item1..range.Item2).IndexOf(searchPattern);
if (tmp != -1)
{
// Könnte verwendet werden, wenn nicht unbedingt das erste Auftreten gewünscht ist,
// sondern irgendein auftreten von searchPattern in source.
//loopState.Stop();
localIndex = tmp + range.Item1;
}
return localIndex;
},
localIndex => InterlockedExchangeIfSmaller(ref index, localIndex);
);
return index == int.MaxValue ? -1 : index;
}
private static int IndexOf(ReadOnlySpan<byte> source, ReadOnlySpan<byte> searchPattern)
=> source.IndexOf(searchPattern);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int InterlockedExchangeIfSmaller(ref int location, int newValue)
{
int snapShot;
do
{
snapShot = location;
if (snapShot < newValue) return snapShot;
} while (snapShot != Interlocked.CompareExchange(ref location, newValue, snapShot));
return snapShot;
}
}
}
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Hallo peterpan4711,
vllt. hab ich mich vorhin ein wenig verschätzt mit Parallel.ForEach. Wenn ich https://benchmarkdotnet.org/ verwende, so erhalte ich
| Method | Size | Mean | Error | StdDev | Median | Ratio | RatioSD |
|------------------- |--------- |-----------------|----------------|----------------|-----------------|--------|---------|
| IndexOf_Sequential | 100 | 35.25 ns | 0.2245 ns | 0.2100 ns | 35.22 ns | 1.00 | 0.00 |
| IndexOf_Parallel | 100 | 6,990.23 ns | 91.0912 ns | 85.2068 ns | 6,980.10 ns | 198.30 | 2.89 |
| | | | | | | | |
| IndexOf_Sequential | 100000 | 6,652.80 ns | 126.0095 ns | 117.8694 ns | 6,638.81 ns | 1.00 | 0.00 |
| IndexOf_Parallel | 100000 | 9,625.42 ns | 34.2770 ns | 32.0627 ns | 9,626.04 ns | 1.45 | 0.03 |
| | | | | | | | |
| IndexOf_Sequential | 10000000 | 1,800,221.32 ns | 30,094.1568 ns | 26,677.6862 ns | 1,799,309.96 ns | 1.00 | 0.00 |
| IndexOf_Parallel | 10000000 | 447,255.93 ns | 8,889.4187 ns | 20,064.8993 ns | 438,615.09 ns | 0.26 | 0.01 |
Wie erwartet ist bei kleineren Länge der Overhead der TPL zu groß und dort ist (vektorisierte) sequentielle Verarbeitung schneller.
Irgendwo in (100000, 10000000) ist dann die TPL schneller*.
Ich hab das Projekt angehängt, damit du selbst die passende Schwelle -- die je nach System unterschiedlich sein kann -- ermitteln kannst bzw. auch die anderen Varianten einfach durch Hinzufügen von weiteren Benchmark-Methoden prüfen kannst.
* zumindest im Benchmark. Wie es im Verhalten vom Gesamtsystem aussieht geht hier nicht hervor, da auch beim Benchmark die CPU voll ausgelastet wird und somit das System insgesamt kaum mehr Reserven hat -- das sollte auch berücksichtigt werden.
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
@gfoidl
Der TE braucht soweit ich dies verstanden habe, alle Treffer des Musters innerhalb der Byte Blocks.
Hier müsstest du also eine List<int> oder ein int Array mit allen Treffern liefern.
Aktuell hast du zwar eine List<int> indices aber verwendest die nicht.
Ist das nur zum testen oder ein Ansatz für den TE zum ausbauen?
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Hallo T-Virus,
ah, danke das hatte ich überlesen und mich somit in die falsche Richtung entwickelt -- sorry (da hatte mich auch die Methoden-Signatur im ersten Post in die Irre geführt, da IReadOnlyList<int> AllIndicesOf(this byte[] source, byte[] searchPattern)
passender wäre, auch der Titel sollte vom OP angepasst werden).
Ja dann einfach eine List<int>
für die Suchtreffer aufbauen und den Code modifizieren dass nicht nur der erste Treffer (pro Range) zählt.
Beim Hinzufügen zur Liste bei TPL auf Races achten und entsprechend synchronisieren -- od. z.B. ConcurrentBag<int>
verwenden, als threadsichere Datenstruktur.
Achtung:
Ich bemerke gerade dass die TPL-Version einen potentiellen Bug hat.
Und zwar genau dann wenn die Ranges genau so aufgeteilt werden, dass das Suchmuster auf zwei (benachbarte) Ranges aufgeteilt wird. Dann gibt es keinen Treffer.
Dieser Umstand müsste noch eingebaut werden, damit die Ergebnisse robust und sicher geliefert werden können.
(Ein Grund mehr warum Unit-Tests hilfreich wären um dieses Verhalten mit Tets abdecken zu können).
List<int> indices
Ist ein Artefakt vom Debuggen, hab ich mittlerweile oben rauseditiert.
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Und noch eine Anmerkung.
Anstelle von List sollte ConcurrentBag verwendet werden, wenn innerhalb der Action in Parallel.For die Einträge hinzugefügt werden.
Meine Version oben ist wegen den parallelen Zugriffen bei mehreren gleichzeitigen Treffern weggeflogen, was ich anfangs wegen nur einem Treffer nicht getestet hatte 😕
Nachtrag:
Den Part mit dem Partitioner.Create müsste ich mir noch mal anschauen, diesen kenne ich noch nicht.
Bei meinem Ansatz laufe ich eben byte für byte über den Index durch und haben somit keine Probleme mit benachbarten Suchmustern.
Erst bei identischen Bytes im Suchmuster und im Byte Block gibt es bei meinem Ansatz fehlerhafte Treffer.
Oder meintest du dies damit?
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Hallo T-Virus,
ich bastle mal eine Variante...ganz folgen kann ich deiner Beschreibung so nicht. Schauen wir einmal...
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Noch als genereller Tipp:
Statt der naiven Suche könnte man hier auch andere String-Matching-Algorithmus benutzen (ein Byte-Array verhält sich ja diesbezüglich analog zu einem String), s.a. mein Beitrag dazu: Boyer-Moore-Horspool Suche (und weitere)
Insbesondere wenn ein Text mehrfach nach unterschiedlichen Mustern durchsucht werden soll, bietet sich jedoch die Erzeugung eines Suffixbaums an (die dort erwähnten Autoren "Giegerich & Kurtz" waren meine Diplombetreuer 😉.
Die Idee mit der Textsuche hatte der TE auch schon anhand seines Beispiels mit dem Hex Editor eingeworfen.
Diese Idee hatte ich aber auch aus dem Grund verworfen, da er dann ein Mapping der String Positionen zu den Byte Array Positionen braucht.
Ebenfalls steigt dann durch die Umwandlung des Byte Array in einen String der Speicherverbrauch nochmals an.
Bei kleinen Blöcken ggf. sinnvoll aber bei 900MB an Bytes dürfte dies dann doch etwas zu viel Speicher werden.
Da wir die Ausführungsumgebung nicht kennen, würde ich auch nicht von beliebig viel Speicher ausgehen und die Speicherschonenste Version wählen.
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Ich meine nicht, das Byte-Array in einen String umzuwandeln, sondern den Algorithmus direkt auf dem Byte-Array durchzuführen (in C zum Beispiel ist ja ein String auch nur ein Byte-Array).
Und dein Beitrag
Dein Hexeditor hat nur den Voteil [sic], dass er die Daten als Text darstellt.
Hier ist es dann auch einfacher zu suchen, da er lediglich im Text nach den Muster suchen muss.
Ist also nicht direkt vergleichbar mit der Suche einer Elementen Kette in einem Array.
ergibt logisch keinen Sinn, denn auch ein Hexeditor sucht dann direkt auf Byte-Ebene und nicht als Text (der ja nur zur Anzeige als ASCI- bzw. Unicode-Zeichen dargestellt wird).
Das hatte ich dann falsch verstanden.
Ich bin leider nicht mit dem Algorithmus vertraut um deinen Ansatz zu verstehen.
Müsste mich da erst einmal einlesen.
In C mag dies funktionieren, bei C# müsste man die Bytes aber in char konvertieren.
Da Strings auch als UTF-16 repräsentiert werden, bin ich nicht sicher ob der Ansatz hier funktioniert.
Aber wie geschrieben, bin ich da nicht drin um das beurteilen zu können.
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Ich habe den Titel jetzt angepasst.
Also das Ziel ist es ein suchArray so oft zu finden wie es vorkommt und jeweils den Index in einer List zu speichern.
Hallo,
meine Umsetzung wäre wie folgt:
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Threading.Tasks;
// Könnte auch im csproj aktiviert werden
// <Nullable>enable</Nullable>
// hier aber so, da ich nur diesen Code kopiere
#nullable enable
namespace Extensions
{
public static class ByteArrayExtensions
{
// Sollte empirisch ermittelt werden, mehr geht nicht auf die einfache Art und Weise
// Könnte z.B. während der Installation durch einen Ermittlungs-Lauf auf dem Ziel-System
// ermittelt werden, aber der Aufwand dafür steigt.
// Der tatsächliche Wert wird vermutlich bei ein paar Millionen liegen -- ich habs nicht geprüft.
internal const int ThreshouldForParallel = 500_000; // internal für die Tests
public static bool AllIndicesOf(
this byte[]? source,
byte[]? searchPattern,
[NotNullWhen(true)] out IReadOnlyCollection<int>? indices)
{
if (source == null) throw new ArgumentNullException(nameof(source));
if (searchPattern == null) throw new ArgumentNullException(nameof(searchPattern));
if (searchPattern.Length == 0)
{
indices = default;
return false;
}
if (source.Length < ThreshouldForParallel)
{
indices = new List<int>(AllIndicesOfSequential(source, searchPattern)).AsReadOnly();
return indices.Count > 0;
}
var indicesSet = new HashSet<int>();
var rangeIndices = new ConcurrentBag<int>();
Parallel.ForEach(
Partitioner.Create(0, source.Length),
range =>
{
rangeIndices.Add(range.Item2);
ReadOnlyMemory<byte> memorySlice = source.AsMemory(range.Item1..range.Item2);
foreach (int index in AllIndicesOfSequential(memorySlice, searchPattern))
{
lock (indicesSet)
{
indicesSet.Add(range.Item1 + index);
}
}
}
);
// Alle oberen Grenzen der jeweiligen Ranges separat prüfen, um Splits über das Suchmuster zu berücksichtigen
foreach (int range in rangeIndices)
{
int start = Math.Max(0, range - searchPattern.Length);
int end = Math.Min(source.Length, range + searchPattern.Length);
ReadOnlyMemory<byte> memorySlice = source.AsMemory(start..end);
foreach (int index in AllIndicesOfSequential(memorySlice, searchPattern))
{
indicesSet.Add(start + index);
}
}
indices = indicesSet;
return indices.Count > 0;
}
// Durch einen eigenen Enumerator könnte die Allokation des vom C# compiler generierten Enumerator
// vermieden werden, aber ich denke das fällt hier nicht ins Gewicht und der Code ist so (viel) einfacher.
private static IEnumerable<int> AllIndicesOfSequential(ReadOnlyMemory<byte> source, byte[] searchPattern)
{
int searchPatternLength = searchPattern.Length;
int currentOffsetFromStart = 0;
while (!source.IsEmpty)
{
int index = source.Span.IndexOf(searchPattern);
if (index == -1)
{
break;
}
yield return currentOffsetFromStart + index;
source = source.Slice(index + searchPatternLength);
currentOffsetFromStart += index + searchPatternLength;
}
}
}
}
Das Test-Programm mit 900 MB und Suchmuster-Länge 15 das 4x vorkommt, braucht ~75ms um die Indizes zu finden.
init...
random data written
searchPattern copied 4 times
init done
measure...
time: 76 ms
count: 4
indices:
0
50
500
899999985
Angehängt das Projekt (mit Tests -- zumindest ein paar, die Projekt-Namen sind sinnfrei gewählt 😉).
Ich kenn jetzt die Implementierung in .NET Core für IndexOf
nicht im Detail, weiß aber dass diese in mehrere Iteationen verbessert wurde. Ob dort Methoden wie von Th69 vorgeschlagen umgesetzt wurden weiß ich jetzt auch nicht, kann mir das aber schon vorstellen.
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Danke! Das scheint genau das zu sein, was ich brauche. Da C#8 komplett neu ist für mich muss ich erstmal ein bisschen mit der Syntax klar kommen.
Aber ich arbeite mich da jetzt mal durch. Nur kurz zum Verstädnis: Ich kann in C#8 doch auch <C#8 Code und Syntax nutzen, oder?
PS: Du scheinst einen echt schnellen PC zu haben:
init...
random data written
searchPattern copied 4 times
init done
measure...
time: 1400 ms
count: 4
indices:
0
50
500
899999985
Ja, C# Versionen sind prinzipiell rückwärtskompatibel.
Das meiste ist quasi nur Syntaktischer Zucker
- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
Hallo peterpan4711,
Du scheinst einen echt schnellen PC zu haben:
Kann sein 😉
Bedenke auch dass nur ab .NET Core 3.0 optimale Leistung erzielt wird, da* dort "Fast-Span" verwendet wird im gegensatz zu .NET 4.x, d.h. der JIT-Compiler (RyuJit) versteht Span-Code besser und erzeugt besseren Maschinencode
viele Span-Operationen vektorisiert sind auf Basis von Hardware Intrinsics in .NET Core
sonst noch eine Menge an Optimierungen in der Code-Basis von .NET Core stattgefunden haben (und stattfinden) die nur teilweise, wenn überhaupt, nach .NET 4.x portiert werden (u.a. ist das ein Grund für das Zusammenlegen mit .NET 5, siehe .NET 5 kommt 2020)
Das "Ziel" von Hex-Editoren mit den 8..10s hast du dennoch geschlagen 😃
Ich kann in C#8 doch auch <C#8 Code und Syntax nutzen, oder?
Wie Abt schon erwähnte sind die C#-Versionen (großteils) rückwärts/abwärtskompatibel.
Ich hab ein paar neue Features von C# 8 verwendet, um zu zeigen wie diese angewandt werden können. Konkret nullable reference types und ranges.
Beides ist kein Muss für diese Methode.
Mit nullable gibt der C#-Compiler Warnungen (od. Fehler wenn TreatWarningsAsErrors
gesetzt wurde) und das hilft bei der Vemeidung von [FAQ] NullReferenceException: Der Objektverweis wurde nicht auf eine Objektinstanz festgelegt
Mit ranges lassen sich Memory-/Span-Operationen wie "Slicing" imho eleganter schreiben, wenn zwei Indizes gegeben sind, da nicht explizit die Länge ermittelt werden muss.
Wegen nullable und der praktischen Verwenden dieser Methode schaut auch die Signatur so aus:
if (source.AllIndicesOf(searchPatter, out IReadOnlyCollection<int>? indices)
{
// Hier kann 'indices' verwendet werden und der C# 8-Compiler weiß, dass 'indices' nicht null sein darf
}
Wäre die Signatur IReadOnlyCollection<int> AllIndicesOf(...)
so müsste das Ergebnis explizit in eine lokale Variable geschrieben werden, da dann auf null
geprüft wird. Mit gewählter Signatur gehts in einem.
Jetzt vorsorglich der Hinweis (auch an mich selbst) nicht zuweit ins Off-Topic C# 8 abzurutschen...
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Moin zuammen,
Die Version von gfoidl, ist ja schon wahnsinnig schnell.
Ich wollte jetzt aber auch ne .Net Framework Version.
Mit eingebundenem .Net Core war das ganze aber 4x langsamer.
Also hab ich dann diverse Funktionen gesucht und getestet, für das suchen im Array...
Auf Stackoverflow (byte[] array pattern search) dann auch was gefunden, was Mordschnell ist. Sogar noch schneller als von gfoidl.
alles unter gleichen Bedingungen (x64) / (.NetCore 3.1) Vs (.Net 4.7.2)
gfoidl (Core) = 105,485 ms
StackOverflow (Core) = 106,537 ms
StackOverflow (Framework) = 73,661 ms
Wers nachprüfen möchte:
Das gleiche wie beim testproject von gfoidl nur mit:
AllIndicesOfFaster(..) statt AllIndicesOf(..)
Hier erstmal die Funktion von stackoverflow die schneller sucht:
public static List<int> IndexOfSequence(this byte[] buffer, byte[] pattern, int startIndex = 0, int searchlength = -1)
{
//https://stackoverflow.com/questions/283456/byte-array-pattern-search#283596
if (searchlength == -1)
searchlength = buffer.Length;
List<int> positions = new List<int>();
int i = Array.IndexOf<byte>(buffer, pattern[0], startIndex);
while (i >= 0 && i <= searchlength - pattern.Length)
{
byte[] segment = new byte[pattern.Length];
Buffer.BlockCopy(buffer, i, segment, 0, pattern.Length);
#if isCORE
bool equal = segment.AsSpan().SequenceEqual(pattern);
#else
bool equal=segment.SequenceEqual<byte>(pattern));
#endif
if (equal)
positions.Add(i);
i = Array.IndexOf<byte>(buffer, pattern[0], i + 1);
}
return positions;
}
(hab die funktion so erweitert, dass sie Parallel ermöglicht (startoffset/länge)
Gesamt Source:
#define isCORE
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Threading.Tasks;
namespace ClassLibrary1
{
public static class ByteArrayExtensions2
{
public static int ThreshouldForParallel = 500_000; // internal für die Tests
public static List<int> IndexOfSequence(this byte[] buffer, byte[] pattern, int startIndex = 0, int searchlength = -1)
{
//https://stackoverflow.com/questions/283456/byte-array-pattern-search#283596
if (searchlength == -1)
searchlength = buffer.Length;
List<int> positions = new List<int>();
int i = Array.IndexOf<byte>(buffer, pattern[0], startIndex);
while (i >= 0 && i <= searchlength - pattern.Length)
{
byte[] segment = new byte[pattern.Length];
Buffer.BlockCopy(buffer, i, segment, 0, pattern.Length);
#if isCORE
bool equal = segment.AsSpan().SequenceEqual(pattern);
#else
bool equal=segment.SequenceEqual<byte>(pattern));
#endif
if (equal)
positions.Add(i);
i = Array.IndexOf<byte>(buffer, pattern[0], i + 1);
}
return positions;
}
public static bool AllIndicesOfFaster(this byte[] source, byte[] searchPattern, out IReadOnlyCollection<int> indices)
{
int totalLength = source.Length;
int searchPatternLength = searchPattern.Length;
if (totalLength < ThreshouldForParallel)
{
//nicht per tasks...
indices = new List<int>(source.IndexOfSequence(searchPattern));
return indices.Count > 0;
}
else
{
var rangeIndices = new ConcurrentBag<int>();
var indicesSet = new HashSet<int>();
Parallel.ForEach(
Partitioner.Create(0, source.Length),
range =>
{
rangeIndices.Add(range.Item2);
int offset = range.Item1;
int length = range.Item2 - range.Item1;
var found = source.IndexOfSequence(searchPattern, offset, length);
foreach (int index in found)
{
lock (indicesSet)
{
indicesSet.Add(range.Item1 + index);
}
}
}
);
//-----------------------------
// Alle oberen Grenzen der jeweiligen Ranges separat prüfen, um Splits über das Suchmuster zu berücksichtigen
foreach (int range in rangeIndices)
{
int start = Math.Max(0, range - searchPattern.Length);
int end = Math.Min(source.Length, range + searchPattern.Length);
int offset = start;
int length = end - start;
var taskCurrent = new byte[length];
Array.Copy(source, offset, taskCurrent, 0, length);
foreach (int index in taskCurrent.IndexOfSequence(searchPattern))
{
indicesSet.Add(start + index);
}
}
var sort = new List<int>(indicesSet);
sort.Sort();
indices = sort;
return indices.Count > 0;
}//else
}
}
}
EDIT: Standard->Framework geändert
@4dk2
Scheinbar hast du die Zeiten von gfoidl nicht richtig gelesen.
Dieser kam auf 76ms, was bei mir auch hin kam.
Schwankungen im 1-2 ms Bereich nach oben und unten mal weggelassen, ist deine Lösung relativ gleich auf mit gfoidls Umsetzung.
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
@T-Virus,
ich hab ja nicht seinen PC Hier 😉
aber seinen allgo, und der läuft bei mir halt langsamer, und der von stackoverflow halt schneller.
und das ist auch der gemessene durchschnitt von 1000 aufrufen...
bei mir sind das halt ~30 ms weniger.
Und bevor jemand nach ner schnellen .net Standard version sucht/testet (weil es Standard sein muss)
ich hab die meisten getestet XD
Ich wollte jetzt aber auch ne .Net Standard Version.
Mit eingebundenem .Net Core war das ganze aber 4x langsamer.
Ähm wat? 🤔 Du kennst den Unterschied von .NET Core und .NET Standard?*.NET Framework und .NET Core sind Runtimes; diese können Applikationen ausführen.
Die Ausdrucksweise, dass .NET Core langsamer als .NET Standard ist: das ist technisch nicht möglich.
So funktioniert .NET nicht.
Du vergleichst wahrscheinlich .NET Framework gegen .NET Core. Genau ist es aber nicht erkennbar.
gfoidl (Core) = 105,485 ms
StackOverflow (Core) = 106,537 ms
StackOverflow (Standard) = 73,661 ms
Aber die Zeile StackOverflow (Standard)
kann so nicht stimmen, denn .NET Standard ist nicht ausführbar.
What is .NET Standard
Du solltest Dich unbedingt mit den Basics des Ökosystems von .NET beschäftigen. 😉
- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
Unterschiede in NetFX vs NetCore kann es geben; normalerweise gehen diese aber für NetCore aus.
a) weil in NetCore Features existieren, die Speicher nicht unnötig allokieren (daher #if isCORE)
b) weil NetCore ingesamt Ressourcenschonener umgesetzt ist und die Basis schon Richtung Performance und nicht FatClients ausgelegt sind
Was Du inhaltlich machst ist, dass Du zwei unterschiedliche Implementierungen auf Geschindigkeit vergleichst.
Da hat die Runtime nur eine untergeordnete Rolle (ausser Du verwendest Runtime-spezifische Implementierungen).
Glaube nicht, dass gfoidl in den Fußnoten hinterlegt hat, dass kein Algo dieser Welt schneller ist als seiner 😉
Daher werde ich nicht schlau, was Du mit Deinem Beitrag ausdrücken willst; denn der Inhalt ".NET Standard vs. NET Core" hab ich Dir ja widerlegt.
Daher solltest Dich evtl korrigieren, was Du eigentlich aussagen willst.
- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
Ja es geht um .Net Framework.
Hab es editiert. Es geht darum das es auch noch Leute geben soll, die mit .net Framework arbeiten müssen. (Ich z.b)
Der Code von stackoverflow ist .net Framework kompatibel, dort schneller und zugleich auch noch bei .net core genausoschnell. Mehr gibt’s dazu nicht zu sagen
Also ist das Fazit: der Code ist allgemein schneller, egal in welcher Runtime. =)
Vermutlich einfach, weil es ein anderer Algorithmus ist, der insgesamt performanter ist - egal in welcher Runtime.
Kannst ja selbst mit https://github.com/dotnet/BenchmarkDotNet oder einem Profiler Deiner Wahl analyseren, was genau schneller/langsamer ist. 😉
- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
in 3.1 Core und 4.7.2 Framework scheint er es zu sein.
Es gibt sicher noch bessere, und ich bin mir sicher UNSAFE{} wird am schnellsten sein.
Und das klingt gut mit benchmarkdotnet, werd ich mal reinhaken.
Hallo 4dk2,
Es gibt sicher noch bessere, und ich bin mir sicher UNSAFE{} wird am schnellsten sein.
Pauschal bin ich mir da wiederum nicht so sicher. Allgemein:* Egal ob unsafe
od. Unsafe
, die Runtime kann keine Sicherheiten in Bezug auf Indexgrenzen, Typsicherheit, etc. mehr gewährleisten und das kann potentielle Bugs mit sich bringen. Will man diese Sicherheit dennoch, so sind indizierte Zugriffe explizit zu validieren, etc. und schon ist der vermeintliche Vorteil von unsicherem Code wieder weg.
da gäbe es noch viel zu schreiben, aber das geht an diesem Thema vorbei.
Statt #if isCORE
(und dem #define
) kannst du die vordefinierten Präprozessor Symbole NETCOREAPP
(mit od. ohne Version) auch verwenden. Siehe dazu Target frameworks in SDK-style projects / How to specify target frameworks.
Vorab: wie Abt erwähnt hat, hab ich keine Fußnote für den schnellsten Code 😉
V.a. dann nicht wenn ich das eher schnell runtertippe, als wirklich als Aufgabe optimierten Code zu liefern.
Aber als ich über den von dir geposteten Code geflogen bin, konnte ich nicht glauben dass dieser so wesentlich schneller ist, da* in IndexOfSequence
jedesmal ein Array alloziiert um dann dorthin zu kopieren -- das Array hat immer die gleich Größe, daher könnte einmal alloziiert und dann wiederverwendet werden od. um die Allokation überhaupt zu sparen stackalloc
(vorzugsweise zusammen mit Span<byte>
verwendet werden damit die Bound-Checks erhalten bleiben)
bei .NET Full in gleicher Methode Linq für SequenceEqual
verwendet wird und das kann nicht schneller sein als eine vektorisierte Variante wie sie per Span gegeben ist. Auch wenn Linq prüft ob es eine IList<T>
ist und dann per for-Schleife iteriert. Es wird dann jedesmal ein Vergleich mit EqualityComparer<byte>.Default
durchgeführt. Dieser wird in neueren Versionen des JITs (.NET Core 2.1 denke ich und dann ab .NET 4.8 da diese Optimierungen zurückportiert wurden) devirtualisiert, da byte
ein Werttyp ist. Nichtsdestotrotz kann das nicht schneller als vektorisierter Code sein, da es Element für Element (wenn auch indiziert) passiert.
für jeden Aufruf von IndexOfSequence
eine List<int>
alloziiert wird -- gut bei meiner Variante wird jedesmal der vom Compiler generierte Iterator alloziiert, aber das ist nur ein Objekt, während es bei der Liste zwei sind, eins für die Liste selbst und eins für das Array, welches die Liste intern verwendet
i = Array.IndexOf(buffer, pattern[0], i + 1);
"rückt" nur um i
weiter wenn es ein Match gab, anstatt i + searchPattern.Length
, erinnert ein wenig an Schlemiel dem Maler (;-))
Array.IndexOf
sucht vom startIndex
bis zum Ende des Arrays. Das ist bei sequentiellem Code kein Problem, aber bei der parallelen Version, da die obere Index-Schranke range.Item2
nicht berücksichtigt wird, d.h. es wird potentiell in einer anderen Range weitergesucht obwohl das nicht nötig wäre. (Es wird dann geprüft ob der gefunden Index innerhalb der gültigen Range ist, daher ist das Ergebnis korrekt.)
ebenso wird taskCurrent
alloziiert, kann vermieden werden und stattdessen direkt mit source
gearbeitet werden
Kurz also jede Menge vermeidbarer Allokationen und sequentieller Code statt vektorisiertem.
Grunsätzlich sollte .NET Core "schneller" sein als .NET Full, da dort die Entwicklung vorangetrieben wird. Bei einem Vergleich sollte jedoch auch Tiered-Compilation berücksichtigt werden, die in .NET Core standardmäßig aktiviert ist. D.h. dort wird während einer "Startphase" der IL-Code nur minimal optimiert, so dass eben der Programmstart rasch fortschreiten kann. Erst wenn eine Methode mehrmals (aktuell 30x) ausgeführt wurde und auch erst nach Ende der Startphase (~150ms nachdem die letzte Methode geJITet wurde) wird diese erneut geJITet, diesmal aber mit maximaler Optimierung (im Sinne des dem JIT möglichen).
Wurde also der Vergleich rein mit meinem simplen Ansatz aus dem Projekt oben durchgeführt, so hakt es schon destwegen.
Soweit die Theorie, die ich (natürlich) validiert habe.
Dass nicht alle Tests vom oben angehängten Projekt mit deiner Lösung passieren lasse ich hier außer Acht, sollte aber wenn schon verglichen wird auch berücksichtigt werden. Daher hab ich für die Vergleiche unten die nötigen null-Checks, etc. eingebaut, so dass die Tests passieren und es vergleichbarer ist.
Dein Code sortiert die Liste, das hab ich bei den Vergleichen entfernt, damit es vergleichbarer ist und da es lt. Aufgabenstellung nicht gefordert ist.
Das Sortieren wäre für alle Varianten ohnehin gleicher Aufwand.
if (totalLength < ThreshouldForParallel) { //nicht per tasks... indices = new List<int>(source.IndexOfSequence(searchPattern)); return indices.Count > 0; } else { // ... }
Wenn IndexOfSequence
als Ergebnis eine List<int>
liefert, warum weist du dann das Ergebnis nicht direkt indices
zu?
Da hast du wohl die Codes falsch zusammenkopiert 😉
Genauso ist "die Else" hier nicht nötig, da beim return
die Methode ohnehin verlassen wird.
Wie vorhin erwähnt ist einfaches Messen nicht so einfach bzw. ist die Gefahr groß, dass die Ergebnisse nicht sinnvoll verwertbar sind. Daher ist z.B. BenchmarkDotNet (BDN) vorzuziehen, da mit diesem Werkzeug etliche Fallstricke berücksichtigt werden (ist aber dennoch kein Allheilmittel, denn die Ergebnisse müssen auch korrekt gelesen werden (können)).
Sequentieller Code-Pfad
Zuerst eine Betrachtung für rein sequentiellen Code, also ohne Parallel.ForEach
.
| Method | Runtime | Mean | Error | StdDev | Ratio | Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |-------------- |---------:|--------:|--------:|------:|------------:|------:|------:|------------:|
| AllIndicesOf | .NET 4.8 | 170.0 ms | 1.88 ms | 1.76 ms | 0.26 | - | - | - | 2731 B |
| AllIndicesOf2 | .NET 4.8 | 654.1 ms | 4.25 ms | 3.97 ms | 1.00 | 116000.0000 | - | - | 366754144 B |
| AllIndicesOf4 | .NET 4.8 | 167.8 ms | 0.95 ms | 0.89 ms | 0.26 | - | - | - | 2731 B |
| | | | | | | | | | |
| AllIndicesOf | .NET Core 3.0 | 160.1 ms | 0.99 ms | 0.93 ms | 0.73 | - | - | - | 645 B |
| AllIndicesOf2 | .NET Core 3.0 | 218.8 ms | 1.75 ms | 1.64 ms | 1.00 | 44666.6667 | - | - | 140643485 B |
| AllIndicesOf4 | .NET Core 3.0 | 159.2 ms | 1.16 ms | 0.97 ms | 0.73 | - | - | - | 244 B |
AllIndicesOf
ist dabei der Code den ich oben gepostet haben.
AllIndicesOf2
ist der von dir gepostete Code (bei dir hieß es AllIndicesOfFaster
)
AllIndicesOf4
ist eine andere Variante die ich gerade erstellt habe und die ich momentan als ganz brauchbar empfinde (ohne auf "unsafe" zurückzugreifen).
AllIndicesOf3
gibt es auch noch und entspricht AllIndicesOf
nur dass der Iterator selbst als ref struct
ausgeführt wurde um die Allokation vom Iterator-Objekt und den Interface-Dispatch bei MoveNext
(von der foreach-Schleife) zu vermeiden. Die Allokation wurde zwar geringer, aber der Laufzeit-Gewinn ist im Bereich des Messfehlers, da der "heiße Teil" das IndexOf
ist, daher nicht in den Ergebnissen angeführt.
In den Ergebnissen ist zum Einen zu sehen dass .NET Full (hier 4.8 statt 4.7.2. (das hab ich nicht installiert)) wie erwartet nicht schneller als die .NET Core Version ist. Sogar ziemlich gegenteilig (v.a. wegen Span-basierten / vektorisiertem IndexOf und SequenceEqual).
Weiters ist zu sehen, dass AllIndicesOf2
jede Menge Allokationen hat und aufgrund der suboptimalen Implementierung doch recht klar langsamer ist.
Die Eingangs erwähnte Theorie ist zumindest beim sequentiellen Pfad bestätigt.
Paralleler Code-Pfad
| Method | Runtime | Mean | Error | StdDev | Median | Ratio | RatioSD | Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |-------------- |----------:|----------:|----------:|----------:|------:|--------:|----------:|------:|------:|------------:|
| AllIndicesOf | .NET 4.8 | 42.610 ms | 0.5172 ms | 0.4838 ms | 42.533 ms | 1.33 | 0.08 | - | - | - | 14 KB |
| AllIndicesOf2 | .NET 4.8 | 29.801 ms | 0.6081 ms | 1.7449 ms | 29.199 ms | 1.00 | 0.00 | 4843.7500 | - | - | 14929.02 KB |
| AllIndicesOf4 | .NET 4.8 | 42.765 ms | 0.5323 ms | 0.4979 ms | 42.821 ms | 1.33 | 0.08 | - | - | - | 8 KB |
| | | | | | | | | | | | |
| AllIndicesOf | .NET Core 3.0 | 42.147 ms | 0.8226 ms | 0.8802 ms | 42.177 ms | 4.23 | 0.16 | - | - | - | 11.79 KB |
| AllIndicesOf2 | .NET Core 3.0 | 9.916 ms | 0.1976 ms | 0.2958 ms | 9.785 ms | 1.00 | 0.00 | 1859.3750 | - | - | 5725.27 KB |
| AllIndicesOf4 | .NET Core 3.0 | 42.019 ms | 0.7827 ms | 0.8038 ms | 41.805 ms | 4.22 | 0.16 | - | - | - | 6.22 KB |
Ui, da schaut es sehr unerwartet aus...*
Dass es auf einmal gravierend langsamer ist entspricht überhaupt nicht dem was ich erwartet habe und entbehrt(e) sich jeglicher Logik.
Nach eingehender Untersuchung (PerfView, VTune) konnte ich einen "Bug" in .NET Core als Übeltäter ausfindig machen, der im Span-basierten Code zum Tragen kommt, während diesem Umstand mit der Array-basierten Methode aus dem Weg gegangen wurde.
Bug ist in "" da der Code ja fehlerfrei funktioniert, aber dennoch ein Bug ist, da die Laufzeit-Ansprüche verfehlt wurden.
Das Schöne an .NET Core ist dass es Open Source ist, somit kann auch gleich die Lösung für den Bug vorgeschlagen werden.
Einen Bug im Framework zu finden ist nicht so einfach, nicht da wenige vorhanden sind, sondern weil -- zumindest ich -- zuerst den Fehler überall anders suche.
Z.B. sind bei den Vergleichen zwischen den beiden Varianten bestimmte verwendete (Framework-) Methoden auszuschließen, da die Implementierung gleich ist.
Span<T>.IndexOf(ROS, ROS)
führt zuerst ein IndexOf(ROS, ROS[0])
(also nach dem ersten Element des Suchmusters) durch und bei einem Treffer wird mit dem restlichen Suchmuster verglichen (ohne ROS[0], das wurde ja schon gefunden).
AllIndicesOf2
macht das gleichwertig, nur mit Array<T>.IndexOf(T[], T, int, int)
und das wiederum -- zumindest in .NET Core -- delegiert zur Span-Version. AllIndicesOf2
vergleicht mit dem gesamten Suchmuster, obwohl nur searchPattern[1..]
nötig wäre.
Summa summarum ist dieser Teil gleichwertig. Der JIT sollten das bischen Overhead vom weiterdelegieren wegoptimieren können und ein paar CPU-Zyklen mehr od. weniger sind im Bereich der Messgenauigkeit.
Dass nun dieser Bug genau bei IndexOf
vorhanden ist, daran dachte ich vorerst nicht.
Wird obiger Benchmark (ohne den Fix) mit einer source
ausgeführt, die lauter 0 enthält, außer dort wo das Suchmuster hinkopiert wurde, so ist AllIndicesOf2
wesentlich langsamer.
| Method | Mean | Error | StdDev | Ratio | Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |----------:|----------:|----------:|------:|------:|------:|------:|----------:|
| AllIndicesOf2 | 412.04 ms | 305.56 ms | 16.749 ms | 1.00 | - | - | - | 15.42 KB |
| AllIndicesOf4 | 36.32 ms | 11.20 ms | 0.614 ms | 0.09 | - | - | - | 6.18 KB |
Das trifft sich genau mit dem Verhalten vom Bug, da so dieser unperformante Framework-Code nur selten -- nur dort wo das Suchmuster tatsächlich ist -- ausgeführt wird.
Die anderen Punkte aus eingangs erwähnter Theorie zeigen sich hier doch recht deutlich.
Somit gut dass du deinen Code gepostet hast, sonst wäre dieser Bug wohl nicht entdeckt worden. Danke dafür!
Zum Prüfen der gefixten Version (per lokalem Build von .NET Core, etc.) hab ich jetzt keine Muße, aber ich gehe davon aus dass AllIndicesOf4
die schneller und weniger allozierende Variante bleibt. Der rein sequentielle Code-Pfad (Benchmark oben) dürft dann ebenfalls bessere Ergebnisse liefern.
Unabhängig vom Bug noch ein paar Anmerkungen zu den Ergebnissen / Code.
Da die Ergebnisse von isolierten Benchmarks stammen gehören diese auch entsprechend interpretiert / gelesen. V.a. in Hinblick auf Real-System ist die GC-Arbeit, durch die Allokationen, nicht zu vernachlässigen.
Ebenso wurden für die Messungen nur ein Suchmuster mit Länge 15 das viermal in die Quelle kopiert wurde verwendet. Da müssten schon ordentlich mehr Vergleiche durchgeführt werden um richtige Aussagen treffen zu können und letztlich wird es -- allgemein gesprochen -- wohl ein Kompromiss in die ein od. andere Richtung werden. Alleine schon wenn ich an ThreshouldForParallel
denke. Was auf einem System besser sein mag, kann auf einem anderen System schlecht sein.
Einschub: aus den Ergebnissen ist auch zu sehen dass der Garbage Collector (GC) in .NET super Arbeit leistet. Das alloziieren ist i.d.R. nur ein Pointer-Move und daher sehr schnell. Aufwändiger ist das Abräumen (collect & compact) und hier leistet der GC -- v.a. für Gen0 -- wirklich effiziente Arbeit.
Anmerkung zu Parallel.ForEach
Parallel.ForEach
versucht den ThreadPool -- sofern der TaskScheduler.Default
verwendet wird -- zur Gänze auszulasten, somit kann auch das "System einfrieren".
Dies gilt es bei GUI-Anwendungen zu beachte, da so auch die GUI einfrieren kann. Hier kann mittels ParallelOptions.MaxDegreeOfParallelism
eine Grenze gesetzt werden, so dass der GUI-Thread reaktiv bleibt.
Bei Server-Anwendungen, v.a. wenn viele gleichzeitige Anfragen zu erwarten sind, würde ich Parallel.ForEach
eher verzichten, da die Parallelität eh über die Request behandelt wird. Ggf. sollten die RPS gemessen werden um entscheiden zu können ob der Einsatz der parallelen Schleife sinnvoll ist od. nicht.
mfG Gü
* bei diesem Ergebnis bin ich mir auch nicht ganz sicher ob der Wert stimmt. Hab zwar mehrmals den Benchmark laufen lassen und da kamen gleich Ergebnisse heraus.
Meine Zweifel konnte auch ein Profiler nicht widerlegen, da dort die CPU recht wenig Threads ausführt anstatt mit allen Kernen voll zu arbeiten. Näher hab ich das -- v.a. wegen des Bugs -- nicht untersucht. Es kann auch sein dass aufgrund der Test-Konstellation (4x Suchmuster reinkopiert) das genau mit dem Partitioner der parallen Schleife zusammenpasst. Um das zu Falsifizieren könnte ein eigener Partitioner erstellt werden, so dass in allen Varianten die parallen Schleifen gleiche Ranges erhalten. Aber auch dazu hab ich jetzt keine Lust mehr 😉
Edit: der Fix ist bereits im master-Branch.
Edit: weiteres Optimierungspotential liegt darin die "Range-Splits" direkt in der parallelen Schleife zu behandeln, so dass das nachherige sequentielle Abarbeiten entfällt, sowie das führen dieser speziellen Liste.
Speedski
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Chapeau! für den Post Gü!
- performance is a feature -
Microsoft MVP - @Website - @AzureStuttgart - github.com/BenjaminAbt - Sustainable Code
@gfoidl
Hut ab für den Post sowie das auffinden und melden des Bugs 😉
Hat doch was für sich, wenn man solche Themen mal im Detail durchleuchtet.
Ich hatte mich auch schon gewundert wie der Code mit .NET Framework schneller sein sollte als mit .NET Core.
Gerade auch bei den Optimierungen in .NET Core kann ich es mir nicht vorstellen, dass Framework Code wie ideser noch zu Core Code aufschließen könnte.
Alleine die Vektoriersierung in Core holt schon einen gewisse Größenordnung mehr Performance raus.
T-Virus
Developer, Developer, Developer, Developer....
99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.
Hallo T-Virus,
dazu eine kleine Ergänzung...
die Vektoriersierung in Core
Span.IndexOf
(die Erweiterungsmethode, eigentlichMemoryMarshal.IndexOf<T>(ROS, ROS)
) schaut ob T ein byte ist wenn ja nimmt es die optimierte Version vonSpanHelper.IndexOf(byte...)
um für das erste Element einen Treffer zu erzielen. Ist dieser vorhanden, so wird der Rest mit dem Suchmusterrest (das je erste Element wurde ja schon gematcht) perSpanHelper.SequenceEqual
verglichen.
SequenceEqual
ist wiederum der generische "Einstiegspunkt", der prüft ob T ein byte ist und falls ja den spezialisierten Code nimmt. Falls nicht muss der Vergleich generisch durchgefürht werden, d.h. einfach per Schleife (ist auch abgewickelt / "unrolled") drüberriterieren und per EqualityComparer<T>.Default
auf Gleichheit prüfen. Das ist aufwändig.
Wird hingegen der byte-spezialisierte Pfad genommen, so können mehre Optimieren durchgeführt werden:* vektorisierter Vergleich -- für SSE sind dazu mind. 16 bytes nötig, für AVX 32, für AVX-512 64, bei ARM analog
long
verglichen werden, dann je 4 bytes per int
, je 2 bytes per short
-- das ist auch Endianess-sicher, da es nur um gleich od. ungleich gehtAnmerkung:
Das gilt nicht nur für byte, sondern allgemein für alle T deren Größe (sizeof
) 1 ist. Somit auch für sbyte
.
Für sizeof(T) == 2
(char, short, ushort) wird eine ähnliche Spezialisierung vorgenommen.
In der Aufgabe hier hat das Suchmuster die Länge 15, ist also für den vektorisierten SequenceEqual
-Pfad zu kurz, dafür können jedoch die im 2. Punkt genannten Tricks angewandt werden. D.h. idealisiert und vereinfacht (dem Amdahlsches Gesetz nicht ganz genüge getan) sollte die Laufzeit dadurch 4...8x verkürzt werden.
den Optimierungen in .NET Core
Hier v.a. das besser interne Handling von Spans, welche der JIT direkt unterstützt und mehr od. weniger nur Prüfungen auf Einhaltung der Grenzen (bound checks) und Pointer-Bewegungen sind. Ziemlich ähnlich wie es bei sz-Arrays der Fall ist (nur dass eben keine Sub-Arrays, Array-Kopien, etc. nötig sind).
Ob diese direkte Unterstützung zu .NET 4.8 zurückportiert wurde weiß ich gerade nicht.
Dann gab es eine Menge Optimierungen in der Thread-Infrastruktur auf welchen die parallen Schleifen beruhen.
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"