unsigned int zu char[]

[Krishty]

Ich habe in den letzten Tagen mehrfach mit dem Gedanken gespielt, das zu optimieren – und jetzt hatte ich endlich Zeit dazu.

Testfall sind 10.000.000 unsigned int-Werte im Bereich von 0 bis 2 Milliarden, mit 1/f²-Verteilung (weil ich denke, dass auch in Wirklichkeit kleine Werte häufiger vorkommen als große):

  static auto const count = 10000000u;

  auto const toNumbers = new unsigned int[count];
  auto const toEndOfNumbers = toNumbers + count;
  for(auto it = toNumbers; it < toEndOfNumbers; ++it) {
    *it = ((unsigned long long)(rand()) * (unsigned long long)(rand()));
  }

Geschrieben wird in ein Array von Strings der Länge 11. Einmal allokiert und initialisiert (damit beim Beschreiben keine Seitenfehler ausgelöst werden):

  struct String {
    char chars[sizeof "4294967295"];
  };

  auto const toStrings = new String[count]();
  {
    LARGE_INTEGER start;
    QueryPerformanceCounter(&start);

    auto toInput = toNumbers;
    auto toOutput = toStrings;
    do {
      binaryToDecimal(*toInput, *toOutput);
    } while(++toOutput, ++toInput < toEndOfNumbers);

    LARGE_INTEGER end;
    QueryPerformanceCounter(&end);
    printf("%u\n", end.QuadPart - start.QuadPart);
  }

Damit Visual C++ nicht alles komplett wegoptimiert fügen wir eine Wirkung hinzu (Summe aller Buchstaben bilden und ausgeben):

  {
    auto sum      = 0u;
    auto toInput  = toNumbers;
    auto toOutput = toStrings;
    do {
      for(auto const & c : toOutput->chars) {
        sum += c;
      }
    } while(++toOutput, ++toInput < toEndOfNumbers);
    printf("%u", sum);
  }

Als Ausgangspunkt nehmen wir das _ultoa() der Visual C++ 2012-Laufzeitbibliothek:

  void __forceinline binaryToDecimal(
    unsigned int binary,
    String &     dec
  ) {
    _ultoa(binary, dec.chars, 10);
  }

Diese Funktion hat eine variable Basis eingebaut (man kann Dezimalzahlen genau so gut ausgeben wie Hexadezimalzahlen, Oktalzahlen, usw.). Sie ist dementsprechend nicht optimiert. Bei mir erreicht sie von fünf Durchläufen in den drei besten 1968845 1979530 2010110 Ticks. (Müsste je ungefähr eine Sekunde sein, ist aber nicht wichtig).

Mit einer Spezialisierung für Dezimalzahlen geht das schneller. Hier ist die Funktion, die ich seit einigen Jahren verwende:

  void __forceinline binaryToDecimal(
    unsigned int binary,
    String & dec
  ) {
    if(0 == binary) {
      dec.chars[0] = '\0';
      return;
    }

    auto * toCharacter = dec.chars;
    for(auto currentBase = 1000000000u; currentBase > 0; currentBase /= 10) {
      auto const currentDigit = binary / currentBase;
      // If at least one digit has already been written or if the current digit is non-zero, write it.
      if((toCharacter > dec.chars) || (0 < currentDigit)) {
        *toCharacter = ASCIICharacter('0' + currentDigit);
        ++toCharacter;
        binary %= currentBase; // (result is recycled from the division a few lines above)
      }
    }

    *toCharacter = '\0';
  }

Die erreicht in ihren drei besten Durchläufen bereits 1639562 1676771 1679365 Ticks. Sie hat also bestenfalls 20 % mehr Durchsatz.

Ich hatte die Idee, man könne das Suchen der höchsten Stelle und die Divisionen in einem Satz erschlagen indem man eine Funktion findet, die die Binärzahlen auf Binary Coded Decimals abbildet – also eine Ziffer pro vier Bits. Dann ist das Suchen der höchsten dezimalen Stelle die Suche nach dem höchsten Bit und eine Division durch 4. Leider muss man dabei auf 64-Bit-Mathematik ausweichen; aber durch geschickte Bitschieberei kann Visual C++ es ganz mit 32-Bit-Arithmetik realisieren:

  void __forceinline binaryToDecimal(
    unsigned int binary,
    String &     dec
  ) {
    if(0 == binary) {
      dec.chars[0] = '\0';
      return;
    }

    UnsignedInt8B bcd;
    auto const sum
      = (binary /         10)
      + (binary /        100 * 16)
      + (binary /       1000 * 16 * 16)
      + (binary /      10000 * 16 * 16 * 16)
      + (binary /     100000 * 16 * 16 * 16 * 16)
      + (binary /    1000000 * 16 * 16 * 16 * 16 * 16)
      + (binary /   10000000 * 16ull * 16 * 16 * 16 * 16 * 16)
      + (binary /  100000000 * 16ull * 16 * 16 * 16 * 16 * 16 * 16)
      + (binary / 1000000000 * 16ull * 16 * 16 * 16 * 16 * 16 * 16 * 16);
    bcd = binary + 6 * sum;

    unsigned long places;
    if(0 == _BitScanReverse(&places, bcd >> 32ull)) {
      _BitScanReverse(&places, (unsigned long)(bcd));
    } else {
      places += 32;
    }
    places = (places + 1 + 3) / 4;

    auto toChar = dec.chars + places;
    *toChar-- = '\0';
    do {
      *toChar = '0' | (bcd & 0xF);
      --toChar;
      bcd >>= 4;
    } while(0 != bcd);
  }

Diese Version erreicht nun immerhin 1054756 1055729 1056300 Ticks, also bestenfalls 87 % mehr Durchsatz als die Laufzeitbibliothek. Für doppelte Geschwindigkeit reicht es dann aber doch nicht.

Die Divisions- / Multiplikationspyramide oben ist, obwohl sie nur zu 9 Multiplikationen und einigen Bitverschiebungen kompiliert, sehr sperrig. Ein Experiment, sie loszuwerden, war die FPU: Die ist seit Beginn der 80er Jahre mit Hardware-Unterstützung für BCDs ausgerüstet. Der Befehl der Wahl ist FBSTP:

  static float const signAdjustment = 4294967296.0f;
  if(binary < 0x80000000) {
    __asm {
      FILD dword ptr binary
      FBSTP qword ptr bcd
    }
  } else {
    __asm {
      FILD dword ptr binary
      FADD dword ptr signAdjustment
      FBSTP qword ptr bcd
    }
  }

Funktioniert nur auf x86, aber ist ja einen Versuch wert! Leider sind Legacy-Befehle wie FBSTP eine Leistungskatastrophe. Die FPU-Konvertierungsfunktion statt der Pyramide punktet 3239838 3287966 3297928 Ticks, hat also 40 % weniger Durchsatz als _ultoa(). Sie ist drei Mal so langsam wie die Pyramide.

Ich kann jetzt nicht alles im Detail erläutern; insbesonder die Magic Numbers und den BCD-Kram. Heute abend habe ich hoffentlich mehr Zeit, dann trage ich das nach.

Falls ihr noch schnelle itoas rumliegen habt, vergleicht sie ruhig gegen _ultoa() und teilt die Ergebnisse mit!

[Krishty]

Ich hatte vergessen, die Abhängigkeitskette aufzubrechen (Visual C++ schnallt nicht, dass keine Überläufe auftreten):

  = ((binary /         10
  +   binary /        100 * 16)
  +  (binary /       1000 * 16    * 16
  +   binary /      10000 * 16    * 16 * 16))
  + ((binary /     100000 * 16    * 16 * 16 * 16
  +   binary /    1000000 * 16    * 16 * 16 * 16 * 16)
  +  (binary /   10000000 * 16ull * 16 * 16 * 16 * 16 * 16
  +   binary /  100000000 * 16ull * 16 * 16 * 16 * 16 * 16 * 16
  +   binary / 1000000000 * 16ull * 16 * 16 * 16 * 16 * 16 * 16 * 16));

974200 982861 984168, also 102 % mehr Durchsatz als die Laufzeitbibliothek. Unter x64 ist der Unterschied noch deutlicher – 129 % mehr.

[Krishty]

Man kann in den letzten drei Zeilen das 16ull * 16 * 16 * 16 * 16 * 16 ausklammern, dadurch kann viel länger mit 32 statt 64 Bits gerechnet werden. 909398 919051 923264 oder +116 %. Vielleicht sollte ich die 64 Bits von Hand auf 32+32 aufteilen; Visual C++ ist dabei ja sichtlich schwach. Nur leidet dann die 64-Bit-Version …

[eXile]

Lesestoff, siehe digits10/uint64ToAscii

[Krishty]

Oh ja; zwei Dezimalstellen auf einmal können wirklich eine Menge bringen. Mal ausprobieren.

[DerAlbi]

Also alle 3.322bit kommt eine Dezimalstelle hinzu. Kannst du den aufwand durch das Abschätzen der Anzahl der Dezimalstellen nicht optimieren?

Den 2er-Logarithmus bekommt man durch sizeof(..)-clz(...) und per Festkommareithmetik den 10er-Log:
(sizeof(..)-clz(...))*int(2^20/3.3219....)>>20 + 1.

clz (count leading zeros) ist defintitv auch irgendwo im Befehlssatz enthalten. Da must du dich nichtmal um die unterdrückung der führenden dezimal-nullen kümmern, da du mit dem Wissen des 10er-Logs keine unnötigen divisionen ausführst...

[Spiele Programmierer]

Wieso benutzt du nicht ggf. "_BitScanReverse64"?

[Krishty]

Erstmal eine kleine Korrektur: Auch nach der Division durch 1000000 muss man noch mit 64-Bit-Ganzzahlen arbeiten. Das kommt davon, wenn man nur Zahlen bis 2 mia testet :(

Also alle 3.322bit kommt eine Dezimalstelle hinzu. Kannst du den aufwand durch das Abschätzen der Anzahl der Dezimalstellen nicht optimieren?

Den 2er-Logarithmus bekommt man durch sizeof(..)-clz(...) und per Festkommareithmetik den 10er-Log:
(sizeof(..)-clz(...))*int(2^20/3.3219....)>>20 + 1.

Genau darauf wollte ich anfangs hinaus :) Ich hatte versucht, direkt eine logarithmische Funktion zu schreiben, die mir die BCDs ausspuckt. Das habe ich aber nicht geschafft, weil die Ausgabe immer 15 Schritte linear ist bevor ein Sprung gemäß log10 folgt (6 für 10…90; 96 für < 100…900; usw). Wegen dieser Stufenform bin ich bei der Pyramide gelandet.

clz (count leading zeros) ist defintitv auch irgendwo im Befehlssatz enthalten. Da must du dich nichtmal um die unterdrückung der führenden dezimal-nullen kümmern, da du mit dem Wissen des 10er-Logs keine unnötigen divisionen ausführst...

Ja; das ist das _BitScanReverse() das auch Spiele Programmierer meint.

Wieso benutzt du nicht ggf. "_BitScanReverse64"?

Habe ich in meiner 64-Bit-Version getan; aber ich wollte den 32-Bit-Quelltext hier nicht verkomplizieren. Ist 10–20 % schneller als zwei 32-Bit BSRs.

[Spiele Programmierer]

Has du mal geschaut, ob man vielleicht mit Vektorisierung (speziell SSE2) einen Schritt(Zb. BCD -> ASCII) noch beschleunigen kann? Vielleicht kann man sogar die Schleife am Ende komplett eliminieren, wenn man davon ausgehen kann, das der Buffer groß genug ist.

[DerAlbi]

OK,
aber deine Code-Beispiele haben immer mindestens so viele Divisionen und Multiplikationen wie die Zahl Dezimalstellen hat.
Ich weiß nicht, wieso das Rumgewurste mit BCD schneler sein soll als die naive Schleife:

Code: Alles auswählen

unsigned int Number = 400051567;
int Length = (_BitScanReverse(Number)*int((1<<23)/3.3219280948873))>>23;
//int Length = log10(Number); 
char Buffer[ganzivel] = {0};

do
{
	unsigned int New = Number/10;
	Buffer[Length--] = Number%10+'0'; //Buffer[Length--] = Number-(New*10)+'0';  div 10 spuckt den modulo eh mit aus... kostenlos.
	Number = New;
}while(Number);

Wenn kirsty die Schleife blöd findet, muss er ein Duffs-Device über "Length" nehmen.
Ich geb zu, ich bin völlig raus.

[Krishty]

Dass da eine Division steht bedeutet ja nicht, dass auch tatsächlich dividiert wird. Visual C++ optimiert die Divisionen zu Multiplikationen mit dem Reziprokwert in Festkommadarstellung – weil dafür sowieso Bitschieben nötig ist, werden die Multiplikationen mit 16^x direkt miterledigt. Die Multiplikation mit 6 ganz am Ende wird zu x + x + 4x. Ich habe also eine Multiplikation für jede bis auf die erste Dezimalstelle. Deine naive Schleife hat hingegen eine Multiplikation und eine Division (die auch zu Reziprokmultiplikation optimiert werden könnte) pro Dezimalstelle. Das deckt sich ungefähr damit, dass sie nur halb so schnell ist.

Dass jede Zeile von der vorherigen abhängt schmerzt in der Tat, aber das habe ich ja durch die Klammerung reduziert.

Das Ergebnis der Division produziert auf x86 immer auch das Modulo, ja. Das ist in der Messung meiner naiven Implementierung im Eingangspost auch schon einbegriffen (und sogar im Quelltext vermerkt ;) ).

Das Abschätzen des Aufwands (entweder via log10() oder durch if) ist etwas, das Alexandrescu ebenfalls vorschlägt. Ich habe nur immer Angst, mit sowas die Sprungvorhersage zu überfordern. Wird ebenfalls getestet!

[DerAlbi]

Ehh sry, irgendwie kam deine Antwort jetzt gerade erst an, die scheint aber schon 23Minuten zu existieren. Ich hab inzwischen nochmal hefigst rumeditiert, es tut mir leid, dass du dich auf Text beziehst, der nicht mehr da ist - ich hätt den nicht weggenommen, wenn den jemand referenziert.
Also ich habe jetzt gar keine Multiplikation mehr drin. nur noch das eine div. ist das wirklich sooh viel schlechter in der Performance? kannst du das mal testen?

[Krishty]

Has du mal geschaut, ob man vielleicht mit Vektorisierung (speziell SSE2) einen Schritt(Zb. BCD -> ASCII) noch beschleunigen kann? Vielleicht kann man sogar die Schleife am Ende komplett eliminieren, wenn man davon ausgehen kann, das der Buffer groß genug ist.

Bei SSE finde ich nativ keine Befehle, die BCD-kompatibel wären. Problematisch bei BCD ist, dass die BCD einer 32-Bit-Zahl 40 Bits groß ist – in SSE also nicht mehr reinpasst. AVX kann 64-Bit-Mathe; aber ich habe weder Erfahrungen damit noch eine CPU, auf der ich experimentieren könnte.

Mit genug Speicher wäre es deutlich einfacher; aber ich weiß nicht, ob ich davon ausgehen darf (was, wenn in einen Platzhalter geschrieben wird, der nur sechs Buchstaben weit ist weil man weiß, dass keine Zahlen über 999.999 vorkommen?) Perfekt wäre es mit 128-Bit-Mathematik: Dann könnte ich ein volles Byte für jede Dezimalziffer reservieren (so arbeiten auch die Legacy-x86-BCD-Befehle). Ein einziges OR mit 0x30303030303030303030 würde überall die ASCII-'0' aufaddieren (statt für jede Ziffer einzeln). Endianness-Vertauschung würde die Ziffern in die richtige Reihenfolge bringen (größte Ziffer vorn). Dann Bits nach links schieben bis die größte Ziffer vorne ist – CLZ (count leading zeroes) und zwei Bitverschiebungen. Schließlich ab in den Speicher mit dem Brocken. Bloß fünf Takte fürs Ausschreiben.

SSE ist zwar 128 Bits groß und bietet Shuffling (was Endianness-Vertauschung ermöglicht), aber nach allem, was ich bisher gehört habe, ist das nicht sonderlich schnell. Erst recht nicht, wenn man die Daten aus den General-Purpose-Registern in die SSE-Register kriegen muss (Spilling!).

Auf einer x64-CPU könnte man das zum Ausgeben von 16-Bit-Zahlen (fünf BCD-Bytes) erproben. Aber 16-Bit-Zahlen sind sogar mit naiven Algorithmen schon recht schnell.

[Krishty]

Ehh sry, irgendwie kam deine Antwort jetzt gerade erst an, die scheint aber schon 23Minuten zu existieren. Ich hab inzwischen nochmal hefigst rumeditiert, es tut mir leid, dass du dich auf Text beziehst, der nicht mehr da ist - ich hätt den nicht weggenommen, wenn den jemand referenziert.

Ich war auch ein Bisschen überrascht als alles weg war ;) Kein Ding.

Also ich habe jetzt gar keine Multiplikation mehr drin. nur noch das eine div. ist das wirklich sooh viel schlechter in der Performance? kannst du das mal testen?

Bin dabei.

Nachtrag: Deine Länge ist 1 zu kurz; ich inkrementiere sie. Ich nulle auch nicht das ganze Array (siehe Antwort an Spiele Programmierer mit dem Speicherblock) sondern setze nur die Null am Ende.

[DerAlbi]

Eigentlich nicht. Nach Durchlauf der Schleife steht bei mir immer eine -1 in Length. Das liegt am Post-Decrement beim letzen Schreibzugriff.
Wenn da mal ne -2 steht, liegts daran, dass der Festkomma-Logarithmus eine Bitungenauigkeit hat (sollte heftigst selten sein). Du kannst natürlich Buffer[Length+1]=0; vorher setzten, anstatt alles sinnlos zu nullen. Ich schreibe die Zahl eh rückwärts.

[Krishty]

Dein Ergebnis ist 28 % langsamer als die BCD-Methode. Visual C++ hat dabei die Division durch eine Reziprokmultiplikation ersetzt statt zu dividieren. Ich weiß nicht genau, wie es jetzt auf das Modulo kommt, aber dies sind die Befehle der inneren Schleife:

  mov   eax,0CCCCCCCDh //Reziprokwert von 10
  lea   r9,[r9-1]
  mul   eax,r8d
  shr   edx,3
  movzx eax,dl
  shl   al,2
  lea   ecx,[rax+rdx]
  add   cl,cl
  sub   r8b,cl
  add   r8b,30h
  mov   byte ptr [r9+1],r8b
  mov   r8d,edx
  test  edx,edx
  jne   main+0E0h

  unsigned long Length;
  _BitScanReverse(&Length, binary);
  Length = 1 + ((Length*int((1<<23)/3.3219280948873))>>23);

  auto * toCharacter = dec.chars + Length;
  *toCharacter-- = '\0';
  do {
    unsigned int New = binary/10;
    *toCharacter-- = binary%10+'0';
    binary = New;
  }while(binary);

Die Division wird wohl kaum schneller sein – von meiner naiven Version aus dem ersten Beitrag weiß ich, dass Visual C++ ein div produziert. Sie ist noch langsamer als deine.

Ich habe auch testweise ein if eingebaut damit bei Zahlen <= 999.999 ausschließlich 32-Bit-Rechnung benutzt wird. Leider ist auch das 2 % langsamer als vorher.

[Spiele Programmierer]

Ich habe gerade mal ein wenig experimentiert und mal SSE2 für den zweiten Teil eingesetzt. Sollte im ersten auch Möglich sein, wenn man die 64 Bit Operationen geschickt in 32 Bit umbastelt.
Diese Variante habe ich auf die Schnelle getestet, scheint zu funktionieren und ist bei mir leicht schneller. Besonders bei langen Zahlen. Wenn man davon ausgeht, dass der Buffer groß genug ist und man die Verzweigung in einen Shuffle + Write umbastellt, sollte noch mehr gehen:

Code: Alles auswählen

static const __m128i Mask0 = _mm_set1_epi8(0x0F);
static const __m128i Mask1 = _mm_set1_epi16(0x0F00);
static const __m128i AsciiMask = _mm_set1_epi8('0');
void __forceinline binaryToDecimalMy(unsigned int binary, String &     dec)
{
    //binary = 2987654321;
    std::uint64_t const sum  = ((binary / 10
        + binary / 100 * 16)
        + (binary / 1000 * 16 * 16
        + binary / 10000 * 16 * 16 * 16))
        + ((binary / 100000 * 16 * 16 * 16 * 16
        + binary / 1000000 * 16 * 16 * 16 * 16 * 16)
        + (binary / 10000000 * 16ull * 16 * 16 * 16 * 16 * 16
        + binary / 100000000 * 16ull * 16 * 16 * 16 * 16 * 16 * 16
        + binary / 1000000000 * 16ull * 16 * 16 * 16 * 16 * 16 * 16 * 16));
    std::uint64_t bcd = binary + 6 * sum;

    unsigned long places;
    if (_BitScanReverse64(&places, bcd))
    {
        /*__m128i Value = _mm_cvtsi64x_si128(bcd);
        const __m128i Zero = _mm_setzero_si128();
        Value = _mm_unpacklo_epi8(Value, Zero);
        __m128i ValueHigh = _mm_slli_epi16(Value, 4);
        Value = _mm_and_si128(Value, Mask0);+
        ValueHigh = _mm_and_si128(ValueHigh, Mask0);
        Value = _mm_or_si128(Value, ValueHigh);
        Value = _mm_or_si128(Value, AsciiMask);*/

        bcd = _byteswap_uint64(bcd); //8 Bit vertauschen
        __m128i Value = _mm_cvtsi64x_si128(bcd); //Geschwindigkeit dieses Befehl ist anders als deine Vermutungen "in Ordnung".
        Value = _mm_unpacklo_epi8(_mm_setzero_si128(), Value); //8Bit auf 16 Bit aufteilen.
        __m128i ValueLow = _mm_srli_epi16(Value, 12);
        __m128i ValueHigh = _mm_and_si128(Value, Mask1);
        Value = _mm_or_si128(ValueHigh, ValueLow); //Die 8Bits Daten, 8Bit interleaven.
        Value = _mm_or_si128(Value, AsciiMask); //BCD -> ASCII
        //Value enthält die Daten in umgekehrter Reihenfolge. ("Richtiger Reihenfolge")

        places = places >> 2;
        __assume(places < 10);
        switch (places)
        {
            case 0:
                Value = _mm_srli_si128(Value, 1);
                *(reinterpret_cast<std::uint16_t*>(dec.chars)) = _mm_extract_epi16(Value, 7);
                break;
            case 1:
                *(reinterpret_cast<std::uint16_t*>(dec.chars)) = _mm_extract_epi16(Value, 7);
                dec.chars[2] = 0;
                break;
            case 2:
                Value = _mm_srli_si128(Value, 13);
                *(reinterpret_cast<std::uint32_t*>(dec.chars)) = _mm_cvtsi128_si32(Value);
                break;
            case 3:
                Value = _mm_srli_si128(Value, 12);
                *(reinterpret_cast<std::uint32_t*>(dec.chars)) = _mm_cvtsi128_si32(Value);
                dec.chars[4] = 0;
                break;
            case 4:
                *(reinterpret_cast<std::uint16_t*>(dec.chars + 4)) = _mm_extract_epi16(Value, 7) >> 8;
                Value = _mm_srli_si128(Value, 11);
                *(reinterpret_cast<std::uint32_t*>(dec.chars)) = _mm_cvtsi128_si32(Value);
                break;
            case 5:
                *(reinterpret_cast<std::uint16_t*>(dec.chars + 4)) = _mm_extract_epi16(Value, 7);
                Value = _mm_srli_si128(Value, 10);
                *(reinterpret_cast<std::uint32_t*>(dec.chars)) = _mm_cvtsi128_si32(Value);
                dec.chars[6] = 0;
                break;
            case 6:
                Value = _mm_srli_si128(Value, 9);
                _mm_storel_epi64(reinterpret_cast<__m128i*>(dec.chars), Value);
                break;
            case 7:
                Value = _mm_srli_si128(Value, 8);
                _mm_storel_epi64(reinterpret_cast<__m128i*>(dec.chars), Value);
                break;
            case 8:
                *(reinterpret_cast<std::uint16_t*>(dec.chars + 8)) = _mm_extract_epi16(Value, 7) >> 8;
                Value = _mm_srli_si128(Value, 7);
                _mm_storel_epi64(reinterpret_cast<__m128i*>(dec.chars), Value);
                break;
            case 9:
                *(reinterpret_cast<std::uint16_t*>(dec.chars + 8)) = _mm_extract_epi16(Value, 7);
                Value = _mm_srli_si128(Value, 6);
                _mm_storel_epi64(reinterpret_cast<__m128i*>(dec.chars), Value);
                dec.chars[10] = 0;
                break;
        }

    }
    else
    {
        dec.chars[0] = '0';
        dec.chars[1] = 0;
    }
}

Beim Testen habe ich spontan festgestellt, das deine BCD-Funktion(die ich irgendwie nicht verstehe) zum Beispiel bei "2987654321" einen falschen Wert ausgibt.

EDIT:
Der Code-Tag ist hier ja ziemlich bescheiden. Sowohl Tabs als auch Leerzeichen werden entfernt(Obwohl im Editor vorhanden). Hellgrün auf Weiß ohne Syntaxhighlighting.

[Schrompf]

Hab Dein cn-Tag mal in ein [code=cpp umgewandelt, jetzt, sieht's ordentlich aus.

[Spiele Programmierer]

Ok, danke. :)
Zu meiner Verteidigung muss ich sagen, dass nirgends stand, wie es geht. ;)

[Krishty]

Ich habe gerade mal ein wenig experimentiert und mal SSE2 für den zweiten Teil eingesetzt. Sollte im ersten auch Möglich sein, wenn man die 64 Bit Operationen geschickt in 32 Bit umbastelt.
Diese Variante habe ich auf die Schnelle getestet, scheint zu funktionieren und ist bei mir leicht schneller. Besonders bei langen Zahlen.

Danke – wird gebencht :)

Beim Testen habe ich spontan festgestellt, das deine BCD-Funktion(die ich irgendwie nicht verstehe) zum Beispiel bei "2987654321" einen falschen Wert ausgibt.

Du meinst, places = (places + 1 + 3) / 4;? Kann sein. Ich habe sie sowieso zu 1 + BSR / 4 vereinfacht. Weil der Visual C++-Optimizer damit nicht klarkam, ist 1 + nun auch raus … also nochmal für alle die Richtigstellung meiner Funktion:

  places = places / 4;

  auto toChar = dec.chars + places;
  toChar[1] = '\0';
  do {
    *toChar = '0' | (bcd & 0xF);
    --toChar;
    bcd >>= 4;
  } while(0 != bcd);

Zu meiner Verteidigung muss ich sagen, dass nirgends stand, wie es geht. ;)

Dass man von jemand anders deswegen verbessert wird ist hier Teil des Aufnahmerituals – du hast nur zu lange kein C++ gepostet ;)

[Krishty]

Hab Dein cn-Tag mal in ein

Code: Alles auswählen

Bis auf die viertletzte Zeile, leider :( Warum ist das mit [cn]'\0'[/cn] passiert?

[Spiele Programmierer]

Gute Frage. Ist auf jeden Fall aber eine '0' und nicht eine '\0'.

[Krishty]

Ups – ja meinte ich :) Und die dritte Zeile? '\x30' oder so?

[Spiele Programmierer]

Auch '0'. '\x30' == '0'
Also irgendwie auch wieder richtig, deine Annahme.

[Krishty]

Sehr schön – läuft bei mir 20 % schneller als meins :) Nur schade, dass es x64-limitiert ist …

Vergiss bitte nicht, dass bei 1000000 auch mit 16ull zu multiplizieren.

[DerAlbi]

Ooooooch das ist doch blöd, wenn komplizierter Code schneller ist als einfacher :-(

[Krishty]

Hat das jemand auf Sandy Bridge oder aufwärts getestet? Dort sind viele Befehle Decoding-bound; die Schleifenvariante könnte dort tatsächlich schneller sein …

… und das wirkliche Oooooooooch ist doch, dass SSE keine Methode zur Verfügung stellt, beliebig viele Bytes zu schreiben – deshalb ist das switch ja erst nötig.

[Spiele Programmierer]

Ich hatte einen relativ neuen Haswell Prozessor zum testen verwendet. (i5-4570)

[DerAlbi]

Kirshty. Deine BCD-Zerlegung ist doch kacke so. Nen Haufen Rechenoperationen für nichts und wieder nichts, wenn die Zahl klein ist. Mich wurmt das :-D

Kannste daraus nicht nen Duff-Device machen? Wenn du die Länge der BCD-Zahl kennst (über den 10er-Log) müsste man da doch noch sparen können.

[Krishty]

Habe ich gemacht: Wenn die Zahl < 999.999 ist, nehme ich die Abkürzung mit weniger als der Hälfte der Rechenoperationen. War 2 % langsamer ;)

Für alles Kleinere kann man auch direkt 16-Bit-Zahlen nehmen. Ab 9.999 geht Spiele Programmierers Version ohne SSE direkt in den 64-Bit-Registern :)