www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Strange counter-performance in an alternative `decimalLength9`

reply Basile B. <b2.temp gmx.com> writes:
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.

After struggling with bad ideas I finally find something that 
looks nice:

- count the leading zero of the input
- switch() this count to have in the worst of the cases only 1 
CMP (when the bit number possibly changes the digit count, e.g 9 
-> 10 (when bsr(input) == 4)

after writing all the values allowing to know the cases where a 
comparison is necessary...

   min2 = 0b10
   max2 = 0b11
   min3 = 0b100
   max3 = 0b111
   ...
   ...
   min32 = 0b100.......0
   max32 = 0b111.......1

...I finally write the "nice" thing.

---

import std.stdio;

ubyte decimalLength9(const uint v)
{
     if (v >= 100000000) { return 9; }
     if (v >= 10000000) { return 8; }
     if (v >= 1000000) { return 7; }
     if (v >= 100000) { return 6; }
     if (v >= 10000) { return 5; }
     if (v >= 1000) { return 4; }
     if (v >= 100) { return 3; }
     if (v >= 10) { return 2; }
     return 1;
}

ubyte fdecimalLength9(const uint v) pure nothrow
{
     import core.bitop;
     const ubyte lzc = cast(ubyte) (bsr(v) + 1);
     ubyte result;
     switch (lzc)
     {
         case 0 :
         case 1 :
         case 2 :
         case 3 : result =  1; break;
         case 4 : result =  v >= 10  ? 2 : 1; break;
         case 5 :
         case 6 : result =  2; break;
         case 7 : result =  v >= 100  ? 3 : 2; break;
         case 8 :
         case 9 : result =  3; break;
         case 10: result =  v >= 1000  ? 4 : 3; break;
         case 11:
         case 12:
         case 13: result =  4; break;
         case 14: result =  v >= 10000  ? 5 : 4; break;
         case 15:
         case 16: result =  5; break;
         case 17: result =  v >= 100000  ? 6 : 5; break;
         case 18:
         case 19: result =  6; break;
         case 20: result =  v >= 1000000  ? 7 : 6; break;
         case 21:
         case 22:
         case 23: result =  7; break;
         case 24: result =  v >= 10000000  ? 8 : 7; break;
         case 25:
         case 26: result =  8; break;
         case 27: result =  v >= 100000000  ? 9 : 8; break;
         case 28:
         case 29:
         case 30:
         case 31:
         case 32: result =  9; break;
         default: assert(false);
     }
     return result;
}

private ubyte ffdecimalLength9(const uint v) pure nothrow
{
     import core.bitop;
     const ubyte lzc = cast(ubyte) (bsr(v) + 1);
     static immutable pure nothrow ubyte function(uint)[33] tbl =
     [
     0 : (uint a) => ubyte(1),
     1 : (uint a) => ubyte(1),
     2 : (uint a) => ubyte(1),
     3 : (uint a) => ubyte(1),
     4 : (uint a) => a >= 10  ? ubyte(2) : ubyte(1),
     5 : (uint a) => ubyte(2),
     6 : (uint a) => ubyte(2),
     7 : (uint a) => a >= 100  ? ubyte(3) : ubyte(2),
     8 : (uint a) => ubyte(3),
     9 : (uint a) => ubyte(3),
     10: (uint a) => a >= 1000  ? ubyte(4) : ubyte(3),
     11: (uint a) => ubyte(4),
     12: (uint a) => ubyte(4),
     13: (uint a) => ubyte(4),
     14: (uint a) => a >= 10000  ? ubyte(5) : ubyte(4),
     15: (uint a) => ubyte(5),
     16: (uint a) => ubyte(5),
     17: (uint a) => a >= 100000  ? ubyte(6) : ubyte(5),
     18: (uint a) => ubyte(6),
     19: (uint a) => ubyte(6),
     20: (uint a) => a >= 1000000  ? ubyte(7) : ubyte(6),
     21: (uint a) => ubyte(7),
     22: (uint a) => ubyte(7),
     23: (uint a) => ubyte(7),
     24: (uint a) => a >= 10000000  ? ubyte(8) : ubyte(7),
     25: (uint a) => ubyte(8),
     26: (uint a) => ubyte(8),
     27: (uint a) => a >= 100000000  ? ubyte(9) : ubyte(8),
     28: (uint a) => ubyte(9),
     29: (uint a) => ubyte(9),
     30: (uint a) => ubyte(9),
     31: (uint a) => ubyte(9),
     32: (uint a) => ubyte(9),
     ];
     return tbl[lzc](v);
}

void main()
{
     import std.datetime.stopwatch, std.range, std.algorithm;

     int s1, s2, s3;
     benchmark!({ iota(100000000u).each!(a => s1 += 
decimalLength9(a+1)); })(10).writeln;
     benchmark!({ iota(100000000u).each!(a => s2 += 
fdecimalLength9(a+1));})(10).writeln;
     benchmark!({ iota(100000000u).each!(a => s3 += 
ffdecimalLength9(a+1));})(10).writeln;
     assert(s1 == s2);
     assert(s1 == s3);
}
---

Then bad surprise. Even with ldmd (so ldc2 basically) feeded with 
the args from the script line. Maybe the fdecimalLength9 version 
is slightly faster. Only *slightly*. Good news, I've lost my 
time. So I try an alternative version that uses a table of 
delegates instead of a switch (ffdecimalLength9) and surprise, 
"tada", it is like **100x** slower then the two others.

How is that possible ?
Feb 25 2020
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Feb 26, 2020 at 12:50:35AM +0000, Basile B. via Digitalmars-d-learn
wrote:
[...]

[...] TBH, I'm skeptical of any performance results using dmd. I wouldn't pay attention to performance numbers obtained this way, and rather look at the ldmd/ldc2 numbers. [...]
 Then bad surprise. Even with ldmd (so ldc2 basically) feeded with the
 args from the script line. Maybe the fdecimalLength9 version is
 slightly faster.  Only *slightly*. Good news, I've lost my time. So I
 try an alternative version that uses a table of delegates instead of a
 switch (ffdecimalLength9) and surprise, "tada", it is like **100x**
 slower then the two others.
 
 How is that possible ?
Did you check the assembly output to see what the difference is? Delegates involve a function call, which involves function call overhead, which includes a CPU pipeline hazard. Worse yet it's an indirect call, meaning you're defeating the CPU branch predictor and invalidating the instruction cache. And on top of that, delegates involve allocating a context, and you *really* do not want allocations inside an inner loop. And of course, normal function calls are easier for compilers to inline, because the destination is fixed. Indirect calls involving delegates are hard to predict, and the optimizer is more liable to just give up. These are just my educated guesses, of course. For the real answer, look at the assembly output. :-D T -- What are you when you run out of Monet? Baroque.
Feb 25 2020
parent Basile B. <b2.temp gmx.com> writes:
On Wednesday, 26 February 2020 at 01:10:07 UTC, H. S. Teoh wrote:
 On Wed, Feb 26, 2020 at 12:50:35AM +0000, Basile B. via 
 Digitalmars-d-learn wrote: [...]

[...] TBH, I'm skeptical of any performance results using dmd. I wouldn't pay attention to performance numbers obtained this way, and rather look at the ldmd/ldc2 numbers.
I didn't use DMD. The script line is actually interpreted by the IDE. It drops the compiler name and just parse the arg and pass them to a compiler that's defined by non overridable options. In my case I used LDMD (this is LDC you see, but with a DMD like options syntax)
Feb 25 2020
prev sibling next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
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.

 [...]
It can be made faster using binary search. Not by much though. You'll get ceil(log2(numberofplaces)) cmps.
Feb 26 2020
prev sibling next sibling parent reply Basile B. <b2.temp gmx.com> writes:
On Wednesday, 26 February 2020 at 00:50:35 UTC, Basile B. wrote:
 How is that possible ?
It turns out that there's a problem with the benchmarking method. With command line argument the different optimization passes of LLVM don't fuck up with the literal constants. It appears that none of the alternatives based on the "most significant bit trick" are faster (at least when covering a decent range of numbers): --- -mattr=+sse2,+sse3,+sse4.1,+sse4.2,+fast-lzcnt,+avx,+avx2,+cmov,+bmi,+bmi2 import core.memory; import core.bitop; import std.stdio; import std.range; import std.algorithm; import std.getopt; ubyte decimalLength9_0(const uint v) { if (v >= 100000000) { return 9; } if (v >= 10000000) { return 8; } if (v >= 1000000) { return 7; } if (v >= 100000) { return 6; } if (v >= 10000) { return 5; } if (v >= 1000) { return 4; } if (v >= 100) { return 3; } if (v >= 10) { return 2; } return 1; } ubyte decimalLength9_1(const uint v) pure nothrow { if (v == 0) // BSR and LZCNT UB when input is 0 return 1; const ubyte lzc = cast(ubyte) bsr(v); ubyte result; switch (lzc) { case 0 : case 1 : case 2 : result = 1; break; case 3 : result = v >= 10 ? 2 : 1; break; case 4 : case 5 : result = 2; break; case 6 : result = v >= 100 ? 3 : 2; break; case 7 : case 8 : result = 3; break; case 9 : result = v >= 1000 ? 4 : 3; break; case 10: case 11: case 12: result = 4; break; case 13: result = v >= 10000 ? 5 : 4; break; case 14: case 15: result = 5; break; case 16: result = v >= 100000 ? 6 : 5; break; case 17: case 18: result = 6; break; case 19: result = v >= 1000000 ? 7 : 6; break; case 20: case 21: case 22: result = 7; break; case 23: result = v >= 10000000 ? 8 : 7; break; case 24: case 25: result = 8; break; case 26: result = v >= 100000000 ? 9 : 8; break; case 27: case 28: case 29: case 30: case 31: result = 9; break; default: assert(false); } return result; } private ubyte decimalLength9_2(const uint v) pure nothrow { if (v == 0) // BSR and LZCNT UB when input is 0 return 1; const ubyte lzc = cast(ubyte) bsr(v); static immutable pure nothrow ubyte function(uint)[32] tbl = [ 0 : (uint a) => ubyte(1), 1 : (uint a) => ubyte(1), 2 : (uint a) => ubyte(1), 3 : (uint a) => a >= 10 ? ubyte(2) : ubyte(1), 4 : (uint a) => ubyte(2), 5 : (uint a) => ubyte(2), 6 : (uint a) => a >= 100 ? ubyte(3) : ubyte(2), 7 : (uint a) => ubyte(3), 8 : (uint a) => ubyte(3), 9 : (uint a) => a >= 1000 ? ubyte(4) : ubyte(3), 10: (uint a) => ubyte(4), 11: (uint a) => ubyte(4), 12: (uint a) => ubyte(4), 13: (uint a) => a >= 10000 ? ubyte(5) : ubyte(4), 14: (uint a) => ubyte(5), 15: (uint a) => ubyte(5), 16: (uint a) => a >= 100000 ? ubyte(6) : ubyte(5), 17: (uint a) => ubyte(6), 18: (uint a) => ubyte(6), 19: (uint a) => a >= 1000000 ? ubyte(7) : ubyte(6), 20: (uint a) => ubyte(7), 21: (uint a) => ubyte(7), 22: (uint a) => ubyte(7), 23: (uint a) => a >= 10000000 ? ubyte(8) : ubyte(7), 24: (uint a) => ubyte(8), 25: (uint a) => ubyte(8), 26: (uint a) => a >= 100000000 ? ubyte(9) : ubyte(8), 27: (uint a) => ubyte(9), 28: (uint a) => ubyte(9), 29: (uint a) => ubyte(9), 30: (uint a) => ubyte(9), 31: (uint a) => ubyte(9), ]; return tbl[lzc](v); } ubyte decimalLength9_3(const uint v) pure nothrow { if (v == 0) // BSR and LZCNT UB when input is 0 return 1; ubyte result; const ubyte lzc = cast(ubyte) bsr(v); const ubyte[32] decimalLength9LUT = [ 0 : ubyte(1), 1 : ubyte(1), 2 : ubyte(1), 3 : ubyte(10), 4 : ubyte(2), 5 : ubyte(2), 6 : ubyte(11), 7 : ubyte(3), 8 : ubyte(3), 9 : ubyte(12), 10: ubyte(4), 11: ubyte(4), 12: ubyte(4), 13: ubyte(12), 14: ubyte(5), 15: ubyte(5), 16: ubyte(13), 17: ubyte(6), 18: ubyte(6), 19: ubyte(14), 20: ubyte(7), 21: ubyte(7), 22: ubyte(7), 23: ubyte(15), 24: ubyte(8), 25: ubyte(8), 26: ubyte(16), 27: ubyte(9), 28: ubyte(9), 29: ubyte(9), 30: ubyte(9), 31: ubyte(9), ]; ubyte resultOrSelector = decimalLength9LUT[lzc]; if (resultOrSelector < 10) result = resultOrSelector; else switch (lzc) { case 3 : result = v >= 10 ? 2 : 1; break; case 6 : result = v >= 100 ? 3 : 2; break; case 9 : result = v >= 1000 ? 4 : 3; break; case 13: result = v >= 10000 ? 5 : 4; break; case 16: result = v >= 100000 ? 6 : 5; break; case 19: result = v >= 1000000 ? 7 : 6; break; case 23: result = v >= 10000000 ? 8 : 7; break; case 26: result = v >= 100000000 ? 9 : 8; break; default: assert(false); } return result; } void main(string[] args) { uint sum; uint count; ubyte func; GC.disable; getopt(args, config.passThrough, "c|count", &count, "f|func", &func); static const funcs = [&decimalLength9_0, &decimalLength9_1, &decimalLength9_2, &decimalLength9_3]; foreach (i; 0 .. count) sum += funcs[func](i); writeln(sum); } --- Results: --- [mr_x pc1 temp]$ time ./declen --count=100000000 --func=0 788888890 real 0m0,207s user 0m0,203s sys 0m0,003s [mr_x pc1 temp]$ time ./declen --count=100000000 --func=1 788888890 real 0m0,369s user 0m0,366s sys 0m0,002s [mr_x pc1 temp]$ time ./declen --count=100000000 --func=2 788888890 real 0m0,271s user 0m0,264s sys 0m0,003s [mr_x pc1 temp]$ time ./declen --count=100000000 --func=3 788888890 real 0m0,253s user 0m0,250s sys 0m0,002s --- That's pathetic ;)
Feb 26 2020
parent reply Bruce Carneal <bcarneal gmail.com> writes:
On Wednesday, 26 February 2020 at 13:50:11 UTC, Basile B. wrote:
 On Wednesday, 26 February 2020 at 00:50:35 UTC, Basile B. wrote:
 ...
     foreach (i; 0 .. count)
         sum += funcs[func](i);
The input stream is highly predictable and strongly skewed towards higher digits. The winning function implementation lines up with that distribution. It would not fare as well with higher entropy input.
Feb 26 2020
parent reply Bruce Carneal <bcarneal gmail.com> writes:
On Wednesday, 26 February 2020 at 19:44:05 UTC, Bruce Carneal 
wrote:
 On Wednesday, 26 February 2020 at 13:50:11 UTC, Basile B. wrote:
 On Wednesday, 26 February 2020 at 00:50:35 UTC, Basile B. 
 wrote:
 ...
     foreach (i; 0 .. count)
         sum += funcs[func](i);
The input stream is highly predictable and strongly skewed towards higher digits. The winning function implementation lines up with that distribution. It would not fare as well with higher entropy input.
Using sorted equi-probable inputs (N 1 digit numbers, N 2 digit numbers, ...) decimalLength9_0 beats a simple branchless implementation by about 10%. After shuffling the input, branchless wins by 2.4X (240%).
Feb 26 2020
parent reply Basile B. <b2.temp gmx.com> writes:
On Wednesday, 26 February 2020 at 20:44:31 UTC, Bruce Carneal 
wrote:
 The winning function implementation lines up with that 
 distribution.  It would not fare as well with higher entropy 
 input.
Using sorted equi-probable inputs (N 1 digit numbers, N 2 digit numbers, ...) decimalLength9_0 beats a simple branchless implementation by about 10%. After shuffling the input, branchless wins by 2.4X (240%).
I've replaced the input by the front of a rndGen (that pops for count times and starting with a custom seed) and I never see the decimalLength9_3 (which seems to be the closest to the original in term of performances) doing better. Maybe you talked about another implementation of decimalLength9 ?
Feb 26 2020
parent reply Bruce Carneal <bcarneal gmail.com> writes:
On Wednesday, 26 February 2020 at 23:09:34 UTC, Basile B. wrote:
 On Wednesday, 26 February 2020 at 20:44:31 UTC, Bruce Carneal 
 wrote:
 After shuffling the input, branchless wins by 2.4X (240%).
I've replaced the input by the front of a rndGen (that pops for count times and starting with a custom seed) and I never see the decimalLength9_3 (which seems to be the closest to the original in term of performances) doing better.
The uniform random uint distribution yields a highly skewed digits distribution. Note, for example, that only 10 of the 2**32 possible outputs from a uint PRNG can be represented by a single decimal digit. Your current winner will be very hard to beat if the inputs are uniform random. That implementation's high-to-low cascade of early exit ifs aligns with PRNG output. If you aren't sure what the input distribution is, or want guaranteed good worst case behavior, then branchless may be a better way to go.
 Maybe you talked about another implementation of decimalLength9 
 ?
Yes. It's one I wrote after I saw your post. Psuedo-code here: auto d9_branchless(uint v) { return 1 + (v >= 10) + (v >= 100) ... } Using ldc to target an x86 with the above yields a series of cmpl, seta instruction pairs in the function body followed by a summing and a return. No branching. Let me know if the above is unclear or insufficient.
Feb 26 2020
next sibling parent Bruce Carneal <bcarneal gmail.com> writes:
On Thursday, 27 February 2020 at 03:58:15 UTC, Bruce Carneal 
wrote:
 On Wednesday, 26 February 2020 at 23:09:34 UTC, Basile B. wrote:
 On Wednesday, 26 February 2020 at 20:44:31 UTC, Bruce Carneal 
 wrote:
 After shuffling the input, branchless wins by 2.4X (240%).
snip Let me know if the above is unclear or insufficient.
The 2.4X improvement came when using a shuffled uniform digits distribution. Equal numbers of 1 digit values, 2 digit values, ... put in to an array and shuffled. Branchless *loses* by 8.5% or so on my Zen1 when the array is not shuffled (when branch predictions are nearly perfect).
Feb 26 2020
prev sibling parent reply Basile B. <b2.temp gmx.com> writes:
On Thursday, 27 February 2020 at 03:58:15 UTC, Bruce Carneal 
wrote:
 Maybe you talked about another implementation of 
 decimalLength9 ?
Yes. It's one I wrote after I saw your post. Psuedo-code here: auto d9_branchless(uint v) { return 1 + (v >= 10) + (v >= 100) ... } Using ldc to target an x86 with the above yields a series of cmpl, seta instruction pairs in the function body followed by a summing and a return. No branching. Let me know if the above is unclear or insufficient.
No thanks, it's crystal clear now.
Feb 26 2020
parent reply Basile B. <b2.temp gmx.com> writes:
On Thursday, 27 February 2020 at 04:44:56 UTC, Basile B. wrote:
 On Thursday, 27 February 2020 at 03:58:15 UTC, Bruce Carneal 
 wrote:
 Maybe you talked about another implementation of 
 decimalLength9 ?
Yes. It's one I wrote after I saw your post. Psuedo-code here: auto d9_branchless(uint v) { return 1 + (v >= 10) + (v >= 100) ... } Using ldc to target an x86 with the above yields a series of cmpl, seta instruction pairs in the function body followed by a summing and a return. No branching. Let me know if the above is unclear or insufficient.
No thanks, it's crystal clear now.
although I don't see the performance gain. Now for me an hybrid version based on a LUT and on the branchless one is the fatest (decimalLength9_5), although still slowest then the original. updated program, incl your branchless version (decimalLength9_4): --- -mattr=+sse2,+sse3,+sse4.1,+sse4.2,+fast-lzcnt,+avx,+avx2,+cmov,+bmi,+bmi2 import core.memory; import core.bitop; import std.stdio; import std.range; import std.algorithm; import std.getopt; import std.random; ubyte decimalLength9_0(const uint v) { if (v >= 100000000) { return 9; } if (v >= 10000000) { return 8; } if (v >= 1000000) { return 7; } if (v >= 100000) { return 6; } if (v >= 10000) { return 5; } if (v >= 1000) { return 4; } if (v >= 100) { return 3; } if (v >= 10) { return 2; } return 1; } ubyte decimalLength9_1(const uint v) pure nothrow { if (v == 0) // BSR and LZCNT UB when input is 0 return 1; const ubyte lzc = cast(ubyte) bsr(v); ubyte result; switch (lzc) { case 0 : case 1 : case 2 : result = 1; break; case 3 : result = v >= 10 ? 2 : 1; break; case 4 : case 5 : result = 2; break; case 6 : result = v >= 100 ? 3 : 2; break; case 7 : case 8 : result = 3; break; case 9 : result = v >= 1000 ? 4 : 3; break; case 10: case 11: case 12: result = 4; break; case 13: result = v >= 10000 ? 5 : 4; break; case 14: case 15: result = 5; break; case 16: result = v >= 100000 ? 6 : 5; break; case 17: case 18: result = 6; break; case 19: result = v >= 1000000 ? 7 : 6; break; case 20: case 21: case 22: result = 7; break; case 23: result = v >= 10000000 ? 8 : 7; break; case 24: case 25: result = 8; break; case 26: result = v >= 100000000 ? 9 : 8; break; case 27: case 28: case 29: case 30: case 31: result = 9; break; default: assert(false); } return result; } private ubyte decimalLength9_2(const uint v) pure nothrow { if (v == 0) // BSR and LZCNT UB when input is 0 return 1; const ubyte lzc = cast(ubyte) bsr(v); static immutable pure nothrow ubyte function(uint)[32] tbl = [ 0 : (uint a) => ubyte(1), 1 : (uint a) => ubyte(1), 2 : (uint a) => ubyte(1), 3 : (uint a) => a >= 10 ? ubyte(2) : ubyte(1), 4 : (uint a) => ubyte(2), 5 : (uint a) => ubyte(2), 6 : (uint a) => a >= 100 ? ubyte(3) : ubyte(2), 7 : (uint a) => ubyte(3), 8 : (uint a) => ubyte(3), 9 : (uint a) => a >= 1000 ? ubyte(4) : ubyte(3), 10: (uint a) => ubyte(4), 11: (uint a) => ubyte(4), 12: (uint a) => ubyte(4), 13: (uint a) => a >= 10000 ? ubyte(5) : ubyte(4), 14: (uint a) => ubyte(5), 15: (uint a) => ubyte(5), 16: (uint a) => a >= 100000 ? ubyte(6) : ubyte(5), 17: (uint a) => ubyte(6), 18: (uint a) => ubyte(6), 19: (uint a) => a >= 1000000 ? ubyte(7) : ubyte(6), 20: (uint a) => ubyte(7), 21: (uint a) => ubyte(7), 22: (uint a) => ubyte(7), 23: (uint a) => a >= 10000000 ? ubyte(8) : ubyte(7), 24: (uint a) => ubyte(8), 25: (uint a) => ubyte(8), 26: (uint a) => a >= 100000000 ? ubyte(9) : ubyte(8), 27: (uint a) => ubyte(9), 28: (uint a) => ubyte(9), 29: (uint a) => ubyte(9), 30: (uint a) => ubyte(9), 31: (uint a) => ubyte(9), ]; return tbl[lzc](v); } ubyte decimalLength9_3(const uint v) pure nothrow { if (v == 0) // BSR and LZCNT UB when input is 0 return 1; ubyte result; enum ubyte doSwitch = ubyte(0); const ubyte lzc = cast(ubyte) bsr(v); const ubyte[32] decimalLength9LUT = [ 0 : ubyte(1), 1 : ubyte(1), 2 : ubyte(1), 3 : doSwitch, 4 : ubyte(2), 5 : ubyte(2), 6 : doSwitch, 7 : ubyte(3), 8 : ubyte(3), 9 : doSwitch, 10: ubyte(4), 11: ubyte(4), 12: ubyte(4), 13: doSwitch, 14: ubyte(5), 15: ubyte(5), 16: doSwitch, 17: ubyte(6), 18: ubyte(6), 19: doSwitch, 20: ubyte(7), 21: ubyte(7), 22: ubyte(7), 23: doSwitch, 24: ubyte(8), 25: ubyte(8), 26: doSwitch, 27: ubyte(9), 28: ubyte(9), 29: ubyte(9), 30: ubyte(9), 31: ubyte(9), ]; ubyte resultOrSelector = decimalLength9LUT[lzc]; if (resultOrSelector != doSwitch) result = resultOrSelector; else switch (lzc) { case 3 : result = v >= 10 ? 2 : 1; break; case 6 : result = v >= 100 ? 3 : 2; break; case 9 : result = v >= 1000 ? 4 : 3; break; case 13: result = v >= 10000 ? 5 : 4; break; case 16: result = v >= 100000 ? 6 : 5; break; case 19: result = v >= 1000000 ? 7 : 6; break; case 23: result = v >= 10000000 ? 8 : 7; break; case 26: result = v >= 100000000 ? 9 : 8; break; default: assert(false); } return result; } 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) ; } ubyte decimalLength9_5(const uint v) pure nothrow { if (v == 0) // BSR and LZCNT UB when input is 0 return 1; ubyte result; enum ubyte doBranchlessWay = ubyte(0); const ubyte lzc = cast(ubyte) bsr(v); const ubyte[32] decimalLength9LUT = [ 0 : ubyte(1), 1 : ubyte(1), 2 : ubyte(1), 3 : doBranchlessWay, 4 : ubyte(2), 5 : ubyte(2), 6 : doBranchlessWay, 7 : ubyte(3), 8 : ubyte(3), 9 : doBranchlessWay, 10: ubyte(4), 11: ubyte(4), 12: ubyte(4), 13: doBranchlessWay, 14: ubyte(5), 15: ubyte(5), 16: doBranchlessWay, 17: ubyte(6), 18: ubyte(6), 19: doBranchlessWay, 20: ubyte(7), 21: ubyte(7), 22: ubyte(7), 23: doBranchlessWay, 24: ubyte(8), 25: ubyte(8), 26: doBranchlessWay, 27: ubyte(9), 28: ubyte(9), 29: ubyte(9), 30: ubyte(9), 31: ubyte(9), ]; ubyte resultOrSelector = decimalLength9LUT[lzc]; if (resultOrSelector != doBranchlessWay) result = resultOrSelector; else { result = 1 + (v >= 10) + (v >= 100) + (v >= 1000) + (v >= 10000) + (v >= 100000) + (v >= 1000000) + (v >= 10000000) + (v >= 100000000) ; } return result; } void main(string[] args) { uint sum; ulong count; uint seed; ubyte func; GC.disable; getopt(args, config.passThrough, "c|count", &count, "f|func", &func, "s|seed", &seed); static const funcs = [&decimalLength9_0, &decimalLength9_1, &decimalLength9_2, &decimalLength9_3, &decimalLength9_4, &decimalLength9_5]; rndGen.seed(seed); foreach (const ulong i; 0 .. count) { sum += funcs[func](rndGen.front()); rndGen.popFront(); } writeln(sum); } --- Could you share your benchmarking method maybe ?
Feb 27 2020
parent reply Bruce Carneal <bcarneal gmail.com> writes:
On Thursday, 27 February 2020 at 08:52:09 UTC, Basile B. wrote:
 On Thursday, 27 February 2020 at 04:44:56 UTC, Basile B. wrote:
 On Thursday, 27 February 2020 at 03:58:15 UTC, Bruce Carneal 
 wrote:
 Maybe you talked about another implementation of 
 decimalLength9 ?
Yes. It's one I wrote after I saw your post. Psuedo-code here: auto d9_branchless(uint v) { return 1 + (v >= 10) + (v >= 100) ... } Using ldc to target an x86 with the above yields a series of cmpl, seta instruction pairs in the function body followed by a summing and a return. No branching. Let me know if the above is unclear or insufficient.
No thanks, it's crystal clear now.
although I don't see the performance gain. snip
 ubyte decimalLength9_0(const uint v)
 {
     if (v >= 100000000) { return 9; }
     if (v >= 10000000) { return 8; }
     if (v >= 1000000) { return 7; }
     if (v >= 100000) { return 6; }
     if (v >= 10000) { return 5; }
     if (v >= 1000) { return 4; }
     if (v >= 100) { return 3; }
     if (v >= 10) { return 2; }
     return 1;
 }

 snip
 Could you share your benchmarking method maybe ?
OK. I'm working with equi-probable digits. You're working with equi-probable values. The use-case may be either of these or, more likely, a third as yet unknown/unspecified distribution. The predictability of the test input sequence clearly influences the performance of the branching implementations. The uniform random input is highly predictable wrt digits. (there are *many* more high digit numbers than low digit numbers) Take the implementation above as an example. If, as in the random number (equi-probable value) scenario, your inputs skew *stongly* toward a higher number of digits, then the code should perform very well. If you believe the function will see uniform random values as input, then testing with uniform random inputs is the way to go. If you believe some digits distribution is what will be seen, then you should alter your inputs to match. (testing uniform random in addition to the supposed target distribution is almost always a good idea for sensitivity analysis). My testing methodology: To obtain an equi-digit distribution, I fill an array with N 1-digit values, followed by N 2-digit values, ... followed by N 9-digit values. I use N == 1000 and loop over the total array until I've presented about 1 billion values to the function under test. I test against that equi-digit array before shuffling (this favors branching implementations) and then again after shuffling (this favors branchless). If you wish to work with equi-digit distributions I'd prefer that you implement the functionality anew. This is some small duplicated effort but will help guard against my having screwed up even that simple task (less than 6 LOC IIRC). I will post my code if there is any meaningful difference in your subsequent results.
Feb 27 2020
next sibling parent Bruce Carneal <bcarneal gmail.com> writes:
On Thursday, 27 February 2020 at 15:29:02 UTC, Bruce Carneal 
wrote:
 big snip
TL;DR for the snipped: Unsurprisingly, different inputs will lead to different timing results. The equi-probable values supplied by a standard PRNG differ significantly from an equi-probable digit input. In particular, the PRNG input is much more predictable. Note also that a uint PRNG will produce numbers that need 10 decimal digits. If my arithmetic is correct, you'll see "9 or better" out of a uint PRNG 97.79% of the time. The predictability of the full set of inputs is, secondarily but importantly, also influenced by the ability of the branch predictor to ferret out combinations. I lack confidence in my ability to reason from first principles when presented with a modern CPU branch predictor and a complex input. Much easier for me to just run tests against various distributions that I think span the input and reason from the results.
Feb 27 2020
prev sibling parent reply Basile B. <b2.temp gmx.com> writes:
On Thursday, 27 February 2020 at 15:29:02 UTC, Bruce Carneal 
wrote:
 On Thursday, 27 February 2020 at 08:52:09 UTC, Basile B. wrote:
 I will post my code if there is any meaningful difference in 
 your subsequent results.
give me something I can compile and verify. I'm not there to steal, if you found something you can still propose it to the repos that would take advantage of the optim.
Feb 27 2020
parent reply Bruce Carneal <bcarneal gmail.com> writes:
On Thursday, 27 February 2020 at 17:11:48 UTC, Basile B. wrote:
 On Thursday, 27 February 2020 at 15:29:02 UTC, Bruce Carneal 
 wrote:
 On Thursday, 27 February 2020 at 08:52:09 UTC, Basile B. wrote:
 I will post my code if there is any meaningful difference in 
 your subsequent results.
give me something I can compile and verify. I'm not there to steal, if you found something you can still propose it to the repos that would take advantage of the optim.
I'm not at all concerned about theft of trivial code. I am concerned that a simple error in my code will live on in a copy/paste environment. Regardless, I'll post the code once I get home. It may be the only way to communicate the central problem as I see it: imprecision in the test specification (the input specification).
Feb 27 2020
parent reply Basile B. <b2.temp gmx.com> writes:
On Thursday, 27 February 2020 at 17:17:32 UTC, Bruce Carneal 
wrote:
 On Thursday, 27 February 2020 at 17:11:48 UTC, Basile B. wrote:
 On Thursday, 27 February 2020 at 15:29:02 UTC, Bruce Carneal 
 wrote:
 On Thursday, 27 February 2020 at 08:52:09 UTC, Basile B. 
 wrote:
 I will post my code if there is any meaningful difference in 
 your subsequent results.
give me something I can compile and verify. I'm not there to steal, if you found something you can still propose it to the repos that would take advantage of the optim.
I'm not at all concerned about theft of trivial code. I am concerned that a simple error in my code will live on in a copy/paste environment. Regardless, I'll post the code once I get home. It may be the only way to communicate the central problem as I see it: imprecision in the test specification (the input specification).
Yes please, post the benchmark method. You see the benchmarks I run with your version are always slowest. I'm aware that rndGen (and generaly any uniform rnd func) is subject to a bias but I dont thing this bias maters much in the case we talk about.
Feb 27 2020
parent reply Bruce Carneal <bcarneal gmail.com> writes:
On Thursday, 27 February 2020 at 19:46:23 UTC, Basile B. wrote:
 Yes please, post the benchmark method. You see the benchmarks I 
 run with your version are always slowest. I'm aware that rndGen 
 (and generaly any uniform rnd func) is subject to a bias but I 
 dont thing this bias maters much in the case we talk about.
The code below is the test jig that I'm using currently. It is adopted from yours but has added the -d=distribution command line option. I have omitted the function bodies for the entries in the funcs[] table. You can cut and paste there at will but I wanted to spare any other readers the bulk. The timings I get from the below are entirely consistent with my earlier reporting and, I believe, with yours. I urge you to investigate the difference in timings between the original, and currently defaulted, distribution and the -d=edig distribution. If you don't understand what's going on there, or if you still don't believe input distributions matter, please get in touch. After all, it's possible that I'm the one with the misunderstanding. Have fun! <code> const funcs = [ &decimalLength9_0, &decimalLength9_1, &decimalLength9_2, &decimalLength9_3, &decimalLength9_4, &decimalLength9_5 ]; ulong runOriginalFuncCount(ubyte funcIdx, ulong count) { GC.disable; uint sum; foreach (const ulong i; 0 .. count) { sum += funcs[funcIdx](rndGen.front()); rndGen.popFront(); } return sum; } ulong runFuncCountDist(ubyte funcIdx, ulong count, string dist) { enum perDigit = 1000; // NOTE: this is a gross distortion given uint.max but it is "the spec" enum maxDigits = 9; uint[perDigit * maxDigits] samples = void; const chunks = count / samples.length; const leftOvers = count % samples.length; if (dist == "prng") { foreach (ref val; samples[]) { val = rndGen.front(); rndGen.popFront(); } } else if (dist == "edig" || dist == "edigsorted") { // for reference, this is the "6 LOC IIRC" uint value = 1; foreach (dig; 0 .. maxDigits) { samples[dig * perDigit .. (dig + 1) * perDigit] = value; value *= 10; } if (auto shuffle = dist != "edigsorted") randomShuffle(samples[]); } else { assert(0, "dist option should be in {oprng, prng, edig, edigsorted}"); } const func = funcs[funcIdx]; if (count < 1) // late check gives us a handle on setup time return 0; // OK, enough with the setup, time to roll ulong sum = 0; foreach (chunk; 0 .. chunks) { foreach (sample; samples[]) sum += func(sample); } foreach (sample; samples[$ - leftOvers .. $]) sum += func(sample); return sum; } // This is a timing test jig for functions that accept a uint // and return the number of decimal digits needed to represent // that uint (except that 10 digit values are lumped in with // 9 digit values currently). // // The command line options here are: // -c=count (the number of values to present to the function selected) // -s=seed (the value supplied to rndGen.seed) // -f=funcIndex (identifies the function under test, see source funcs[]) // -d=distribution (one of: oprng, prng, edig, edigsorted) // // Distributions explained: // oprng: original prng distribution, a rndGen.popFront per function call // prng: prng distribution, also rndGen but coming from a large, pre-filled, array // edig: same number of 1-digit, 2-digit, ... numbers, shuffled // edigsorted: edig values but sorted to highlight the branch predictor impact // // This test jig could evolve in at least six ways: // 1) the full digit range could (arguably should) be accounted for // 2) additional distributions, like "favor small numbers", could be added // 3) additional implementation ideas can be explored // 4) the input range could be made variable // 5) the number base could be templatized // 6) inlined performance could be tested by aliasing Func (runtime switch to template) // // Final note: the main benefit of working on this problem is better understanding, not // shaving nanoseconds on this particular function. void main(string[] args) { ulong count; uint seed; ubyte func; // NOTE: oprng writeln output will usually not equal that of -d=prng enum defaultDistribution = "oprng"; string dist = defaultDistribution; GC.disable; getopt(args, config.passThrough, "c|count", &count, "f|func", &func, "s|seed", &seed, "d|distribution", &dist); rndGen.seed(seed); const original = dist == "oprng"; const sum = original ? runOriginalFuncCount(func, count) : runFuncCountDist(func, count, dist); writeln(sum); } <code>
Feb 27 2020
parent Basile B. <b2.temp gmx.com> writes:
On Thursday, 27 February 2020 at 21:46:08 UTC, Bruce Carneal 
wrote:
 On Thursday, 27 February 2020 at 19:46:23 UTC, Basile B. wrote:
 [...]
The code below is the test jig that I'm using currently. It is adopted from yours but has added the -d=distribution command line option. [...]
Yes I finally can see the branchless version beating the original with -dedig. Thanks for your time.
Feb 28 2020
prev sibling next sibling parent reply Johan <j j.nl> writes:
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.

 ...

 Then bad surprise. Even with ldmd (so ldc2 basically) feeded 
 with the args from the script line. Maybe the fdecimalLength9 
 version is slightly faster. Only *slightly*. Good news, I've 
 lost my time. So I try an alternative version that uses a table 
 of delegates instead of a switch (ffdecimalLength9) and 
 surprise, "tada", it is like **100x** slower then the two 
 others.

 How is that possible ?
Hi Basile, I recently saw this presentation: https://www.youtube.com/watch?v=Czr5dBfs72U It has some ideas that may help you make sure your measurements are good and may give you ideas to find the performance bottleneck or where to optimize. llvm-mca is featured on godbolt.org: https://mca.godbolt.org/z/YWp3yv cheers, Johan
Feb 26 2020
next sibling parent Basile B. <b2.temp gmx.com> writes:
On Wednesday, 26 February 2020 at 22:07:30 UTC, Johan wrote:
 On Wednesday, 26 February 2020 at 00:50:35 UTC, Basile B. wrote:
 [...]
Hi Basile, I recently saw this presentation: https://www.youtube.com/watch?v=Czr5dBfs72U It has some ideas that may help you make sure your measurements are good and may give you ideas to find the performance bottleneck or where to optimize. llvm-mca is featured on godbolt.org: https://mca.godbolt.org/z/YWp3yv cheers, Johan
yes llvm-mca looks excellent, although I don't know if it worth continuing... You see this function is certainly not a bottleneck, it's just that I wanted to try better than the naive implementation. Fundamentatlly the problem is that 1. the original is smaller, faster to decode 2. the alternatives (esp. the 3rd) is conceptually better but the cost of the jump table + lzcnt wastes it.
Feb 26 2020
prev sibling parent reply Basile B. <b2.temp gmx.com> writes:
On Wednesday, 26 February 2020 at 22:07:30 UTC, Johan wrote:
 On Wednesday, 26 February 2020 at 00:50:35 UTC, Basile B. wrote:
 [...]
Hi Basile, I recently saw this presentation: https://www.youtube.com/watch?v=Czr5dBfs72U
Andrei made a talk about this too a few years ago.
 It has some ideas that may help you make sure your measurements 
 are good and may give you ideas to find the performance 
 bottleneck or where to optimize.
 llvm-mca is featured on godbolt.org: 
 https://mca.godbolt.org/z/YWp3yv

 cheers,
   Johan
Feb 27 2020
parent Basile B. <b2.temp gmx.com> writes:
On Thursday, 27 February 2020 at 14:12:35 UTC, Basile B. wrote:
 On Wednesday, 26 February 2020 at 22:07:30 UTC, Johan wrote:
 On Wednesday, 26 February 2020 at 00:50:35 UTC, Basile B. 
 wrote:
 [...]
Hi Basile, I recently saw this presentation: https://www.youtube.com/watch?v=Czr5dBfs72U
Andrei made a talk about this too a few years ago.
 It has some ideas that may help you make sure your 
 measurements are good and may give you ideas to find the 
 performance bottleneck or where to optimize.
 llvm-mca is featured on godbolt.org: 
 https://mca.godbolt.org/z/YWp3yv

 cheers,
   Johan
https://www.youtube.com/watch?v=Qq_WaiwzOtI
Feb 27 2020
prev sibling next sibling parent reply Dennis Cote <private secret.com> writes:
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.
Feb 27 2020
parent reply Basile B. <b2.temp gmx.com> writes:
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/ctidwrnxvwwkouprjszw forum.dlang.org for the latest evolution of the discussion.
Feb 27 2020
parent Basile B. <b2.temp gmx.com> writes:
On Thursday, 27 February 2020 at 09:41:20 UTC, Basile B. wrote:
 On Thursday, 27 February 2020 at 09:33:28 UTC, Dennis Cote 
 wrote:
 [...]
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/ctidwrnxvwwkouprjszw forum.dlang.org for the latest evolution of the discussion.
maybe just add you version to the test program and run time ./declen -c100000000 -f0 -s137 // original time ./declen -c100000000 -f4 -s137 // the 100% branchless time ./declen -c100000000 -f5 -s137 // the LUT + branchless for the bit num that need attention time ./declen -c100000000 -f6 -s137 // assumed to be your version to see if it beats the original. Thing is that i cannot do it right now but otherwise will try tomorrow.
Feb 27 2020
prev sibling parent reply 9il <ilyayaroshenko gmail.com> writes:
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.

 [...]
bsr can be done in one/two CPU operation, quite quick. But core.bitop.bsr wouldn't be inlined. Instead, mir-core (mir.bitop: ctlz) or LDC intrinsics llvm_ctlz can be used for to get code with inlining.
Feb 27 2020
parent reply Bruce Carneal <bcarneal gmail.com> writes:
On Friday, 28 February 2020 at 06:50:55 UTC, 9il 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.

 [...]
bsr can be done in one/two CPU operation, quite quick. But core.bitop.bsr wouldn't be inlined. Instead, mir-core (mir.bitop: ctlz) or LDC intrinsics llvm_ctlz can be used for to get code with inlining.
That's surprising. I just got ldc to inline core.bitop.bsr on run.dlang.io using ldc -O3 -mcpu=native. (not sure what the target CPU is) Under what conditions should I be guarding against an inlining failure?
Feb 28 2020
next sibling parent Bruce Carneal <bcarneal gmail.com> writes:
On Friday, 28 February 2020 at 10:11:23 UTC, Bruce Carneal wrote:
 On Friday, 28 February 2020 at 06:50:55 UTC, 9il 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.

 [...]
bsr can be done in one/two CPU operation, quite quick. But core.bitop.bsr wouldn't be inlined. Instead, mir-core (mir.bitop: ctlz) or LDC intrinsics llvm_ctlz can be used for to get code with inlining.
That's surprising. I just got ldc to inline core.bitop.bsr on run.dlang.io using ldc -O3 -mcpu=native. (not sure what the target CPU is) Under what conditions should I be guarding against an inlining failure?
Here's the code I used: int main(string[] args) { import core.bitop : bsr; return bsr(cast(uint)args.length); } BTW, I'm a huge fan of your performance work.
Feb 28 2020
prev sibling next sibling parent kinke <noone nowhere.com> writes:
On Friday, 28 February 2020 at 10:11:23 UTC, Bruce Carneal wrote:
 On Friday, 28 February 2020 at 06:50:55 UTC, 9il wrote:
 bsr can be done in one/two CPU operation, quite quick. But 
 core.bitop.bsr wouldn't be inlined. Instead, mir-core 
 (mir.bitop: ctlz) or LDC intrinsics llvm_ctlz can be used for 
 to get code with inlining.
That's surprising. I just got ldc to inline core.bitop.bsr on run.dlang.io using ldc -O3 -mcpu=native.
These tiny core.bitop wrappers around LLVM intrinsics are always inlined (`pragma(inline, true)`), i.e., you don't even need -O.
Feb 28 2020
prev sibling parent 9il <ilyayaroshenko gmail.com> writes:
On Friday, 28 February 2020 at 10:11:23 UTC, Bruce Carneal wrote:
 On Friday, 28 February 2020 at 06:50:55 UTC, 9il 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.

 [...]
bsr can be done in one/two CPU operation, quite quick. But core.bitop.bsr wouldn't be inlined. Instead, mir-core (mir.bitop: ctlz) or LDC intrinsics llvm_ctlz can be used for to get code with inlining.
That's surprising. I just got ldc to inline core.bitop.bsr on run.dlang.io using ldc -O3 -mcpu=native. (not sure what the target CPU is)
Ah, my bad. It fails to inline with LDC <= 1.14 https://d.godbolt.org/z/iz9p-6
 Under what conditions should I be guarding against an inlining 
 failure?
Mark it with `pragma(inline, true)`. LDC also has cross-module inlining for non-templated functions.
Feb 28 2020