Schnelle Array Bearbeitung

[Ralph Erdt (2)]

Hallo.

Ich habe hier eine Operation, die ich auf alle Elemente eines Arrays loslassen muss. Klar..

for (int i = 0; i < array.length; i++) 
      array[i] = array[i]+-*/ y;

geht. Ich habe aber kein gutes Gefühl dabei, vor allem, wenn dass einige Millionen mal durchlaufen werden muss (*)

Gibt es da etwas effizienteres? (Oder habe ich zuviel mit MatLab gearbeitet? )

Danke

(* Natürlich habe ich kein so großes Array, ich hole dann die Daten paketweise!)

[Christian Marquardt]

array[i]+-*/ y;

Das ist die Rechenoperation?
Nun, ggf. kann man Werte shiften, da geht die Berechung schneller

[gfoidl]

Hallo,

ich hole dann die Daten paketweise!)

Das wird eher die Bremse sein als die simple Schleife.

Je nach Kontext, den wir hier nicht wissen, könnte parallelisiert gearbeitet werden. Wobei bei dieser simplen Schleife der Overhead für eine parallele for-Schleife wohl zu groß ist -- das hängt aber von der Array-Größe ab.
Auch je nach tatsächlicher Operation kann mittels SIMD (Nuget-Paket System.Numerics.Vectors) eine (prozessorbasierte) Beschleunigung erfolgen. Das wäre dann z.B.
[highlight=c#]
using System.Numerics;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
double[] vector = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
double y = 10;

double[] result = MySuperVectorOperation(vector, y);
}

private static double[] MySuperVectorOperation(double[] vector, double y)
{
int registerLength = Vector<double>.Count;
int i = 0;
var dividend = new Vector<double>(y);

for (i = 0; i < vector.Length - registerLength; i += registerLength)
{
var va = new Vector<double>(vector, i);
var res = va / dividend;
var rrr = Vector.Divide(va, dividend);
res.CopyTo(vector, i);
}

for (; i < vector.Length; ++i)
vector[i] /= y;

return vector;
}
}
}
[/highlight]
Für float statt double wäre es noch etwas schneller, da dann die SIMD-Registerlänge größer ist (doppelt so groß).

Beschreib mal was du da vorhast, dann findet sich schon eine passende Lösung.

mfG Gü

[Ralph Erdt (2)]

Hallo.

Das ist die Rechenoperation?

Das war nur ein Beispiel / Pseudocode.

Das wird eher die Bremse sein als die simple Schleife.

Sorry, aber ab einer gewissen Paketgröße macht das kein Unterschied, bzw. wenn Windows wegen Speichermangel auf Platte auslagern muss...

Je nach Kontext, den wir hier nicht wissen, könnte parallelisiert gearbeitet werden. Wobei bei dieser simplen Schleife der Overhead für eine parallele for-Schleife wohl zu groß ist -- das hängt aber von der Array-Größe ab.
Auch je nach tatsächlicher Operation kann mittels SIMD (Nuget-Paket System.Numerics.Vectors) eine (prozessorbasierte) Beschleunigung erfolgen. Das wäre dann z.B.[..]

Danke, werde es mir mal ansehen.

Beschreib mal was du da vorhast, dann findet sich schon eine passende Lösung.

...
Eine Datei ist "verschlüsselt" geschrieben, und muss beim einlesen entschlüsselt werden (=gleiche Operation auf jedes Byte). (Über [s]Sinn und[/s] Unsinn dieser "Verschlüsselung" möchte hier nicht diskutieren - das weiß ich. Betriebsinterna).

Ich habe daher eine Klasse geschrieben, die vom Stream ableitet und einfach alles an einen weiteren Stream durchreicht und nur im Read diese "Entschlüsselung" macht (write ist (vorerst) noch deaktiviert).

Grüße
Ralph

[gfoidl]

Hallo,

ab einer gewissen Paketgröße macht das kein Unterschied, bzw. wenn Windows wegen Speichermangel auf Platte auslagern muss...

in diesem Fall ist das Holen der Daten dann noch langsamer und bestätigt ja gerade meine Aussage: Schleifen << Holen der Daten.

Optimierungen könntest du dann eher in der Richtung anstellen wie schneller gelesen werden kann. Z.B. in dem an den Buffergrößen geschraubt wird, usw.
Sollte es wirklich nur eine simple Operation in der Schleife sein, so passt diese. Ist die Operation jedoch wesentlich aufwändiger, so dass sie zeitlich gesehen grob in der Größenordnung des Holens eines Pakets ist, so kann ein Pipelining (cf. Pipelines -- Producer/Consumer) insgesamt hilfreich sein, da das Holen der Pakete asynchron zu den Operationen erfolgen kann.

Ist die zu lesende Datei "riesig" so könnte durch "memory mapped files" und Bewegen der View über die Datei ein Vorteil entstehen. Ob dies tatsächlich so ist, muss probiert werden, denn pauschal können solche Aussagen nicht getätigt werden.

Ich habe daher eine Klasse geschrieben, die vom Stream ableitet

Ich weiß jetzt nicht genau wie du das umgesetzt hast, aber schau dir ggf. als Entwurfmuster den "Decorator" an, da dieser genau für solche Fälle passt.
Dein Entschlüsselungs-Stream wird also über den zugrundelegenden Stream gepackt, dieser also "dekoriert".



mfG Gü

[Ralph Erdt (2)]

Hallo.

Ich habe jetzt mal die System.Numerics.Vectors Variante implementiert.

Bei einer 8MB Datei braucht der Plain (ohne Vektor, nur eine einfache Schleife) ca 50ms. Mit Vectoroperationen (optimiert*) ca. 500ms. Vermutlich zerhaut das Objekt erzeugen (+GC) die Zeit.
(*Ich habe "dividend" ausgelagert (wird nur einmal während der Programmlaufzeit angelegt))

Decorator:
Ich habe mal den Wikipedia Artikel grob überflogen. Wenn ich es richtig verstehe, ist es genau das, was ich gemacht habe (wieder einen Namen gelernt für etwas, was ich schon lange mache...).

Danke für die Mühe
Ralph

P.S.
In deinem Beispielcode wird "var rrr" nicht verwendet.

[gfoidl]

Hallo,

das hat mir jetzt keine Ruhe gelassen und ich musste das selbst probieren ;-)

Wichtig beim Testen ist dass dies im "Release" durchgeführt wird. Ansonsten führt der Compiler (sowohl C# als der JITer) keine Optimierungen aus. SIMD ist ebenfalls nur im Release verfügbar.

Vermutlich zerhaut das Objekt erzeugen (+GC) die Zeit.

Vector<T> ist eine Struktur, da hat der GC keine Arbeit da Strukturen auf dem Stack (und nicht auf dem Heap = GC) erzeugt werden.
Das kostet also nicht mehr als wenn eine int-Variable angelegt wird.
Dennoch gibt es durch das Hin-/Herkopieren einen Overhead. Hier ist es tatsächlich so, dass SIMD nicht schneller ist, allerdings bei mir nicht so in der Größenordnung wie bei dir (vllt. Debug/Release).

Angehängt mein Test-Projekt dazu (Ralph Erdt.zip). Damit kannst du noch rumspielen und v.a. die korrekte "Entschlüsselung" einbauen. Die Ausgabe ist auf meinem Rechner und dem Test-Projekt:

Hardware-Info
=============

OSVersion                      Microsoft Windows NT 6.1.7601 Service Pack 1
Is64BitOperatingSystem         True
Is64BitProcess                 True
ProcessorCount                 8
IsHardwareAccelerated          True
SIMD-Register for int          4
SIMD-Register for long         2
SIMD-Register for float        4
SIMD-Register for double       2
SIMD-Register for byte         16

Source Stream = MemoryStream
============================
Buffer  Name                           Time
1024    naive                          38
2048    naive                          41
4096    naive                          39
8192    naive                          39
16384   naive                          39
32768   naive                          38
65536   naive                          39
131072  naive                          39
262144  naive                          38
524288  naive                          39

1024    parallel for                   165
2048    parallel for                   122
4096    parallel for                   78
8192    parallel for                   57
16384   parallel for                   49
32768   parallel for                   39
65536   parallel for                   42
131072  parallel for                   37
262144  parallel for                   33
524288  parallel for                   33

1024    parallel for chunked           135
2048    parallel for chunked           89
4096    parallel for chunked           58
8192    parallel for chunked           44
16384   parallel for chunked           33
32768   parallel for chunked           25
65536   parallel for chunked           24
131072  parallel for chunked           23
262144  parallel for chunked           20
524288  parallel for chunked           18

1024    simd                           70
2048    simd                           73
4096    simd                           71
8192    simd                           71
16384   simd                           72
32768   simd                           71
65536   simd                           70
131072  simd                           71
262144  simd                           70
524288  simd                           70

1024    parallel for chunked + simd    147
2048    parallel for chunked + simd    132
4096    parallel for chunked + simd    73
8192    parallel for chunked + simd    66
16384   parallel for chunked + simd    41
32768   parallel for chunked + simd    35
65536   parallel for chunked + simd    32
131072  parallel for chunked + simd    30
262144  parallel for chunked + simd    27
524288  parallel for chunked + simd    29

Best:
524288  parallel for chunked           18

Source Stream = FileStream
============================
Buffer  Name                           Time
1024    naive                          43
2048    naive                          44
4096    naive                          42
8192    naive                          41
16384   naive                          40
32768   naive                          41
65536   naive                          42
131072  naive                          41
262144  naive                          40
524288  naive                          40

1024    parallel for                   193
2048    parallel for                   149
4096    parallel for                   110
8192    parallel for                   76
16384   parallel for                   67
32768   parallel for                   49
65536   parallel for                   53
131072  parallel for                   51
262144  parallel for                   39
524288  parallel for                   37

1024    parallel for chunked           156
2048    parallel for chunked           119
4096    parallel for chunked           85
8192    parallel for chunked           52
16384   parallel for chunked           40
32768   parallel for chunked           28
65536   parallel for chunked           24
131072  parallel for chunked           22
262144  parallel for chunked           21
524288  parallel for chunked           20

1024    simd                           77
2048    simd                           78
4096    simd                           76
8192    simd                           74
16384   simd                           76
32768   simd                           73
65536   simd                           74
131072  simd                           73
262144  simd                           73
524288  simd                           73

1024    parallel for chunked + simd    184
2048    parallel for chunked + simd    133
4096    parallel for chunked + simd    106
8192    parallel for chunked + simd    66
16384   parallel for chunked + simd    44
32768   parallel for chunked + simd    37
65536   parallel for chunked + simd    34
131072  parallel for chunked + simd    30
262144  parallel for chunked + simd    29
524288  parallel for chunked + simd    29

Best:
524288  parallel for chunked           20


End.

Am schnellsten geht es mit:
[highlight=c#]
public override void Decrypt(byte[] buffer, int offset, int count, byte dividend = 3)
{
// Da die Arbeit in der Schleife gering ist, ist es die Verwendung eines
// Partitioner sinnvoll.
Parallel.ForEach(
Partitioner.Create(offset, offset + count),
range =>
{
for (int i = range.Item1; i < range.Item2; ++i)
buffer[i] /= dividend;
}
);
}
[/highlight]

Dass SIMD hier nicht schneller ist, v.a. da die Regiter-Größe bei byte 16 ist, hat mich schon ein wenig gewundert. Vermutlich ist der Overhead einfach zu groß für die "kleinen" Blöcke (aus numerischer Vektorsicht).
Würde direkt mit Assembler programmiert werden, so muss SIMD schneller sein, sonst verstehe ich das nicht mehr ;-) (Das hab ich aber nicht probiert).

P.S.
In deinem Beispielcode wird "var rrr" nicht verwendet.

Ups, das war ein Copy & Paste Fehler. Ich war nicht mehr ganz sicher ob bei Vector<T> der Divisions-Operator / implementiert ist und v.a. wie. Daher hab ich mittels (der sinnfreien Bezeichnung) "rrr" die Probe gemacht.


mfG Gü

[Ralph Erdt (2)]

Hallo.

Oh.. Danke für den Aufwand, den ich mache ..
So ausführlich habe ich es nicht getestet.

Mein Code:
(Entschuldige bitte, dass ich einige Stellen faken musste. Ich will hier kein Stress bekommen, wenn das "öffentlich" wird:
* XXX: Irgendwelche Werte
* BitOperation: Eine BitOperation
* MathOperation: Eine Mathematische Operation
* Rechne: Das Rechnen eben..)

* native:

        public override int Read(byte[] buffer, int offset, int count)
        {
            int readed = stream.Read(buffer, offset, count);

            for (int i = offset; i < offset + readed; i++)
            {
                buffer[i] = (byte)(..Rechne..);
            }

            return readed;
        }

*SIMD:

        Vector<byte> opM = new Vector<byte>(XXX);
        Vector<byte> opB = new Vector<byte>(XXX);
        int registerLength = Vector<byte>.Count;

        public override int Read(byte[] buffer, int offset, int count)
        {
            int readed = stream.Read(buffer, offset, count);
            
            int i = 0;
            for (i = 0; i < readed - registerLength; i += registerLength)
            {
                Vector.BitOperation(Vector.MathOperation(new Vector<byte>(buffer, offset + i), opB), opX).CopyTo(buffer, offset + i);
            }
            for (; i < readed; ++i)
                buffer[i] = (byte)(..Rechne..);

            return readed;
        }

* Getestet mit:

            Stopwatch sw = new Stopwatch();
            sw.Start();
            String s = new StreamReader(new Decryptor(new FileStream(@"c:\temp\XXXX", FileMode.Open, FileAccess.Read)), Encoding.Unicode, true, 102400).ReadToEnd();
            sw.Stop();
            MessageBox.Show("Sw: " + sw.ElapsedMilliseconds);
            textBox1.Text = s;

Ich weiß, hier wird viel mehr mitgemessen, als nur die "Verschlüsselung", aber es ist für Größenordnungen ausreichend.

Ich werde mir mal dein Code demnächst in Ruhe reinziehen..

Danke nochmal
Ralph

P.S.
Ich habe ganz vergessen etwas zum wichtigsten zu schreiben:
In der Release Konfiguration ist das einfach fast doppelt so schnell (50 -> 30), die SIMD nur etwas (500 -> 400)

[Ralph Erdt (2)]

Nachtrag:
Ich habe auch mal das Parallel.For mit Cluster ausprobiert: Auch langsamer. Der Compiler scheint die Plain Variante sehr gut zu optimieren.