3. Motorola zu Intel konvertieren ....

Motorola zu Intel konvertieren ....

  • C
    Mod

    das geht dann allerdings auch ohne LUT, indem wir die maske als laufvariable der schleife missbrauchen (vorausgesetzt, der entsprechende typ ist exakt 32bit breit):

    unsigned result = 0;
   for (unsigned mask=1; mask!=0; mask<<=1)
   {
      if (read_bit() == 1)   // hi-bit kommt als erstes
         result |= mask;
   }
    0
  • J

    @net, na da hast du ja mal eine richtig tolle lösung gefunden.
    du schreibst also lieber die ganzen masken hin, anstatt die zu schiften?
    so ganz kann ich das leider nicht akzeptieren.

    zumal der nächste auch gleich wieder die maske vorschlägt. natürlich ein bisschen cleverer implementiert als ich aber mit maske...

    ciao,
    jenz

    0
  • N

    jenz schrieb:

    @net, na da hast du ja mal eine richtig tolle lösung gefunden.
    du schreibst also lieber die ganzen masken hin, anstatt die zu schiften?
    so ganz kann ich das leider nicht akzeptieren.

    toll ist das alles nicht (wegen der 32 schleifendurchläufe). aber lookuptables sind immer ein tickchen schneller. kannst es ja mal testen (beide versionen einige millionen mal aufrufen und zeit messen).

    0
  • J
     

    toll ist das alles nicht (wegen der 32 schleifendurchläufe). aber lookuptables sind immer ein tickchen schneller. kannst es ja mal testen (beide versionen einige millionen mal aufrufen und zeit messen).

    okay, wenn sich bis samstag nicht irgendein anderer daran versucht hat werde ich das mal durchmessen.
    ich bin mir sicher, dass die variante ohne lut schneller ist. vor allem dann, wenn auch noch threadwechsel stattfinden. wovon man wohl ausgehen sollte.

    bis dahin,
    jenz

    0
  • N

    jenz schrieb:

    ich bin mir sicher, dass die variante ohne lut schneller ist. vor allem dann, wenn auch noch threadwechsel stattfinden. wovon man wohl ausgehen sollte.

    das könnte schon sein, weil der shiftwert in 'nem register gehalten wird. andererseits könnte ein geschickter compiler die schleife auflösen und die werte aus dem array direkt nehmen (also ohne array-zugriffe zu machen). dann wär' wieder die lut-variante schneller 😉

    0
  • T

    Es gibt noch eine Möglichkeit (ohne Schleife):

    Zuerst swappt man die 4 Bytes (d.h. aus "abcd" wird "dcba").
    Dann greift man über eine Lookup-Table mit 256 Werten für jedes Byte darauf zu und swappt jeweils die 8 Bits.

    0 -> 0 00000000 -> 00000000
    1 -> 128 00000001 -> 10000000
    2 -> 64 00000010 -> 01000000
    ...
    254 -> 127 11111110 -> 01111111
    255 -> 255 11111111 -> 11111111

    0
  • J

    @th: das swappen ist schon längst nicht mehr unser problem. 😉
    wir reden über ein möglichst effizientes einlesen...

    ciao,
    jenz

    0
  • T

    Ich habe hier mal ein Testprogramm geschrieben, mit dem ich verschiedene Varianten ausprobiert habe. Die Lookuptabelle gewinnt bei mir um ca. den Faktor 6. Hier ist meine Rotationsfunktion, die ich auch zum initialisieren der Lookuptabelle verwende:

    template <typename T>
T rotbits(T v, unsigned bits = 8)
{
  T ret = 0;
  for (unsigned n = 0; n < bits; ++n)
  {
    ret = (ret << 1) | (v & 1);
    v >>= 1;
  }
  return ret;
}

    Wenn Interesse besteht, kann ich auch mein komplettes Testprgramm posten.

    Tntnet

    0
  • N

    ich hatte auch mal etwas lange weile:

    #include <stdio.h>
#include <windows.h>

// dummy
int read_bit (void)
{
   return 1;
}

unsigned long read32_reverse_table (void)
{
   static unsigned long table[] =
   {
      0x00000001,
      0x00000002,
      0x00000004,
      0x00000008,
      0x00000010,
      0x00000020,
      0x00000040,
      0x00000080,
      0x00000100,
      0x00000200,
      0x00000400,
      0x00000800,
      0x00001000,
      0x00002000,
      0x00004000,
      0x00008000,
      0x00010000,
      0x00020000,
      0x00040000,
      0x00080000,
      0x00100000,
      0x00200000,
      0x00400000,
      0x00800000,
      0x01000000,
      0x02000000,
      0x04000000,
      0x08000000,
      0x10000000,
      0x20000000,
      0x40000000,
      0x80000000
   };

   register unsigned long result = 0;
   register unsigned long s;

   for (s=0; s<32; s++)
   {
      if (read_bit() == 1)
         result |= table[s];
   }

   return result;
}

unsigned long read32_reverse_loopless (void)
{
   register unsigned long result = 0;

   if (read_bit() == 1)
      result |= 0x00000001;
   if (read_bit() == 1)
      result |= 0x00000002;
   if (read_bit() == 1)
      result |= 0x00000004;
   if (read_bit() == 1)
      result |= 0x00000008;
   if (read_bit() == 1)
      result |= 0x00000010;
   if (read_bit() == 1)
      result |= 0x00000020;
   if (read_bit() == 1)
      result |= 0x00000040;
   if (read_bit() == 1)
      result |= 0x00000080;
   if (read_bit() == 1)
      result |= 0x00000100;
   if (read_bit() == 1)
      result |= 0x00000200;
   if (read_bit() == 1)
      result |= 0x00000400;
   if (read_bit() == 1)
      result |= 0x00000800;
   if (read_bit() == 1)
      result |= 0x00001000;
   if (read_bit() == 1)
      result |= 0x00002000;
   if (read_bit() == 1)
      result |= 0x00004000;
   if (read_bit() == 1)
      result |= 0x00008000;
   if (read_bit() == 1)
      result |= 0x00010000;
   if (read_bit() == 1)
      result |= 0x00020000;
   if (read_bit() == 1)
      result |= 0x00040000;
   if (read_bit() == 1)
      result |= 0x00080000;
   if (read_bit() == 1)
      result |= 0x00100000;
   if (read_bit() == 1)
      result |= 0x00200000;
   if (read_bit() == 1)
      result |= 0x00400000;
   if (read_bit() == 1)
      result |= 0x00800000;
   if (read_bit() == 1)
      result |= 0x01000000;
   if (read_bit() == 1)
      result |= 0x02000000;
   if (read_bit() == 1)
      result |= 0x04000000;
   if (read_bit() == 1)
      result |= 0x08000000;
   if (read_bit() == 1)
      result |= 0x10000000;
   if (read_bit() == 1)
      result |= 0x20000000;
   if (read_bit() == 1)
      result |= 0x40000000;
   if (read_bit() == 1)
      result |= 0x80000000;

   return result;
}

unsigned long read32_reverse_mask (void)
{
   register unsigned long result = 0;
   register unsigned long mask;

   for (mask=1; mask!=0; mask<<=1)
   {
      if (read_bit() == 1)   
         result |= mask;
   }

   return result;
}

#define REPETITIONS 10000000L

void test (void)
{
   unsigned long timer;
   unsigned long s;

   // mask
   timer = GetTickCount();
   for (s=0; s<REPETITIONS; s++)
      read32_reverse_mask();
   timer = GetTickCount() - timer;
   printf ("mask: %lu\n", timer);

   // table
   timer = GetTickCount();
   for (s=0; s<REPETITIONS; s++)
      read32_reverse_table();
   timer = GetTickCount() - timer;
   printf ("table: %lu\n", timer);

   // w/o loop
   timer = GetTickCount();
   for (s=0; s<REPETITIONS; s++)
      read32_reverse_loopless();
   timer = GetTickCount() - timer;
   printf ("loopless: %lu\n", timer);

   printf ("------------------------------\n");
}

void main (void)
{
   SetPriorityClass (GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
   SetThreadPriority (GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);

   test();
   test();
   test();
   test();
}

    ergebnis:

    mask: 1656
table: 1672
loopless: 1125
------------------------------
mask: 1656
table: 1672
loopless: 1125
------------------------------
mask: 1656
table: 1672
loopless: 1141
------------------------------
mask: 1656
table: 1688
loopless: 1125
------------------------------
Press any key to continue

    demnach ist die lut-version etwas schlechter als die mit dem shiften.
    aber ohne schleife ist es um ca. 1/3 schneller....

    0
  • T

    @net: Ich glaube, einer von uns beiden hat das Problem nicht richtig verstanden. Du gehst von einer Funktion read_bit aus, welches ein bit nach dem anderen liefert. Ich gehe davon aus, daß ein 32-Bit-Wort zur verfügung steht, welches bitweise umgedreht werden soll.

    Auch ist Deine Lookup-tabelle was anderes, als meine. Die Idee ist doch, daß man ein Byte umdreht, indem man in einer Tabelle mit den 256 Byte-Werten den entsprechenden umgedrehten Byte nachschaut.

    Bei mir sieht das so aus:

    static unsigned char lut[256];

  // initialize lookup-table
  for (unsigned i = 0; i < 256; ++i)
    lut[i] = rotbits(i);

  unsigned char ch = getIrgendeinByte();
  unsigned char rch = lut[ch];  // schlage in der Lookup-tabelle nach

    Und diese Variante ist in der Tat wesentlich schneller als etwa:

    unsigned char rch = rotbits(ch);

    welches jedes einzelne Byte algorithmisch undreht.

    Tntnet

    0
  • H

    die API's geben die Daten telegrammorinetiert raus
    ich bekomm nen array von ner Struct:
    [...]
    char[8] array

    unsigned char b;
b = ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;

    (Bit Twiddling Hacks)

    0
  • J

    @tntnet, net programmiert da etwas anderes. das ist so ne kleine privatfehde.

    @net, fleißig. sieht man mal, das unsere ersten varianten nicht so besonders waren. die ausgerollte ist halt am besten.
    einigen wir uns darauf, dass wir beide danebenlagen? 😉
    die paar ticks sind dann ja wirklich egal.

    also back to topic, vielleicht können wir dem tntnet noch was zeigen 😉

    ciao,
    jenz

    0
  • ?

    RHBaum schrieb:

    im schnitt max 3800 Nachrichten = 2+1+8 byte pro sekunde ... der zeitstempel wird beim empfang generiert.

    3800 Botschaften pro Sekunde wären aber schon recht viel für 500k. Ihr fahrt da hoffentlich nur mit einem Sender, oder?

    0
  • N

    jenz schrieb:

    @net, fleißig. sieht man mal, das unsere ersten varianten nicht so besonders waren. die ausgerollte ist halt am besten.

    ja, und die moral von der geschicht? schleifen haben in zeitkritischen codes nix zu suchen :p

    0
  • T

    net schrieb:

    jenz schrieb:

    @net, fleißig. sieht man mal, das unsere ersten varianten nicht so besonders waren. die ausgerollte ist halt am besten.

    ja, und die moral von der geschicht? schleifen haben in zeitkritischen codes nix zu suchen :p

    Ich würde eher sagen: die Moral von der Geschicht: Wer was misst misst Mist.

    Ich habe den Code auch mal ein wenig getestet und bin zu dem Ergebnis gekommen, daß es verschiedene Faktoren gibt, die das Ergebnis wesentlich beeinflussen können.

    Zunächst habe ich den Code auf Linux portiert, da ich hier kein Windows habe. Aber das sollte auf der Qualität der Aussagen keinen Einfluß haben. Auch habe ich die REPETITIONS ein wenig erhöht, um durch eine längere Laufzeit eine geringere Varianz zu erreichen.

    Wer einen großen Einfluß auf die Performance hat, ist natürlich der Optimierer. Und wenn der die read_bit-Funktion sieht, da lacht er doch nur darüber und optimiert sie weg. Und schon ist der ganze Test futsch :p .

    Also erst mal die read_bit-Funktion in eine separate Compilationseinheit und der Datensalat sieht schon anders aus. Und dann mit unterschiedlichen Optimierungsstufen testen. Unter Linux habe ich -O2 und -O3 getestet.

    Mit -O2 kam heraus, daß die "table"- und "loopless"-Varianten in etwa gleichauf sind. "mask" ist weit abgeschlagen. Mit -O3 dreht ändert sich das Bild. Da geben sich die Varianten nicht viel. Da ist die "loopless"-Variante eher ein wenig langsamer als die anderen. Also hier meine Ergebnisse:

    Mit -O2:

    mask: 22445
table: 10314
loopless: 9053
------------------------------
mask: 21564
table: 9924
loopless: 10185
------------------------------
mask: 21574
table: 10838
loopless: 9654
------------------------------
mask: 21998
table: 11176
loopless: 8998
------------------------------

    Und mit -O3:

    mask: 8213
table: 8611
loopless: 8869
------------------------------
mask: 8734
table: 7332
loopless: 9590
------------------------------
mask: 7781
table: 7943
loopless: 8882
------------------------------
mask: 7802
table: 8169
loopless: 8890
------------------------------

    Das gilt natürlich nur für den einen bestimmten Prozessor mit einem bestimmten Compiler unter einem bestimmten Betriebssystem. Bei solchen manuellen loop-unrolling spielt auch die Größe des Caches im Prozessor eine Rolle, wenn man das weiter treibt.

    Tntnet

    0
  • J

    cool, noch ein messer.

    da interessiert mich aber mal der generierte assemblercode. wundert mich, dass es sich nur durch die optimierung noch ändert.

    leider habe ich zur zeit keinen zugriff auf meine werkzeuge, bin ein bisschen in urlaub und habe nicht den eigenen rechner dabei...

    read_bit() sozusagen auszulagern finde ich ich gut. clever.

    aber was man auch noch berücksichtigen müsste irgendwie, wäre dass threadwechsel stattfinden, im normalfall. und dann auch gleich die luts aus den caches gefegt werden. höchstwahrscheinlich, oder nicht?

    still interested,
    jenz

    0
  • T

    Die Zeitscheiben im Betriebssystem sind schon groß genug, daß das mit der Cache-entleerung sicherlich keine allzu grosse Rolle spielt. Bis zum nächsten Prozeßwechsel schafft das Programm sicherlich einige Millionen Iterationen. Da macht es nicht viel aus, wenn der Cache bei der 1. direkt aus dem RAM lesen muß. Und selbst das gilt nur, wenn es etwas anderes zu tun gibt und das andere den Cache vollständig austauscht. Auf einem ansonsten unbelasteten Rechner sollte das also gar nichts ausmachen.

    Tntnet

    0
  • J

    ich würde aber davon ausgehen, das zwischen wenigen emfpangenen bits ein prozesswechsel stattfindet.
    einfach weil die einleseroutine dem bs mitteilt, "ich habe nichts mehr zu tun, der nächste bitte" wäre ja nur sinnvoll.
    und dann haben wir den wechsel öfter, als die zeitscheiben sagen, die daten liegen ja auch nicht immer so an, dass es passend zu den scheiben ist.

    aber da wird es dann wahrscheinlich doch ein wenig zu unsicher, oder?

    0
  • N

    tntnet schrieb:

    Wer einen großen Einfluß auf die Performance hat, ist natürlich der Optimierer. Und wenn der die read_bit-Funktion sieht, da lacht er doch nur darüber und optimiert sie weg. Und schon ist der ganze Test futsch :p .

    hey, solche tests darfste natürlich nicht mit optimierungen machen sonst haste so gut wie keine aussage über die geschwindigkeit. wenn der optimierer die 'read_bit' als eine feste '1' erkennt braucht er auch die abfragen nicht mehr zu machen. wenn er dann noch die schleife beseitigt, hat man plötzlich einen konstanten wert 'result = 0xffffffff' und wundert sich, warum die lut-version 1000-fach schneller ist als alles andere 😉

    einflüsse wie thread-switches und interrupts kann man ja etwas umgehen, indem man dem tester möglichst hohe prio gibt, die tests mehrfach ausführt und dann den mittelwert nimmt...

    das mit der schleife: es ist natürlich gut wenn ein compiler bei 'optimize for speed' schleifen selbständig beseitigt aber dummerweise hat man keinen einfluss darauf, nach welchen kriterien er's macht. manch einer löst nur kleine schleifen auf, um nicht zu viel code zu erzeugen. da kann man also ruhig mal nachhelfen wenn man ganz sicher gehen will. je weniger sich im schleifeninnern tut, desto mehr fällt die ausführung der schleife selber in's gewicht. also wenn's echt um mikrosekunden geht: schleifen, funktionsaufrufe, maschinenfremde datentypen (wie longs auf 16 bittern) und globale/statische variablen vermeiden etc. ...und immer schön das disassembly betrachten...;)

    0
  • H

    ich find' das ja irgendwie ganz niedlich wie steil ihr alle geht,
    aber welches problem diskutiert ihr hier ueberhaupt?
    keine api der welt uebertraegt einzelne bits...

    solche tests darfste natürlich nicht mit optimierungen machen
    sonst haste so gut wie keine aussage über die geschwindigkeit

    und ohne optimierung wohl auch nicht...

    0
Anmelden zum Antworten