Schneller Byte-Austausch (XOR swap)

    • Allgemein

      Schneller Byte-Austausch (XOR swap)

      Heute beschäftigen wir uns mal mit der Programm-Optimierung :)
      Um etwas genauer zu sein geht es ums vertauschen von 2 Bytes / Integers / Longs miteinander. Solche Vorgänge benötigt man z.B. bei Sortier-Funktionen.
      Literatur gibts da zu auf der Wikipedia - siehe unten.


      Wenn man 2 Bytes vertauschen will, verwendet man normalerweise folgenden Code:

      VB.NET-Quellcode

      1. Dim x as Byte 'oder integer oder long
      2. Dim y as Byte
      3. Dim z as Byte
      5. x = ... 'wird iwo im Programm gesetzt
      6. y = ... 'wird iwo im Programm gesetzt
      8. 'Austausch
      9. z = x
      10. x = y
      11. y = z



      XOR Swap ist jedoch die schnellere Methode:

      VB.NET-Quellcode

      1. 'xor swap
      2. Dim x as Byte 'oder integer oder long
      3. Dim y as Byte
      5. x = ... 'wird iwo im Programm gesetzt
      6. y = ... 'wird iwo im Programm gesetzt
      8. 'Austausch
      9. x = x xor y
      10. y = y xor x
      11. x = x xor y



      Bei Arrays ist die schnellste Methode CopyMemory / RtlMoveMemory:

      VB.NET-Quellcode

      1. 'API-Deklaration:
      2. Public Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" _
      3. (Destination As Any, Source As Any, ByVal Length As Long)
      5. 'Code:
      6. Dim x() as Byte 'oder integer oder long
      7. Dim y() as Byte
      8. Dim z() as Byte
      10. redim x(255)
      11. redim y(255)
      12. redim z(255)
      14. 'x(...) und y(...) befüllen ...
      16. 'Austausch
      17. 'Der erste Parameter ist das 1. Byte des Ziels,
      18. 'der zweite Parameter das 1. Byte der Quelle und
      19. 'der dritte Parameter die Länge der Daten IN BYTES!
      20. CopyMemory z(0), x(0), 256
      21. CopyMemory x(0), y(0), 256
      22. CopyMemory y(0), x(0), 256



      Hier meine Test-Ergebnisse:

      Quellcode

      1. 1 Byte:
      2. xor: 3,078 ns
      3. copy: 3,343 ns
      5. 256-Byte-Array:
      6. xor: 6813 ns (Schleife: jedes einzelne Byte)
      7. copy: 3516 ns (ganzes Array kopieren)
      8. api: 907 ns (Code von oben)
      10. ns = Nanosekunde
      11. Zeiten pro Durchlauf


      Achtung!
      Die gelisteten Zeiten sind als kompilierte .exe.
      In der IDE ist das Kopieren mehr als doppelt so schnell wie die XOR-Methode!


      Ein bisschen Literatur dazu findet man auch in der Wikipedia: XOR swap algorithm
      Leider hat dieser Algorithmus nicht so eine Effizienz wie bspw. in Assembler, da man nicht direkt auf die Register zugreifen kann.


      so long..
      Andy


      Keywords: Visual Basic, VB6, XOR Swap Algorithm, XOR Swap Algorithmus, XOR, Exklusiv Oder, CopyMemory, RtlMoveMemory

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Mad Andy“ ()

    Facebook
    Telefonspende