Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Auch die Ausgabe des Assembler Quellcodes vergrößert sich dadurch. Bei meinem Test gestern von ca. 17kB auf über 60kB. Und gerade habe ich noch etwas interessantes entdeckt:
.LBB4:
.loc 2 71 0
cmpl $0, -104(%rbp)
jg .L26
.loc 2 71 0 is_stmt 0 discriminator 1
cmpl $0, -100(%rbp)
jle .L27
.L26:
.LBB5:
.LBB6:
.loc 2 72 0 is_stmt 1
movl -84(%rbp), %eax
movl %eax, -140(%rbp)
...
Die 71 und 72 im Pseudokommando .loc scheinen die Zeilennummern aus der Originaldatei zu sein. Bei mir passt das jedenfalls. Das sind genau diese beiden Zeilen.
if (left > 0 || right > 0) // in case skip for performance
for (int y = top2; y < bottom2; y += lz) {
...
|
UlfZibis
(Themenstarter)
Anmeldungsdatum: 13. Juli 2011
Beiträge: 3023
Wohnort: Köln
|
Dakuan schrieb: Ich hänge mal die kompletten an, in logischer und linearer Ordnung.
Welche Logik dahinter steckt, kann ich noch nicht erkennen.
In der linearen Ordnung mittels Option /s ist nicht so leicht zu erkennen, wie viele und welche Maschinenbefehle zu einer C-Anweisung gehören, da der GCC "re-ordered code" produziert, um die CPU-interne Pipeline effektiver zu nutzen. Von den Speicheradressen geht das ziemlich durcheinander.
Das betrifft die "logische" Anordnung mittels Option /m. Dafür kann man da auf einen Blick erkennen, welche Maschinenbefehle zu einer C-Anweisung gehören, allerdings wird dabei leider das Drumherum um den memcpy() -Aufruf verschluckt. Sonst finde ich die Anordnung für meine Zwecke aber praktischer. Da sieht man dann z.B. sehr schön, dass das Kompilat der beiden for -Anweisungen aus C-Zeile 186 und 187 von Version p15 viel umfangreicher als das von Version p14 ist. Das könnte doch durchaus die Verlangsamung um 20 % bewirken. Aber der fehlende Block, der zur Abfrage gehört ist da.
Du meinst den Block von +150 - +464 (der eigentlich keiner ist, da in sich auch sehr "code-reordered")? Der gehört aber eben nicht zu der if -Abfrage, sondern zu anderen C-Anweisungen.
Das sind allerdings nur 11 zusätzliche Befehle. Die können nicht so lange dauern.
Insgesamt ja, entscheidend wird aber wohl sein, wie oft welche Befehle durchlaufen werden. was vor allem die innere for -Schleife aus C-Zeile 187 betrifft, aber auch die äußere aus 186 wird für jede der 600 Bildzeilen einmal durchlaufen. Man könnte fast den Eindruck haben, das der Optimierer komplett ausgeschaltet ist, oder irgendetwas ihm ein Bein gestellt hat. Jedenfalls ist der Stackframe anders organisiert.
Ich würde sagen, mehrere Optimierungsstrategien laufen da gegeneinander um die Wette und das Gesamtergebnis ist dann nicht immer optimal und leider von vielen zufälligen nicht determinierbaren Faktoren abhängig.
Ich spekuliere jetzt mal, da ich nur eine dunkle Vorstellung davon habe, wie ein Optimierer arbeitet. Die Abfrage der Bedingung könnte verhindern, das eine der Variablen temporär in einem Register gespeichert werden kann, weil dieses zwischenzeitlich nochmal gebraucht wird. Ist jetzt allerdings sehr weit hergeholt. Aber mehr fällt mir dazu momentan nicht ein.
Das könnte einer der Gründe sein, sicher spielt aber auch die "versuchte" Pipeline-Optimierung durch das "code-reordering" eine große Rolle. Allerdings erscheinen mir 20% langsamer sehr viel. Wie hast du das ermittelt?
Hier beschrieben!
Ich habe in das MAKEFILE noch nicht reingeguckt, aber ich gehe davon aus, dass da komplizierte Compiler-Optionen gesetzt werden.
Was die Möglichkeiten von make betrifft bin ich zwar auch noch in der Vorschulklasse, aber so kompliziert sollte das nicht sein. Meist werden die Optionen in irgendwelche Variablen verpackt, oder von Scripts eingebunden. Ich glaube nicht, das da irgendetwas bei ist, was dich interessiert, es sei denn, da sind unübliche Include Pfade ...
Ich auch. Was soll es nützen, das zu verstehen zu versuchen? Ich muss sie sowieso so nehmen, wie sie sind. Dakuan schrieb: Anmerkung: Bei Bildern mit feinen Strukturen in den Ecken fällt auf, das die horizontalen Balken bevorzugt werden. Es wäre schöner, wenn der Übergangsbereich diagonal verliefe, also wie bei einem Bilderrahmen.
Das wäre sicher auch ganz hübsch, ist aber sicher komplizierter zu implementieren. Wäre was für eine zusätzliche Option: "mirror_nice". Kannst Dich ja mal ranmachen, das zu kodieren und dem FFmpeg-Team als Patch vorschlagen. Dabei wirst Du dann (hoffentlich) bemerken, dass meine Patches nicht nur zur Performance, sondern auch erheblich zur Vereinfachung beitragen würden. Hier geht der Thread los: https://ffmpeg.org/pipermail/ffmpeg-devel/2019-March/240975.html
|
UlfZibis
(Themenstarter)
Anmeldungsdatum: 13. Juli 2011
Beiträge: 3023
Wohnort: Köln
|
rklm schrieb: Ja, dann führst Du make einfach mit "--dry-run" oder "-d" aus, fischt die tatsächliche Kommandozeile aus der Ausgabe und fügst die Option "-S" hinzu.
Hm, welchen Vorteil soll das bringen? gegenüber: (gdb) file ffmpeg_g
Reading symbols from ffmpeg_g...fertig.
(gdb) disas /m mirror_borders16
Dump of assembler code for function mirror_borders16:
201 {
0x000000000020047b <+11>: push %r15
0x000000000020047d <+13>: push %r14
0x000000000020047f <+15>: mov %rdi,%rax
[.....]
Außerdem würde es mich nicht wundern, wenn in dem komplizierten FFmpeg-Projekt für verschiedene Bereiche auch noch unterschiedliche Compiler-Optionen gesetzt werden. -d steht übrigens für -debug , nicht --dry-run . Hab' die Zeile mal aus der 1,7 MByte langen Ausgabe herausgefischt:
printf "CC\t%s\n" libavfilter/vf_fillborders.o; gcc -I. -I./ -D_ISOC99_SOURCE -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -D_POSIX_C_SOURCE=200112 -D_XOPEN_SOURCE=600 -DPIC -DZLIB_CONST -DHAVE_AV_CONFIG_H -DBUILDING_avfilter -std=c11 -fomit-frame-pointer -fPIC -pthread -g -Wdeclaration-after-statement -Wall -Wdisabled-optimization -Wpointer-arith -Wredundant-decls -Wwrite-strings -Wtype-limits -Wundef -Wmissing-prototypes -Wno-pointer-to-int-cast -Wstrict-prototypes -Wempty-body -Wno-parentheses -Wno-switch -Wno-format-zero-length -Wno-pointer-sign -Wno-unused-const-variable -Wno-bool-operation -Wno-char-subscripts -O3 -fno-math-errno -fno-signed-zeros -fno-tree-vectorize -Werror=format-security -Werror=implicit-function-declaration -Werror=missing-prototypes -Werror=return-type -Werror=vla -Wformat -fdiagnostics-color=auto -Wno-maybe-uninitialized -MMD -MF libavfilter/vf_fillborders.d -MT libavfilter/vf_fillborders.o -c -o libavfilter/vf_fillborders.o libavfilter/vf_fillborders.c Dakuan schrieb: Auch die Ausgabe des Assembler Quellcodes vergrößert sich dadurch. Bei meinem Test gestern von ca. 17kB auf über 60kB.
Heißt das, dass da mehr Details drin stehen? In Deinem Auszug kann ich das allerdings nicht erkennen.
Die 71 und 72 im Pseudokommando .loc scheinen die Zeilennummern aus der Originaldatei zu sein. Bei mir passt das jedenfalls. Das sind genau diese beiden Zeilen.
Sehe ich auch so. Mir gefällt die Ausgabe von (gdb) disas /m mirror_borders16 aber besser. MisterIgo schrieb: FFmpeg macht das automatisch beim Kompilieren, um die ffmpeg_g zu erzeugen und strippt dann die Debuginformationen weg um ffmpeg zu erzeugen. Das ganze scheint man über configure steuern zu können.
Genau, und deshalb setze ich den gbd doch gleich darauf zum Disassemblieren an.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12801
|
UlfZibis schrieb: rklm schrieb: Ja, dann führst Du make einfach mit "--dry-run" oder "-d" aus, fischt die tatsächliche Kommandozeile aus der Ausgabe und fügst die Option "-S" hinzu.
Hm, welchen Vorteil soll das bringen? gegenüber:
Probier es halt aus. Ist ja nicht so viel Aufwand und Du möchtest etwas herausfinden, oder?
Außerdem würde es mich nicht wundern, wenn in dem komplizierten FFmpeg-Projekt für verschiedene Bereiche auch noch unterschiedliche Compiler-Optionen gesetzt werden.
Deshalb ja die Empfehlung, die Optionen der entsprechenden Quelle aus einem tatsächlichen Compilierprozess zu extrahieren.
-d steht übrigens für -debug , nicht --dry-run .
Habe ich auch nie behauptet. Es gibt halt zwei Möglichkeiten, an die Kommandozeile zu kommen.
Hab' die Zeile mal aus der 1,7 MByte langen Ausgabe herausgefischt: printf "CC\t%s\n" libavfilter/vf_fillborders.o; gcc -I. -I./ -D_ISOC99_SOURCE -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -D_POSIX_C_SOURCE=200112 -D_XOPEN_SOURCE=600 -DPIC -DZLIB_CONST -DHAVE_AV_CONFIG_H -DBUILDING_avfilter -std=c11 -fomit-frame-pointer -fPIC -pthread -g -Wdeclaration-after-statement -Wall -Wdisabled-optimization -Wpointer-arith -Wredundant-decls -Wwrite-strings -Wtype-limits -Wundef -Wmissing-prototypes -Wno-pointer-to-int-cast -Wstrict-prototypes -Wempty-body -Wno-parentheses -Wno-switch -Wno-format-zero-length -Wno-pointer-sign -Wno-unused-const-variable -Wno-bool-operation -Wno-char-subscripts -O3 -fno-math-errno -fno-signed-zeros -fno-tree-vectorize -Werror=format-security -Werror=implicit-function-declaration -Werror=missing-prototypes -Werror=return-type -Werror=vla -Wformat -fdiagnostics-color=auto -Wno-maybe-uninitialized -MMD -MF libavfilter/vf_fillborders.d -MT libavfilter/vf_fillborders.o -c -o libavfilter/vf_fillborders.o libavfilter/vf_fillborders.c
Hübsch.
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Das betrifft die "logische" Anordnung mittels Option /m. ...
Ah, jetzt erkenne ich den Unterschied der Listings. Und langsam bekomme ich auch eine dunkle Vorstellung davon was da passiert sein könnte. Ist aber auch nur eine Spekulation. Aus der Zeile
if (left > 0 || right > 0) // in case skip for performance
könnte man schließen, dass dieser Fall selten eintrifft. Daher wurden die Anweisungsblöcke so umsortiert, das der nachfolgende (häufigere) Fall, ohne Sprungbefehl direkt ausgeführt werden kann. Der (angenommen) weniger häufige Fall wurde ans Ende sortiert und ist nur über einen Sprung erreichbar. Sollte dieser Block benötigt werden ist dann leider auch ein Rücksprung erforderlich. Aber das ist nur eine Vermutung. Da aber die Ränder sowieso unabhängig voneinander sind, könntest du diese Behandlung der Seitenränder auch ans Ende der Funktion legen und mal gucken was der Compiler daraus macht.
Ich würde sagen, mehrere Optimierungsstrategien laufen da gegeneinander um die Wette ...
Das glaube ich eher weniger. Ich hatte mich ganz früher mal mit Small-C und da speziell mit dem Code Generator und dem Peephole optimizer beschäftigt. Wenn ich das richtig erinnere, gibt es nur einen Optimierer, der allerdings unterschiedliche Prioiritäten vorgegeben bekommen kann (Speed, Speicherplatz, ...).
Das wäre sicher auch ganz hübsch, ist aber sicher komplizierter zu implementieren. Wäre was für eine zusätzliche Option: "mirror_nice". Kannst Dich ja mal ranmachen, das zu kodieren und dem FFmpeg-Team als Patch vorschlagen.
Das geht leider nicht so ohne weiteres. Ich könnte das in meinem bisherigen Umfeld nicht testen, da alle meine Tools die Farbkanäle linear hintereinander in einem Array erwarten. Das erfordert eine andere Struktur der Schleifen. Außerdem bin ich bei meinen bisherigen Überlegungen dazu davon aus gegangen, dass alle Ränder gleich breit sind.
Heißt das, dass da mehr Details drin stehen? In Deinem Auszug kann ich das allerdings nicht erkennen.
Nein, aber man kann die Zuordnung zu den Zeilen erkennen. Das bezog sich auf
gcc -g -S DATEINAME
Als ich das geschrieben habe, war mir das lineare Format der *.ass Dateien noch nicht klar. Das ist natürlich schöner, weil da die originale Zeile mit enthalten ist.
|
UlfZibis
(Themenstarter)
Anmeldungsdatum: 13. Juli 2011
Beiträge: 3023
Wohnort: Köln
|
Dakuan schrieb: Ist aber auch nur eine Spekulation. Aus der Zeile
if (left > 0 || right > 0) // in case skip for performance
könnte man schließen, dass dieser Fall selten eintrifft. ...
Könnte man, der Compiler schließt an verschiedenen Stellen aber unterschiedlich, wie es ihm gerade passt ... die Logik dahinter kann ich nicht erkennen. Allerdings dürfte es für die Gesamtperformance ziemlich egal sein, ob da einmal gesprungen wird oder nicht. Die Anzahl der Anweisungen und Sprünge in den vielfach durchlaufenen for -Schleifen dürfte da entscheidender sein.
Da aber die Ränder sowieso unabhängig voneinander sind, könntest du diese Behandlung der Seitenränder auch ans Ende der Funktion legen und mal gucken was der Compiler daraus macht.
Hatte ich auch schon mal gedacht ... aber wie oben schon gesagt, sollte das nicht viel Unterschied machen.
Ich würde sagen, mehrere Optimierungsstrategien laufen da gegeneinander um die Wette ...
Das glaube ich eher weniger. Ich hatte mich ganz früher mal mit Small-C und da speziell mit dem Code Generator und dem Peephole optimizer beschäftigt. Wenn ich das richtig erinnere, gibt es nur einen Optimierer, der allerdings unterschiedliche Prioiritäten ...
Was doch soviel heißt, wie unterschiedliche Strategien. Außerdem gab's da bestimmt keinen umordnenden Pipline-Optimierer, was die Sache nochmal komplizierter macht. Du siehst ja in dem von mir aus dem make herausgezogenen Befehl, wie viele Kombinationen von Optionen da möglich sind.
Das wäre sicher auch ganz hübsch, ist aber sicher komplizierter zu implementieren. Wäre was für eine zusätzliche Option: "mirror_nice". Kannst Dich ja mal ranmachen, das zu kodieren und dem FFmpeg-Team als Patch vorschlagen.
Das geht leider nicht so ohne weiteres. Ich könnte das in meinem bisherigen Umfeld nicht testen, da alle meine Tools die Farbkanäle linear hintereinander in einem Array erwarten. Das erfordert eine andere Struktur der Schleifen.
Der Algorithmus für die Spiegelung an der Diagonalen dürfte doch immer der gleiche sein, egal wie die Farbkanäle angeordnet sind. Außerdem bin ich bei meinen bisherigen Überlegungen dazu davon aus gegangen, dass alle Ränder gleich breit sind.
Wenn sie unterschiedlich breit sind, müsste die Trennung dann eben im passenden Winkel erfolgen, also nicht 45 °.
Das ist natürlich schöner, weil da die originale Zeile mit enthalten ist.
Da meine ich eben auch. Und noch schöner ist da die Nutzung von ddd. Ich hab' mir da 2 Custom-Knöpfe angelegt für disas /m mirror_borders16 und disas /s mirror_borders16 . Ich hab' jetzt mal die Zeile | if (left > 0 || right < width) // in case skip for performance
|
durch | if (left + width > right) // in case skip for performance
|
ersetzt, das spart einen Sprungbefehl. Und wieder macht der Compiler mit dem nachfolgenden Code, was er will, also in einigen Fällen ergibt sich eine Beschleunigung und in anderen eine Verlangsamung um bis zu 20 %. Hab' mich dann in p16 für die jeweils schnellste Variante entschieden, siehe Anhänge.
- Benchmarks.zip (12.0 KiB)
- Download Benchmarks.zip
- vf_fillborders.zip (7.2 KiB)
- Download vf_fillborders.zip
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Du siehst ja in dem von mir aus dem make herausgezogenen Befehl, wie viele Kombinationen von Optionen da möglich sind.
Ich glaube, das meiste davon betrifft deinen Code nicht. Möglicherweise könnte man das auf -g und -O3 reduzieren.
Der Algorithmus für die Spiegelung an der Diagonalen dürfte doch immer der gleiche sein, egal wie die Farbkanäle angeordnet sind.
Der Algorithmus ja, aber die Umsetzung nicht. In deinem Fall werden die Farbebenen in der äußeren Schleife durchlaufen, bei mir in der innersten. Das zu ändern ist nicht schwierig, aber man braucht dafür eine Testumgebung. Ich bin schon bei kleineren Umstellungen auf die Nase gefallen.
Wenn sie unterschiedlich breit sind, müsste die Trennung dann eben im passenden Winkel erfolgen, also nicht 45 °.
Das würde ich mir nicht antun wollen. Einen 45° Winkel kann man über Zähler realisieren. Aber bei anderen Winkeln könnte das auf Bresenham oder Bilineare-Interpolation hinauslaufen. Letzteres ist richtig langsam. Das neue Ergebnis schaue ich mir nachher mal an. Ich muss gleich nochmal weg.
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Ich sehe gerade dass du die Anzahl der Rechenoperationen bei den Arrayzugriffen verringern konntest. Darüber hatte ich auch schon nachgedacht, aber ohne Ergebnis. Wenn du noch weiter experimentieren willst, hätte ich noch 2 Ideen. Einmal könnte man die Abfragen für left und right einzeln direkt vor die betreffenden Schleifen stellen. Das würde alledings bedeuten dass man
for (int y = top2; y < bottom2; y += lz) {
nochmal wiederholen muss. Die andere Idee ist, die senkrechten Ränder spaltenweise zu erzeugen. Die Idee dahinter ist, das die Schleifendurchläufe dann länger sind und weniger häufig gesprungen werden muss. Und meine Idee mit den "nice-borders" sollten wir wieder vergessen. Das funktioniert nicht gut, wenn man "in-place" arbeiten muss, da es immer wieder passiert, das man auf Pixelwerte zugreifen muss, die vorher schon verändert wurden. Mann könnte sich zwar, quasi im Kreis, von außen nach innen vorarbeiten, aber ich glaube nicht, dass sich der Aufwand lohnt. Die meisten Leute werden den feinen Unterschied wahrscheinlich nicht bemerken.
|
UlfZibis
(Themenstarter)
Anmeldungsdatum: 13. Juli 2011
Beiträge: 3023
Wohnort: Köln
|
Dakuan schrieb: Ich sehe gerade dass du die Anzahl der Rechenoperationen bei den Arrayzugriffen verringern konntest. Darüber hatte ich auch schon nachgedacht, aber ohne Ergebnis.
Es ginge sogar noch mehr, z.B. mit | for (int y = top; y < bottom; y += lz) {
for (int x = y + left, x2 = x; x > y; )
data[--x] = data[x2++];
// oder:
for (uint16_t *y = data + top, *y2 = y; y > data; y2 += lz)
memcpy(y -= lz, y2, width * sizeof(uint16_t));
|
doch hat sich das als langsamer herausgestellt.
Wenn du noch weiter experimentieren willst, hätte ich noch 2 Ideen. Einmal könnte man die Abfragen für left und right einzeln direkt vor die betreffenden Schleifen stellen. Das würde allerdings bedeuten, dass man
for (int y = top2; y < bottom2; y += lz) {
nochmal wiederholen muss.
Du meinst Innen- mit Außenschleife vertauschen, ja das würde dann | if (left > 0 || right < width) // in case skip for performance
|
überflüssig machen. Das würde allerdings bedeuten, dass man den Speicher in +lz statt +1-Sprüngen bearbeitet. Letzteres kann der Compiler sicher besser optimieren.
Die andere Idee ist, die senkrechten Ränder spaltenweise zu erzeugen. Die Idee dahinter ist, das die Schleifendurchläufe dann länger sind und weniger häufig gesprungen werden muss.
Ich verstehe nicht, warum das weniger Sprünge werden sollten, denn beim Übergang in die nächste Spalte müsste ich doch den Index mittels if -Abfrage (was auch einen Sprung bedeutet) wieder zurücksetzen. (ginge vielleicht auch mit einer Modulo-Division, die aber auch Zeit kostet, bleibt aber immer noch, dass +lz gegenüber +1-Inkrementen teurer sind.) Was ich interessant fände wäre eine memset() -Funktion, die mit 16-Bit-Werten arbeitet. Dann könnte ich manche Array-Einzelzugriffe dadurch ersetzen. Gibt es so was in der großen C-Bibliothek, und ich hab's noch nicht gefunden?
Und meine Idee mit den "nice-borders" sollten wir wieder vergessen. Das funktioniert nicht gut, wenn man "in-place" arbeiten muss, da es immer wieder passiert, das man auf Pixelwerte zugreifen muss, die vorher schon verändert wurden.
Warum? Man füllt zuerst die je 2 Dreiecke in den Ecken, und dann die Randabschnitte zwischen den Ecken.
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Ich verstehe nicht, warum das weniger Sprünge werden sollten, denn beim Übergang in die nächste Spalte müsste ich doch den Index mittels if-Abfrage (was auch einen Sprung bedeutet) wieder zurücksetzen.
Vielleicht liege ich mit meiner Milchmädchenrechnung ja falsch. Der Gedankengang ist folgender. Die Anzahl der Speicherzugriffe und Abfragen ist gleich. Bei einer Bildhöhe von 100 px und einer Randbreite von 20 px ergibt das 20 auszuführende Sprünge bei vertikaler Abarbeitung. Bei horizontaler Abarbeitung komme ich auf 20x100 (oder sollte ich da wieder mal einen Knick in der Logik haben?). Eine IF-Abfrage führt nur dann zu einem Sprung, wenn die Bedingung zutrifft.
(ginge vielleicht auch mit einer Modulo-Division, ...
So etwas versuche ich immer zu vermeiden. Ich finde das aber immer wieder, wenn es im Bereich digitaler Signalverarbeitung um den eigentlich immer benötigten Ringpuffer geht. Aber das ist in meinen Augen Blödsinn (obwohl mathematisch korrekt), denn man kann das gleiche Ergebnis oft durch einen einfachen Zähler erreichen. Nach meinem Kenntnisstand bedeutet "Modulo" immer das eine Division tatsächlich durchgeführt werden muss.
Was ich interessant fände wäre eine memset()-Funktion, die mit 16-Bit-Werten arbeitet.
Was hinder dich daran so eine memset16() oder auch mencpy16() Funktion selber zu bauen, oder noch besser den Code direkt in deine Funktion einzubauen, quasi wie ein Makro. Du würdest dann auch noch den Overhead, der durch die Parameterübergabe auf dem Stack entsteht, einsparen. Das sollte mit 10 Zeilen machbar sein (habe ich jetzt aber nicht geprüft).
Warum? Man füllt zuerst die je 2 Dreiecke in den Ecken, und dann die Randabschnitte zwischen den Ecken.
Muss ich nochmal drauf nachdenken. Aber mit unterschiedlich breiten Rändern kann ich mich immer noch nicht anfreunden. Ich muss das mal in meiner Anwendung ausprobieren. Aber ich bin in meinem Zeitplan wieder mal im Rückstand, weil ich mich wieder mal mit einem Bug Report aus dem Fenster gelehnt hatte und dabei auch bei der Lösung eingespannt wurde. Nachtrag: Ich bin zwar gerade von TV abgelenkt, aber hoffe das der nebenbei eingetippte Code in der Nähe der Wahrheit liegt (nicht getestet!):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | /*
**
*/
void *
memcpy16( void* to, void* from, int n ) {
int16_t * d = (int16_t*)to;
int16_t * s = (int16_t*)s;
for( int i = 0; i < n; ++i ) {
*d++ = *s++;
}
return to;
}
/* entspricht nicht ganz der Konvention wg. kein Rückgabewert */
void
memset16( int16_t * to, int16_t val, int num ) {
for( int i = 0; i < num, ++i )
*to++ = val;
}
|
Vielleicht hilft es ja.
|
UlfZibis
(Themenstarter)
Anmeldungsdatum: 13. Juli 2011
Beiträge: 3023
Wohnort: Köln
|
Dakuan schrieb: Vielleicht liege ich mit meiner Milchmädchenrechnung ja falsch.
Ich denke schon 😲 Der Gedankengang ist folgender. Die Anzahl der Speicherzugriffe und Abfragen ist gleich. Bei einer Bildhöhe von 100 px und einer Randbreite von 20 px ergibt das 20 auszuführende Sprünge bei vertikaler Abarbeitung.
Aber in der Spalte hast Du dann doch auch wieder eine for -Schleife die in 100 Sprüngen à +lz abläuft. Ich würde sogar sagen, dass Dein Vorschlag eher bei horizontaler Abarbeitung, z.B. mit for (x = 0; x < top*lz; x++) data[x] = fill; , anwendbar wäre, wenn da nicht das Problem wäre, dass lz=width" hier nur höchstens dann gilt, wenn witdh durch 16 teilbar ist.
Eine IF-Abfrage führt nur dann zu einem Sprung, wenn die Bedingung zutrifft.
Die trifft aber bei jedem Spaltenwechsel, also 20 mal zu.
(ginge vielleicht auch mit einer Modulo-Division, ...
So etwas versuche ich immer zu vermeiden. Ich finde das aber immer wieder, wenn es im Bereich digitaler Signalverarbeitung um den eigentlich immer benötigten Ringpuffer geht. Aber das ist in meinen Augen Blödsinn (obwohl mathematisch korrekt), denn man kann das gleiche Ergebnis oft durch einen einfachen Zähler erreichen.
Ja, aber immer wenn der Zähler seinen Endwert erreicht hat, muss ein if - oder for -Sprung für dessen Rücksetzung sorgen. Modulo besorgt das "mathematisch" ohne Sprung. Nach meinem Kenntnisstand bedeutet "Modulo" immer das eine Division tatsächlich durchgeführt werden muss.
Die ist bei Division durch Potenzen von 2 ziemlich billig, auch auch für krumme Zahlen sind heutige CPUs da ganz schon schnell.
Was ich interessant fände wäre eine memset()-Funktion, die mit 16-Bit-Werten arbeitet.
Was hinder dich daran so eine memset16() oder auch mencpy16() Funktion selber zu bauen, oder noch besser den Code direkt in deine Funktion einzubauen, quasi wie ein Makro. Du würdest dann auch noch den Overhead, der durch die Parameterübergabe auf dem Stack entsteht, einsparen. Das sollte mit 10 Zeilen machbar sein (habe ich jetzt aber nicht geprüft).
memcpy16() macht keinen Sinn, da reicht es einfach width*2 in menmpy() einzusetzen. memset() ist ja deshalb schneller, als eine entsprechende for -Schleife, weil dahinter ein Maschinen-Befehl steckt, der in einem Rutsch den ganzen Bereich mit dem fill-Byte füllt. Wenn ich es richtig in Erinnerung habe, gibt es so einen Maschinenbefehl auch für 16- oder zumindest für 32-Bit fill-Werte. So eine selbstgebastelte Funktion unter Verwendung von for würde dem aber genauso wenig dienen, wie die jetzigen for -Schleifen.
Warum? Man füllt zuerst die je 2 Dreiecke in den Ecken, und dann die Randabschnitte zwischen den Ecken.
Muss ich nochmal drauf nachdenken. Aber mit unterschiedlich breiten Rändern kann ich mich immer noch nicht anfreunden. Ich muss das mal in meiner Anwendung ausprobieren. Aber ich bin in meinem Zeitplan wieder mal im Rückstand, weil ich mich wieder mal mit einem Bug Report aus dem Fenster gelehnt hatte und dabei auch bei der Lösung eingespannt wurde.
Das Problem kenne ich gut, guck' mal: https://netbeans.org/bugzilla/buglist.cgi?bug_status=UNCONFIRMED&bug_status=NEW&bug_status=STARTED&bug_status=REOPENED&bug_status=RESOLVED&bug_status=VERIFIED&bug_status=CLOSED&columnlist=product%2Ccomponent%2Cassigned_to%2Cbug_status%2Cresolution%2Cshort_desc%2Cchangeddate%2Creporter&email1=ulfzibis&emailassigned_to1=1&emailcc1=1&emaillongdesc1=1&emailqa_contact1=1&emailreporter1=1&emailtype1=substring&query_based_on=&query_format=advanced oder: https://markmail.org/search/?q=list%3Anet.java.openjdk#query:list%3Anet.java.openjdk+page:1+state:facets und dann unten links bei "Who send it" auf view more klicken, da findest Du mich ungefähr auf Position 66. Vor 10 Jahren war ich da noch unter den ersten 10. oder: https://netbeans.org/community/articles/interviews/netcat68-ulf-zibis.html
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Ob eine andere Anordnung etwas bringt, sehe ich immer erst, wenn ich es tatsächlich eingetippt habe. Ich hatte mal bei einer Funktion (ich glaube es war kippen) festgestellt, das es einen Unterschied macht, ob das Ausgangsbild im Hoch- oder Querformat vorliegt. Habe das aber nicht weiter untersucht. Modulo: Die ist bei Division durch Potenzen von 2 ziemlich billig, auch auch für krumme Zahlen sind heutige CPUs da ganz schon schnell.
Ich habe da immer Signalprozessoren im Hinterkopf, die oft nichtmal eine FPU haben. Wie schnell das bei einer normalen CPU geht, muss ich mal messen/vergleichen.
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Das mit dem Modulo Operator kaufe ich dir noch nicht ab. Ich habe das gerade mal ausprobiert. Zumindest so wie ich es implementiert habe, ergibt das eine deutliche Verschlechterung. Ich hoffe das ich da nicht wieder mal einen kapitalen Bock geschossen habe. Daher zeige ich mal den Code, mit dem ich getestet habe, damit du beurteilen kannst, ob ich da was falsch gemacht habe:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | // Run an FIR filter in direct form 2
double
F_fir_df2::run( double in_val ) {
int it; // tap (reg) index
int ib; // b coefficient index
double sum;
inbuf[ix++] = in_val; // store input and advance index to oldest sample
//if( ix >= num_taps ) // buffer is a circular buffer
// ix = 0;
ix = ix%num_taps; // speed test
sum = 0.0;
it = ix;
for( ib = 0; ib < num_taps; ib++ ) {
sum += b[ib] * inbuf[it++];
//if( it == num_taps )
// it = 0;
it = it%num_taps; // speed test 2
}
return sum;
}
|
Dabei ist zu berücksichtigen, das der Code unbegrenzt lange laufen könnte, also ein Zähler auch überlaufen könnte. Die Modulo Version dauert fast 3 Mal so lange. Getestet habe ich mit ca. 3.5 Mio durchläufen. Der Ringpuffer war dabei 255 Einträge lang. Bei jedem Aufruf wird die innere Schleife einmal komplett durchlaufen, d.h. der Überlauf findet immer 1 Mal statt, bei normaler Audio Anwendung also z.B. 44100 Mal pro Sekunde. Dagegen erscheinen mir deine Laufzeitprobleme fast vernachlässigbar <kein passenden Smily gefunden>.
|
UlfZibis
(Themenstarter)
Anmeldungsdatum: 13. Juli 2011
Beiträge: 3023
Wohnort: Köln
|
Dakuan schrieb: Das mit dem Modulo Operator kaufe ich dir noch nicht ab. Ich habe das gerade mal ausprobiert. Zumindest so wie ich es implementiert habe, ergibt das eine deutliche Verschlechterung. Ich hoffe das ich da nicht wieder mal einen kapitalen Bock geschossen habe.
Ist num_taps eine Variable, oder eine Konstante? Was passiert denn mit const int num_taps = 128 ? (oder ein anderer beliebiger Wert) Wenn num_taps keine Potenz von 2 ist, kann die Division evtl. trotzdem länger brauchen als die if -Abfrage. Und ansonsten habe ich wohl den Bock geschossen 👿
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6339
Wohnort: Hamburg
|
Bei dem gezeigten Code handelt es sich um das ausführende Organ eines FIR-Filters. Das muss die Daten so abarbeiten wie sie sind. num_taps ist dabei die Anzahl der benötigten Speicherplatze (Taps) und gleichzeitig auch die Anzahl der Filterkoeffizienten im b[]-Array. Diese Daten werden von einem externen Programm vorgegeben. Die hohe Anzahl der Schleifendurchläufe ist in diesem Fall durch das Messverfahren bedingt und weil ich die Anzahl der Messungen pro Frequenz absichtlich hochgedreht habe. Ich hatte Angst, das der Unterschied sonst zu gering ausfällt. Eigentlich habe ich den Test ausgeführt um sicher zu gehen. Ich ich habe da schonmal danebengelegen, weil mir niemand erzählt hatte das heutige CPUs inzwischen Barrel-Shifter haben. Hätte ja sein können, dass ich auch hier wieder etwas nicht mitgekriegt habe. Den Assembler Output habe ich mir auch angesehen. Da taucht doch tatsächlich
idivl %ecx
auf.
|