Strange counter-performance in an alternative `decimalLength9` function

[Bruce Carneal]

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.