Floyd-Steinberg - geht das nicht noch schneller?

[Jörg "Yadgar" Bleimann]

Hi(gh)!

Jetzt habe ich also (danke, Stefan Reuther!) meinen
Floyd-Steinberg-Filter einwandfrei implementiert und lasse ihn gerade
per bash-Skript eine Sequenz von über 7000 Bildern bearbeiten... aber
irgendwie kommt mir das alles ziemlich behäbig vor, was die
Rechengeschwindigkeit angeht. Für 2000 Bilder (unkomprimierte TGAs, 533
x 400 Pixel) 69 Minuten, und das auf einem AMD-Hexacore mit 6 x 3,852
GHz... ließe sich da nicht noch einiges optimieren? Ich habe zum
Beispiel das Gefühl, dass yip nur einen der sechs Prozessorkerne
nutzt... wo finde ich (für mich verständliche!) Informationen zum Thema
Multithreading mit C++?

Bis bald im Khyberspace!

Yadgar

[Stefan Ram]

=?UTF-8?Q?J=c3=b6rg_=22Yadgar=22_Bleimann?= <yazd...@gmx.de> writes:
>Rechengeschwindigkeit angeht. Für 2000 Bilder (unkomprimierte TGAs, 533
>x 400 Pixel) 69 Minuten, und das auf einem AMD-Hexacore mit 6 x 3,852
>GHz... ließe sich da nicht noch einiges optimieren? Ich habe zum

Eventuell könnte es effizienter sein, nur einen Vektor zu
verwenden.

vector<vector<pixel> >
->
::std::vector<pixel>

img[r].at(c)
->
img[r*C+c]

(Im [aus Sicht des Programmierstils] besten Fall, weiß ein
Klient der Zeichenfläche gar nicht, welche der beiden
Implementationen gewählt wurde [implementation hiding],
beispielsweise:

image img; /* mit Deinem eigenen Typ image */
...
rowref r = img[ r ]; /* mit Deinem eigenen Operator [] und Typ rowref */
...
pixel c = rowref[ c ]; /* mit Deinem eigenen Operator [] */)

Allgemein könntest Du wiederholt berechnete Teilausdrücke
einmal am Schleifenanfang puffern, beispielsweise

imgr = img + r * C; /* u. s. w. */

>Beispiel das Gefühl, dass yip nur einen der sechs
>Prozessorkerne nutzt... wo finde ich (für mich
>verständliche!) Informationen zum Thema Multithreading mit
>C++?

Der Algorithmus ist mit der Aufsummierung der /bisherigen/
Fehler ja erst einmal sequentiell. Selbst, wenn er parallel
wäre, könnten solche Effekte wie Synchronisationsaufwand,
cache sharing und false sharing dazu beitragen, daß die
Beschleunigung kleiner ist als erhofft.

Aber wenn Du mehr als ein Bild hast, wäre es eventuell einen
Versuch wert, mehrere Prozesse mit diesem Programm einfach
jeweils gleichzeitig auf eine Teilmenge der Bilder loszulassen.

[Stefan Reuther]

Am 20.02.2017 um 19:27 schrieb Jörg "Yadgar" Bleimann:
> Jetzt habe ich also (danke, Stefan Reuther!) meinen
> Floyd-Steinberg-Filter einwandfrei implementiert und lasse ihn gerade
> per bash-Skript eine Sequenz von über 7000 Bildern bearbeiten... aber
> irgendwie kommt mir das alles ziemlich behäbig vor, was die
> Rechengeschwindigkeit angeht. Für 2000 Bilder (unkomprimierte TGAs, 533
> x 400 Pixel) 69 Minuten, und das auf einem AMD-Hexacore mit 6 x 3,852
> GHz... ließe sich da nicht noch einiges optimieren?

Da kann man Bücher drüber schreiben. Die offensichtliche Frage natürlich
zuerst: Compiler-Optimierung schon eingeschaltet? Zentrale Methoden
ge-inline-d? Das erscheint mir auch so recht langsam.

Ansonsten ist deine Implementierung natürlich sehr naiv (und das sage
ich ganz ausdrücklich nicht abwertend): Du nutzt vector<vector<>>. Du
nutzt die Bereichsprüfung per vector.at. Du nutzt Klassen für alles
Mögliche. Das ist schön zum lernen und experimentieren, aber eben nicht
schnell.

Echte[tm] Bildverarbeitungsalgorithmen arbeiten auf nacktem Speicher,
also bestenfalls ein Vektor, auf dessen Inhalt dann am Ende per
Pointer+Länge zugegriffen wird (die Größe ändert sich ja nicht). Pixel
werden dann nach Möglichkeit nicht in einer Klasse dargestellt, sondern
in einem Datentyp, der es erlaubt, die SIMD-Instruktionen des Prozessors
zu nutzen. Und wenn's sehr pressiert, werden die zentralen Routinen dann
in Assembler geschrieben.

Das musst du dir nun nicht alles antun, aber schon das Umbauen von
vector<vector<>> und at auf einen vector und [] dürfte einiges bringen.

> Ich habe zum Beispiel das Gefühl, dass yip nur einen der sechs
> Prozessorkerne nutzt... wo finde ich (für mich verständliche!)
> Informationen zum Thema Multithreading mit C++?

Ich weiß ja nicht, was dein Ausgangspunkt ist, aber ich würde vermutlich
anfangen, erst einmal ein paar allgemeine Artikel zum Thema
Multithreading reinzupfeifen, und danach etwas zur gewünschten
Threading-Bibliothek der Wahl (Qt? C++11? pthreads?).

Für den konkreten Fall, ich habe einen Algorithmus in ein Programm
gegossen und will den maximal schnell auf viele Dateien loslassen,
schreib ich allerdings meistens einfach ein Makefile und lass make das
ganze auf Prozessebene parallelisieren.


Stefan

[Markus Schaaf]

Am 21.02.2017 um 18:49 schrieb Stefan Reuther:

> Für den konkreten Fall, ich habe einen Algorithmus in ein Programm
> gegossen und will den maximal schnell auf viele Dateien loslassen,
> schreib ich allerdings meistens einfach ein Makefile und lass make das
> ganze auf Prozessebene parallelisieren.

Danke für die elegante Idee. Ich hatte xargs im Kopf, habe mir eine
Antwort jedoch verkniffen, da bei diesem einfachen Algorithmus der
Massenspeicher der limitierende Faktor sein dürfte. (Ich hatte vor ein
paar Tagen einen ähnlichen Gedanken, als ich sha256sum parallelisieren
wollte, dann aber merkte, dass das Problem nicht die Hashfunktion,
sondern das Lesen der Dateien war.)

MfG

[Jörg "Yadgar" Bleimann]

Hi(gh)!

On 21.02.2017 18:49, Stefan Reuther wrote:
> Am 20.02.2017 um 19:27 schrieb Jörg "Yadgar" Bleimann:
>> Jetzt habe ich also (danke, Stefan Reuther!) meinen
>> Floyd-Steinberg-Filter einwandfrei implementiert und lasse ihn gerade
>> per bash-Skript eine Sequenz von über 7000 Bildern bearbeiten... aber
>> irgendwie kommt mir das alles ziemlich behäbig vor, was die
>> Rechengeschwindigkeit angeht. Für 2000 Bilder (unkomprimierte TGAs, 533
>> x 400 Pixel) 69 Minuten, und das auf einem AMD-Hexacore mit 6 x 3,852
>> GHz... ließe sich da nicht noch einiges optimieren?
>
> Da kann man Bücher drüber schreiben. Die offensichtliche Frage natürlich
> zuerst: Compiler-Optimierung schon eingeschaltet?

So weit ich weiß, nicht... ich kompliere immer g++ quelle.cc -o kompilat

> Zentrale Methoden
> ge-inline-d?

Da müsste ich erstmal meinen "Aupperle" ausgraben, um nochmal
nachzulesen, wie das geht...

Das erscheint mir auch so recht langsam.
>
> Ansonsten ist deine Implementierung natürlich sehr naiv (und das sage
> ich ganz ausdrücklich nicht abwertend): Du nutzt vector<vector<>>. Du
> nutzt die Bereichsprüfung per vector.at. Du nutzt Klassen für alles
> Mögliche. Das ist schön zum lernen und experimentieren, aber eben nicht
> schnell.

...ich bin doch nur ein besoffener Manta-Schrauber, der versucht, die
Technik eines Formel-1-Rennwagens zu ergünden! :-)

> Echte[tm] Bildverarbeitungsalgorithmen arbeiten auf nacktem Speicher,
> also bestenfalls ein Vektor, auf dessen Inhalt dann am Ende per
> Pointer+Länge zugegriffen wird (die Größe ändert sich ja nicht).

Nein, Pixel bestehen an sich aus jeweils drei unsigned char-Werten...
die müssen zum Rechnen natürlich in längere Typen umgewandelt werden!

> Pixel
> werden dann nach Möglichkeit nicht in einer Klasse dargestellt, sondern
> in einem Datentyp, der es erlaubt, die SIMD-Instruktionen

SIMD? Kann das mein Hexacore?

> des Prozessors
> zu nutzen. Und wenn's sehr pressiert, werden die zentralen Routinen dann
> in Assembler geschrieben.

Ouhauerha! Bevor ich mich da rantraue, lerne ich erstmal 6502-Assembler,
damit ich meinen C 64 endlich mal richtig ausreizen kann... später
könnte ich dann zum 68000 übergehen, hier steht nämlich auch noch ein
Atari 1040 STFM, der sich mittlerweile schon ziemlich vernachlässigt
fühlt...

> Das musst du dir nun nicht alles antun, aber schon das Umbauen von
> vector<vector<>> und at auf einen vector und [] dürfte einiges bringen.
>

> Ich weiß ja nicht, was dein Ausgangspunkt ist, aber ich würde vermutlich
> anfangen, erst einmal ein paar allgemeine Artikel zum Thema
> Multithreading reinzupfeifen, und danach etwas zur gewünschten
> Threading-Bibliothek der Wahl (Qt? C++11? pthreads?).
>
> Für den konkreten Fall, ich habe einen Algorithmus in ein Programm
> gegossen und will den maximal schnell auf viele Dateien loslassen,
> schreib ich allerdings meistens einfach ein Makefile und lass make das
> ganze auf Prozessebene parallelisieren.

Ich habe es mir gestern Nacht einfacher gemacht und einfach fünf
Instanzen von yip gestartet, jede bearbeitete jeweils rund 7000
Bilddateien, heute vormittag gegen halb elf war alles fertig! Aber mit
deinen Vorschlägen wäre natürlich noch mehr Speed drin... aber alles
eins nach dem anderen!

[Stefan Reuther]

Am 22.02.2017 um 16:29 schrieb Jörg "Yadgar" Bleimann:
>>> Jetzt habe ich also (danke, Stefan Reuther!) meinen
>>> Floyd-Steinberg-Filter einwandfrei implementiert und lasse ihn gerade
>>> per bash-Skript eine Sequenz von über 7000 Bildern bearbeiten... aber
>>> irgendwie kommt mir das alles ziemlich behäbig vor, was die
>>> Rechengeschwindigkeit angeht. Für 2000 Bilder (unkomprimierte TGAs, 533
>>> x 400 Pixel) 69 Minuten, und das auf einem AMD-Hexacore mit 6 x 3,852
>>> GHz... ließe sich da nicht noch einiges optimieren?
>>
>> Da kann man Bücher drüber schreiben. Die offensichtliche Frage natürlich
>> zuerst: Compiler-Optimierung schon eingeschaltet?
>
> So weit ich weiß, nicht... ich kompliere immer g++ quelle.cc -o kompilat

Dann pack da noch ein -O oder -O2 dazu und staune.

>> Echte[tm] Bildverarbeitungsalgorithmen arbeiten auf nacktem Speicher,
>> also bestenfalls ein Vektor, auf dessen Inhalt dann am Ende per
>> Pointer+Länge zugegriffen wird (die Größe ändert sich ja nicht).
>
> Nein, Pixel bestehen an sich aus jeweils drei unsigned char-Werten...
> die müssen zum Rechnen natürlich in längere Typen umgewandelt werden!

Dann könntest du schon einen Gewinn daraus ziehen, dass du diese Klasse
von "drei unsigned char" auf "ein uint32_t" umbaust. "get_red" ist dann
"return (pixel >> 16)", "set_red" ist "pixel = (pixel & 0x00FFFF) |
(value << 16)", und so weiter.

>> Pixel
>> werden dann nach Möglichkeit nicht in einer Klasse dargestellt, sondern
>> in einem Datentyp, der es erlaubt, die SIMD-Instruktionen
>
> SIMD? Kann das mein Hexacore?

Das kann sogar ein 20 Jahre alter Pentium MMX.

SIMD ist der Oberbegriff für MMX, SSE, AltiVec, NEON, und wie das alles
heißt. Voraussetzung dafür ist aber meistens speziell geschriebener Code
und die Verwendung spezieller Datentypen, und dann kann der Prozessor
halt in einem Zyklus 8 Integer auf einmal addieren.

Allerdings: wenn dein "Hauptverkaufsargument" nicht hochoptimierte
Grafikalgorithmen sind, ist das alles nicht nötig. Meine
Grafikspielereien arbeiten auch nur mit ganz normalem C++ (also ohne
SIMD, ohne Assembler) und waren schon auf 200 MHz schnell genug, um
damit eine passable GUI zu bauen.


Stefan

[Stefan Ram]

Stefan Reuther <stefa...@arcor.de> writes:
>Dann pack da noch ein -O oder -O2 dazu und staune.

Warum nicht »-03«?

>Dann könntest du schon einen Gewinn daraus ziehen, dass du
>diese Klasse von "drei unsigned char" auf "ein uint32_t"
>umbaust. "get_red" ist dann "return (pixel >> 16)", "set_red"
>ist "pixel = (pixel & 0x00FFFF) | (value << 16)", und so
>weiter.

Hier wird

a.y = c;

zu

movb %dl, 49(%rsp)

kompiliert (a ist eine struct mit drei chars x,y,z bei 48,
c befindet sich schon in edx).

Aus

a = a&0xff00ff | c<<8;

wird (jetzt ist a ein unsigned long bei 64,
c ist wieder schon in edx)

movl 64(%rsp), %eax
andl $16711935, %eax
movl %eax, %ecx
movsbl %dl, %eax
sall $8, %eax
orl %ecx, %eax
movl %eax, 64(%rsp)

Ist das immer effizienter als ein einzelnes »movb«?

Was ist, wenn ich die ganze struct zuweise?

In einer bestimmten Konfiguration verwendet die
Implementation hier, um eine

struct { char x, y, z; }

zu kopieren ein movw und ein movb, aber wenn man ein
Füll-char hinzufügt:

struct { char x, y, z, f; }

wird nur ein einziges movl genommen. Das muß dann
nicht unbedingt ineffizienter sein als das Kopieren
eines long.

>Das kann sogar ein 20 Jahre alter Pentium MMX.

Bei gcc kann man sich auch mal Optionen wie

-msse2

oder

-march=native

ansehen.

[Stefan Reuther]

Am 23.02.2017 um 02:14 schrieb Stefan Ram:
> Stefan Reuther <stefa...@arcor.de> writes:
>> Dann pack da noch ein -O oder -O2 dazu und staune.
>
> Warum nicht »-03«?

Weil "-03" keine gültige Option ist :) und "-O3" zumindest im
Normalbetrieb für mich keinen sinnvollen Gewinn mehr bringt verglichen
mit dem Aufwand.

>> Dann könntest du schon einen Gewinn daraus ziehen, dass du
>> diese Klasse von "drei unsigned char" auf "ein uint32_t"
>> umbaust. "get_red" ist dann "return (pixel >> 16)", "set_red"
>> ist "pixel = (pixel & 0x00FFFF) | (value << 16)", und so
>> weiter.
>
> Hier wird
>
> a.y = c;
>
> zu
>
> movb %dl, 49(%rsp)
>
> kompiliert (a ist eine struct mit drei chars x,y,z bei 48,
> c befindet sich schon in edx).
>
> Aus
>
> a = a&0xff00ff | c<<8;
>
> wird (jetzt ist a ein unsigned long bei 64,
> c ist wieder schon in edx)
>
> movl 64(%rsp), %eax
> andl $16711935, %eax
> movl %eax, %ecx
> movsbl %dl, %eax
> sall $8, %eax
> orl %ecx, %eax
> movl %eax, 64(%rsp)
>
> Ist das immer effizienter als ein einzelnes »movb«?

Interessanter wird das dann, wenn du mehrere solcher Operationen machst.

Speicherzugriffe sind teurer als Rechenoperationen. Bei
komponentenweisen Zugriffen werden halt mehrere Zugriffe generiert, den
uint32_t holt der Compiler in einem Rutsch. Wieviel davon der Cache auf
einem Desktop-Schlachtschiff wegoptimiert, kann ich zugegebenermaßen
nicht sagen, aber auf Embedded-Systemen hab ich durchaus schon solche
Effekte messen können.

Ein kleverer Compiler fasst
a = (a & 0xFF00FF) | (g << 8);
a = (a & 0xFFFF00) | b;
zu einem
a = (x & 0xFF0000) | (g << 8) | b;
zusammen, und wenn du das in einer Schleife tust, wird das "<<" auch
noch aus der Schleife gezogen. Der uint32_t ist auch immer aligned, so
dass memcpy zumindest in einen schnelleren Pfad gehen wird als bei einem
misaligned struct {uint8 r,g,b,a} oder gar struct {uint8 r,g,b}.


Stefan

[Bonita Montero]

Ich geh mal davon aus, dass das Kreieren eines Prozesses für jedes Bild
schon einiges an Rechenzeit kostet. Am besten Du lässt ei Wildcard auf
dein Programm los und verteilst die Parameter im argv auf Threads so
viele Du logische Threads im System hast. Damit wäre schon mal einiges
gewonnen.

--
http://facebook.com/bonita.montero/

[Stefan Reuther]

Am 23.02.2017 um 18:27 schrieb Bonita Montero:
> Ich geh mal davon aus, dass das Kreieren eines Prozesses für jedes Bild
> schon einiges an Rechenzeit kostet. Am besten Du lässt ei Wildcard auf
> dein Programm los und verteilst die Parameter im argv auf Threads so
> viele Du logische Threads im System hast. Damit wäre schon mal einiges
> gewonnen.

Bei 69 Minuten für 2000 Bilder, also ca. 2 Sekunden pro Prozess, ist die
Startupzeit des Prozesses definitiv nicht das Limit. Bei Verwendung des
gcc hast du auch eine Handvoll Prozesse pro Compilierungsvorgang (gcc,
cpp, cc1plus, as, collect2, ld). Und heutige Betriebssysteme können den
gcc eigentlich alle recht performant ausführen.

Es sei denn, wir reden von CP/M und Disketten, dann wäre das Programm
schon außergewöhnlich schnell :)


Stefan

[Jörg "Yadgar" Bleimann]

Hi(gh)!

On 22.02.2017 19:07, Stefan Reuther wrote:
> Am 22.02.2017 um 16:29 schrieb Jörg "Yadgar" Bleimann:

> Dann könntest du schon einen Gewinn daraus ziehen, dass du diese Klasse
> von "drei unsigned char" auf "ein uint32_t" umbaust. "get_red" ist dann
> "return (pixel >> 16)", "set_red" ist "pixel = (pixel & 0x00FFFF) |
> (value << 16)", und so weiter.

Wieso uint32_t und nicht einfach unsigned int - ist doch üblicherweise
auch 4 Byte groß!

>>> Pixel
>>> werden dann nach Möglichkeit nicht in einer Klasse dargestellt, sondern
>>> in einem Datentyp, der es erlaubt, die SIMD-Instruktionen
>>
>> SIMD? Kann das mein Hexacore?
>
> Das kann sogar ein 20 Jahre alter Pentium MMX.
>
> SIMD ist der Oberbegriff für MMX, SSE, AltiVec, NEON, und wie das alles
> heißt. Voraussetzung dafür ist aber meistens speziell geschriebener Code
> und die Verwendung spezieller Datentypen, und dann kann der Prozessor
> halt in einem Zyklus 8 Integer auf einmal addieren.

Wenn Klassen das Programm ausbremsen, wäre es dann nicht besser, das
alles in reinem C zu schreiben? Um die Speicherverwaltung müsste ich
mich dann zwar selbst kümmern, aber C dürfte doch immer noch schneller
sein als selbst C++ ohne Klassen, oder?

> Allerdings: wenn dein "Hauptverkaufsargument" nicht hochoptimierte
> Grafikalgorithmen sind, ist das alles nicht nötig. Meine
> Grafikspielereien arbeiten auch nur mit ganz normalem C++ (also ohne
> SIMD, ohne Assembler) und waren schon auf 200 MHz schnell genug, um
> damit eine passable GUI zu bauen.

Also, längstfristig (so bis 2050) träume ich ja von YIP als GIMP- und
ImageMagick-Killer... mit einem Schwerpunkt auf Steuerbarkeit von
Konsole, ohne vorher erst noch Python oder gar Scheme lernen zu müssen
(wie es bei GIMP ja leider der Fall ist)!

[Stefan Reuther]

Am 22.03.2017 um 02:23 schrieb Jörg "Yadgar" Bleimann:
> On 22.02.2017 19:07, Stefan Reuther wrote:
>> Am 22.02.2017 um 16:29 schrieb Jörg "Yadgar" Bleimann:
>> Dann könntest du schon einen Gewinn daraus ziehen, dass du diese Klasse
>> von "drei unsigned char" auf "ein uint32_t" umbaust. "get_red" ist dann
>> "return (pixel >> 16)", "set_red" ist "pixel = (pixel & 0x00FFFF) |
>> (value << 16)", und so weiter.
>
> Wieso uint32_t und nicht einfach unsigned int - ist doch üblicherweise
> auch 4 Byte groß!

Während der 'unsigned int' heutzutage *üblicherweise* 4 Byte a 8 Bit
groß ist, ist der uint32_t *immer* (sofern er denn existiert) 32 Bit
groß. In sehr vielen Fällen ist daher uint32_t die bessere Wahl.

Einen Compiler, in dem 'unsigned int' 2 Byte a 8 Bit groß ist, und einen
Compiler, in dem 'unsigned int' 1 Byte a 24 Bit groß ist, kann ich noch
mühelos auftreiben (zugegebenermaßen nicht nach neuestem Sprachstandard).

>>>> Pixel
>>>> werden dann nach Möglichkeit nicht in einer Klasse dargestellt, sondern
>>>> in einem Datentyp, der es erlaubt, die SIMD-Instruktionen
>>>
>>> SIMD? Kann das mein Hexacore?
>>
>> Das kann sogar ein 20 Jahre alter Pentium MMX.
>>
>> SIMD ist der Oberbegriff für MMX, SSE, AltiVec, NEON, und wie das alles
>> heißt. Voraussetzung dafür ist aber meistens speziell geschriebener Code
>> und die Verwendung spezieller Datentypen, und dann kann der Prozessor
>> halt in einem Zyklus 8 Integer auf einmal addieren.
>
> Wenn Klassen das Programm ausbremsen, wäre es dann nicht besser, das
> alles in reinem C zu schreiben? Um die Speicherverwaltung müsste ich
> mich dann zwar selbst kümmern, aber C dürfte doch immer noch schneller
> sein als selbst C++ ohne Klassen, oder?

Man kann C++ so schreiben, dass es so effizient wie C ist. Und vor
allem: man kann das so tun, dass es deutlich weniger Mühe macht als in C.

Ein Programm, das die Farbkomponenten per Funktionsaufruf aus einer
Struktur holt, ist in C genauso ineffizient wie in C++. Eine Klasse, die
einen uint32_t mit ein paar Inline-Methoden dekoriert, ist hingegen
genauso schnell wie ein Sack C-Makros, der das gleiche tut.


Stefan