Laden...

Performanterer Weg in einem Byte Array ein anderes (mehrfach) zu suchen

Erstellt von peterpan4711 vor 4 Jahren Letzter Beitrag vor 4 Jahren 6.321 Views
P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren
Performanterer Weg in einem Byte Array ein anderes (mehrfach) zu suchen

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?

T
2.219 Beiträge seit 2008
vor 4 Jahren

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.

16.806 Beiträge seit 2008
vor 4 Jahren

Was haste denn bisher versucht oder recherchiert??
Bisher hast ja einfach nur zwei simple Schleifen.

Allgemeine Tipps:

  • Können die 900 MB wirklich zeitgleich in den RAM? -> Asynchrone Streams (erfordert C# 8)
  • Unnötige Allocations können durch Span vermieden werden
  • Kann man das Array parallel lesen? -> Paralelle Schleife (Achte auf die .NET Pitfalls hier, siehe Doku)
T
2.219 Beiträge seit 2008
vor 4 Jahren

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.

P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren

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.

T
2.219 Beiträge seit 2008
vor 4 Jahren

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.

P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren

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?

T
2.219 Beiträge seit 2008
vor 4 Jahren

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.

P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren

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.

T
2.219 Beiträge seit 2008
vor 4 Jahren

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 😃

Doku

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.

P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren

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.

16.806 Beiträge seit 2008
vor 4 Jahren

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/

P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren

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?

16.806 Beiträge seit 2008
vor 4 Jahren

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

T
2.219 Beiträge seit 2008
vor 4 Jahren

@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.

P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren

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.

T
2.219 Beiträge seit 2008
vor 4 Jahren

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.

P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren

Danke. Werde mir jetzt Span ansehen.

Wie lang dauert der komplette Scan der 900MB inkl. Finden von ca 50 Einträgen bei Dir ca?

T
2.219 Beiträge seit 2008
vor 4 Jahren

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.

6.911 Beiträge seit 2009
vor 4 Jahren

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!"

6.911 Beiträge seit 2009
vor 4 Jahren

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!"

T
2.219 Beiträge seit 2008
vor 4 Jahren

@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.

6.911 Beiträge seit 2009
vor 4 Jahren

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!"

T
2.219 Beiträge seit 2008
vor 4 Jahren

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.

6.911 Beiträge seit 2009
vor 4 Jahren

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!"

4.931 Beiträge seit 2008
vor 4 Jahren

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 😉.

T
2.219 Beiträge seit 2008
vor 4 Jahren

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.

4.931 Beiträge seit 2008
vor 4 Jahren

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).

T
2.219 Beiträge seit 2008
vor 4 Jahren

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.

P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren

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.

6.911 Beiträge seit 2009
vor 4 Jahren

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!"

P
peterpan4711 Themenstarter:in
19 Beiträge seit 2019
vor 4 Jahren

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
16.806 Beiträge seit 2008
vor 4 Jahren

Ja, C# Versionen sind prinzipiell rückwärtskompatibel.
Das meiste ist quasi nur Syntaktischer Zucker

6.911 Beiträge seit 2009
vor 4 Jahren

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!"

4
12 Beiträge seit 2018
vor 4 Jahren

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

T
2.219 Beiträge seit 2008
vor 4 Jahren

@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.

4
12 Beiträge seit 2018
vor 4 Jahren

@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

16.806 Beiträge seit 2008
vor 4 Jahren

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.

  • .NET Standard ist ein "Vertrag", der vorgibt, was eine Runtime implementiert haben muss.
    .NET Standard selbst ist nur für den Entwicklungsweg relevant; .NET Standard kann keine Applikationen ausführen.
    Eine Bibliothek, die gegen .NET Standard entwickelt wurde, kann von jeder Runtime verwendet werden, die die jeweilige Version unterstützt.

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. 😉

4
12 Beiträge seit 2018
vor 4 Jahren

@Abt
Ups!
ja .Net Framework zu .Net Core 8o

16.806 Beiträge seit 2008
vor 4 Jahren

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.

4
12 Beiträge seit 2018
vor 4 Jahren

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

16.806 Beiträge seit 2008
vor 4 Jahren

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. 😉

4
12 Beiträge seit 2018
vor 4 Jahren

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.

6.911 Beiträge seit 2009
vor 4 Jahren

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.

  • Es gibt ein paar "Tricks" mit denen sicherer Code genauso effizient wie unsicherer Code ist, da der JIT gleichen bzw. gleichwertigen Maschinencode erzeugt. Da denke ich v.a. an das Vermeiden von Bound-Checks bei indizierten Zugriffen.
  • ...

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!"

16.806 Beiträge seit 2008
vor 4 Jahren

Chapeau! für den Post Gü!

T
2.219 Beiträge seit 2008
vor 4 Jahren

@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.

6.911 Beiträge seit 2009
vor 4 Jahren

Hallo T-Virus,

dazu eine kleine Ergänzung...

die Vektoriersierung in Core Span.IndexOf (die Erweiterungsmethode, eigentlich MemoryMarshal.IndexOf<T>(ROS, ROS)) schaut ob T ein byte ist wenn ja nimmt es die optimierte Version von SpanHelper.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) per SpanHelper.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

  • statt byte für byte, können z.B. je 8 bytes per 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 geht

Anmerkung:
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!"