On Thursday, 27 February 2020 at 09:33:28 UTC, Dennis Cote wrote:
On Wednesday, 26 February 2020 at 00:50:35 UTC, Basile B. wrote:
So after reading the translation of RYU I was interested too
see if the decimalLength() function can be written to be
faster, as it cascades up to 8 CMP.
Perhaps you could try something like this.
<code>
int decimalDigitLength(ulong n) {
if (n < 10000)
if (n < 100)
return n < 10 ? 1 : 2;
else
return n < 1000 ? 3 : 4;
else
if (n < 100000000)
if (n < 1000000)
return n < 100000 ? 5 : 6;
else
return n < 10000000 ? 7 : 8;
else
if (n < 1000000000000)
if (n < 10000000000)
return n < 1000000000 ? 9 : 10;
else
return n < 100000000000 ? 11 : 12;
else
if (n < 10000000000000000)
if (n < 100000000000000)
return n < 10000000000000 ? 13
: 14;
else
return n < 1000000000000000 ?
15 : 16;
else
if (n < 1000000000000000000)
return n < 100000000000000000 ?
17 : 18;
else
return n < 10000000000000000000
? 19 : 20;
}
</code>
This uses at most 6 compares for any 64 bit number and only 3
for the most common small numbers less than 10000.
I was glad to see that with ldc at run.dlang.io using the -O3
optimization I could change the function signature to match
yours and the compiler eliminated all the unreachable dead code
for larger values. The compiler produced the following assembler
<code>
.section .text.ubyte
onlineapp.decimalLength9(uint),"axG",@progbits,ubyte
onlineapp.decimalLength9(uint),comdat
.globl ubyte onlineapp.decimalLength9(uint)
.p2align 4, 0x90
.type ubyte onlineapp.decimalLength9(uint),@function
ubyte onlineapp.decimalLength9(uint):
.cfi_startproc
cmpl $9999, %edi
ja .LBB1_5
cmpl $99, %edi
ja .LBB1_4
cmpl $10, %edi
movb $2, %al
sbbb $0, %al
retq
.LBB1_5:
cmpl $99999999, %edi
ja .LBB1_9
cmpl $999999, %edi
ja .LBB1_8
cmpl $100000, %edi
movb $6, %al
sbbb $0, %al
retq
.LBB1_4:
cmpl $1000, %edi
movb $4, %al
sbbb $0, %al
retq
.LBB1_9:
cmpl $1000000000, %edi
movb $10, %al
sbbb $0, %al
retq
.LBB1_8:
cmpl $10000000, %edi
movb $8, %al
sbbb $0, %al
retq
.Lfunc_end1:
.size ubyte onlineapp.decimalLength9(uint), .Lfunc_end1-ubyte
onlineapp.decimalLength9(uint)
.cfi_endproc
</code>
for the same body with signature ubyte decimalLength9(uint n).
This may be faster than your sequential comparison function
depending upon the distribution of numbers. In real
applications, small numbers are far more common so the reduced
number of compares for those values should be beneficial in
most cases.
Sorry but no. I think that you have missed how this has changed
since the first message.
1. the way it was tested initially was wrong because LLVM was
optimizing some stuff in some tests and not others, due to
literals constants.
2. Apparently there would be a branchless version that's fast
when testing with unbiased input (to be verified)
this version is:
---
ubyte decimalLength9_4(const uint v) pure nothrow
{
return 1 + (v >= 10) +
(v >= 100) +
(v >= 1000) +
(v >= 10000) +
(v >= 100000) +
(v >= 1000000) +
(v >= 10000000) +
(v >= 100000000) ;
}
---
but i cannot see the improvment when use time on the test program
and 100000000 calls feeded with a random number.
see
https://forum.dlang.org/post/ctidwrnxvwwkouprj...@forum.dlang.org
for the latest evolution of the discussion.
