AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Assembler: Reihenfolge eines Bitfelds umdrehen

Assembler: Reihenfolge eines Bitfelds umdrehen

Ein Thema von theomega · begonnen am 24. Jun 2005 · letzter Beitrag vom 26. Jun 2005
Antwort Antwort
Seite 2 von 2     12
Phistev
(Gast)

n/a Beiträge
 
#11

Re: Assembler: Reihenfolge eines Bitfelds umdrehen

  Alt 25. Jun 2005, 10:53
BSWAP steht theomega doch nicht zur Verfügung Also bringt Hagen's Idee nicht unbedingt etwas
  Mit Zitat antworten Zitat
Benutzerbild von theomega
theomega

Registriert seit: 18. Jun 2002
684 Beiträge
 
#12

Re: Assembler: Reihenfolge eines Bitfelds umdrehen

  Alt 25. Jun 2005, 11:02
Danke für die vielen Antworten, ich habe es inzwischen durch ein achtfaches rausschieben links und wieder reinschieben auch links gelöst. Dummerweise braucht die Sache damit 16 Prozessorzyklen, ist ein bischen ärgerlich, aber es funktioniert zumindest.

Gruß
TO
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#13

Re: Assembler: Reihenfolge eines Bitfelds umdrehen

  Alt 25. Jun 2005, 11:35
@Flocke: ja diese optimierungen wären möglich, natürlich sollte man dann wieder einige OpCodes in ihrer reihenfolge verschieben. Das bewirkt dann das der Code auf Piplined CPU's (alle neueren CPU's) wieder schneller ausgeführt werden kann.

Das BSWAP EAX kann ohne Problem vermieden werden.

16 Taktzyklen für eine Schleifenbasierte Lösung halte ich für zu optimistisch. Ich würde eher ca. 64 Zyklen abschätzen wollen. Das liegt am Konstruktionsdesign der heutigen CPU's. Diese CPU's bevorzugen Atomare, Flag-unabhängige und parallelisierbare Instruktionen. Im Grunde sind also Operationen wie RCL,ROL,ROR,RCR das genaue Gegenteil von "guten" Instruktionen auf neueren CPU's. Verschlimmert wird das dann noch wenn diese OpCodes in einer Schleife programmiert werden. Zu den rein theoretischen Taktzyklen muß man dann noch einige Branches, Misses und Waitstates in den U/V Pipelines hinzu rechnen. Das macht die 16 Taktzyklen Angabe eher unwahrscheinlich.

Ganz im Gegensatz dazu steht mein Source. Dieser vermischt die Registerbenutzung, Flagauswertungen und Abhängigkeiten der einzelnen Register, so daß der Code quasi in parallel in zwei Pipelines getrennt ablaufen kann. Statt für 2 OpCodes 2 Taktzyklen zu benötigen werden diese 2 OpCodes nur noch 1 Taktzyklus benötigen, ergo der Code läuft doppelt so schnell als die theoretisch errechneten Taktzyklen laut OpCodes. Hinzukommt dann noch das der Source nur einen einzigsten Branch besitzt, der Hauptcode ist also ein unrolled und Schleifenloser Code. Solch Code kann durch die CPU viel viel schneller abgearbeitet werden.
In meinen eigenen Test's habe ich auf einem P4/1.5Ghz eine Durchschnittliche Laufzeit von 10 Taktzyklen gemessen.

@Flocke: obige Ausführungen erklären auch warum ich den LEA Trick vermieden habe, dieser OpCode kann nur in der U Pipeline der CPU ausgeführt werden, im Gegensatz zu MOV,SHR,SHL,ADD,SUB,OR,AND usw. Es ist (nach meinem Gefühl) sehr wahrscheinlicher das das LEA zwar den Code verkürzt und vereinfacht, aber eben NICHT beschleunigt. Das müsste man aber praktischer Weise noch beweisen (statt sich auf mein Gefühl zu verlassen, bin mir aber ziemlich sicher das es so ist). Der Nachteil vom LEA ist nämlich dessen OpCode Länge, sprich die Anzahl der benötigten Bytes im Codesegment. Der Prozessorteil der diese Instruktionen aus dem Speicher in die CPU lädt und dann diesen OpCode Dekodieren muß benötigt somit mehr Zeit für LEA als für zb. MOV EAX,ECX o.ä.


Gruß Hagen
  Mit Zitat antworten Zitat
Benutzerbild von Flocke
Flocke

Registriert seit: 9. Jun 2005
Ort: Unna
1.172 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#14

Re: Assembler: Reihenfolge eines Bitfelds umdrehen

  Alt 25. Jun 2005, 23:57
@Hagen: Du hast sehr wahrscheinlich Recht. Mit Pipelining habe ich mich noch nicht so intensiv befasst, meine Assembler-Zeit endete so ca. vor 8 Jahren, so dass ich eher für 486 optimiert gedacht habe.

Zu den 16 Taktzyklen: theomega hat doch nur einen 8-Bit Mikroprozessor, und da werden wohl 16 Instruktionen = 16 Taktzyklen sein (8x LSR plus 8x ROL), wenn auch vielleicht nicht im GHz-Bereich!
Volker
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#15

Re: Assembler: Reihenfolge eines Bitfelds umdrehen

  Alt 26. Jun 2005, 07:55
Wieso benutzt ihr nicht einfach eine Lookuptabelle? Das dürfte IMHO das bei weitem schnellste sein (1-2 Takte pro Byte), sämtliche Optimierungsüberlegungen sind damit hinfällig, und zur Not gehts auch in nativem Delphi:
Delphi-Quellcode:
Type TFourBytes = Array [0..3] Of Byte;
Function ReverseBits (aValue : Integer) : Integer;
Begin
  TFourBytes(Result)[3] := rbLookup[TFourBytes(aValue)[0]];
  TFourBytes(Result)[2] := rbLookup[TFourBytes(aValue)[1]];
  TFourBytes(Result)[1] := rbLookup[TFourBytes(aValue)[2]];
  TFourBytes(Result)[0] := rbLookup[TFourBytes(aValue)[3]];
End;
Wobei in rbLookup[b] der die Bit-Inverse der Zahl b (0..255) steht.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#16

Re: Assembler: Reihenfolge eines Bitfelds umdrehen

  Alt 26. Jun 2005, 12:47
Zitat:
theomega hat doch nur einen 8-Bit Mikroprozessor
Hm, sehe ich auch gerade, er hat das viel zu versteckt nebenbei erwähnt.

@theomega: schau mal hier rein http://www.mikrocontroller.net/forum/ , da werden sie geholfen.

Auf einem AVR wird selbstverständlich eine Schleife oder sogar auch unrolled Loop mit den OpCodes RCL, RCR seine 32 Taktzyklen für 16 Bitwerte ergeben. Im obengenannten Forum finden sich aber auch bessere Varianten, die im Grunde auf dem gleichen Trick wie mein Intel Code arbeiten.

Gruß Hagen
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 14:38 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf