PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

ASM-Ersatzcode gesucht

https://www.purebasic.fr/german/viewtopic.php?t=26020

Seite 1 von 2

ASM-Ersatzcode gesucht

Verfasst: 28.10.2012 07:20
von 7x7
Mir kommt es wieder mal auf jede Nanosekunde an und habe deshalb eine kleine Frage an die Assembler-Geeks:

Kann ich z.B. folgenden Code in Bezug auf Geschwindigkeit verbessern?

Code: Alles auswählen

!MOV eax, dword[ebx+ 4]
!INC dword[eax]
Was ich bräuchte wäre z.B. sowas:

Code: Alles auswählen

!INC dword[dword[ebx+ 4]]
Gibts aber leider nicht :mrgreen:

Das ganze Problem schaut so aus:
(der Pointer '*y' zeigt auf eine Liste die NICHT FORTLAUFENDE Adressen enthält)

Code: Alles auswählen

Macro StoreNewParameter	
	!mov ebx,dword[p_y]
   ;----		
	!mov eax,dword[ebx]      ;k1(1)
	!Inc dword[eax]
	;----
	!mov eax,dword[ebx+ 4]	;k1(2)
	!Inc dword[eax]
	!mov eax,dword[ebx+ 8]	;k2(1,2)
	!Inc dword[eax]
	;----
	!mov eax,dword[ebx+12]	;k1(3)
	!Inc dword[eax]
	!mov eax,dword[ebx+16]	;k2(1,3)
	!Inc dword[eax]
	!mov eax,dword[ebx+20]	;k2(2,3)
	!Inc dword[eax]
	;---
	!mov eax,dword[ebx+24]	;k1(4)
	!Inc dword[eax]
	!mov eax,dword[ebx+28]	;k2(1,4)
	!Inc dword[eax]
	!mov eax,dword[ebx+32]	;k2(2,4)
	!Inc dword[eax]
	!mov eax,dword[ebx+36]	;k2(3,4)
	!Inc dword[eax]
	;----
	!mov eax,dword[ebx+40]	;k1(5)
	!Inc dword[eax]
	!mov eax,dword[ebx+44]	;k2(1,5)
	!Inc dword[eax]
	!mov eax,dword[ebx+48]	;k2(2,5)
	!Inc dword[eax]
	!mov eax,dword[ebx+52]	;k2(3,5)
	!Inc dword[eax]
	!mov eax,dword[ebx+56]	;k2(4,5)
	!Inc dword[eax]
   ;----
	!mov eax,dword[ebx+60]	;k1(6)
	!Inc dword[eax]
	!mov eax,dword[ebx+64]	;k2(1,6)
	!Inc dword[eax]
	!mov eax,dword[ebx+68]	;k2(2,6)
	!Inc dword[eax]
	!mov eax,dword[ebx+72]	;k2(3,6)
	!Inc dword[eax]
   !mov eax,dword[ebx+76]	;k2(4,6)
	!Inc dword[eax]
	!mov eax,dword[ebx+80]	;k2(5,6)
	!Inc dword[eax]
EndMacro
Auf diese Art gibt es noch 2 weitere ähnliche Macros. Nehme dankend alles an was Speed bringt! :mrgreen:

(Verbesserungsvorschläge sollten aber auf 32+64-Bit Rechnern laufen können)

Re: ASM-Ersatzcode gesucht

Verfasst: 28.10.2012 11:09
von Danilo
7x7 hat geschrieben: Was ich bräuchte wäre z.B. sowas:

Code: Alles auswählen

!INC dword[dword[ebx+ 4]]
Gibts aber leider nicht :mrgreen:
Was Du meinst ist vielleicht:

Code: Alles auswählen

Macro StoreNewParameter   
   !mov ebx, [p_y]
   !lea dword ebx, [ebx]
   ;----      

   !Inc dword [ebx]         ;k1(1)
   ;----
   !inc dword [ebx + 4]     ;k1(2)
   !Inc dword [ebx + 8]     ;k2(1,2)
   ;----
EndMacro

Structure myStructure
    x.l[20]
EndStructure

Global *y.myStructure = AllocateMemory(SizeOf(myStructure))

For i = 0 To 19
    *y\x[i] = i + 1
Next i

StoreNewParameter

For i = 0 To 19
    Debug *y\x[i]
Next i
Allerdings ist das nur 32bit, so wie Dein Code.

Was Du mit "NICHT FORTLAUFENDE Adressen" meinst, weiss ich nicht.
Dein "StoreNewParameter" nutzt doch fortlaufende Adressen (+4, +8, + 12, + 16, ...).

Ein Schnellschuss für x86 und x64:

Code: Alles auswählen

CompilerIf #PB_Compiler_Processor = #PB_Processor_x64
    !sizeof_int equ 8
    !reg        equ rbx
    !integer    equ qword
CompilerElse
    !sizeof_int equ 4
    !reg equ    ebx
    !integer    equ dword
CompilerEndIf

Macro StoreNewParameter   
   !mov integer reg, [p_y]
   !lea integer reg, [reg]
   ;----      

   !Inc integer [reg + 0 * sizeof_int]     ;k1(1)
   ;----
   !inc integer [reg + 1 * sizeof_int]     ;k1(2)
   !Inc integer [reg + 2 * sizeof_int]     ;k2(1,2)
   ;----
EndMacro

Structure myStructure
    x.i[20]
EndStructure

Global *y.myStructure = AllocateMemory(SizeOf(myStructure))

For i = 0 To 19
    *y\x[i] = i + 1
Next i

StoreNewParameter

For i = 0 To 19
    Debug *y\x[i]
Next i
Aber ich denke, da sind noch mehr Informationen von Dir nötig.
Möchtest Du nur alle Werte in einem Integer-Array um den Wert 1 erhöhen/inkrementieren?

Re: ASM-Ersatzcode gesucht

Verfasst: 28.10.2012 12:09
von 7x7
Danilo danke für deinen Versuch, mir zu helfen.
Untenstehendes Beispielprogramm soll etwas deutlicher machen, was ich genau bezwecke:

Code: Alles auswählen

;Beispielcode

Macro StoreNewParameter
	!mov ebx,dword[p_y]
	;----
	!mov eax,dword[ebx]		
	!Inc dword[eax]
	!mov eax,dword[ebx+ 4]	
	!Inc dword[eax]
	!mov eax,dword[ebx+ 8]	
	!Inc dword[eax]
	!mov eax,dword[ebx+12]	
	!Inc dword[eax]
	!mov eax,dword[ebx+16]	
	!Inc dword[eax]
	!mov eax,dword[ebx+20]	
	!Inc dword[eax]
	!mov eax,dword[ebx+24]	
	!Inc dword[eax]
	!mov eax,dword[ebx+28]	
	!Inc dword[eax]
	!mov eax,dword[ebx+32]	
	!Inc dword[eax]
	!mov eax,dword[ebx+36]	
	!Inc dword[eax]
EndMacro


Global Dim Ergebnis.l(50)

Global Dim AdressListe.l(10)

;AdressListe mit den Adressen der zu ändernten Ergebnis-Indizes füllen
Adressliste( 1)=@Ergebnis(15)
Adressliste( 2)=@Ergebnis(25)
Adressliste( 3)=@Ergebnis(39)
Adressliste( 4)=@Ergebnis(42)
Adressliste( 5)=@Ergebnis(17)
Adressliste( 6)=@Ergebnis(50)
Adressliste( 7)=@Ergebnis(23)
Adressliste( 8)=@Ergebnis( 7)
Adressliste( 9)=@Ergebnis( 2)
Adressliste(10)=@Ergebnis(36)

*y=@AdressListe(1)
StoreNewParameter

For a=1 To 50
	Debug Ergebnis(a)
Next a
Du siehst, was ich mit NICHT FORTLAUFENDEN Adressen in der AdressListe meine.

Der Debug-Output zeigt meine Absicht.

Mit "muss auf 32/64-Bit Rechnern laufen" wollte ich sagen, dass nur 32Bit-ASM-Befehle verwendet werden sollen. Der Code läuft auf x unterschiedlichen Clients im Netzwerk.

Re: ASM-Ersatzcode gesucht

Verfasst: 28.10.2012 14:04
von NicTheQuick
Hm... Darf man wissen, um was es hier genau geht?

Nicht fortlaufende Adressen sind ja schon Cache-problematisch. Es wird also höchstwahrscheinlich passieren, dass jedes Mal die Werte aus dem Arbeitsspeicher in den Cache und dann in Register geladen werden müssen, was natürlich am langsamsten ist. Würde alle Werte am Stück existieren, könnten sie in einem Rutsch in den Cache geladen, dann alle blitzschnell geändert und wieder zurück geschrieben werden.

Wenn's um Nanosekunden geht, darf man nicht mehr nur an einzelnen ASM-Befehlen herum doktern, sondern muss die Hardware-Struktur der Maschine, auf der man programmiert, kennen und richtig nutzen.

Vielleicht kann ich dir noch Ideen und Vorschläge geben, wenn ich genau weiß, was der Hintergrund ist. Womöglich ist dein Ansatz für dieses Problem sogar schon nicht optimal.

Re: ASM-Ersatzcode gesucht

Verfasst: 28.10.2012 15:30
von 7x7
NicTheQuick hat geschrieben:Hm... Darf man wissen, um was es hier genau geht?
Vereinfacht gesagt: Ich suche einen Lösungsweg zu einem Ziel, das mathematisch beweisbar ist. Das Ergebnis ist DER WEG! (wie beim Navi...man kennt das Ziel, aber den Weg nicht)
Mathematik hilft hier nur begrenzt. Ein Regelwerk bestimmt die Richtung. Das ganze läuft im Trial & Error-Verfahren wie beim Schach. Ein erzeugter Knotenpunkt generiert wiederum x-Möglichkeiten für den weiteren Weg.
Nicht fortlaufende Adressen sind ja schon Cache-problematisch...
Diese Überlegung hatte ich auch schon im Hinterkopf. Ist aber leider nicht zu verhindern.
...sondern muss die Hardware-Struktur der Maschine, auf der man programmiert, kennen und richtig nutzen.
Leider kann ich nicht davon ausgehen, dass das Programm überall die gleichen Bedingungen vorfindet, wie auf meinem Rechner. Wie ich oben schon schrieb: "Der Code läuft auf x unterschiedlichen Clients im Netzwerk"


Ähnlich dem "SETI-Projekt" werde ich irgendwann das Client-Programm auf einer Website zum Download anbieten. Wäre doch schade, wenn Millionen Rechner auf der Welt den ganzen Tag nur sinnlos vor sich hin laufen.

Re: ASM-Ersatzcode gesucht

Verfasst: 28.10.2012 23:23
von NicTheQuick
7x7 hat geschrieben:
NicTheQuick hat geschrieben:Hm... Darf man wissen, um was es hier genau geht?
Vereinfacht gesagt: Ich suche einen Lösungsweg zu einem Ziel, das mathematisch beweisbar ist. Das Ergebnis ist DER WEG! (wie beim Navi...man kennt das Ziel, aber den Weg nicht)
Mathematik hilft hier nur begrenzt. Ein Regelwerk bestimmt die Richtung. Das ganze läuft im Trial & Error-Verfahren wie beim Schach. Ein erzeugter Knotenpunkt generiert wiederum x-Möglichkeiten für den weiteren Weg.
Schon mal über Schwarmalgorithmen wie Simulated Annealing, Particle Swarm Optimization oder Genetic Algorithms nach gedacht? Das klingt mir ganz nach einem Einsatzgebiet für eines dieser oder ähnliche Algorithmen.

Hier auch einige Paper zum Thema und ein paar Folien aus dem Seminar "Multi-Core Programming Lab on Swarm Algorithms", an dem ich mal teil genommen hatte.

Re: ASM-Ersatzcode gesucht

Verfasst: 01.11.2012 07:31
von 7x7
Sorry, NicTheQuick, dass ich erst jetzt antworte. War zu sehr mit der Programmierung beschäftigt (zum Leidwesen aller in meiner Umgebung ;-))
NicTheQuick hat geschrieben:Schon mal über Schwarmalgorithmen wie Simulated Annealing, Particle Swarm Optimization oder Genetic Algorithms nach gedacht?
Klingt alles sehr interessant und werde mich mal -wenn ich Zeit habe- damit beschäftigen. Den Status "Simulated Annealing" habe ich aber bereits mit "Reality Analing" :mrgreen: verlassen.

Deine Papers/Folien habe ich mir teilweise angesehen, bringen mich aber im Moment nicht weiter. Der Algo für mein Problem ist relativ simpel und enthält bereits alle bekannten Möglichkeiten der Wegoptimierung.

Was mich weiterbringen würde, wäre die Einbeziehung der enormen Rechenleistung vorhander Grafikkarten auf den Clients mit den hunderten Shadern/Kernen. Das wäre eine geile Sache! Habe aber keine Ahnung, wie ich DAS realisieren kann. Weiss nur, dass ich mich dann mit "OpenCL" befassen muss. Das wiederum würde wohl mehr Fragen aufwerfen und mehr Zeit erfordern, als es mich letztlich weiterbringt. Denn inzwischen hätten 100000 Clients das Problem wohl auch schon gelöst. :D

Re: ASM-Ersatzcode gesucht

Verfasst: 01.11.2012 08:28
von Danilo
Hallo 7x7,

ich habe 5 oder 6 verschiedene Varianten für Deine genaue Problembeschreibung im 2. Posting ausprobiert,
gemessen und verglichen. In EBX hast Du den Array-Pointer, und danach verwendest Du nur noch EAX
um Pointer-Werte zu bekommen und an diesen Adressen zu inkrementieren. Also probiert auch ECX und EDX
einzubinden (Pairing, CPU-Dekodier-Pipelines usw.).
Oder das ganze als Loop machen, dann ist es einfacher zu nutzen... aber wieder etwas "langsamer".

Code: Alles auswählen

;Beispielcode

Macro StoreNewParameter
   !mov ebx,dword[p_y]
   !MOV ecx,dword[v_count]
   !dec ecx
   ;----
   !loop1:
     !mov eax,dword[ebx + ecx*4]      
     !inc dword[eax]
     !dec ecx
   !jnz loop1
   !mov eax,dword[ebx]
   !inc dword[eax]
EndMacro


Global Dim Ergebnis.l(50)

Global Dim AdressListe.l(10)

;AdressListe mit den Adressen der zu ändernten Ergebnis-Indizes füllen
Adressliste( 1)=@Ergebnis(15)
Adressliste( 2)=@Ergebnis(25)
Adressliste( 3)=@Ergebnis(39)
Adressliste( 4)=@Ergebnis(42)
Adressliste( 5)=@Ergebnis(17)
Adressliste( 6)=@Ergebnis(50)
Adressliste( 7)=@Ergebnis(23)
Adressliste( 8)=@Ergebnis( 7)
Adressliste( 9)=@Ergebnis( 2)
Adressliste(10)=@Ergebnis(36)

*y=@AdressListe(1)
count = 10
StoreNewParameter

For a=1 To 50
   Debug Str(a) + ": " + Str(Ergebnis(a))
Next a
(natürlich ohne Debugger und mit performance counter oder !RDTSC getestet)

Auch MMX mit mehreren Operation war in meinen Tests höchstens gleich schnell.
Das Problem scheint zu klein für große Optimierungen zu sein. Es ist ja nur eine Dereferenzierung eines Zeigers
und das inkrementieren (erhöhen um 1) des Wertes am Zeiger-Ziel.
Das Problem ist wohl der Zugriff auf Speicher, der immer langsamer ist als Register-Zugriffe. Deshalb kann man
auch verschiedene Register verwenden, aber es wird trotzdem nicht schneller, da Speicherzugriffe zu langsam sind -
wobei wir hier über CPU-Ticks reden, wenn wir "langsam" sagen. ;)
Dieses simple Problem auf die Grafikkarte auszulagern wird bestimmt auch nicht helfen, wenn Dein Array im
Hauptspeicher ist. Dann muss die GraKa aus dem Hauptspeicher die Array-Adresse lesen, und dann per Index (+4, +8, ...)
wieder eine Adresse aus dem Hauptspeicher lesen, um den Wert an dieser Hauptspeicheradresse dann um 1 zu erhöhen.

Dein kleines Problem ist also IMO der Zugriff auf das Array und das dereferenzieren der Pointer des Arrays
und inkrementieren dieser Werte... weil das Array und die dereferenzierten Speicherzellen alle im "langsamen" Hauptspeicher liegen.

Re: ASM-Ersatzcode gesucht

Verfasst: 01.11.2012 09:22
von 7x7
Hi Danilo,

das Prefeching der CPU habe ich bereits vor 2 Tagen auf der Suche nach Optimierung durch Verwendung der restlichen Register im Originalcode (optimal?) berücksichtigt und brachte unglaubliche 100% Leistungssteigerung in diesem Codesegment und den anderen ähnlichen Macros!!:

Code: Alles auswählen

Macro StoreNewParameter
	!mov ebx,dword[p_y]
	
	!mov eax,dword[ebx]	;k1(1)
	!Inc dword[eax]
	;----
	!mov eax,dword[ebx+ 4]	;k1(2)
	!mov ecx,dword[ebx+ 8]	;k2(1,2)	
	!Inc dword[eax]
	!Inc dword[ecx]
	;----
	!mov eax,dword[ebx+12]	;k1(3)
	!mov ecx,dword[ebx+16]	;k2(1,3)	
	!mov edx,dword[ebx+20]	;k2(2,3)	
	!Inc dword[eax]
	!Inc dword[ecx]
	!Inc dword[edx]
	;---
	!mov eax,dword[ebx+24]	;k1(4)
	!mov ecx,dword[ebx+28]	;k2(1,4)	
	!mov edx,dword[ebx+32]	;k2(2,4)	
	!Inc dword[eax]
	!Inc dword[ecx]
	!mov eax,dword[ebx+36]	;k2(3,4)
	!Inc dword[edx]
	!Inc dword[eax]
	;----
	!mov eax,dword[ebx+40]	;k1(5)
	!mov ecx,dword[ebx+44]	;k2(1,5)	
	!mov edx,dword[ebx+48]	;k2(2,5)	
	!Inc dword[eax]
	!Inc dword[ecx]
	!mov eax,dword[ebx+52]	;k2(3,5)
	!Inc dword[edx]
	!mov ecx,dword[ebx+56]	;k2(4,5)
	!Inc dword[eax]
	!Inc dword[ecx]
	;----
	!mov eax,dword[ebx+60]	;k1(6)
	!mov ecx,dword[ebx+64]	;k2(1,6)	
	!mov edx,dword[ebx+68]	;k2(2,6)	
	!Inc dword[eax]
	!Inc dword[ecx]
	!mov eax,dword[ebx+72]	;k2(3,6)
	!Inc dword[edx]
	!mov ecx,dword[ebx+76]	;k2(4,6)
	!Inc dword[eax]
	!mov edx,dword[ebx+80]	;k2(5,6)
	!Inc dword[ecx]
	!Inc dword[edx]
EndMacro
Danilo hat geschrieben:Das Problem ist wohl der Zugriff auf Speicher, der immer langsamer ist als Register-Zugriffe.
Ja genau! Da liegt der Hase im Pfeffer!

/Edit:
Habe ich irgendwie die Möglichkeit, direkt den Cache der CPU zu meinen Gunsten zu manipulieren? Also in der Art, dass ich bestimmte Teile des Hauptspeichers in den Cache (egal ob Level1 oder Level2) lege?

Re: ASM-Ersatzcode gesucht

Verfasst: 01.11.2012 16:56
von Helle
Zum Cache vorfüttern gibt es die PREFETCHx-Instruktionen, die aber nicht so ganz ohne sind; besonders wenn unterschiedliche PC-Generationen damit laufen sollen (wie vermutlich bei Dir). AMD hat da dann auch noch teilweise sein eigenes Süppchen gekocht (Relikt von 3DNow!). Zum sinnvollen Einsatz sollte unbedingt die Größe einer Cache-Line bekannt sein (meist 64 Byte, aber...) und der Code in einer Schleife laufen (wäre zumindest positiv, und nicht bloß 2-3 Loops). Ein Loop sollte nicht zu klein (ineffektiv) und nicht zu groß (Gefahr des Rausschmeißens) sein usw.
Aber probieren kann man es ja mal!
Gruß
Helle
Alle Zeiten sind UTC+02:00
Seite 1 von 2

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de