Schnellste Array-Adressierung

Ich bin mit einem Bild-Analyse-code auf ein array zum speichern von Informationen über das Bild. Leider ist der code sehr schwer und dauert durchschnittlich 25s laufen über einen einzigen frame. Das Hauptproblem, das ich sehe, ist die array-Adressierung. Welche ist die am schnellsten zu laufen, durch ein 2d-array und gibt es überhaupt Unterschiede in der

horizontale, dann vertikale

for (int y = 0; y < array.Length; ++y)
    for (int x = 0; x < array[].Length; ++x)
        //Code using array[y][x]

und vertikaler dann horrizontal?

for (int x = 0; x < array[].Length; ++x)
    for (int y = 0; y < array.Length; ++y)
        //Code using array[y][x]

Darüber hinaus habe ich versucht zu vermeiden die direkte Adressierung und die Verwendung von Zeigern statt.

for (int y = 0; y < array.Length; ++y)
    int* ptrArray = (int*)array[0];
    for (int x = 0; x < array[].Length; ++x, ++ptrArray)
        //Code using ptrArray for array[y][x]

oder

for (int x = 0; x < array[].Length; ++x)
    int* ptrArray = (int*)array[0];
    for (int y = 0; y < array.Length; ++y, ptrArray += array[].Length)
        //Code using ptrArray for array[y][x]

Jede Hilfe wird sehr geschätzt.
Max

  • Ich sollte erwähnt haben, dass das array ist eigentlich ein BitmapData für bitmap-Farbe-Zuordnung :/ sry...
  • So, Sie sind schon pinning Speicher?
  • Haben Sie versucht, die Codierung bis jede Lösung und Messen, wie lange es dauert? Geben Sie die genaue Antwort. Aber wenn ich raten müsste, würde ich sagen, dass die Optionen 3 und 4 sind wohl etwas schneller als die Optionen 1 und 2.
  • Wenn man 25s für ein einzelnes Bild, die code-Stücke, die Sie geschrieben sind eindeutig nicht der begrenzende Teile.
  • Ihr größtes problem ist die Verwendung eines multi-dimensionale jagged array. Könntest du diesen in einen single-dimensionale null-basiertes array verwenden?
  • Ich denke, deine Geschwindigkeit bei der Bildverarbeitung hängt davon ab, WIE Sie ihn verarbeiten. Also, was machst du in loops?
  • Ihre aktuelle code ist nicht stabil, btw - du hast nicht behoben, das array vor der Einnahme einen Zeiger
  • Ich denke, das problem hier ist nicht die Schleifen, sondern: die //Code using {blah}. Wenn Sie nichts tun außer den loops, wie lange dauert es? Wir können nicht raten, auf {blah} ohne zu sehen {blah}
  • Der code in Schleifen kann nicht optimiert werden, viel, denn es ist so leicht, wie es sein wird (AForge). Das problem war das zählen, statt nach unten. Es reduziert meine volle computational Geschwindigkeit zu <4s 🙂

InformationsquelleAutor Max Z. | 2011-12-13
  1. 2

    Eine Möglichkeit ist die Verwendung von reverse-Schleife (start Ihre for() loop aus array.Length 0)

    Werde, dass die Dinge beschleunigen abit.

    beispielsweise

    for (int x = array[].Length-1; x >= 0; --x)
    int* ptrArray = (int*)array[0];
    for (int y = array.Length-1; y >= 0 ; --y, ptrArray += array[].Length)
        //Code using ptrArray for array[y][x]
    • Warum wäre das zu beschleunigen?
    • Wie würde die Dinge beschleunigen? Sollte der compiler clever genug sein, auf die Eigenschaft nur einmal, da die array-Länge wird sich nicht ändern in der Zwischenzeit.
    • Vergleich auf 0 ist schneller
    • link Lesen, zum Beispiel
    • Dieser link ist für Java, nicht .NET, es ist also nicht garantiert, sich zu bewerben. Auch, es scheint, gibt es einige Uneinigkeit. Ich denke, es ist einen Versuch Wert, obwohl, wie es dauert nur eine minute, um es auszuprobieren.
    • das ist der link für java; die JIT - (nicht C#, sondern: die VM) kann in der Regel vor Ort eine regelmäßige Vektor for Schleife und entfernen Sie die bounds-check etc... ich denke, das würde mehr brauchen klare Profilierung zu unterstützen, persönlich.
    • Vielleicht Max z. können überprüfen für uns.
    • Ich würde nicht einmal erwarten, dass es unbedingt wahr oder unwahr, für jede Java-VM, never mind .NET.
    • Nur ich schrieb meinen ganzen code, um den countdown, zu vergleichen, zu null und Zeiger verwenden, so oft wie möglich. Ich reduzierte die Geschwindigkeit von 25s auf <4s. Vielen Dank Jungs 🙂
    • Tolle Arbeit Max Z.!
    • Ausgezeichnet. Haben Sie überprüft, in welcher Reihenfolge Sie wurden gegen die Grenzen und bewegen sich von jagged-2-dimenstional?
    • Dies kann ein bisschen spät, aber vielleicht interessieren Sie in diesem. Ich bin mit der BitmapData-um das Bild zu erzeugen, welches ein 2d-array, die in der Tat ist eine lange 1d-array. Finden Sie die Zeiger, ich bin mit *.Scan0.ToPointer() zu finden und die Grenze zwischen ich benutze *.Stride (wo * ist die BitmapData-Instanz). Dies ermöglicht es mir, overjump möglich, ungenutzte Bereiche am Rand des Bildes neu zu definieren und den Zeiger auf den Anfang jeder Zeile des Bildes.
    • beachten Sie, dass der Vergleich gegen null arbeitet schneller, als es ist einfacher in der Montage zu prüfen, für die 0 als im Vergleich zu einigen numerischen Wert.

    InformationsquelleAutor Shai
  2. 2

    Die wichtigste Regel ist, dass es ist alle Theorie, bis Sie Profil. Ich glaube nicht, halten Sie mit diejenigen, die darauf bestehen, die Profilierung ist alles (ohne irgendeine Theorie, du bist nicht besser als ein Cargo-Kultisten setzen Kokosnüsse an Ihre Ohren und warten auf das Flugzeug zu kommen), aber deine Theorie kann immer falsch sein, oder unvollständig, so ist die Profilierung entscheidend.

    Im Allgemeinen, wir wollen, dass die inner-scan horizontal (in Bezug auf das array, eher als das Bild, obwohl für die meisten Formate, ist das gleiche). Der Grund dafür ist, dass mit einem array wie:

    00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29

    Es wird dargelegt werden, wie:

    00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

    Wollen Sie sein, Scannen entlang zusammenhängende Blöcke, die geladen werden können die CPU-caches und dann komplett benutzt, eher als das Scannen von block zu block und müssen regelmäßig ändern Sie die CPU-cache-Inhalt.

    Dies ist umso wichtiger, wenn Sie versuchen, parallelise der Algorithmus. Sie wollen, dass jeder thread, den Umgang mit Ihren eigenen zusammenhängenden Blöcken des Speichers so weit wie die beiden input-und output geht, anstatt leiden nicht nur unter der Möglichkeit single-threaded code mit arm-cache-hit-Frequenz, aber auch zu jeder anderen Puffer werden verschmutzt und müssen erfrischend. Dies kann den Unterschied zwischen parallelising führt zu einem speed-boost und parallelising eigentlich Verlangsamung Dinge nach unten.

    Andere Sache ist der Unterschied zwischen einem 2-dimensionalen array byte[,] eher als ein array von arrays byte[][], die Ihren Kommentar in deiner Frage "array[y][x]" das macht mich Frage mich, ob vielleicht Sie verwenden. Mit den ehemaligen zu erhalten, arr[1,2] die Logik ist:

    1. Check Bounds
    2. Berechnen position (einfache schnelle Arithmetik)
    3. Abrufen Wert.

    Mit der letzteren, die Logik ist:

    1. Check bounds
    2. Erhalten Arrays über Zeiger.
    3. Check bounds
    4. Abrufen Wert.

    Gibt es auch weniger gute cache-Speicher-Treffer-Frequenz. Letzteres hat Vorteile, wenn die "zerklüfteten" Strukturen benötigt, aber das ist hier nicht der Fall. 2D ist fast immer schneller als array von arrays.

    Dinge sehe ich nicht als wahrscheinlich zu helfen, aber ich würde sicherlich versuchen, Sie in Ihrer situation:

    Finden Sie eine boost-tun Sie Ihre 1d <=> 2d-Logik. Ein single-dimension-array, wobei idx = y * Breite + x. Es sollte nicht machen einen spürbaren Unterschied, aber es ist einen Versuch Wert.

    Optimierungen, die versuchen, beide hoist Aufrufe .Length auszulassen und unnötig bounds checking, so können Sie feststellen, manuell hochziehen und die Umstellung auf Zeiger-Arithmetik nicht alles gewinnen, aber in einem Fall, wo Sie wirklich brauchen, um down Zeit ist es sicher Wert profiling.

    Schließlich. Haben Sie sich profiliert, wie schnell dein code ist beim Scannen der Arrays und nichts zu tun? Könnte es sein, dass ein anderer Teil des Codes ist der eigentliche Flaschenhals, und du bist die Festsetzung der falsche.

    • Es sei denn, die Dinge haben sich verändert in den letzten .NET CLR rechteckige arrays in .NETTO wurden notorisch langsam und oft der speedup kommt in der umgekehrten Richtung (geht aus x[,] zu x[][]) eher als die Richtung, die hier vorgeschlagen werden.
    • Einer der .NET-Probleme in der Umsetzung ist, dass rechteckige arrays können nicht-null-Basen, die erschwert, die viele der Kern-Operationen. Mehr Infos hier: blog.mischel.com/2013/05/08/...
    InformationsquelleAutor Jon Hanna
  3. 1

    Habe ich keine Ahnung, aber hast du schon kommen mit die Beispiele. So könnten Sie führen Sie den code-Beispiele in einer Schleife und Profil-it-yourself.

    var sw = new Stopwatch();
sw.Start();
ExecuteMyCode();
sw.Stop();
Console.WriteLine("Time: " + sw.Elapsed);

    Könnten Sie in der Lage sein, um die Geschwindigkeit Ihrer Verarbeitung durch die Verwendung eines multi-threading-Konstrukt wie Parallel.ForEach. Dies würde gut funktionieren, wenn der code in der Schleife vermeidet Abhängigkeiten zwischen schleifeniterationen.

    • lol... glaube nicht, dass der Xo
    InformationsquelleAutor Merlyn Morgan-Graham
  4. 0

    Können Sie goy unsicher? Zeiger. Das problem mit Arrays ist, dass Sie immer NOCH die Grenze, die Kontrollen auf alle Zugriff. Zeiger zu entfernen. Hinweis tha dies ist völlig in C# unterstützt - aber Sie brauchen, um es in einen unsafe-block. Es bedeutet auch, Sie müssen in der LAGE sein, um unsicheren code ausführen, was nicht immer gegeben.

    http://msdn.microsoft.com/en-us/library/28k1s2k6.aspx

    ist mit einem code-Beispiel.

    • Die Beispiele mit int* (in der Frage) dies bereits tun. Beachten Sie auch, dass der JIT ist in der Regel in der Lage zu entfernen bounds-checks auf den Vektor/for Schleifen.
    InformationsquelleAutor TomTom
  5. 0

    Wenn es möglich ist, versuchen zu reservieren das array so, dass die erste dimension ist weniger als der zweite. Es würde die Dinge etwas beschleunigen drastisch.
    Eine andere Lösung ist die Umverteilung der Daten in einem eindimensionalen array wie oben vorgeschlagen.

    InformationsquelleAutor George
  6. 0

    Immer stellen Sie sicher, dass Sie Ihre innersten Schleife greift auf zusammenhängenden Speicher.

    Dies ist in der Regel die Zeile des Bildes. Beachten Sie, dass bei rechteckigen arrays, sollten Sie dies der Letzte index: array[y,x].

    dieses Papier deutet darauf hin, dass die integrierte C# - rechteckige arrays (mit der mehrere Indizes) sind Recht langsam. Ich lese diese vor, aber dies ist der einzige Hinweis, den ich bekam. Ich würde beginnen mit einer linear-array -, und berechnen eines offset für jede Zeile einmal. Nicht verwaltete hilft Ihnen nur in sehr trivialen Fällen.

    Wenn ein einzelnes Bild dauert 25 Sekunden, dann ist es entweder huuuuge, oder Sie sehr aufwendige Verarbeitung. In diesem Fall ist es nur interessant zu verbringen Aufwand auf die Optimierung der Speicher-Zugriff, wenn Sie den Zugriff auf viele Eingangs-Pixel für jedes pixel-Ausgabe, der.

    • Beide... Es ist mit FFT und Filter für die eingehende Analyse
    InformationsquelleAutor
Schreibe einen Kommentar