Kopie Funktion

[tuxie]

Hallo,

ich habe hier eine Sauber funktionierende Funktion zum Kopieren von Pixeln, doch diese Läuft sehr unsauber bzw. erzeugt beim Kompilieren keinen Optimalen Code was zur Folge hat das das Kopieren sehr lange dauert. Mit Assembler haben wir diese um das 5 Fache beschleunigen können. Aber das Ziel ist diese in C zu lassen da sie an mehreren stellen Verwendung findet.

Gegebenheiten !
Unbestimmte Anzahl an Zeilen
Unbestimmte Anzahl an Pixeln pro Zeile
32Bit Kopieren ist möglich. (Pointer recast? )

Wie würdet ihr die Schleifen so optimal wie möglich aussehen lassen ?
Wie könnte man mehrere Pixel pro Schleifendurchlauf kopieren.
Sollte man anstatt auf den Pointer der Adresse zuzugreifen lieber auf einen direkten wert zugreifen ?

Ich wäre für Ideen dankbar!

Hier ist der Ausgangscode !

https://franke.ms/cex/z/mWH7zF

[mfro]

erstmal

Code: [Auswählen]

-fomit-frame-pointer -O2
bei den Compiler-Optionen ergänzen. Sonst optimiert gcc 1. nichts und führt 2. unnötigerweise frame-pointer mit.

Auf den ersten Blick scheinen die Schleifenzähler in den Schleifen nicht genutzt zu werden. Du kannst also die Schleifen statt von h bzw w - 1 bis 0 von h bzw. w -2 bis -1 laufen lassen, ohne dass sich sonst etwas ändert.
Mit etwas Glückt verwendet gcc dann ein dbra.

Dein Compiler explorer verwendet gcc 2.95. Der ist mittlerweile etwa 20 Jahre alt und bezüglich Optimierung - vorsichtig ausgedrückt - nicht auf der Höhe der Zeit.

Tu' dir einen Gefallen und nimm' was neueres. 4.6.4 ist zwar auch nicht aktuell, aber diesbezüglich deutlich besser.

[Thorsten Otto]

Schau mal ins Popup, da kann man auch gcc 6.5 und gcc 8.2 auswählen

@tuxie: auch wenns nicht deine Seite ist, hast du zufällig ne Ahnung wie man ne eigene *public* Instance von compiler-explorer aufsetzt?

[tuxie]

Hallo Ihr beiden,

also generell geht es mir nicht um die Compiler Optimierung, die steht ja dann eh im makefile und ist bereits auf -O2 -fomit..... gesetzt. Mir geht es wirklich um die Optimierung des Ablaufes um so viele Daten wie moeglich in kürzester Zeit zu kopieren. Hier in dem fall haben wir zwei schleifen, einmal die schleife für die Zeilen und eine fuer die Pixel pro Zeile. Der Gedanke war das man mehrere Pixel pro durchlauf kopiert um so wenig wie moeglich Schleifendurchlaeufe zu haben.

Compiler habe ich im übrigen den 4.6.4 von Vincent im Einsatz. Will aber jetzt mal schauen das ich auf den 8er gehen kann.

Zum Code, eins habe ich schon rausgefunden, ich muss die beiden Zähler ints zu short int machen (reicht ja aus) dann feuert er auch dbra aus da dbra nur short kann laut aussagen von Gunnar alias BigGun

Im nächsten war die Idee eine Abfrage zu machen wie oft eine gewisse Zahl in die Pixel passt und demnach 3 oder 4 Routinen zu bauen er 1 2 3 4 pixel jeweils auf einmal kopiert.
@Thorsten Otto
schau mal hier
https://github.com/mattgodbolt/compiler-explorer

[Thorsten Otto]

also generell geht es mir nicht um die Compiler Optimierung, die steht ja dann eh im makefile und ist bereits auf -O2 -fomit.

Das ist schon klar, nur solltest du dann nach Möglichkeit auch für den compiler-explorer einen link posten wo das gesetzt ist (und ein entsprechender compiler benutzt wird), ansonsten kann man schlecht beurteilen ob eine Änderung wirklich besseren code bring. Ganz ohne Optimierung ist der erzeugte code ziemlich grottig.

Zum Code, eins habe ich schon rausgefunden, ich muss die beiden Zähler ints zu short int machen (reicht ja aus)

ich muss die beiden Zähler ints zu short int machen (reicht ja aus) dann feuert er auch dbra aus

Nicht zwangsläufig. Insbesondere wenn int nicht = short, ist der erzeugte code dann meistens schlechter als vorher. Ausserdem scheint er es zu bevorzugen, schon vor der Schleife das erwartete Ende für eine der Adressen zu berechnen, und dann in der Schleife die Adresse zu vergleichen.

Tests (alle mit -O2 -fomit-frame-pointer -mshort):

Code: [Auswählen]

void test(char *dst, char *src, unsigned short n)
{
    short i;
   
    for (i = n - 1; i >= 0; i--)
        *dst++ = *src++;
}

Erzeugt mit gcc 4.6.4:

Code: [Auswählen]

_test:
        move.l 4(%sp),%a0
        move.w 12(%sp),%d0
        subq.w #1,%d0
        jmi .L1
        move.l 8(%sp),%a1
.L3:
        move.b (%a1)+,(%a0)+
        subq.w #1,%d0
        jpl .L3
.L1:
        rts

Mit gcc 7.3.1:

Code: [Auswählen]

_test:
        move.l 8(%sp),%a0
        move.w 12(%sp),%d0
        subq.w #1,%d0
        jmi .L1
        move.l 4(%sp),%a1
.L3:
        move.b (%a0)+,(%a1)+
        dbra %d0,.L3
.L1:
        rts

(sieht ganz gut aus). Aber mit gcc 8.3.0:

Code: [Auswählen]

_test:
        move.l %d2,-(%sp)
        move.l 12(%sp),%d2
        move.w 16(%sp),%d1
        move.w %d1,%d0
        subq.w #1,%d0
        jmi .L1
        move.l 8(%sp),%a1
        move.l %d2,%a0
.L3:
        move.b (%a0)+,(%a1)+
        move.w %a0,%d0
        not.w %d0
        add.w %d2,%d0
        add.w %d1,%d0
        jpl .L3
.L1:
        move.l (%sp)+,%d2
        rts

Die letzte Version versteh ich irgendwie nicht, da bezieht er irgendwie die Addresse selber mit ein. Da scheint noch was falsch zu laufen, oder zumindest suboptimal.

schau mal hier

Ja, kenn ich, hab ich auch schon lokal laufen. Mir ist nur nicht ganz klar wie man den auf 'nem öffentlichen Web-Server zum laufen kriegt, ohne daß er sich mit dem normalen HTTP-Server beisst. Funktioniert möglicherweise nur mit Aber schauen wir mal.

[1ST1]

Ist das zufällig für den 68080? Hast du mal drüber nachgedacht, ob du da AMMX einsetzen kannst? Das wäre dann SIMD, das müsste die Sache gut beschleunigen...

[tuxie]

Hier geht es um einen Einfachen move!!! Gunnar hat mir eine Gedankenstütze gegeben
1
move.w
 --
2
move.l
 --
3
move.l
move.w
 --
4
move.l
move.l
dbra
5
move.l
move.l
dbra
move.w
6
move.l
move.l
dbra
move.l
 7
4*n +3rest
aus=breite and 3
if breite >=4 auswahl+4

So das quasi keine schleifen mehr entstehen da die schleifen echt zeit kosten.
Problem ist, man weiss nicht wieviele Pixel in der Zeile existieren, es können 4 sein aber es könnten auch 380 sein.
Das ziel ist es den Block von A nach B zu kopieren!! Am besten ohne schleifen, was aber nicht geht aber man könnte die Schleifendurchlaeufe reduzieren auf ein minimum.

Wie kann ich am besten den Pointer recasten? So das ich quasi anstatt einem word ein Langword kopiere ? Weil das kann der Core sehr schnell.. Aber dazu muss ich die Pointer auf die Adressen recasten.. aber irgendwie will das nicht in meinen Kopf rein. brrrrr

[Thorsten Otto]

In deinem Beispeil (für die innere Schleife, die innerhalb der Zeile kopiert), in etwa so:

Code: [Auswählen]

if (w >= 4)
{
    long *dst_addrl = (long *)dst_addr;
    long *src_addrl = (long *)src_addr;
    for (j = w / 2 - 1; j >= 0; j--)
        *dst_addrl++ = *src_addrl++;
}

ohne hier jetzt die Sonderfälle zu berücksichtigen wenn die Anzahl ungerade ist.

[Chocco]

for-Schleifen sind immer etwas tricky. Am besten nimmt man wohl eine while-Schleife, bei der auf >0 getestet wird. Im Compiler Explorer wird aus:

Code: [Auswählen]

    j = w;
    while( j-- ) {
        *dst_addr++ = *src_addr++;
    }

Die in meinen Augen schnellste Variante:

Code: [Auswählen]

L9:
        movew a1@+,a0@+
        dbra d0,L9


[Thorsten Otto]

Dein Beispiel ist das gleiche wie

Code: [Auswählen]

for (j = w; j--; )...Es hat nichts mit for/while zu tun, sondern lediglich wie die Ende-Bedingung aussieht. Und auch ob innnerhalb der Schleife nur ein move gemacht wird, oder mehrere:

Code: [Auswählen]

void test(char *dst, char *src, unsigned short n)
{
    short i;

    for (i = n - 1; i >= 0; i--)
        *dst++ = *src++;
}
erzeugt

Code: [Auswählen]

.L3:
        move.b (%a0)+,(%a1)+
        dbra %d0,.L3
(siehe http://brownbot.mooo.com/z/V4E4wk).

Aber

Code: [Auswählen]

void test(short *dst, short *src, unsigned short n)
{
    short i;

    for (i = n - 1; i >= 0; i--)
    {
        *dst++ = *src++;
        *dst++ = *src++;
    }
}
benutzt x(a0) anstatt post-increment (siehe http://brownbot.mooo.com/z/qTe-ge)

[Chocco]

Dein Beispiel ist das gleiche wie

Code: [Auswählen]

for (j = w; j--; )...Es hat nichts mit for/while zu tun, sondern lediglich wie die Ende-Bedingung aussieht. Und auch ob innerhalb der Schleife nur ein move gemacht wird, oder mehrere:

Genau das meinte ich mit "tricky" 

[Lynxman]

Aber das Ziel ist diese in C zu lassen da sie an mehreren stellen Verwendung findet.

Verstehe ich nicht.

[ari.tao]

Aber das Ziel ist diese in C zu lassen da sie an mehreren stellen Verwendung findet.

Verstehe ich nicht.

Ich auch nicht.

[Chocco]

Aber das Ziel ist diese in C zu lassen da sie an mehreren stellen Verwendung findet.

Verstehe ich nicht.

Ich auch nicht.

Im Grunde macht die Verwendung einer höheren Sprache wie z.B. "C" natürlich Sinn, weil man dadurch unabhängig von der verwendeten CPU entwickeln kann. Die oben vorgestellte Aufgabe ist im Prinzip eine sehr "schmale" Bitblt-Funktion. Unter Linux wird "Bitblt" als generische C-Funktion bereitgestellt, die dann vom Compiler für die Zielplattform den entsprechenden Maschinencode erzeugt. Aus ein und demselben C-Quelltext kann dann Code für diverse 68K, ARM oder Intel erzeugt werden.

Die Herausforderung besteht gerade bei zeitkritischen Routinen einfach darin, dem Compiler möglichst wenig Spielraum zur Interpretation des C-Quelltext zu geben. Ziel sollte dabei sein, dass der Compiler auch ohne Optimierungsschalter den optimalen Assembler-Text generiert.

P.S. Zum Thema Bitblt habe ich in meiner Link-Liste noch ein spannendes Dokument aus der Vorzeit gefunden: https://pdos.csail.mit.edu/~rsc/pike84bitblt.pdf

[Lynxman]

Ah okay, jetzt macht das Sinn.
Bin zur Zeit mit uCom Programmierung beschäftigt und meine Assembler Routinen laufen auf der ganzen Familie...

Danke fürs aufwecken!

[Chocco]

Ah okay, jetzt macht das Sinn.
Bin zur Zeit mit uCom Programmierung beschäftigt und meine Assembler Routinen laufen auf der ganzen Familie...

Solange es in der Familie bleibt ist doch alles i.O. 

[goetz @ 3rz]

P.S. Zum Thema Bitblt habe ich in meiner Link-Liste noch ein spannendes Dokument aus der Vorzeit gefunden: https://pdos.csail.mit.edu/~rsc/pike84bitblt.pdf

Da trage ich noch Dan Ingalls Vorführung von Smalltalk und Bitblt bei. Das ist im Prinzip obiges, nur älter und zum zugucken, wie er es auf *der* GUI-Maschine schlechthin vorführt: einer Xerox Alto.

https://www.youtube.com/watch?v=uknEhXyZgsg

Die Maschine hatte 128 KB frei zugängliches RAM (64k 16-Bit-Words), der Rest war VRAM, ähnlich wie beim ST. Nur, die hatten in den 128 KB das gesamte WIMP-System in Smalltalk implementiert, nix sparsames C. Und alles zur Laufzeit editierbar.

Der ST dagegen konnte nicht mit 256 KB RAM ausgeliefert werden, weil es zu eng wurde, wenn das OS im RAM war. Und das war 10 Jahre nach der Alto …

[mfro]

... Nur, die hatten in den 128 KB das gesamte WIMP-System in Smalltalk implementiert, nix sparsames C. Und alles zur Laufzeit editierbar.

Das liest man hin und wieder, aber wenn man sich die (mittlerweile frei verfügbaren) Quellen anschaut, scheint das nicht die ganze Wahrheit zu sein: http://xeroxalto.computerhistory.org/xerox_alto_file_system_archive.html

Wenn ich das richtig sehe, ist das Basis-Betriebssystem (I/O und Speicherverwaltung) in BCPL und Assembler geschrieben und implementiert mittels ein- und ausgelagerten Overlays eine simple Art virtuellen Speicher, in dem die Smalltalk-Maschine läuft. Die Kiste hat also immer nur einen Bruchteil des über 900KB grossen Smalltalk-Images im Speicher und lebt ansonsten von ihren (ich glaube, zwei) Festplatten.

Wunder konnten die Xerox-Entwickler auch nicht bewirken.

Für die damalige Zeit trotzdem sehr eindrucksvoll.

[goetz @ 3rz]

... Nur, die hatten in den 128 KB das gesamte WIMP-System in Smalltalk implementiert, nix sparsames C. Und alles zur Laufzeit editierbar.

Das liest man hin und wieder, aber wenn man sich die (mittlerweile frei verfügbaren) Quellen anschaut, scheint das nicht die ganze Wahrheit zu sein: http://xeroxalto.computerhistory.org/xerox_alto_file_system_archive.html

Wenn ich das richtig sehe, ist das Basis-Betriebssystem (I/O und Speicherverwaltung) in BCPL und Assembler geschrieben und implementiert mittels ein- und ausgelagerten Overlays eine simple Art virtuellen Speicher, in dem die Smalltalk-Maschine läuft. Die Kiste hat also immer nur einen Bruchteil des über 900KB grossen Smalltalk-Images im Speicher und lebt ansonsten von ihren (ich glaube, zwei) Festplatten.

Wunder konnten die Xerox-Entwickler auch nicht bewirken.

Für die damalige Zeit trotzdem sehr eindrucksvoll.

Der BCPL-Anteil kommt idT. in dem von mir verlinkten Video nicht raus, aber Dan betont mehrfach, dass das System ohne das Swapping nicht laufen würde. Und man hört die Alto beim Arbeiten auch mehrfach swappen.