osdir.com


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Algorithmic explorations of bitmaps vs. sentinel values


I'm surprised that using a stack variable has an impact, but I should
probably update the benchmarks to do that (and merge with the
SumState<T> at the end of the function) for thoroughness. Thanks!
On Wed, Oct 17, 2018 at 9:07 AM Francois Saint-Jacques
<fsaintjacques@xxxxxxxxxxxxxxx> wrote:
>
> It seems the code for the naive Scalar example is not friendly with the
> compiler auto-vectorization component. If you accumulate in a local state
> (instead of SumState pointer), you'll get different results. at least with
> clang++6.0.
>
> benchmark-noavx (only SSE):
> BM_SumInt32Scalar                      42390 us      42389 us         16
> bytes_per_second=8.78824G/s items_per_second=2.35908G/s
> BM_SumInt32ScalarRegister              28036 us      28035 us         25
> bytes_per_second=13.2878G/s items_per_second=3.56691G/s
> BM_SumInt32ScalarUnrolled              31660 us      31659 us         22
> bytes_per_second=11.7668G/s items_per_second=3.15863G/s
> BM_SumInt32ScalarSentinel              49541 us      49540 us         14
> bytes_per_second=7.51971G/s items_per_second=2.01856G/s
> BM_SumInt32ScalarSentinelRegister      55655 us      55654 us         12
> bytes_per_second=6.69369G/s items_per_second=1.79683G/s
> BM_SumInt64Scalar                      65030 us      65030 us         11
> bytes_per_second=11.4572G/s items_per_second=1.53776G/s
> BM_SumInt64ScalarRegister              55370 us      55369 us         13
> bytes_per_second=13.4563G/s items_per_second=1.80607G/s
> BM_SumInt64ScalarUnrolled              61287 us      61286 us         11
> bytes_per_second=12.1571G/s items_per_second=1.6317G/s
> BM_SumInt64ScalarSentinel              69792 us      69792 us         10
> bytes_per_second=10.6755G/s items_per_second=1.43284G/s
> BM_SumInt64ScalarSentinelRegister      68418 us      68416 us         10
> bytes_per_second=10.89G/s items_per_second=1.46164G/
>
> benchmark-native (AVX512):
> BM_SumInt32Scalar                      43981 us      43980 us         16
> bytes_per_second=8.47046G/s items_per_second=2.27377G/s
> BM_SumInt32ScalarRegister              28381 us      28380 us         24
> bytes_per_second=13.1263G/s items_per_second=3.52355G/s
> BM_SumInt32ScalarUnrolled              79035 us      79033 us          9
> bytes_per_second=4.71361G/s items_per_second=1.2653G/s
> BM_SumInt32ScalarSentinel              53430 us      53429 us         13
> bytes_per_second=6.97235G/s items_per_second=1.87163G/s
> BM_SumInt32ScalarSentinelRegister      32450 us      32450 us         22
> bytes_per_second=11.4802G/s items_per_second=3.0817G/s
> BM_SumInt64Scalar                      68112 us      68111 us         10
> bytes_per_second=10.9389G/s items_per_second=1.46819G/s
> BM_SumInt64ScalarRegister              56188 us      56187 us         12
> bytes_per_second=13.2603G/s items_per_second=1.77977G/s
> BM_SumInt64ScalarUnrolled              65649 us      65648 us         11
> bytes_per_second=11.3492G/s items_per_second=1.52327G/s
> BM_SumInt64ScalarSentinel              69674 us      69673 us         10
> bytes_per_second=10.6937G/s items_per_second=1.43528G/s
> BM_SumInt64ScalarSentinelRegister      59200 us      59199 us         12
> bytes_per_second=12.5857G/s items_per_second=1.68922G/s
>
> The interesting part here is that the ScalarSentinelRegister version is
> very close the the fully vectorized ScalarRegister version on AVX512.
> Antoine, the compiler is doing exactly what you're suggesting:
>
> 374 │       vmovdqu 0x20(%rcx,%rdi,8),%ymm9
>
>  48 │       vmovdqu 0x40(%rcx,%rdi,8),%ymm10
>
> 230 │       vmovdqu 0x60(%rcx,%rdi,8),%ymm11
>
>     │       static inline bool NotNull(int64_t val) { return val !=
> null_sentinel; }
>     │       vpcmpneqq %ymm13,%ymm8,%k2
>
>  25 │       vpcmpneqq %ymm13,%ymm9,%k3
>
>  20 │       vpcmpneqq %ymm13,%ymm10,%k4
>
>  72 │       vpcmpneqq %ymm13,%ymm11,%k1
>
>     │           if (Traits<T>::NotNull(*values)) {
>
>     │       vpbroadcastq %rbx,%ymm12{%k2}{z}
>
>  15 │       vpaddq %ymm12,%ymm3,%ymm3
>
>   9 │       vpbroadcastq %rbx,%ymm12{%k3}{z}
>
>  57 │       vpaddq %ymm12,%ymm5,%ymm5
>
>     │       vpbroadcastq %rbx,%ymm12{%k4}{z}
>
>  39 │       vpaddq %ymm12,%ymm6,%ymm6
>
>  22 │       vpbroadcastq %rbx,%ymm12{%k1}{z}
>
>  88 │       vpaddq %ymm12,%ymm7,%ymm7
>
> See my fork, https://github.com/fsaintjacques/bitmaps-vs-sentinels . I
> didn't have time to look at the other Sum (bitmap) implementation and
> didn't have time to clean the code. I'll try improve this over the weekend.
>
> On Tue, Oct 16, 2018 at 8:05 AM Wes McKinney <wesmckinn@xxxxxxxxx> wrote:
>
> > hi folks,
> >
> > I explored a bit the performance implications of using validity
> > bitmaps (like the Arrow columnar format) vs. sentinel values (like
> > NaN, INT32_MIN) for nulls:
> >
> > http://wesmckinney.com/blog/bitmaps-vs-sentinel-values/
> >
> > The vectorization results may be of interest to those implementing
> > analytic functions targeting the Arrow memory format. There's probably
> > some other optimizations that can be employed, too.
> >
> > Caveat: it's entirely possible I made some mistakes in my code. I
> > checked the various implementations for correctness only, and did not
> > dig too deeply beyond that.
> >
> > - Wes
> >
>
>
> --
> Sent from my jetpack.