Wykorzystanie właściwości IEEE 754 do zaokrąglenia i zmiany na uint64 tak, żeby działało w przypadku brzegowym z .5 po przecinku

0

Cześć, bawię się w robocie doublami. Jest kawałek kodu gdzie możemy przyjąć pewne założenia co do standardu (IEEE 754) oraz możliwych trzymanych wartości. W tym kawałku kodu muszę w pewnym momencie zaokrąglić wartość i zamienić na inta. Te miejsce kodu jest o tyle ciekawe, że fajnie by było nie używać relatwnie wolnego std::round. Używam sztuczki wykorzystującej właściwości ieee, żeby w mantysie znalazła się zaokrąglona wartość, potem szybki AND i mamy wszystko w uint64_t.

Problem jest z zaokrągleniem gdy po przecinku mamy .5. Oczywiście jak jest piątka, to powinno zaokrąglić w górę. No ale nie zaokrągla. Jak po przecinku są wartości 0.{6,7,8,9}, to kod śmiga jak trzeba.

Sztuczka jest opisana tu: https://stackoverflow.com/a/17035583
Kod wygląda powiedzmy tak:

std::uint64_t my_round(double d) {
    d += 6755399441055744.0;

    std::uint64_t roundedValue;
    const std::byte *dPtr = reinterpret_cast<const std::byte *>(&d);
    std::memcpy(&roundedValue, dPtr, sizeof(roundedValue));

    return roundedValue & std::uint64_t{0x7FFFFFFFFFFFF};
}


// Wyteguje się bo `roundedValue == 284464158943456`
assert(my_round(284464158943456.5) == 284464158943457ul)

// Przejdzie
assert(my_round(284464158943456.6) == 284464158943457ul)

No to ten, jakieś pomysły? Założenie jest takie, żeby kod był jak najszybszy. Jak zawlimy wydajność, to mogę równie dobrze wrócić do std::round :)

0

Hmm używasz stockowego algosa - powinien działać, tutaj alternatywna implementacja oparta o unie: https://gist.github.com/jcward/47e6defd8dfec2949e14#file-main-hx-L18

inline int float2int( double d )
{
   union Cast
   {
      double d;
      long l;
    };
   volatile Cast c;
   c.d = d + 6755399441055744.0;
   return c.l;
}

W sumie potwierdzam to nie działa dla 332.5, lol jest też komentarz https://stackoverflow.com/questions/429632/how-to-speed-up-floating-point-to-integer-number-conversion - no cóż wygląda na trade off za szybkość...

0

Z uniami jest ten problem, że masz UB.

no cóż wygląda na trade off za szybkość

Nie biorę takiej odpowiedzi ^^ trzeba coś wymyślić

0

screenshot-20210714113159.png

Ciekawe jest natomiast to dlaczego algo nie działa - okazuje się że po prostu że stała 6755399441055744.0 jest na tyle duża że double zaczynają tracić dokładność. Liczby [0 - 8) są zaokrąglane poprawnie. Raczej tego prosto nie naprawisz...

Można by jeszcze popróbować z trybem zaokrągleń (https://stackoverflow.com/a/6867722/1779504) no ale to może popsuć coś innego...

0

Tak, 6755399441055744.0 jest duże i o to właśnie chodzi. Dodając to umieszczam moją liczbę w zakresie 2^52 - 2^53, dzięki czamu w mantysie mam mojego inta i wystarczy AND.
Założenie jest takie, że dodanie mojego doubla do tej dużej stałej zaokrągli co trzeba. Tylko jak widać z .5 ma problem.

Z trybem zaokrągleń nie chcę mieszać bo jest za dużo do popsucia.

Ogólnie mam wrażenie, że da się coś tu wymyślić. Tylko jeszcze nie wiem co. Dlatego przyszedłem do Was, może będą jakieś pomysły

1

@MarekR22: żeby nie być gołosłownym takie wychodzą benchmarki. Tam się trochę więcej dzieje w funkcji niż tylko zaokrąglanie, ale sama metoda zaokrąglania ma taki wpływ. (oczywiście .5 nie jest jeszcze ogarnięte, więc mogą być zmiany w wynikach po ogarnięciu tego przypadku)

---------------------------------------------------------
Benchmark                   Time           CPU Iterations
---------------------------------------------------------
FromDoubleStdRound         68 ns         68 ns   10052805
FromDoubleMagic            30 ns         30 ns   23288550
5

Miał być komentarz, wyjdzie cały post ;)
@MarekR22: problemem jest obsługa floating point exceptions w procesorze. -fno-trapping-math pozwala na inlinowanie, pytanie na ile @stryku chce to zaryzykować.

https://godbolt.org/z/MvP4bzMqb
Można jeszcze obsługę errno wyłączyć dla FP, ale tutaj nic ona wg Godbolta nie zmienia.
warto też to poczytać: https://gcc.gnu.org/wiki/FloatingPointMath

0

Dzięki @alagner ! Poczytam na pewno, ale nie wiem czy chcę zmieniać semantykę dla całego wszechświata, żeby ogarnąć moje przypadki :)
Zobaczę jak benchmarki z tym wychodzą i czy warto się zastanawiać

2

W sumie nie dałem znać jak ta hustoria się skończyła.
Uznaliśmy, że zysk wydajności jest większy niż problemy z zaokrąglaniem w przytoczonych przypadkach. Kod śmiga na pradukcji od sierpnia i działa wyśmienicie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1