Re: [boost] interest in structure of arrays container?

Subject: Re: [boost] interest in structure of arrays container?
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2016-10-27 02:10:07

On 10/26/2016 1:33 PM, Chris Glover wrote:
>>
>>  I guess some optimisation from way yonder (something modern compilers do
>> routinely, even on a Monday morning!)... but more than probable irrelevant
>> nowadays...
>>
>> degski
>>
>
> I might be pessimistic, but I never trust the compiler and generally check
> what's being output. In this case, FWIW, on MSVC2015, the bit-twiddling
> version generates faster code than the mod version -- about 25% faster. I
> didn't test gcc or clang.
>
> Using google benchmark:
>
> Code:
>
> static void AlignedMod(benchmark::State& state)
> {
>     while (state.KeepRunning())
>     {
>         for(int i = state.range_x(); i < 128; i += state.range_y())
>         {
>             bool aligned = (i % 16) == 0;
>             benchmark::DoNotOptimize(aligned);
>         }
>     }
> }
> BENCHMARK(AlignedMod)->ArgPair(1, 1);
>
> static void AlignedAnd(benchmark::State& state)
> {
>     while (state.KeepRunning())
>     {
>         for(int i = state.range_x(); i < 128; i += state.range_y())
>         {
>             bool aligned = ((i - 1) & 15) == 0;
>             benchmark::DoNotOptimize(aligned);
>         }
>     }
> }
> BENCHMARK(AlignedAnd)->ArgPair(1, 1);
>
> Generated code of the inner loop:
>
> Mod version:
> mov         eax,ebx
> and         eax,8000000Fh
> jge         AlignedMod+50h
> dec         eax
> or          eax,0FFFFFFF0h
> inc         eax
> test        eax,eax
> lea         rcx,[aligned]
> sete        byte ptr [aligned]
> call        07FF73B84A180h
> add         ebx,dword ptr [rdi+1Ch]
> cmp         ebx,80h
> jl          AlignedMod+40h
>
>
> And version:
> lea         eax,[rbx-1]
> test        al,0Fh
> lea         rcx,[aligned]
> sete        byte ptr [aligned]
> call        07FF73B84A180h
> add         ebx,dword ptr [rdi+1Ch]
> cmp         ebx,80h
> jl          AlignedAnd+40h
>
>
> Result:
> Benchmark                                   Time           CPU Iterations
> -------------------------------------------------------------------------
> AlignedMod/1/1                            204 ns        203 ns    4072727
> AlignedAnd/1/1                            153 ns        154 ns    4977778
>

It's very dangerous to draw conclusions from benchmarks like this.

The operation and elapsed time are way too small for the results to be 
distinguishable from noise on the system.

AlignedAnd has a random '- 1' in it so it's not even checking if i is 16 
byte aligned.

AlignedMod is taking the mod of a signed integer. Make it use an 
unsigned integer and some very familiar code gets generated.

         for ( unsigned i = state.range_x(); i < 128; i += state.range_y() )
00007FF7ACBA316C  mov         ebx,dword ptr [rdi+14h]
00007FF7ACBA316F  cmp         ebx,80h
00007FF7ACBA3175  jae         AlignedMod+12h (07FF7ACBA3132h)
00007FF7ACBA3177  nop         word ptr [rax+rax]
         {
             bool aligned = (i % 16) == 0;
00007FF7ACBA3180  test        bl,0Fh
             benchmark::DoNotOptimize( aligned );
00007FF7ACBA3183  lea         rcx,[aligned]
         {
             bool aligned = (i % 16) == 0;
00007FF7ACBA3188  sete        byte ptr [aligned]
             benchmark::DoNotOptimize( aligned );
00007FF7ACBA318D  call        benchmark::internal::UseCharPointer 
(07FF7ACBA1019h)
     {
         for ( unsigned i = state.range_x(); i < 128; i += state.range_y() )
00007FF7ACBA3192  add         ebx,dword ptr [rdi+1Ch]
00007FF7ACBA3195  cmp         ebx,80h
00007FF7ACBA319B  jb          AlignedMod+60h (07FF7ACBA3180h)
         }
     }
00007FF7ACBA319D  jmp         AlignedMod+12h (07FF7ACBA3132h)
}
00007FF7ACBA319F  mov         rbx,qword ptr [rsp+38h]
00007FF7ACBA31A4  mov         rsi,qword ptr [rsp+40h]
00007FF7ACBA31A9  add         rsp,20h
00007FF7ACBA31AD  pop         rdi
00007FF7ACBA31AE  ret

I don't agree that it is more obscure. I think it's perfectly natural to 
understand that the bottom 4 bits must be zero in order to be multiple 
of 16.
I recommend to everyone the book Hacker's Delight which will make you 
truly appreciate how wonderful integers are.