[C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

Hi everyone,
I've noticed that we include xsimd as an abstraction over all of the simd
architectures. I'd like to propose a different solution which would result
in fewer lines of code, while being more readable.

My thinking is that anything simple enough to abstract with xsimd can be
autovectorized by the compiler. Any more interesting SIMD algorithm usually
is tailored to the target instruction set and can't be abstracted away with
xsimd anyway.

With that in mind, I'd like to propose the following strategy:
1. Write a single source file with simple, element-at-a-time for loop
implementations of each function.
2. Compile this same source file several times with different compile flags
for different vectorization (e.g. if we're on an x86 machine that supports
AVX2 and AVX512, we'd compile once with -mavx2 and once with -mavx512vl).
3. Functions compiled with different instruction sets can be differentiated
by a namespace, which gets defined during the compiler invocation. For
example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2 and then
for something like elementwise addition of two arrays, we'd call
arrow::AVX2::VectorAdd.

I believe this would let us remove xsimd as a dependency while also giving
us lots of vectorized kernels at the cost of some extra cmake magic. After
that, it would just be a matter of making the function registry point to
these new functions.

Please let me know your thoughts!

Thanks,
Sasha Krassovsky

Re: [C++] Replacing xsimd with compiler autovectorization

[Antoine Pitrou <an...@python.org>]

Le 03/04/2022 à 21:38, Sasha Krassovsky a écrit :
> 
>> There is concrete proof that autovectorization produces very flimsy results (even on the same compiler, simply by varying the datatypes).
> 
> As I’ve shown, the Vector-Vector Add kernel example is consistently vectorized well across compilers if written in a simple way.

Does it handle a validity bitmap efficiently? Does it handle an entire 
range of datatypes? Does it handle both array and scalar inputs? If not, 
how would you propose to handle all these? Chances are, you'll end up 
rewriting another array of template abstractions.

> Until I’ve seen a poorly-vectorized scalar kernel written as a simple for loop, I consider these arguments theoretical as well.

This makes little sense. The Arrow C++ codebase is not "theoretical", 
it's what you are presently working on.

> It seems that we’re in agreement at least in terms of concrete action for an initial PR: make the kernels system more SIMD-amenable and enable the several-times-compilation of source files to at least enable the instruction sets. Next, we can evaluate which kernels it’s worth to rewrite in terms of xsimd. Does that sound right?

Indeed you can have an initial stab at that.

Regards

Antoine.


> 
> Sasha
> 
> 
>> 3 апр. 2022 г., в 11:47, Antoine Pitrou <an...@python.org> написал(а):
>>
>> It would be a very significant contributor, as the inconsistency can manifest under the form of up to 8-fold differences in performance (or perhaps more).
> 

Re: [C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

> It would be a very significant contributor, as the inconsistency can manifest under the form of up to 8-fold differences in performance (or perhaps more).

This is on a micro benchmark. For a user workload, the kernel will account for maybe 20% of the runtime, so even if the kernel gets 10x faster the user workload will only be 18% faster (or in the ballpark, I didn’t math it rigorously). 

> There is concrete proof that autovectorization produces very flimsy results (even on the same compiler, simply by varying the datatypes).

There is concrete proof of flimsy results for large template monsters, hidden behind layers of indirection across several source files. As I’ve shown, the Vector-Vector Add kernel example is consistently vectorized well across compilers if written in a simple way. Until I’ve seen a poorly-vectorized scalar kernel written as a simple for loop, I consider these arguments theoretical as well. 

> There is a far cry however, between the proposal of leveraging autovectorization as a first step towards better performance

Yes, I did amend my proposal earlier in this thread, saying that leaving xsimd in and using it for kernels that don’t autovectorize well would work. 

It seems that we’re in agreement at least in terms of concrete action for an initial PR: make the kernels system more SIMD-amenable and enable the several-times-compilation of source files to at least enable the instruction sets. Next, we can evaluate which kernels it’s worth to rewrite in terms of xsimd. Does that sound right?

Sasha


> 3 апр. 2022 г., в 11:47, Antoine Pitrou <an...@python.org> написал(а):
> 
> It would be a very significant contributor, as the inconsistency can manifest under the form of up to 8-fold differences in performance (or perhaps more).

Re: [C++] Replacing xsimd with compiler autovectorization

[Antoine Pitrou <an...@python.org>]

Le 01/04/2022 à 08:43, Sasha Krassovsky a écrit :
> I agree that a potential inconsistent experience is a problem, but I
> disagree that SIMD would be the root of the problem, or even be a
> significant contributor to it.

It would be a very significant contributor, as the inconsistency can 
manifest under the form of up to 8-fold differences in performance (or 
perhaps more). Usually, compiler differences can produce differences on 
the order of a few tens of percent, and that is understood by users, but 
an order of magnitude is unexpected and makes it more difficult to 
advertise Arrow performance.

> And
> lastly, who can say that xsimd will be compiled properly and perform better
> than autovectorization?

I don't think such theoretical statements help a lot. There is concrete 
proof that autovectorization produces very flimsy results (even on the 
same compiler, simply by varying the datatypes). Is there any proof that 
xsimd-using code produces such fragile results? I haven't seen any, and 
it is unlikely to be the case (why would a compiler deoptimize SIMD 
intrinsics into plain scalar code?).

> At the very
> least, for an initial PR, I would like to keep everything simpler.

We can certainly do that. There is a far cry however, between the 
proposal of leveraging autovectorization as a first step towards better 
performance, and the original proposal of removing the xsimd dependency 
and only relying on autovectorization for future efforts :-)

Regards

Antoine.

Re: [C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

I agree that a potential inconsistent experience is a problem, but I
disagree that SIMD would be the root of the problem, or even be a
significant contributor to it.
The problem is essentially: "How can we be sure that all compilers will
generate good code on all platforms?" As you said, we have a lot of
platforms so that's not really practical.
I think that since we already try to use autovectorization in the kernels
subsystem, none of these problems are new. By not enabling AVX2 when it
would be simple enough to do so is akin to disabling compiler optimizations
because they may make the program better for some people. On the other
hand, rewriting everything to be explicitly vectorized is also much more
work than just enabling more instruction sets for autovectorization. And
lastly, who can say that xsimd will be compiled properly and perform better
than autovectorization?

So overall, no matter what, we'll have to rewrite the kernel system to be
more SIMD amenable, and enable the relevant instruction sets in the build
system. I don't see writing everything without xsimd introducing any
problems that wouldn't exist with xsimd. I would be fine keeping xsimd
around to give us opportunities to further tune performance. At the very
least, for an initial PR, I would like to keep everything simpler. We can
then evaluate xsimd-fying the kernels separately.

Sasha

On Thu, Mar 31, 2022 at 12:36 AM Antoine Pitrou <an...@python.org> wrote:

>
> Le 31/03/2022 à 09:19, Sasha Krassovsky a écrit :
> >> As I showed, those auto-vectorized kernels may be vectorized only in
> some situations, depending on the compiler version, the input datatypes...
> >
> > I would more than anything interpret the fact that that code was
> vectorized at all as an amazing win for compiler technology, as it’s a very
> abstract way of gluing together different pieces of code using templates
> and lambda expressions.
>
> That's a possible interpretation, but it doesn't really help the bottom
> line :-)
>
> > A lot of the kernels that we would be writing are probably basic unit
> tests [1] for the compiler’s vectorizer, and I’ve hopefully shown that even
> very old versions do just fine.
> >
> > Anyway, in the worst case we will eventually write every kernel with
> xsimd, and have the autovectorized kernels temporarily there. If we find
> that performance is good on our platforms, then we can skip the “rewrite in
> xsimd” step.
>
> "Our platforms" are rather broad however. We have binary packages for
> Windows, macOS, Linux, using several compilers and toolchains (because
> there are R packages, Python packages and sometimes C++ packages). For
> example, on Windows the R packages are built with different versions of
> MinGW/gcc depending on the R version, while the Python packages are
> built with some version of MSVC (which might be of a different version
> depending on whether it's a conda package or a Python wheel, I'm not sure).
>
> And there are of course the different architectures: we support x86 and
> arm64 for both macOS and Linux, for example; we might even have ppc64
> packages of some sort (?).
>
> Regards
>
> Antoine.
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Antoine Pitrou <an...@python.org>]

Le 31/03/2022 à 09:19, Sasha Krassovsky a écrit :
>> As I showed, those auto-vectorized kernels may be vectorized only in some situations, depending on the compiler version, the input datatypes...
> 
> I would more than anything interpret the fact that that code was vectorized at all as an amazing win for compiler technology, as it’s a very abstract way of gluing together different pieces of code using templates and lambda expressions.

That's a possible interpretation, but it doesn't really help the bottom 
line :-)

> A lot of the kernels that we would be writing are probably basic unit tests [1] for the compiler’s vectorizer, and I’ve hopefully shown that even very old versions do just fine.
> 
> Anyway, in the worst case we will eventually write every kernel with xsimd, and have the autovectorized kernels temporarily there. If we find that performance is good on our platforms, then we can skip the “rewrite in xsimd” step.

"Our platforms" are rather broad however. We have binary packages for 
Windows, macOS, Linux, using several compilers and toolchains (because 
there are R packages, Python packages and sometimes C++ packages). For 
example, on Windows the R packages are built with different versions of 
MinGW/gcc depending on the R version, while the Python packages are 
built with some version of MSVC (which might be of a different version 
depending on whether it's a conda package or a Python wheel, I'm not sure).

And there are of course the different architectures: we support x86 and 
arm64 for both macOS and Linux, for example; we might even have ppc64 
packages of some sort (?).

Regards

Antoine.

Re: [C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

> As I showed, those auto-vectorized kernels may be vectorized only in some situations, depending on the compiler version, the input datatypes...

I would more than anything interpret the fact that that code was vectorized at all as an amazing win for compiler technology, as it’s a very abstract way of gluing together different pieces of code using templates and lambda expressions. 

A lot of the kernels that we would be writing are probably basic unit tests [1] for the compiler’s vectorizer, and I’ve hopefully shown that even very old versions do just fine. 

Anyway, in the worst case we will eventually write every kernel with xsimd, and have the autovectorized kernels temporarily there. If we find that performance is good on our platforms, then we can skip the “rewrite in xsimd” step. 

Sasha 

[1] https://github.com/llvm/llvm-project/blob/main/llvm/test/Transforms/LoopVectorize/gcc-examples.ll

> 30 марта 2022 г., в 23:38, Antoine Pitrou <an...@python.org> написал(а):
> 
> As I showed, those auto-vectorized kernels may be vectorized only in some situations, depending on the compiler version, the input datatypes...

Re: [C++] Replacing xsimd with compiler autovectorization

[Antoine Pitrou <an...@python.org>]

Le 31/03/2022 à 01:24, Weston Pace a écrit :
> Apologies if this is an over simplified opinion but does it have to be one
> or the other?
> 
> If people contribute and maintain XSIMD kernels then great.
> 
> If people contribute and maintain auto-vectorizable kernels then great.
> 
> Then it just comes down to having consistent dispatch rules.  Something
> like "use XSIMD kernels if it supports the arch otherwise fall back to
> whatever else."
> 
> The plan to generate different auto vectorized versions sounds reasonable.
> Maybe cmake can even add the flags by convention based on the filename.  If
> it causes downstream cmake issues then we just add a flag to disable that
> feature.

As I showed, those auto-vectorized kernels may be vectorized only in 
some situations, depending on the compiler version, the input 
datatypes... If we go through the pain of building the scaffolding for 
that, I'd rather see those kernels explicitly vectorized using xsimd.

Regards

Antoine.



> 
> 
> On Wed, Mar 30, 2022, 11:18 AM Micah Kornfield <em...@gmail.com>
> wrote:
> 
>>>
>>> We were not going to use xsimd's dynamic dispatch, and instead roll our
>> own
>>
>> There is already a dynamic dispatch facility see: arrow/util/dispatch.h
>>
>> Since we're rolling our own dynamic dispatch, we'd still have to compile
>>> the same source file several times with different, so my proposal doesn't
>>> change that.
>>
>> If we are going to be compiling the same file over and over again, it would
>> be nice to have a naming convention for such files so they can be easily
>> distinguished.  We'd need to tackle this complexity at some point, but
>> trying to keep the mechanism understandable by people outside the project
>> is something that we should evaluate as this is implemented.
>>
>> -Micah
>>
>>
>>
>> On Wed, Mar 30, 2022 at 1:19 PM Sasha Krassovsky <
>> krassovskysasha@gmail.com>
>> wrote:
>>
>>>> Looking at the disassembly, the int16 and int32 versions are unrolled
>> and
>>> vectorized by clang 12.0, the int8 and int64 are not...
>>> I think a big part of this is how fragile the current kernel system
>>> implementation is. It seems to rely on templating lots of different parts
>>> of kernels and hoping compiler will glue them together via inlining, and
>>> then vectorize.
>>> GCC 10 does not unroll or vectorize even int32 or int16 for me. I am able
>>> to reproduce the vectorization you noticed with Clang (I'm actually
>> really
>>> impressed).
>>> But still, as you said it's not ideal to have one compiler be much faster
>>> than another. The reason for the difference is possibly due to the
>> ordering
>>> of optimization passes. If a compiler does all of its inlining before
>>> vectorization,
>>> then we can expect good output. If vectorization happens between two
>>> inlining phases, then the compiler cannot vectorize (even if something
>> gets
>>> inlined later). My personal rule of thumb to handle this is to
>>> write code that would be optimized well within only a few optimization
>>> passes (e.g. rely on an inlining, a constant propagation, and a
>>> vectorization pass) instead of relying on the correct distribution of a
>>> large number of passes.
>>>
>>>> How do we ensure that common compiler optimize this routine as
>> expected?
>>> I think the main thing we can do is to write simple code that's obvious
>> for
>>> the compiler to vectorize ("meet the compiler half way" in some sense).
>>> A simple for loop operating on pointers is vectorized very well even by
>>> ancient compilers (below I tested clang 3.9), so I think for a lot of
>> these
>>> kernels if we'd be much more confident of it being consistently
>> vectorized.
>>> https://godbolt.org/z/e36M948jv
>>>
>>>> therefore using xsimd does not prevent the compiler from optimizing
>> more.
>>> My main hesitation here is the same as above with the kernels system: the
>>> more inlining that has to happen, the less likely it is for the compiler
>> to
>>> optimize as efficiently. However,
>>> I do agree this is probably not a big issue with xsimd as it seems pretty
>>> lightweight.
>>>
>>>> we are very responsive to any request and we can quickly implement
>>> features
>>> This is great to hear, and definitely makes me feel alot better about
>>> keeping and using xsimd where necessary.
>>>
>>>> Note however that it requires some basic checking of the output across
>>> different compilers and different compiler versions.
>>> Definitely agree here too. I would be in favor of some middleground of
>>> using autovectorization for simple stuff (like the Add kernel above), and
>>> use xsimd for stuff that doesn't get vectorized well by some compilers.
>>>
>>> So it seems to me that before my email, the current status was:
>>> - We were going to simd-optimize our kernels using xsimd, but hadn't
>> gotten
>>> to it yet. This would've involved changing the kernels system to use
>> xsimd
>>> inside of the operation functors?
>>> - We were not going to use xsimd's dynamic dispatch, and instead roll our
>>> own
>>>
>>> If that's the case then my proposal is relatively minor. Since we're
>>> rolling our own dynamic dispatch, we'd still have to compile the same
>>> source file several times with different, so my proposal doesn't change
>>> that.
>>> The part that my proposal changes is to refactor the code to be more
>>> autovectorization-friendly. This seems to be a minor difference from what
>>> was planned before, where instead of having the operation functor process
>>> one simd-batch at a time, we have it process the whole batch (to minimize
>>> the reliance on inlining). And of course we'd have to actually implement
>>> the dynamic dispatch (I don't think I see it for most of the kernels
>>> system).
>>> Does something like this sound reasonable to people?
>>>
>>> Sasha
>>>
>>> On Wed, Mar 30, 2022 at 1:47 AM Johan Mabille <jo...@gmail.com>
>>> wrote:
>>>
>>>> Hi all,
>>>>
>>>> xsimd core developer here writing on behalf of the xsimd core team ;)
>>>>
>>>> I just wanted to add some elements to this thread:
>>>>
>>>> - xsimd is more than a library that wraps simple intrinsics. It
>> provides
>>>> vectorized (and accurate) implementations of the traditional
>> mathematical
>>>> functions (exp, sin, cos , etc), that a compiler may not be able to
>>>> vectorize. And when the compiler does vectorize them, it usually relies
>>> on
>>>> external libraries that provide such implementations. Therefore, you
>> can
>>>> not guarantee that every compiler will optimize these calls, nor the
>> same
>>>> accuracy across different platforms.
>>>>
>>>> - compilers actually understand intrinsics and can optimize them; it's
>>> not
>>>> a "one intrinsic -> one asm "instruction mapping at all. Therefore,
>> using
>>>> xsimd does not prevent the compiler from optimizing more.
>>>>
>>>> - xsimd is actively developed and maintained. It is used as a building
>>>> block of the xtensor stack, and in Pythran which has been integrated in
>>>> scipy. Some features may be missing because of a lack of time and/or
>>> higher
>>>> priorities. However, Antoine can confirm that we are very responsive to
>>> any
>>>> request and we can quickly implement features that would be mandatory
>> for
>>>> Apache Arrow.
>>>>
>>>> - It is 100% true that for simple loops with simple arithmetic
>>> operations,
>>>> it is easier not to write xsimd code and let the compiler optimize the
>>>> loop. Note however that it requires some basic checking of the output
>>>> across different compilers and different compiler versions. See for
>>>> instance https://godbolt.org/z/KTcTe1zPn. Different versions of gcc
>>>> generate different vectorized code, and clang and gcc do not
>>> auto-vectorize
>>>> at the same optimization level (O2 for clang and O3 or O2
>>> -ftree-vectorize
>>>> for gcc)
>>>>
>>>> Regards,
>>>>
>>>> Johan
>>>>
>>>> On Wed, Mar 30, 2022 at 10:10 AM Antoine Pitrou <an...@python.org>
>>>> wrote:
>>>>
>>>>>
>>>>> Hi Sasha,
>>>>>
>>>>> Le 30/03/2022 à 00:14, Sasha Krassovsky a écrit :
>>>>>> I've noticed that we include xsimd as an abstraction over all of
>> the
>>>> simd
>>>>>> architectures. I'd like to propose a different solution which would
>>>>> result
>>>>>> in fewer lines of code, while being more readable.
>>>>>>
>>>>>> My thinking is that anything simple enough to abstract with xsimd
>> can
>>>> be
>>>>>> autovectorized by the compiler. Any more interesting SIMD algorithm
>>>>> usually
>>>>>> is tailored to the target instruction set and can't be abstracted
>>> away
>>>>> with
>>>>>> xsimd anyway.
>>>>>
>>>>> As a matter of fact, we already rely on auto-vectorization in a
>> couple
>>>>> of places (mostly `aggregate_basic_avx2.cc` and friends).
>>>>>
>>>>> The main concern with doing this is that auto-vectorization makes
>>>>> performance difficult to predict and ensure. Some compiler or
>> compiler
>>>>> versions may fail vectorizing a given piece of code (how does MSVC
>> fare
>>>>> these days?). As a consequence, some Arrow builds may be 2x to 8x
>>> faster
>>>>> than others on the same machine and the same workload. This is not an
>>>>> optimal user experience, and in many cases it can be difficult or
>>>>> impossible to change the compiler version.
>>>>>
>>>>>
>>>>> As matter of fact, on x86 our baseline instruction set is SSE4.2, so
>> we
>>>>> already get some auto-vectorization and we can look at the concrete
>>>>> numbers. On my AMD Zen 2 CPU I get the following numbers on the
>>> pairwise
>>>>> addition kernel (this is with clang 12.0):
>>>>> https://gist.github.com/pitrou/dbfa3d97afb4ebbe096bab69cb6bb4d5
>>>>>
>>>>> Judging that PADDB, PADDW, PADDD and PADDQ all have the same
>> throughput
>>>>> on that CPU (according to
>>>>> https://www.agner.org/optimize/instruction_tables.pdf), all these
>> data
>>>>> types should show the same performance in bytes/second.  Yet int64
>> gets
>>>>> half of int16 and int32, and int8 is far behind.
>>>>>
>>>>> Looking at the disassembly, the int16 and int32 versions are unrolled
>>>>> and vectorized by clang 12.0, the int8 and int64 are not... Why? How
>> do
>>>>> we ensure that common compiler optimize this routine as expected?
>>>>> Personally, I have no idea.
>>>>>
>>>>>
>>>>> As for why xsimd rather than hand-written intrinsics, it's a middle
>>>>> ground in terms of maintainability and readability. Code using
>>>>> intrinsics quickly gets hard to follow except for the daily SIMD
>>>>> specialist, and it's also annoying to port to another architecture
>>> (even
>>>>> due to gratuitous naming differences).
>>>>>
>>>>> As for why xsimd is not very much used accross the codebase, the
>>> initial
>>>>> intent was to have more SIMD-accelerated code, but nobody actually
>> got
>>>>> around to do it, due to other priorities. In the end, we spend more
>>> time
>>>>> adding features than hand-optimizing the existing code.
>>>>>
>>>>> Regards
>>>>>
>>>>> Antoine.
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> With that in mind, I'd like to propose the following strategy:
>>>>>> 1. Write a single source file with simple, element-at-a-time for
>> loop
>>>>>> implementations of each function.
>>>>>> 2. Compile this same source file several times with different
>> compile
>>>>> flags
>>>>>> for different vectorization (e.g. if we're on an x86 machine that
>>>>> supports
>>>>>> AVX2 and AVX512, we'd compile once with -mavx2 and once with
>>>> -mavx512vl).
>>>>>> 3. Functions compiled with different instruction sets can be
>>>>> differentiated
>>>>>> by a namespace, which gets defined during the compiler invocation.
>>> For
>>>>>> example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2
>> and
>>>> then
>>>>>> for something like elementwise addition of two arrays, we'd call
>>>>>> arrow::AVX2::VectorAdd.
>>>>>>
>>>>>> I believe this would let us remove xsimd as a dependency while also
>>>>> giving
>>>>>> us lots of vectorized kernels at the cost of some extra cmake
>> magic.
>>>>> After
>>>>>> that, it would just be a matter of making the function registry
>> point
>>>> to
>>>>>> these new functions.
>>>>>>
>>>>>> Please let me know your thoughts!
>>>>>>
>>>>>> Thanks,
>>>>>> Sasha Krassovsky
>>>>>>
>>>>>
>>>>
>>>
>>
> 

Re: [C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

Yep a suffix _simd would make perfect sense too. 

Sasha 

> 30 марта 2022 г., в 22:58, Micah Kornfield <em...@gmail.com> написал(а):
> 
> 
>> 
>> 
>> As for a naming convention, we could use something like the prefix `simd_`?
> 
> Bikeshedding moment: we use suffixes today for instructions sets would it
> make sense to continue that for consistency.
> 
> `scalar_arithmetic_simd.cc`?
> 
>> On Wed, Mar 30, 2022 at 4:58 PM Sasha Krassovsky <kr...@gmail.com>
>> wrote:
>> 
>> Yep, that's basically what I'm suggesting. If someone contributes an xsimd
>> kernel that's faster than the autovectorized kernel, then it'll be seamless
>> to switch.
>> The xsimd and autovectorized kernels would share the same source file, so
>> anyone contributing an xsimd kernel would just have to change that one
>> function.
>> 
>> As for a naming convention, we could use something like the prefix `simd_`?
>> So for example scalar_arithmetic.cc would have a corresponding file
>> `simd_scalar_arithmetic.cc`,
>> which would be compiled for each simd instruction set that we're targeting.
>> `scalar_arithmetic.cc` would then be responsible for generating the
>> dispatch rules .
>> 
>> Sasha
>> 
>> 
>>> On Wed, Mar 30, 2022 at 4:24 PM Weston Pace <we...@gmail.com> wrote:
>>> 
>>> Apologies if this is an over simplified opinion but does it have to be
>> one
>>> or the other?
>>> 
>>> If people contribute and maintain XSIMD kernels then great.
>>> 
>>> If people contribute and maintain auto-vectorizable kernels then great.
>>> 
>>> Then it just comes down to having consistent dispatch rules.  Something
>>> like "use XSIMD kernels if it supports the arch otherwise fall back to
>>> whatever else."
>>> 
>>> The plan to generate different auto vectorized versions sounds
>> reasonable.
>>> Maybe cmake can even add the flags by convention based on the filename.
>> If
>>> it causes downstream cmake issues then we just add a flag to disable that
>>> feature.
>>> 
>>> 
>>> On Wed, Mar 30, 2022, 11:18 AM Micah Kornfield <em...@gmail.com>
>>> wrote:
>>> 
>>>>> 
>>>>> We were not going to use xsimd's dynamic dispatch, and instead roll
>> our
>>>> own
>>>> 
>>>> There is already a dynamic dispatch facility see: arrow/util/dispatch.h
>>>> 
>>>> Since we're rolling our own dynamic dispatch, we'd still have to
>> compile
>>>>> the same source file several times with different, so my proposal
>>> doesn't
>>>>> change that.
>>>> 
>>>> If we are going to be compiling the same file over and over again, it
>>> would
>>>> be nice to have a naming convention for such files so they can be
>> easily
>>>> distinguished.  We'd need to tackle this complexity at some point, but
>>>> trying to keep the mechanism understandable by people outside the
>> project
>>>> is something that we should evaluate as this is implemented.
>>>> 
>>>> -Micah
>>>> 
>>>> 
>>>> 
>>>> On Wed, Mar 30, 2022 at 1:19 PM Sasha Krassovsky <
>>>> krassovskysasha@gmail.com>
>>>> wrote:
>>>> 
>>>>>> Looking at the disassembly, the int16 and int32 versions are
>> unrolled
>>>> and
>>>>> vectorized by clang 12.0, the int8 and int64 are not...
>>>>> I think a big part of this is how fragile the current kernel system
>>>>> implementation is. It seems to rely on templating lots of different
>>> parts
>>>>> of kernels and hoping compiler will glue them together via inlining,
>>> and
>>>>> then vectorize.
>>>>> GCC 10 does not unroll or vectorize even int32 or int16 for me. I am
>>> able
>>>>> to reproduce the vectorization you noticed with Clang (I'm actually
>>>> really
>>>>> impressed).
>>>>> But still, as you said it's not ideal to have one compiler be much
>>> faster
>>>>> than another. The reason for the difference is possibly due to the
>>>> ordering
>>>>> of optimization passes. If a compiler does all of its inlining before
>>>>> vectorization,
>>>>> then we can expect good output. If vectorization happens between two
>>>>> inlining phases, then the compiler cannot vectorize (even if
>> something
>>>> gets
>>>>> inlined later). My personal rule of thumb to handle this is to
>>>>> write code that would be optimized well within only a few
>> optimization
>>>>> passes (e.g. rely on an inlining, a constant propagation, and a
>>>>> vectorization pass) instead of relying on the correct distribution
>> of a
>>>>> large number of passes.
>>>>> 
>>>>>> How do we ensure that common compiler optimize this routine as
>>>> expected?
>>>>> I think the main thing we can do is to write simple code that's
>> obvious
>>>> for
>>>>> the compiler to vectorize ("meet the compiler half way" in some
>> sense).
>>>>> A simple for loop operating on pointers is vectorized very well even
>> by
>>>>> ancient compilers (below I tested clang 3.9), so I think for a lot of
>>>> these
>>>>> kernels if we'd be much more confident of it being consistently
>>>> vectorized.
>>>>> https://godbolt.org/z/e36M948jv
>>>>> 
>>>>>> therefore using xsimd does not prevent the compiler from optimizing
>>>> more.
>>>>> My main hesitation here is the same as above with the kernels system:
>>> the
>>>>> more inlining that has to happen, the less likely it is for the
>>> compiler
>>>> to
>>>>> optimize as efficiently. However,
>>>>> I do agree this is probably not a big issue with xsimd as it seems
>>> pretty
>>>>> lightweight.
>>>>> 
>>>>>> we are very responsive to any request and we can quickly implement
>>>>> features
>>>>> This is great to hear, and definitely makes me feel alot better about
>>>>> keeping and using xsimd where necessary.
>>>>> 
>>>>>> Note however that it requires some basic checking of the output
>>> across
>>>>> different compilers and different compiler versions.
>>>>> Definitely agree here too. I would be in favor of some middleground
>> of
>>>>> using autovectorization for simple stuff (like the Add kernel above),
>>> and
>>>>> use xsimd for stuff that doesn't get vectorized well by some
>> compilers.
>>>>> 
>>>>> So it seems to me that before my email, the current status was:
>>>>> - We were going to simd-optimize our kernels using xsimd, but hadn't
>>>> gotten
>>>>> to it yet. This would've involved changing the kernels system to use
>>>> xsimd
>>>>> inside of the operation functors?
>>>>> - We were not going to use xsimd's dynamic dispatch, and instead roll
>>> our
>>>>> own
>>>>> 
>>>>> If that's the case then my proposal is relatively minor. Since we're
>>>>> rolling our own dynamic dispatch, we'd still have to compile the same
>>>>> source file several times with different, so my proposal doesn't
>> change
>>>>> that.
>>>>> The part that my proposal changes is to refactor the code to be more
>>>>> autovectorization-friendly. This seems to be a minor difference from
>>> what
>>>>> was planned before, where instead of having the operation functor
>>> process
>>>>> one simd-batch at a time, we have it process the whole batch (to
>>> minimize
>>>>> the reliance on inlining). And of course we'd have to actually
>>> implement
>>>>> the dynamic dispatch (I don't think I see it for most of the kernels
>>>>> system).
>>>>> Does something like this sound reasonable to people?
>>>>> 
>>>>> Sasha
>>>>> 
>>>>> On Wed, Mar 30, 2022 at 1:47 AM Johan Mabille <
>> johan.mabille@gmail.com
>>>> 
>>>>> wrote:
>>>>> 
>>>>>> Hi all,
>>>>>> 
>>>>>> xsimd core developer here writing on behalf of the xsimd core team
>> ;)
>>>>>> 
>>>>>> I just wanted to add some elements to this thread:
>>>>>> 
>>>>>> - xsimd is more than a library that wraps simple intrinsics. It
>>>> provides
>>>>>> vectorized (and accurate) implementations of the traditional
>>>> mathematical
>>>>>> functions (exp, sin, cos , etc), that a compiler may not be able to
>>>>>> vectorize. And when the compiler does vectorize them, it usually
>>> relies
>>>>> on
>>>>>> external libraries that provide such implementations. Therefore,
>> you
>>>> can
>>>>>> not guarantee that every compiler will optimize these calls, nor
>> the
>>>> same
>>>>>> accuracy across different platforms.
>>>>>> 
>>>>>> - compilers actually understand intrinsics and can optimize them;
>>> it's
>>>>> not
>>>>>> a "one intrinsic -> one asm "instruction mapping at all. Therefore,
>>>> using
>>>>>> xsimd does not prevent the compiler from optimizing more.
>>>>>> 
>>>>>> - xsimd is actively developed and maintained. It is used as a
>>> building
>>>>>> block of the xtensor stack, and in Pythran which has been
>> integrated
>>> in
>>>>>> scipy. Some features may be missing because of a lack of time
>> and/or
>>>>> higher
>>>>>> priorities. However, Antoine can confirm that we are very
>> responsive
>>> to
>>>>> any
>>>>>> request and we can quickly implement features that would be
>> mandatory
>>>> for
>>>>>> Apache Arrow.
>>>>>> 
>>>>>> - It is 100% true that for simple loops with simple arithmetic
>>>>> operations,
>>>>>> it is easier not to write xsimd code and let the compiler optimize
>>> the
>>>>>> loop. Note however that it requires some basic checking of the
>> output
>>>>>> across different compilers and different compiler versions. See for
>>>>>> instance https://godbolt.org/z/KTcTe1zPn. Different versions of
>> gcc
>>>>>> generate different vectorized code, and clang and gcc do not
>>>>> auto-vectorize
>>>>>> at the same optimization level (O2 for clang and O3 or O2
>>>>> -ftree-vectorize
>>>>>> for gcc)
>>>>>> 
>>>>>> Regards,
>>>>>> 
>>>>>> Johan
>>>>>> 
>>>>>> On Wed, Mar 30, 2022 at 10:10 AM Antoine Pitrou <
>> antoine@python.org>
>>>>>> wrote:
>>>>>> 
>>>>>>> 
>>>>>>> Hi Sasha,
>>>>>>> 
>>>>>>> Le 30/03/2022 à 00:14, Sasha Krassovsky a écrit :
>>>>>>>> I've noticed that we include xsimd as an abstraction over all
>> of
>>>> the
>>>>>> simd
>>>>>>>> architectures. I'd like to propose a different solution which
>>> would
>>>>>>> result
>>>>>>>> in fewer lines of code, while being more readable.
>>>>>>>> 
>>>>>>>> My thinking is that anything simple enough to abstract with
>> xsimd
>>>> can
>>>>>> be
>>>>>>>> autovectorized by the compiler. Any more interesting SIMD
>>> algorithm
>>>>>>> usually
>>>>>>>> is tailored to the target instruction set and can't be
>> abstracted
>>>>> away
>>>>>>> with
>>>>>>>> xsimd anyway.
>>>>>>> 
>>>>>>> As a matter of fact, we already rely on auto-vectorization in a
>>>> couple
>>>>>>> of places (mostly `aggregate_basic_avx2.cc` and friends).
>>>>>>> 
>>>>>>> The main concern with doing this is that auto-vectorization makes
>>>>>>> performance difficult to predict and ensure. Some compiler or
>>>> compiler
>>>>>>> versions may fail vectorizing a given piece of code (how does
>> MSVC
>>>> fare
>>>>>>> these days?). As a consequence, some Arrow builds may be 2x to 8x
>>>>> faster
>>>>>>> than others on the same machine and the same workload. This is
>> not
>>> an
>>>>>>> optimal user experience, and in many cases it can be difficult or
>>>>>>> impossible to change the compiler version.
>>>>>>> 
>>>>>>> 
>>>>>>> As matter of fact, on x86 our baseline instruction set is SSE4.2,
>>> so
>>>> we
>>>>>>> already get some auto-vectorization and we can look at the
>> concrete
>>>>>>> numbers. On my AMD Zen 2 CPU I get the following numbers on the
>>>>> pairwise
>>>>>>> addition kernel (this is with clang 12.0):
>>>>>>> https://gist.github.com/pitrou/dbfa3d97afb4ebbe096bab69cb6bb4d5
>>>>>>> 
>>>>>>> Judging that PADDB, PADDW, PADDD and PADDQ all have the same
>>>> throughput
>>>>>>> on that CPU (according to
>>>>>>> https://www.agner.org/optimize/instruction_tables.pdf), all
>> these
>>>> data
>>>>>>> types should show the same performance in bytes/second.  Yet
>> int64
>>>> gets
>>>>>>> half of int16 and int32, and int8 is far behind.
>>>>>>> 
>>>>>>> Looking at the disassembly, the int16 and int32 versions are
>>> unrolled
>>>>>>> and vectorized by clang 12.0, the int8 and int64 are not... Why?
>>> How
>>>> do
>>>>>>> we ensure that common compiler optimize this routine as expected?
>>>>>>> Personally, I have no idea.
>>>>>>> 
>>>>>>> 
>>>>>>> As for why xsimd rather than hand-written intrinsics, it's a
>> middle
>>>>>>> ground in terms of maintainability and readability. Code using
>>>>>>> intrinsics quickly gets hard to follow except for the daily SIMD
>>>>>>> specialist, and it's also annoying to port to another
>> architecture
>>>>> (even
>>>>>>> due to gratuitous naming differences).
>>>>>>> 
>>>>>>> As for why xsimd is not very much used accross the codebase, the
>>>>> initial
>>>>>>> intent was to have more SIMD-accelerated code, but nobody
>> actually
>>>> got
>>>>>>> around to do it, due to other priorities. In the end, we spend
>> more
>>>>> time
>>>>>>> adding features than hand-optimizing the existing code.
>>>>>>> 
>>>>>>> Regards
>>>>>>> 
>>>>>>> Antoine.
>>>>>>> 
>>>>>>> 
>>>>>>> 
>>>>>>>> 
>>>>>>>> With that in mind, I'd like to propose the following strategy:
>>>>>>>> 1. Write a single source file with simple, element-at-a-time
>> for
>>>> loop
>>>>>>>> implementations of each function.
>>>>>>>> 2. Compile this same source file several times with different
>>>> compile
>>>>>>> flags
>>>>>>>> for different vectorization (e.g. if we're on an x86 machine
>> that
>>>>>>> supports
>>>>>>>> AVX2 and AVX512, we'd compile once with -mavx2 and once with
>>>>>> -mavx512vl).
>>>>>>>> 3. Functions compiled with different instruction sets can be
>>>>>>> differentiated
>>>>>>>> by a namespace, which gets defined during the compiler
>>> invocation.
>>>>> For
>>>>>>>> example, for AVX2 we'd invoke the compiler with
>> -DNAMESPACE=AVX2
>>>> and
>>>>>> then
>>>>>>>> for something like elementwise addition of two arrays, we'd
>> call
>>>>>>>> arrow::AVX2::VectorAdd.
>>>>>>>> 
>>>>>>>> I believe this would let us remove xsimd as a dependency while
>>> also
>>>>>>> giving
>>>>>>>> us lots of vectorized kernels at the cost of some extra cmake
>>>> magic.
>>>>>>> After
>>>>>>>> that, it would just be a matter of making the function registry
>>>> point
>>>>>> to
>>>>>>>> these new functions.
>>>>>>>> 
>>>>>>>> Please let me know your thoughts!
>>>>>>>> 
>>>>>>>> Thanks,
>>>>>>>> Sasha Krassovsky
>>>>>>>> 
>>>>>>> 
>>>>>> 
>>>>> 
>>>> 
>>> 
>> 

Re: [C++] Replacing xsimd with compiler autovectorization

[Micah Kornfield <em...@gmail.com>]

>
> As for a naming convention, we could use something like the prefix `simd_`?

Bikeshedding moment: we use suffixes today for instructions sets would it
make sense to continue that for consistency.

`scalar_arithmetic_simd.cc`?

On Wed, Mar 30, 2022 at 4:58 PM Sasha Krassovsky <kr...@gmail.com>
wrote:

> Yep, that's basically what I'm suggesting. If someone contributes an xsimd
> kernel that's faster than the autovectorized kernel, then it'll be seamless
> to switch.
> The xsimd and autovectorized kernels would share the same source file, so
> anyone contributing an xsimd kernel would just have to change that one
> function.
>
> As for a naming convention, we could use something like the prefix `simd_`?
> So for example scalar_arithmetic.cc would have a corresponding file
> `simd_scalar_arithmetic.cc`,
> which would be compiled for each simd instruction set that we're targeting.
> `scalar_arithmetic.cc` would then be responsible for generating the
> dispatch rules .
>
> Sasha
>
>
> On Wed, Mar 30, 2022 at 4:24 PM Weston Pace <we...@gmail.com> wrote:
>
> > Apologies if this is an over simplified opinion but does it have to be
> one
> > or the other?
> >
> > If people contribute and maintain XSIMD kernels then great.
> >
> > If people contribute and maintain auto-vectorizable kernels then great.
> >
> > Then it just comes down to having consistent dispatch rules.  Something
> > like "use XSIMD kernels if it supports the arch otherwise fall back to
> > whatever else."
> >
> > The plan to generate different auto vectorized versions sounds
> reasonable.
> > Maybe cmake can even add the flags by convention based on the filename.
> If
> > it causes downstream cmake issues then we just add a flag to disable that
> > feature.
> >
> >
> > On Wed, Mar 30, 2022, 11:18 AM Micah Kornfield <em...@gmail.com>
> > wrote:
> >
> > > >
> > > > We were not going to use xsimd's dynamic dispatch, and instead roll
> our
> > > own
> > >
> > > There is already a dynamic dispatch facility see: arrow/util/dispatch.h
> > >
> > > Since we're rolling our own dynamic dispatch, we'd still have to
> compile
> > > > the same source file several times with different, so my proposal
> > doesn't
> > > > change that.
> > >
> > > If we are going to be compiling the same file over and over again, it
> > would
> > > be nice to have a naming convention for such files so they can be
> easily
> > > distinguished.  We'd need to tackle this complexity at some point, but
> > > trying to keep the mechanism understandable by people outside the
> project
> > > is something that we should evaluate as this is implemented.
> > >
> > > -Micah
> > >
> > >
> > >
> > > On Wed, Mar 30, 2022 at 1:19 PM Sasha Krassovsky <
> > > krassovskysasha@gmail.com>
> > > wrote:
> > >
> > > > > Looking at the disassembly, the int16 and int32 versions are
> unrolled
> > > and
> > > > vectorized by clang 12.0, the int8 and int64 are not...
> > > > I think a big part of this is how fragile the current kernel system
> > > > implementation is. It seems to rely on templating lots of different
> > parts
> > > > of kernels and hoping compiler will glue them together via inlining,
> > and
> > > > then vectorize.
> > > > GCC 10 does not unroll or vectorize even int32 or int16 for me. I am
> > able
> > > > to reproduce the vectorization you noticed with Clang (I'm actually
> > > really
> > > > impressed).
> > > > But still, as you said it's not ideal to have one compiler be much
> > faster
> > > > than another. The reason for the difference is possibly due to the
> > > ordering
> > > > of optimization passes. If a compiler does all of its inlining before
> > > > vectorization,
> > > > then we can expect good output. If vectorization happens between two
> > > > inlining phases, then the compiler cannot vectorize (even if
> something
> > > gets
> > > > inlined later). My personal rule of thumb to handle this is to
> > > > write code that would be optimized well within only a few
> optimization
> > > > passes (e.g. rely on an inlining, a constant propagation, and a
> > > > vectorization pass) instead of relying on the correct distribution
> of a
> > > > large number of passes.
> > > >
> > > > > How do we ensure that common compiler optimize this routine as
> > > expected?
> > > > I think the main thing we can do is to write simple code that's
> obvious
> > > for
> > > > the compiler to vectorize ("meet the compiler half way" in some
> sense).
> > > > A simple for loop operating on pointers is vectorized very well even
> by
> > > > ancient compilers (below I tested clang 3.9), so I think for a lot of
> > > these
> > > > kernels if we'd be much more confident of it being consistently
> > > vectorized.
> > > > https://godbolt.org/z/e36M948jv
> > > >
> > > > > therefore using xsimd does not prevent the compiler from optimizing
> > > more.
> > > > My main hesitation here is the same as above with the kernels system:
> > the
> > > > more inlining that has to happen, the less likely it is for the
> > compiler
> > > to
> > > > optimize as efficiently. However,
> > > > I do agree this is probably not a big issue with xsimd as it seems
> > pretty
> > > > lightweight.
> > > >
> > > > > we are very responsive to any request and we can quickly implement
> > > > features
> > > > This is great to hear, and definitely makes me feel alot better about
> > > > keeping and using xsimd where necessary.
> > > >
> > > > > Note however that it requires some basic checking of the output
> > across
> > > > different compilers and different compiler versions.
> > > > Definitely agree here too. I would be in favor of some middleground
> of
> > > > using autovectorization for simple stuff (like the Add kernel above),
> > and
> > > > use xsimd for stuff that doesn't get vectorized well by some
> compilers.
> > > >
> > > > So it seems to me that before my email, the current status was:
> > > > - We were going to simd-optimize our kernels using xsimd, but hadn't
> > > gotten
> > > > to it yet. This would've involved changing the kernels system to use
> > > xsimd
> > > > inside of the operation functors?
> > > > - We were not going to use xsimd's dynamic dispatch, and instead roll
> > our
> > > > own
> > > >
> > > > If that's the case then my proposal is relatively minor. Since we're
> > > > rolling our own dynamic dispatch, we'd still have to compile the same
> > > > source file several times with different, so my proposal doesn't
> change
> > > > that.
> > > > The part that my proposal changes is to refactor the code to be more
> > > > autovectorization-friendly. This seems to be a minor difference from
> > what
> > > > was planned before, where instead of having the operation functor
> > process
> > > > one simd-batch at a time, we have it process the whole batch (to
> > minimize
> > > > the reliance on inlining). And of course we'd have to actually
> > implement
> > > > the dynamic dispatch (I don't think I see it for most of the kernels
> > > > system).
> > > > Does something like this sound reasonable to people?
> > > >
> > > > Sasha
> > > >
> > > > On Wed, Mar 30, 2022 at 1:47 AM Johan Mabille <
> johan.mabille@gmail.com
> > >
> > > > wrote:
> > > >
> > > > > Hi all,
> > > > >
> > > > > xsimd core developer here writing on behalf of the xsimd core team
> ;)
> > > > >
> > > > > I just wanted to add some elements to this thread:
> > > > >
> > > > > - xsimd is more than a library that wraps simple intrinsics. It
> > > provides
> > > > > vectorized (and accurate) implementations of the traditional
> > > mathematical
> > > > > functions (exp, sin, cos , etc), that a compiler may not be able to
> > > > > vectorize. And when the compiler does vectorize them, it usually
> > relies
> > > > on
> > > > > external libraries that provide such implementations. Therefore,
> you
> > > can
> > > > > not guarantee that every compiler will optimize these calls, nor
> the
> > > same
> > > > > accuracy across different platforms.
> > > > >
> > > > > - compilers actually understand intrinsics and can optimize them;
> > it's
> > > > not
> > > > > a "one intrinsic -> one asm "instruction mapping at all. Therefore,
> > > using
> > > > > xsimd does not prevent the compiler from optimizing more.
> > > > >
> > > > > - xsimd is actively developed and maintained. It is used as a
> > building
> > > > > block of the xtensor stack, and in Pythran which has been
> integrated
> > in
> > > > > scipy. Some features may be missing because of a lack of time
> and/or
> > > > higher
> > > > > priorities. However, Antoine can confirm that we are very
> responsive
> > to
> > > > any
> > > > > request and we can quickly implement features that would be
> mandatory
> > > for
> > > > > Apache Arrow.
> > > > >
> > > > > - It is 100% true that for simple loops with simple arithmetic
> > > > operations,
> > > > > it is easier not to write xsimd code and let the compiler optimize
> > the
> > > > > loop. Note however that it requires some basic checking of the
> output
> > > > > across different compilers and different compiler versions. See for
> > > > > instance https://godbolt.org/z/KTcTe1zPn. Different versions of
> gcc
> > > > > generate different vectorized code, and clang and gcc do not
> > > > auto-vectorize
> > > > > at the same optimization level (O2 for clang and O3 or O2
> > > > -ftree-vectorize
> > > > > for gcc)
> > > > >
> > > > > Regards,
> > > > >
> > > > > Johan
> > > > >
> > > > > On Wed, Mar 30, 2022 at 10:10 AM Antoine Pitrou <
> antoine@python.org>
> > > > > wrote:
> > > > >
> > > > > >
> > > > > > Hi Sasha,
> > > > > >
> > > > > > Le 30/03/2022 à 00:14, Sasha Krassovsky a écrit :
> > > > > > > I've noticed that we include xsimd as an abstraction over all
> of
> > > the
> > > > > simd
> > > > > > > architectures. I'd like to propose a different solution which
> > would
> > > > > > result
> > > > > > > in fewer lines of code, while being more readable.
> > > > > > >
> > > > > > > My thinking is that anything simple enough to abstract with
> xsimd
> > > can
> > > > > be
> > > > > > > autovectorized by the compiler. Any more interesting SIMD
> > algorithm
> > > > > > usually
> > > > > > > is tailored to the target instruction set and can't be
> abstracted
> > > > away
> > > > > > with
> > > > > > > xsimd anyway.
> > > > > >
> > > > > > As a matter of fact, we already rely on auto-vectorization in a
> > > couple
> > > > > > of places (mostly `aggregate_basic_avx2.cc` and friends).
> > > > > >
> > > > > > The main concern with doing this is that auto-vectorization makes
> > > > > > performance difficult to predict and ensure. Some compiler or
> > > compiler
> > > > > > versions may fail vectorizing a given piece of code (how does
> MSVC
> > > fare
> > > > > > these days?). As a consequence, some Arrow builds may be 2x to 8x
> > > > faster
> > > > > > than others on the same machine and the same workload. This is
> not
> > an
> > > > > > optimal user experience, and in many cases it can be difficult or
> > > > > > impossible to change the compiler version.
> > > > > >
> > > > > >
> > > > > > As matter of fact, on x86 our baseline instruction set is SSE4.2,
> > so
> > > we
> > > > > > already get some auto-vectorization and we can look at the
> concrete
> > > > > > numbers. On my AMD Zen 2 CPU I get the following numbers on the
> > > > pairwise
> > > > > > addition kernel (this is with clang 12.0):
> > > > > > https://gist.github.com/pitrou/dbfa3d97afb4ebbe096bab69cb6bb4d5
> > > > > >
> > > > > > Judging that PADDB, PADDW, PADDD and PADDQ all have the same
> > > throughput
> > > > > > on that CPU (according to
> > > > > > https://www.agner.org/optimize/instruction_tables.pdf), all
> these
> > > data
> > > > > > types should show the same performance in bytes/second.  Yet
> int64
> > > gets
> > > > > > half of int16 and int32, and int8 is far behind.
> > > > > >
> > > > > > Looking at the disassembly, the int16 and int32 versions are
> > unrolled
> > > > > > and vectorized by clang 12.0, the int8 and int64 are not... Why?
> > How
> > > do
> > > > > > we ensure that common compiler optimize this routine as expected?
> > > > > > Personally, I have no idea.
> > > > > >
> > > > > >
> > > > > > As for why xsimd rather than hand-written intrinsics, it's a
> middle
> > > > > > ground in terms of maintainability and readability. Code using
> > > > > > intrinsics quickly gets hard to follow except for the daily SIMD
> > > > > > specialist, and it's also annoying to port to another
> architecture
> > > > (even
> > > > > > due to gratuitous naming differences).
> > > > > >
> > > > > > As for why xsimd is not very much used accross the codebase, the
> > > > initial
> > > > > > intent was to have more SIMD-accelerated code, but nobody
> actually
> > > got
> > > > > > around to do it, due to other priorities. In the end, we spend
> more
> > > > time
> > > > > > adding features than hand-optimizing the existing code.
> > > > > >
> > > > > > Regards
> > > > > >
> > > > > > Antoine.
> > > > > >
> > > > > >
> > > > > >
> > > > > > >
> > > > > > > With that in mind, I'd like to propose the following strategy:
> > > > > > > 1. Write a single source file with simple, element-at-a-time
> for
> > > loop
> > > > > > > implementations of each function.
> > > > > > > 2. Compile this same source file several times with different
> > > compile
> > > > > > flags
> > > > > > > for different vectorization (e.g. if we're on an x86 machine
> that
> > > > > > supports
> > > > > > > AVX2 and AVX512, we'd compile once with -mavx2 and once with
> > > > > -mavx512vl).
> > > > > > > 3. Functions compiled with different instruction sets can be
> > > > > > differentiated
> > > > > > > by a namespace, which gets defined during the compiler
> > invocation.
> > > > For
> > > > > > > example, for AVX2 we'd invoke the compiler with
> -DNAMESPACE=AVX2
> > > and
> > > > > then
> > > > > > > for something like elementwise addition of two arrays, we'd
> call
> > > > > > > arrow::AVX2::VectorAdd.
> > > > > > >
> > > > > > > I believe this would let us remove xsimd as a dependency while
> > also
> > > > > > giving
> > > > > > > us lots of vectorized kernels at the cost of some extra cmake
> > > magic.
> > > > > > After
> > > > > > > that, it would just be a matter of making the function registry
> > > point
> > > > > to
> > > > > > > these new functions.
> > > > > > >
> > > > > > > Please let me know your thoughts!
> > > > > > >
> > > > > > > Thanks,
> > > > > > > Sasha Krassovsky
> > > > > > >
> > > > > >
> > > > >
> > > >
> > >
> >
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

Yep, that's basically what I'm suggesting. If someone contributes an xsimd
kernel that's faster than the autovectorized kernel, then it'll be seamless
to switch.
The xsimd and autovectorized kernels would share the same source file, so
anyone contributing an xsimd kernel would just have to change that one
function.

As for a naming convention, we could use something like the prefix `simd_`?
So for example scalar_arithmetic.cc would have a corresponding file
`simd_scalar_arithmetic.cc`,
which would be compiled for each simd instruction set that we're targeting.
`scalar_arithmetic.cc` would then be responsible for generating the
dispatch rules .

Sasha


On Wed, Mar 30, 2022 at 4:24 PM Weston Pace <we...@gmail.com> wrote:

> Apologies if this is an over simplified opinion but does it have to be one
> or the other?
>
> If people contribute and maintain XSIMD kernels then great.
>
> If people contribute and maintain auto-vectorizable kernels then great.
>
> Then it just comes down to having consistent dispatch rules.  Something
> like "use XSIMD kernels if it supports the arch otherwise fall back to
> whatever else."
>
> The plan to generate different auto vectorized versions sounds reasonable.
> Maybe cmake can even add the flags by convention based on the filename.  If
> it causes downstream cmake issues then we just add a flag to disable that
> feature.
>
>
> On Wed, Mar 30, 2022, 11:18 AM Micah Kornfield <em...@gmail.com>
> wrote:
>
> > >
> > > We were not going to use xsimd's dynamic dispatch, and instead roll our
> > own
> >
> > There is already a dynamic dispatch facility see: arrow/util/dispatch.h
> >
> > Since we're rolling our own dynamic dispatch, we'd still have to compile
> > > the same source file several times with different, so my proposal
> doesn't
> > > change that.
> >
> > If we are going to be compiling the same file over and over again, it
> would
> > be nice to have a naming convention for such files so they can be easily
> > distinguished.  We'd need to tackle this complexity at some point, but
> > trying to keep the mechanism understandable by people outside the project
> > is something that we should evaluate as this is implemented.
> >
> > -Micah
> >
> >
> >
> > On Wed, Mar 30, 2022 at 1:19 PM Sasha Krassovsky <
> > krassovskysasha@gmail.com>
> > wrote:
> >
> > > > Looking at the disassembly, the int16 and int32 versions are unrolled
> > and
> > > vectorized by clang 12.0, the int8 and int64 are not...
> > > I think a big part of this is how fragile the current kernel system
> > > implementation is. It seems to rely on templating lots of different
> parts
> > > of kernels and hoping compiler will glue them together via inlining,
> and
> > > then vectorize.
> > > GCC 10 does not unroll or vectorize even int32 or int16 for me. I am
> able
> > > to reproduce the vectorization you noticed with Clang (I'm actually
> > really
> > > impressed).
> > > But still, as you said it's not ideal to have one compiler be much
> faster
> > > than another. The reason for the difference is possibly due to the
> > ordering
> > > of optimization passes. If a compiler does all of its inlining before
> > > vectorization,
> > > then we can expect good output. If vectorization happens between two
> > > inlining phases, then the compiler cannot vectorize (even if something
> > gets
> > > inlined later). My personal rule of thumb to handle this is to
> > > write code that would be optimized well within only a few optimization
> > > passes (e.g. rely on an inlining, a constant propagation, and a
> > > vectorization pass) instead of relying on the correct distribution of a
> > > large number of passes.
> > >
> > > > How do we ensure that common compiler optimize this routine as
> > expected?
> > > I think the main thing we can do is to write simple code that's obvious
> > for
> > > the compiler to vectorize ("meet the compiler half way" in some sense).
> > > A simple for loop operating on pointers is vectorized very well even by
> > > ancient compilers (below I tested clang 3.9), so I think for a lot of
> > these
> > > kernels if we'd be much more confident of it being consistently
> > vectorized.
> > > https://godbolt.org/z/e36M948jv
> > >
> > > > therefore using xsimd does not prevent the compiler from optimizing
> > more.
> > > My main hesitation here is the same as above with the kernels system:
> the
> > > more inlining that has to happen, the less likely it is for the
> compiler
> > to
> > > optimize as efficiently. However,
> > > I do agree this is probably not a big issue with xsimd as it seems
> pretty
> > > lightweight.
> > >
> > > > we are very responsive to any request and we can quickly implement
> > > features
> > > This is great to hear, and definitely makes me feel alot better about
> > > keeping and using xsimd where necessary.
> > >
> > > > Note however that it requires some basic checking of the output
> across
> > > different compilers and different compiler versions.
> > > Definitely agree here too. I would be in favor of some middleground of
> > > using autovectorization for simple stuff (like the Add kernel above),
> and
> > > use xsimd for stuff that doesn't get vectorized well by some compilers.
> > >
> > > So it seems to me that before my email, the current status was:
> > > - We were going to simd-optimize our kernels using xsimd, but hadn't
> > gotten
> > > to it yet. This would've involved changing the kernels system to use
> > xsimd
> > > inside of the operation functors?
> > > - We were not going to use xsimd's dynamic dispatch, and instead roll
> our
> > > own
> > >
> > > If that's the case then my proposal is relatively minor. Since we're
> > > rolling our own dynamic dispatch, we'd still have to compile the same
> > > source file several times with different, so my proposal doesn't change
> > > that.
> > > The part that my proposal changes is to refactor the code to be more
> > > autovectorization-friendly. This seems to be a minor difference from
> what
> > > was planned before, where instead of having the operation functor
> process
> > > one simd-batch at a time, we have it process the whole batch (to
> minimize
> > > the reliance on inlining). And of course we'd have to actually
> implement
> > > the dynamic dispatch (I don't think I see it for most of the kernels
> > > system).
> > > Does something like this sound reasonable to people?
> > >
> > > Sasha
> > >
> > > On Wed, Mar 30, 2022 at 1:47 AM Johan Mabille <johan.mabille@gmail.com
> >
> > > wrote:
> > >
> > > > Hi all,
> > > >
> > > > xsimd core developer here writing on behalf of the xsimd core team ;)
> > > >
> > > > I just wanted to add some elements to this thread:
> > > >
> > > > - xsimd is more than a library that wraps simple intrinsics. It
> > provides
> > > > vectorized (and accurate) implementations of the traditional
> > mathematical
> > > > functions (exp, sin, cos , etc), that a compiler may not be able to
> > > > vectorize. And when the compiler does vectorize them, it usually
> relies
> > > on
> > > > external libraries that provide such implementations. Therefore, you
> > can
> > > > not guarantee that every compiler will optimize these calls, nor the
> > same
> > > > accuracy across different platforms.
> > > >
> > > > - compilers actually understand intrinsics and can optimize them;
> it's
> > > not
> > > > a "one intrinsic -> one asm "instruction mapping at all. Therefore,
> > using
> > > > xsimd does not prevent the compiler from optimizing more.
> > > >
> > > > - xsimd is actively developed and maintained. It is used as a
> building
> > > > block of the xtensor stack, and in Pythran which has been integrated
> in
> > > > scipy. Some features may be missing because of a lack of time and/or
> > > higher
> > > > priorities. However, Antoine can confirm that we are very responsive
> to
> > > any
> > > > request and we can quickly implement features that would be mandatory
> > for
> > > > Apache Arrow.
> > > >
> > > > - It is 100% true that for simple loops with simple arithmetic
> > > operations,
> > > > it is easier not to write xsimd code and let the compiler optimize
> the
> > > > loop. Note however that it requires some basic checking of the output
> > > > across different compilers and different compiler versions. See for
> > > > instance https://godbolt.org/z/KTcTe1zPn. Different versions of gcc
> > > > generate different vectorized code, and clang and gcc do not
> > > auto-vectorize
> > > > at the same optimization level (O2 for clang and O3 or O2
> > > -ftree-vectorize
> > > > for gcc)
> > > >
> > > > Regards,
> > > >
> > > > Johan
> > > >
> > > > On Wed, Mar 30, 2022 at 10:10 AM Antoine Pitrou <an...@python.org>
> > > > wrote:
> > > >
> > > > >
> > > > > Hi Sasha,
> > > > >
> > > > > Le 30/03/2022 à 00:14, Sasha Krassovsky a écrit :
> > > > > > I've noticed that we include xsimd as an abstraction over all of
> > the
> > > > simd
> > > > > > architectures. I'd like to propose a different solution which
> would
> > > > > result
> > > > > > in fewer lines of code, while being more readable.
> > > > > >
> > > > > > My thinking is that anything simple enough to abstract with xsimd
> > can
> > > > be
> > > > > > autovectorized by the compiler. Any more interesting SIMD
> algorithm
> > > > > usually
> > > > > > is tailored to the target instruction set and can't be abstracted
> > > away
> > > > > with
> > > > > > xsimd anyway.
> > > > >
> > > > > As a matter of fact, we already rely on auto-vectorization in a
> > couple
> > > > > of places (mostly `aggregate_basic_avx2.cc` and friends).
> > > > >
> > > > > The main concern with doing this is that auto-vectorization makes
> > > > > performance difficult to predict and ensure. Some compiler or
> > compiler
> > > > > versions may fail vectorizing a given piece of code (how does MSVC
> > fare
> > > > > these days?). As a consequence, some Arrow builds may be 2x to 8x
> > > faster
> > > > > than others on the same machine and the same workload. This is not
> an
> > > > > optimal user experience, and in many cases it can be difficult or
> > > > > impossible to change the compiler version.
> > > > >
> > > > >
> > > > > As matter of fact, on x86 our baseline instruction set is SSE4.2,
> so
> > we
> > > > > already get some auto-vectorization and we can look at the concrete
> > > > > numbers. On my AMD Zen 2 CPU I get the following numbers on the
> > > pairwise
> > > > > addition kernel (this is with clang 12.0):
> > > > > https://gist.github.com/pitrou/dbfa3d97afb4ebbe096bab69cb6bb4d5
> > > > >
> > > > > Judging that PADDB, PADDW, PADDD and PADDQ all have the same
> > throughput
> > > > > on that CPU (according to
> > > > > https://www.agner.org/optimize/instruction_tables.pdf), all these
> > data
> > > > > types should show the same performance in bytes/second.  Yet int64
> > gets
> > > > > half of int16 and int32, and int8 is far behind.
> > > > >
> > > > > Looking at the disassembly, the int16 and int32 versions are
> unrolled
> > > > > and vectorized by clang 12.0, the int8 and int64 are not... Why?
> How
> > do
> > > > > we ensure that common compiler optimize this routine as expected?
> > > > > Personally, I have no idea.
> > > > >
> > > > >
> > > > > As for why xsimd rather than hand-written intrinsics, it's a middle
> > > > > ground in terms of maintainability and readability. Code using
> > > > > intrinsics quickly gets hard to follow except for the daily SIMD
> > > > > specialist, and it's also annoying to port to another architecture
> > > (even
> > > > > due to gratuitous naming differences).
> > > > >
> > > > > As for why xsimd is not very much used accross the codebase, the
> > > initial
> > > > > intent was to have more SIMD-accelerated code, but nobody actually
> > got
> > > > > around to do it, due to other priorities. In the end, we spend more
> > > time
> > > > > adding features than hand-optimizing the existing code.
> > > > >
> > > > > Regards
> > > > >
> > > > > Antoine.
> > > > >
> > > > >
> > > > >
> > > > > >
> > > > > > With that in mind, I'd like to propose the following strategy:
> > > > > > 1. Write a single source file with simple, element-at-a-time for
> > loop
> > > > > > implementations of each function.
> > > > > > 2. Compile this same source file several times with different
> > compile
> > > > > flags
> > > > > > for different vectorization (e.g. if we're on an x86 machine that
> > > > > supports
> > > > > > AVX2 and AVX512, we'd compile once with -mavx2 and once with
> > > > -mavx512vl).
> > > > > > 3. Functions compiled with different instruction sets can be
> > > > > differentiated
> > > > > > by a namespace, which gets defined during the compiler
> invocation.
> > > For
> > > > > > example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2
> > and
> > > > then
> > > > > > for something like elementwise addition of two arrays, we'd call
> > > > > > arrow::AVX2::VectorAdd.
> > > > > >
> > > > > > I believe this would let us remove xsimd as a dependency while
> also
> > > > > giving
> > > > > > us lots of vectorized kernels at the cost of some extra cmake
> > magic.
> > > > > After
> > > > > > that, it would just be a matter of making the function registry
> > point
> > > > to
> > > > > > these new functions.
> > > > > >
> > > > > > Please let me know your thoughts!
> > > > > >
> > > > > > Thanks,
> > > > > > Sasha Krassovsky
> > > > > >
> > > > >
> > > >
> > >
> >
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Weston Pace <we...@gmail.com>]

Apologies if this is an over simplified opinion but does it have to be one
or the other?

If people contribute and maintain XSIMD kernels then great.

If people contribute and maintain auto-vectorizable kernels then great.

Then it just comes down to having consistent dispatch rules.  Something
like "use XSIMD kernels if it supports the arch otherwise fall back to
whatever else."

The plan to generate different auto vectorized versions sounds reasonable.
Maybe cmake can even add the flags by convention based on the filename.  If
it causes downstream cmake issues then we just add a flag to disable that
feature.


On Wed, Mar 30, 2022, 11:18 AM Micah Kornfield <em...@gmail.com>
wrote:

> >
> > We were not going to use xsimd's dynamic dispatch, and instead roll our
> own
>
> There is already a dynamic dispatch facility see: arrow/util/dispatch.h
>
> Since we're rolling our own dynamic dispatch, we'd still have to compile
> > the same source file several times with different, so my proposal doesn't
> > change that.
>
> If we are going to be compiling the same file over and over again, it would
> be nice to have a naming convention for such files so they can be easily
> distinguished.  We'd need to tackle this complexity at some point, but
> trying to keep the mechanism understandable by people outside the project
> is something that we should evaluate as this is implemented.
>
> -Micah
>
>
>
> On Wed, Mar 30, 2022 at 1:19 PM Sasha Krassovsky <
> krassovskysasha@gmail.com>
> wrote:
>
> > > Looking at the disassembly, the int16 and int32 versions are unrolled
> and
> > vectorized by clang 12.0, the int8 and int64 are not...
> > I think a big part of this is how fragile the current kernel system
> > implementation is. It seems to rely on templating lots of different parts
> > of kernels and hoping compiler will glue them together via inlining, and
> > then vectorize.
> > GCC 10 does not unroll or vectorize even int32 or int16 for me. I am able
> > to reproduce the vectorization you noticed with Clang (I'm actually
> really
> > impressed).
> > But still, as you said it's not ideal to have one compiler be much faster
> > than another. The reason for the difference is possibly due to the
> ordering
> > of optimization passes. If a compiler does all of its inlining before
> > vectorization,
> > then we can expect good output. If vectorization happens between two
> > inlining phases, then the compiler cannot vectorize (even if something
> gets
> > inlined later). My personal rule of thumb to handle this is to
> > write code that would be optimized well within only a few optimization
> > passes (e.g. rely on an inlining, a constant propagation, and a
> > vectorization pass) instead of relying on the correct distribution of a
> > large number of passes.
> >
> > > How do we ensure that common compiler optimize this routine as
> expected?
> > I think the main thing we can do is to write simple code that's obvious
> for
> > the compiler to vectorize ("meet the compiler half way" in some sense).
> > A simple for loop operating on pointers is vectorized very well even by
> > ancient compilers (below I tested clang 3.9), so I think for a lot of
> these
> > kernels if we'd be much more confident of it being consistently
> vectorized.
> > https://godbolt.org/z/e36M948jv
> >
> > > therefore using xsimd does not prevent the compiler from optimizing
> more.
> > My main hesitation here is the same as above with the kernels system: the
> > more inlining that has to happen, the less likely it is for the compiler
> to
> > optimize as efficiently. However,
> > I do agree this is probably not a big issue with xsimd as it seems pretty
> > lightweight.
> >
> > > we are very responsive to any request and we can quickly implement
> > features
> > This is great to hear, and definitely makes me feel alot better about
> > keeping and using xsimd where necessary.
> >
> > > Note however that it requires some basic checking of the output across
> > different compilers and different compiler versions.
> > Definitely agree here too. I would be in favor of some middleground of
> > using autovectorization for simple stuff (like the Add kernel above), and
> > use xsimd for stuff that doesn't get vectorized well by some compilers.
> >
> > So it seems to me that before my email, the current status was:
> > - We were going to simd-optimize our kernels using xsimd, but hadn't
> gotten
> > to it yet. This would've involved changing the kernels system to use
> xsimd
> > inside of the operation functors?
> > - We were not going to use xsimd's dynamic dispatch, and instead roll our
> > own
> >
> > If that's the case then my proposal is relatively minor. Since we're
> > rolling our own dynamic dispatch, we'd still have to compile the same
> > source file several times with different, so my proposal doesn't change
> > that.
> > The part that my proposal changes is to refactor the code to be more
> > autovectorization-friendly. This seems to be a minor difference from what
> > was planned before, where instead of having the operation functor process
> > one simd-batch at a time, we have it process the whole batch (to minimize
> > the reliance on inlining). And of course we'd have to actually implement
> > the dynamic dispatch (I don't think I see it for most of the kernels
> > system).
> > Does something like this sound reasonable to people?
> >
> > Sasha
> >
> > On Wed, Mar 30, 2022 at 1:47 AM Johan Mabille <jo...@gmail.com>
> > wrote:
> >
> > > Hi all,
> > >
> > > xsimd core developer here writing on behalf of the xsimd core team ;)
> > >
> > > I just wanted to add some elements to this thread:
> > >
> > > - xsimd is more than a library that wraps simple intrinsics. It
> provides
> > > vectorized (and accurate) implementations of the traditional
> mathematical
> > > functions (exp, sin, cos , etc), that a compiler may not be able to
> > > vectorize. And when the compiler does vectorize them, it usually relies
> > on
> > > external libraries that provide such implementations. Therefore, you
> can
> > > not guarantee that every compiler will optimize these calls, nor the
> same
> > > accuracy across different platforms.
> > >
> > > - compilers actually understand intrinsics and can optimize them; it's
> > not
> > > a "one intrinsic -> one asm "instruction mapping at all. Therefore,
> using
> > > xsimd does not prevent the compiler from optimizing more.
> > >
> > > - xsimd is actively developed and maintained. It is used as a building
> > > block of the xtensor stack, and in Pythran which has been integrated in
> > > scipy. Some features may be missing because of a lack of time and/or
> > higher
> > > priorities. However, Antoine can confirm that we are very responsive to
> > any
> > > request and we can quickly implement features that would be mandatory
> for
> > > Apache Arrow.
> > >
> > > - It is 100% true that for simple loops with simple arithmetic
> > operations,
> > > it is easier not to write xsimd code and let the compiler optimize the
> > > loop. Note however that it requires some basic checking of the output
> > > across different compilers and different compiler versions. See for
> > > instance https://godbolt.org/z/KTcTe1zPn. Different versions of gcc
> > > generate different vectorized code, and clang and gcc do not
> > auto-vectorize
> > > at the same optimization level (O2 for clang and O3 or O2
> > -ftree-vectorize
> > > for gcc)
> > >
> > > Regards,
> > >
> > > Johan
> > >
> > > On Wed, Mar 30, 2022 at 10:10 AM Antoine Pitrou <an...@python.org>
> > > wrote:
> > >
> > > >
> > > > Hi Sasha,
> > > >
> > > > Le 30/03/2022 à 00:14, Sasha Krassovsky a écrit :
> > > > > I've noticed that we include xsimd as an abstraction over all of
> the
> > > simd
> > > > > architectures. I'd like to propose a different solution which would
> > > > result
> > > > > in fewer lines of code, while being more readable.
> > > > >
> > > > > My thinking is that anything simple enough to abstract with xsimd
> can
> > > be
> > > > > autovectorized by the compiler. Any more interesting SIMD algorithm
> > > > usually
> > > > > is tailored to the target instruction set and can't be abstracted
> > away
> > > > with
> > > > > xsimd anyway.
> > > >
> > > > As a matter of fact, we already rely on auto-vectorization in a
> couple
> > > > of places (mostly `aggregate_basic_avx2.cc` and friends).
> > > >
> > > > The main concern with doing this is that auto-vectorization makes
> > > > performance difficult to predict and ensure. Some compiler or
> compiler
> > > > versions may fail vectorizing a given piece of code (how does MSVC
> fare
> > > > these days?). As a consequence, some Arrow builds may be 2x to 8x
> > faster
> > > > than others on the same machine and the same workload. This is not an
> > > > optimal user experience, and in many cases it can be difficult or
> > > > impossible to change the compiler version.
> > > >
> > > >
> > > > As matter of fact, on x86 our baseline instruction set is SSE4.2, so
> we
> > > > already get some auto-vectorization and we can look at the concrete
> > > > numbers. On my AMD Zen 2 CPU I get the following numbers on the
> > pairwise
> > > > addition kernel (this is with clang 12.0):
> > > > https://gist.github.com/pitrou/dbfa3d97afb4ebbe096bab69cb6bb4d5
> > > >
> > > > Judging that PADDB, PADDW, PADDD and PADDQ all have the same
> throughput
> > > > on that CPU (according to
> > > > https://www.agner.org/optimize/instruction_tables.pdf), all these
> data
> > > > types should show the same performance in bytes/second.  Yet int64
> gets
> > > > half of int16 and int32, and int8 is far behind.
> > > >
> > > > Looking at the disassembly, the int16 and int32 versions are unrolled
> > > > and vectorized by clang 12.0, the int8 and int64 are not... Why? How
> do
> > > > we ensure that common compiler optimize this routine as expected?
> > > > Personally, I have no idea.
> > > >
> > > >
> > > > As for why xsimd rather than hand-written intrinsics, it's a middle
> > > > ground in terms of maintainability and readability. Code using
> > > > intrinsics quickly gets hard to follow except for the daily SIMD
> > > > specialist, and it's also annoying to port to another architecture
> > (even
> > > > due to gratuitous naming differences).
> > > >
> > > > As for why xsimd is not very much used accross the codebase, the
> > initial
> > > > intent was to have more SIMD-accelerated code, but nobody actually
> got
> > > > around to do it, due to other priorities. In the end, we spend more
> > time
> > > > adding features than hand-optimizing the existing code.
> > > >
> > > > Regards
> > > >
> > > > Antoine.
> > > >
> > > >
> > > >
> > > > >
> > > > > With that in mind, I'd like to propose the following strategy:
> > > > > 1. Write a single source file with simple, element-at-a-time for
> loop
> > > > > implementations of each function.
> > > > > 2. Compile this same source file several times with different
> compile
> > > > flags
> > > > > for different vectorization (e.g. if we're on an x86 machine that
> > > > supports
> > > > > AVX2 and AVX512, we'd compile once with -mavx2 and once with
> > > -mavx512vl).
> > > > > 3. Functions compiled with different instruction sets can be
> > > > differentiated
> > > > > by a namespace, which gets defined during the compiler invocation.
> > For
> > > > > example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2
> and
> > > then
> > > > > for something like elementwise addition of two arrays, we'd call
> > > > > arrow::AVX2::VectorAdd.
> > > > >
> > > > > I believe this would let us remove xsimd as a dependency while also
> > > > giving
> > > > > us lots of vectorized kernels at the cost of some extra cmake
> magic.
> > > > After
> > > > > that, it would just be a matter of making the function registry
> point
> > > to
> > > > > these new functions.
> > > > >
> > > > > Please let me know your thoughts!
> > > > >
> > > > > Thanks,
> > > > > Sasha Krassovsky
> > > > >
> > > >
> > >
> >
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Micah Kornfield <em...@gmail.com>]

>
> We were not going to use xsimd's dynamic dispatch, and instead roll our own

There is already a dynamic dispatch facility see: arrow/util/dispatch.h

Since we're rolling our own dynamic dispatch, we'd still have to compile
> the same source file several times with different, so my proposal doesn't
> change that.

If we are going to be compiling the same file over and over again, it would
be nice to have a naming convention for such files so they can be easily
distinguished.  We'd need to tackle this complexity at some point, but
trying to keep the mechanism understandable by people outside the project
is something that we should evaluate as this is implemented.

-Micah



On Wed, Mar 30, 2022 at 1:19 PM Sasha Krassovsky <kr...@gmail.com>
wrote:

> > Looking at the disassembly, the int16 and int32 versions are unrolled and
> vectorized by clang 12.0, the int8 and int64 are not...
> I think a big part of this is how fragile the current kernel system
> implementation is. It seems to rely on templating lots of different parts
> of kernels and hoping compiler will glue them together via inlining, and
> then vectorize.
> GCC 10 does not unroll or vectorize even int32 or int16 for me. I am able
> to reproduce the vectorization you noticed with Clang (I'm actually really
> impressed).
> But still, as you said it's not ideal to have one compiler be much faster
> than another. The reason for the difference is possibly due to the ordering
> of optimization passes. If a compiler does all of its inlining before
> vectorization,
> then we can expect good output. If vectorization happens between two
> inlining phases, then the compiler cannot vectorize (even if something gets
> inlined later). My personal rule of thumb to handle this is to
> write code that would be optimized well within only a few optimization
> passes (e.g. rely on an inlining, a constant propagation, and a
> vectorization pass) instead of relying on the correct distribution of a
> large number of passes.
>
> > How do we ensure that common compiler optimize this routine as expected?
> I think the main thing we can do is to write simple code that's obvious for
> the compiler to vectorize ("meet the compiler half way" in some sense).
> A simple for loop operating on pointers is vectorized very well even by
> ancient compilers (below I tested clang 3.9), so I think for a lot of these
> kernels if we'd be much more confident of it being consistently vectorized.
> https://godbolt.org/z/e36M948jv
>
> > therefore using xsimd does not prevent the compiler from optimizing more.
> My main hesitation here is the same as above with the kernels system: the
> more inlining that has to happen, the less likely it is for the compiler to
> optimize as efficiently. However,
> I do agree this is probably not a big issue with xsimd as it seems pretty
> lightweight.
>
> > we are very responsive to any request and we can quickly implement
> features
> This is great to hear, and definitely makes me feel alot better about
> keeping and using xsimd where necessary.
>
> > Note however that it requires some basic checking of the output across
> different compilers and different compiler versions.
> Definitely agree here too. I would be in favor of some middleground of
> using autovectorization for simple stuff (like the Add kernel above), and
> use xsimd for stuff that doesn't get vectorized well by some compilers.
>
> So it seems to me that before my email, the current status was:
> - We were going to simd-optimize our kernels using xsimd, but hadn't gotten
> to it yet. This would've involved changing the kernels system to use xsimd
> inside of the operation functors?
> - We were not going to use xsimd's dynamic dispatch, and instead roll our
> own
>
> If that's the case then my proposal is relatively minor. Since we're
> rolling our own dynamic dispatch, we'd still have to compile the same
> source file several times with different, so my proposal doesn't change
> that.
> The part that my proposal changes is to refactor the code to be more
> autovectorization-friendly. This seems to be a minor difference from what
> was planned before, where instead of having the operation functor process
> one simd-batch at a time, we have it process the whole batch (to minimize
> the reliance on inlining). And of course we'd have to actually implement
> the dynamic dispatch (I don't think I see it for most of the kernels
> system).
> Does something like this sound reasonable to people?
>
> Sasha
>
> On Wed, Mar 30, 2022 at 1:47 AM Johan Mabille <jo...@gmail.com>
> wrote:
>
> > Hi all,
> >
> > xsimd core developer here writing on behalf of the xsimd core team ;)
> >
> > I just wanted to add some elements to this thread:
> >
> > - xsimd is more than a library that wraps simple intrinsics. It provides
> > vectorized (and accurate) implementations of the traditional mathematical
> > functions (exp, sin, cos , etc), that a compiler may not be able to
> > vectorize. And when the compiler does vectorize them, it usually relies
> on
> > external libraries that provide such implementations. Therefore, you can
> > not guarantee that every compiler will optimize these calls, nor the same
> > accuracy across different platforms.
> >
> > - compilers actually understand intrinsics and can optimize them; it's
> not
> > a "one intrinsic -> one asm "instruction mapping at all. Therefore, using
> > xsimd does not prevent the compiler from optimizing more.
> >
> > - xsimd is actively developed and maintained. It is used as a building
> > block of the xtensor stack, and in Pythran which has been integrated in
> > scipy. Some features may be missing because of a lack of time and/or
> higher
> > priorities. However, Antoine can confirm that we are very responsive to
> any
> > request and we can quickly implement features that would be mandatory for
> > Apache Arrow.
> >
> > - It is 100% true that for simple loops with simple arithmetic
> operations,
> > it is easier not to write xsimd code and let the compiler optimize the
> > loop. Note however that it requires some basic checking of the output
> > across different compilers and different compiler versions. See for
> > instance https://godbolt.org/z/KTcTe1zPn. Different versions of gcc
> > generate different vectorized code, and clang and gcc do not
> auto-vectorize
> > at the same optimization level (O2 for clang and O3 or O2
> -ftree-vectorize
> > for gcc)
> >
> > Regards,
> >
> > Johan
> >
> > On Wed, Mar 30, 2022 at 10:10 AM Antoine Pitrou <an...@python.org>
> > wrote:
> >
> > >
> > > Hi Sasha,
> > >
> > > Le 30/03/2022 à 00:14, Sasha Krassovsky a écrit :
> > > > I've noticed that we include xsimd as an abstraction over all of the
> > simd
> > > > architectures. I'd like to propose a different solution which would
> > > result
> > > > in fewer lines of code, while being more readable.
> > > >
> > > > My thinking is that anything simple enough to abstract with xsimd can
> > be
> > > > autovectorized by the compiler. Any more interesting SIMD algorithm
> > > usually
> > > > is tailored to the target instruction set and can't be abstracted
> away
> > > with
> > > > xsimd anyway.
> > >
> > > As a matter of fact, we already rely on auto-vectorization in a couple
> > > of places (mostly `aggregate_basic_avx2.cc` and friends).
> > >
> > > The main concern with doing this is that auto-vectorization makes
> > > performance difficult to predict and ensure. Some compiler or compiler
> > > versions may fail vectorizing a given piece of code (how does MSVC fare
> > > these days?). As a consequence, some Arrow builds may be 2x to 8x
> faster
> > > than others on the same machine and the same workload. This is not an
> > > optimal user experience, and in many cases it can be difficult or
> > > impossible to change the compiler version.
> > >
> > >
> > > As matter of fact, on x86 our baseline instruction set is SSE4.2, so we
> > > already get some auto-vectorization and we can look at the concrete
> > > numbers. On my AMD Zen 2 CPU I get the following numbers on the
> pairwise
> > > addition kernel (this is with clang 12.0):
> > > https://gist.github.com/pitrou/dbfa3d97afb4ebbe096bab69cb6bb4d5
> > >
> > > Judging that PADDB, PADDW, PADDD and PADDQ all have the same throughput
> > > on that CPU (according to
> > > https://www.agner.org/optimize/instruction_tables.pdf), all these data
> > > types should show the same performance in bytes/second.  Yet int64 gets
> > > half of int16 and int32, and int8 is far behind.
> > >
> > > Looking at the disassembly, the int16 and int32 versions are unrolled
> > > and vectorized by clang 12.0, the int8 and int64 are not... Why? How do
> > > we ensure that common compiler optimize this routine as expected?
> > > Personally, I have no idea.
> > >
> > >
> > > As for why xsimd rather than hand-written intrinsics, it's a middle
> > > ground in terms of maintainability and readability. Code using
> > > intrinsics quickly gets hard to follow except for the daily SIMD
> > > specialist, and it's also annoying to port to another architecture
> (even
> > > due to gratuitous naming differences).
> > >
> > > As for why xsimd is not very much used accross the codebase, the
> initial
> > > intent was to have more SIMD-accelerated code, but nobody actually got
> > > around to do it, due to other priorities. In the end, we spend more
> time
> > > adding features than hand-optimizing the existing code.
> > >
> > > Regards
> > >
> > > Antoine.
> > >
> > >
> > >
> > > >
> > > > With that in mind, I'd like to propose the following strategy:
> > > > 1. Write a single source file with simple, element-at-a-time for loop
> > > > implementations of each function.
> > > > 2. Compile this same source file several times with different compile
> > > flags
> > > > for different vectorization (e.g. if we're on an x86 machine that
> > > supports
> > > > AVX2 and AVX512, we'd compile once with -mavx2 and once with
> > -mavx512vl).
> > > > 3. Functions compiled with different instruction sets can be
> > > differentiated
> > > > by a namespace, which gets defined during the compiler invocation.
> For
> > > > example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2 and
> > then
> > > > for something like elementwise addition of two arrays, we'd call
> > > > arrow::AVX2::VectorAdd.
> > > >
> > > > I believe this would let us remove xsimd as a dependency while also
> > > giving
> > > > us lots of vectorized kernels at the cost of some extra cmake magic.
> > > After
> > > > that, it would just be a matter of making the function registry point
> > to
> > > > these new functions.
> > > >
> > > > Please let me know your thoughts!
> > > >
> > > > Thanks,
> > > > Sasha Krassovsky
> > > >
> > >
> >
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

> Looking at the disassembly, the int16 and int32 versions are unrolled and
vectorized by clang 12.0, the int8 and int64 are not...
I think a big part of this is how fragile the current kernel system
implementation is. It seems to rely on templating lots of different parts
of kernels and hoping compiler will glue them together via inlining, and
then vectorize.
GCC 10 does not unroll or vectorize even int32 or int16 for me. I am able
to reproduce the vectorization you noticed with Clang (I'm actually really
impressed).
But still, as you said it's not ideal to have one compiler be much faster
than another. The reason for the difference is possibly due to the ordering
of optimization passes. If a compiler does all of its inlining before
vectorization,
then we can expect good output. If vectorization happens between two
inlining phases, then the compiler cannot vectorize (even if something gets
inlined later). My personal rule of thumb to handle this is to
write code that would be optimized well within only a few optimization
passes (e.g. rely on an inlining, a constant propagation, and a
vectorization pass) instead of relying on the correct distribution of a
large number of passes.

> How do we ensure that common compiler optimize this routine as expected?
I think the main thing we can do is to write simple code that's obvious for
the compiler to vectorize ("meet the compiler half way" in some sense).
A simple for loop operating on pointers is vectorized very well even by
ancient compilers (below I tested clang 3.9), so I think for a lot of these
kernels if we'd be much more confident of it being consistently vectorized.
https://godbolt.org/z/e36M948jv

> therefore using xsimd does not prevent the compiler from optimizing more.
My main hesitation here is the same as above with the kernels system: the
more inlining that has to happen, the less likely it is for the compiler to
optimize as efficiently. However,
I do agree this is probably not a big issue with xsimd as it seems pretty
lightweight.

> we are very responsive to any request and we can quickly implement
features
This is great to hear, and definitely makes me feel alot better about
keeping and using xsimd where necessary.

> Note however that it requires some basic checking of the output across
different compilers and different compiler versions.
Definitely agree here too. I would be in favor of some middleground of
using autovectorization for simple stuff (like the Add kernel above), and
use xsimd for stuff that doesn't get vectorized well by some compilers.

So it seems to me that before my email, the current status was:
- We were going to simd-optimize our kernels using xsimd, but hadn't gotten
to it yet. This would've involved changing the kernels system to use xsimd
inside of the operation functors?
- We were not going to use xsimd's dynamic dispatch, and instead roll our
own

If that's the case then my proposal is relatively minor. Since we're
rolling our own dynamic dispatch, we'd still have to compile the same
source file several times with different, so my proposal doesn't change
that.
The part that my proposal changes is to refactor the code to be more
autovectorization-friendly. This seems to be a minor difference from what
was planned before, where instead of having the operation functor process
one simd-batch at a time, we have it process the whole batch (to minimize
the reliance on inlining). And of course we'd have to actually implement
the dynamic dispatch (I don't think I see it for most of the kernels
system).
Does something like this sound reasonable to people?

Sasha

On Wed, Mar 30, 2022 at 1:47 AM Johan Mabille <jo...@gmail.com>
wrote:

> Hi all,
>
> xsimd core developer here writing on behalf of the xsimd core team ;)
>
> I just wanted to add some elements to this thread:
>
> - xsimd is more than a library that wraps simple intrinsics. It provides
> vectorized (and accurate) implementations of the traditional mathematical
> functions (exp, sin, cos , etc), that a compiler may not be able to
> vectorize. And when the compiler does vectorize them, it usually relies on
> external libraries that provide such implementations. Therefore, you can
> not guarantee that every compiler will optimize these calls, nor the same
> accuracy across different platforms.
>
> - compilers actually understand intrinsics and can optimize them; it's not
> a "one intrinsic -> one asm "instruction mapping at all. Therefore, using
> xsimd does not prevent the compiler from optimizing more.
>
> - xsimd is actively developed and maintained. It is used as a building
> block of the xtensor stack, and in Pythran which has been integrated in
> scipy. Some features may be missing because of a lack of time and/or higher
> priorities. However, Antoine can confirm that we are very responsive to any
> request and we can quickly implement features that would be mandatory for
> Apache Arrow.
>
> - It is 100% true that for simple loops with simple arithmetic operations,
> it is easier not to write xsimd code and let the compiler optimize the
> loop. Note however that it requires some basic checking of the output
> across different compilers and different compiler versions. See for
> instance https://godbolt.org/z/KTcTe1zPn. Different versions of gcc
> generate different vectorized code, and clang and gcc do not auto-vectorize
> at the same optimization level (O2 for clang and O3 or O2 -ftree-vectorize
> for gcc)
>
> Regards,
>
> Johan
>
> On Wed, Mar 30, 2022 at 10:10 AM Antoine Pitrou <an...@python.org>
> wrote:
>
> >
> > Hi Sasha,
> >
> > Le 30/03/2022 à 00:14, Sasha Krassovsky a écrit :
> > > I've noticed that we include xsimd as an abstraction over all of the
> simd
> > > architectures. I'd like to propose a different solution which would
> > result
> > > in fewer lines of code, while being more readable.
> > >
> > > My thinking is that anything simple enough to abstract with xsimd can
> be
> > > autovectorized by the compiler. Any more interesting SIMD algorithm
> > usually
> > > is tailored to the target instruction set and can't be abstracted away
> > with
> > > xsimd anyway.
> >
> > As a matter of fact, we already rely on auto-vectorization in a couple
> > of places (mostly `aggregate_basic_avx2.cc` and friends).
> >
> > The main concern with doing this is that auto-vectorization makes
> > performance difficult to predict and ensure. Some compiler or compiler
> > versions may fail vectorizing a given piece of code (how does MSVC fare
> > these days?). As a consequence, some Arrow builds may be 2x to 8x faster
> > than others on the same machine and the same workload. This is not an
> > optimal user experience, and in many cases it can be difficult or
> > impossible to change the compiler version.
> >
> >
> > As matter of fact, on x86 our baseline instruction set is SSE4.2, so we
> > already get some auto-vectorization and we can look at the concrete
> > numbers. On my AMD Zen 2 CPU I get the following numbers on the pairwise
> > addition kernel (this is with clang 12.0):
> > https://gist.github.com/pitrou/dbfa3d97afb4ebbe096bab69cb6bb4d5
> >
> > Judging that PADDB, PADDW, PADDD and PADDQ all have the same throughput
> > on that CPU (according to
> > https://www.agner.org/optimize/instruction_tables.pdf), all these data
> > types should show the same performance in bytes/second.  Yet int64 gets
> > half of int16 and int32, and int8 is far behind.
> >
> > Looking at the disassembly, the int16 and int32 versions are unrolled
> > and vectorized by clang 12.0, the int8 and int64 are not... Why? How do
> > we ensure that common compiler optimize this routine as expected?
> > Personally, I have no idea.
> >
> >
> > As for why xsimd rather than hand-written intrinsics, it's a middle
> > ground in terms of maintainability and readability. Code using
> > intrinsics quickly gets hard to follow except for the daily SIMD
> > specialist, and it's also annoying to port to another architecture (even
> > due to gratuitous naming differences).
> >
> > As for why xsimd is not very much used accross the codebase, the initial
> > intent was to have more SIMD-accelerated code, but nobody actually got
> > around to do it, due to other priorities. In the end, we spend more time
> > adding features than hand-optimizing the existing code.
> >
> > Regards
> >
> > Antoine.
> >
> >
> >
> > >
> > > With that in mind, I'd like to propose the following strategy:
> > > 1. Write a single source file with simple, element-at-a-time for loop
> > > implementations of each function.
> > > 2. Compile this same source file several times with different compile
> > flags
> > > for different vectorization (e.g. if we're on an x86 machine that
> > supports
> > > AVX2 and AVX512, we'd compile once with -mavx2 and once with
> -mavx512vl).
> > > 3. Functions compiled with different instruction sets can be
> > differentiated
> > > by a namespace, which gets defined during the compiler invocation. For
> > > example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2 and
> then
> > > for something like elementwise addition of two arrays, we'd call
> > > arrow::AVX2::VectorAdd.
> > >
> > > I believe this would let us remove xsimd as a dependency while also
> > giving
> > > us lots of vectorized kernels at the cost of some extra cmake magic.
> > After
> > > that, it would just be a matter of making the function registry point
> to
> > > these new functions.
> > >
> > > Please let me know your thoughts!
> > >
> > > Thanks,
> > > Sasha Krassovsky
> > >
> >
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Johan Mabille <jo...@gmail.com>]

Hi all,

xsimd core developer here writing on behalf of the xsimd core team ;)

I just wanted to add some elements to this thread:

- xsimd is more than a library that wraps simple intrinsics. It provides
vectorized (and accurate) implementations of the traditional mathematical
functions (exp, sin, cos , etc), that a compiler may not be able to
vectorize. And when the compiler does vectorize them, it usually relies on
external libraries that provide such implementations. Therefore, you can
not guarantee that every compiler will optimize these calls, nor the same
accuracy across different platforms.

- compilers actually understand intrinsics and can optimize them; it's not
a "one intrinsic -> one asm "instruction mapping at all. Therefore, using
xsimd does not prevent the compiler from optimizing more.

- xsimd is actively developed and maintained. It is used as a building
block of the xtensor stack, and in Pythran which has been integrated in
scipy. Some features may be missing because of a lack of time and/or higher
priorities. However, Antoine can confirm that we are very responsive to any
request and we can quickly implement features that would be mandatory for
Apache Arrow.

- It is 100% true that for simple loops with simple arithmetic operations,
it is easier not to write xsimd code and let the compiler optimize the
loop. Note however that it requires some basic checking of the output
across different compilers and different compiler versions. See for
instance https://godbolt.org/z/KTcTe1zPn. Different versions of gcc
generate different vectorized code, and clang and gcc do not auto-vectorize
at the same optimization level (O2 for clang and O3 or O2 -ftree-vectorize
for gcc)

Regards,

Johan

On Wed, Mar 30, 2022 at 10:10 AM Antoine Pitrou <an...@python.org> wrote:

>
> Hi Sasha,
>
> Le 30/03/2022 à 00:14, Sasha Krassovsky a écrit :
> > I've noticed that we include xsimd as an abstraction over all of the simd
> > architectures. I'd like to propose a different solution which would
> result
> > in fewer lines of code, while being more readable.
> >
> > My thinking is that anything simple enough to abstract with xsimd can be
> > autovectorized by the compiler. Any more interesting SIMD algorithm
> usually
> > is tailored to the target instruction set and can't be abstracted away
> with
> > xsimd anyway.
>
> As a matter of fact, we already rely on auto-vectorization in a couple
> of places (mostly `aggregate_basic_avx2.cc` and friends).
>
> The main concern with doing this is that auto-vectorization makes
> performance difficult to predict and ensure. Some compiler or compiler
> versions may fail vectorizing a given piece of code (how does MSVC fare
> these days?). As a consequence, some Arrow builds may be 2x to 8x faster
> than others on the same machine and the same workload. This is not an
> optimal user experience, and in many cases it can be difficult or
> impossible to change the compiler version.
>
>
> As matter of fact, on x86 our baseline instruction set is SSE4.2, so we
> already get some auto-vectorization and we can look at the concrete
> numbers. On my AMD Zen 2 CPU I get the following numbers on the pairwise
> addition kernel (this is with clang 12.0):
> https://gist.github.com/pitrou/dbfa3d97afb4ebbe096bab69cb6bb4d5
>
> Judging that PADDB, PADDW, PADDD and PADDQ all have the same throughput
> on that CPU (according to
> https://www.agner.org/optimize/instruction_tables.pdf), all these data
> types should show the same performance in bytes/second.  Yet int64 gets
> half of int16 and int32, and int8 is far behind.
>
> Looking at the disassembly, the int16 and int32 versions are unrolled
> and vectorized by clang 12.0, the int8 and int64 are not... Why? How do
> we ensure that common compiler optimize this routine as expected?
> Personally, I have no idea.
>
>
> As for why xsimd rather than hand-written intrinsics, it's a middle
> ground in terms of maintainability and readability. Code using
> intrinsics quickly gets hard to follow except for the daily SIMD
> specialist, and it's also annoying to port to another architecture (even
> due to gratuitous naming differences).
>
> As for why xsimd is not very much used accross the codebase, the initial
> intent was to have more SIMD-accelerated code, but nobody actually got
> around to do it, due to other priorities. In the end, we spend more time
> adding features than hand-optimizing the existing code.
>
> Regards
>
> Antoine.
>
>
>
> >
> > With that in mind, I'd like to propose the following strategy:
> > 1. Write a single source file with simple, element-at-a-time for loop
> > implementations of each function.
> > 2. Compile this same source file several times with different compile
> flags
> > for different vectorization (e.g. if we're on an x86 machine that
> supports
> > AVX2 and AVX512, we'd compile once with -mavx2 and once with -mavx512vl).
> > 3. Functions compiled with different instruction sets can be
> differentiated
> > by a namespace, which gets defined during the compiler invocation. For
> > example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2 and then
> > for something like elementwise addition of two arrays, we'd call
> > arrow::AVX2::VectorAdd.
> >
> > I believe this would let us remove xsimd as a dependency while also
> giving
> > us lots of vectorized kernels at the cost of some extra cmake magic.
> After
> > that, it would just be a matter of making the function registry point to
> > these new functions.
> >
> > Please let me know your thoughts!
> >
> > Thanks,
> > Sasha Krassovsky
> >
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Antoine Pitrou <an...@python.org>]

Hi Sasha,

Le 30/03/2022 à 00:14, Sasha Krassovsky a écrit :
> I've noticed that we include xsimd as an abstraction over all of the simd
> architectures. I'd like to propose a different solution which would result
> in fewer lines of code, while being more readable.
> 
> My thinking is that anything simple enough to abstract with xsimd can be
> autovectorized by the compiler. Any more interesting SIMD algorithm usually
> is tailored to the target instruction set and can't be abstracted away with
> xsimd anyway.

As a matter of fact, we already rely on auto-vectorization in a couple 
of places (mostly `aggregate_basic_avx2.cc` and friends).

The main concern with doing this is that auto-vectorization makes 
performance difficult to predict and ensure. Some compiler or compiler 
versions may fail vectorizing a given piece of code (how does MSVC fare 
these days?). As a consequence, some Arrow builds may be 2x to 8x faster 
than others on the same machine and the same workload. This is not an 
optimal user experience, and in many cases it can be difficult or 
impossible to change the compiler version.


As matter of fact, on x86 our baseline instruction set is SSE4.2, so we 
already get some auto-vectorization and we can look at the concrete 
numbers. On my AMD Zen 2 CPU I get the following numbers on the pairwise 
addition kernel (this is with clang 12.0):
https://gist.github.com/pitrou/dbfa3d97afb4ebbe096bab69cb6bb4d5

Judging that PADDB, PADDW, PADDD and PADDQ all have the same throughput 
on that CPU (according to 
https://www.agner.org/optimize/instruction_tables.pdf), all these data 
types should show the same performance in bytes/second.  Yet int64 gets 
half of int16 and int32, and int8 is far behind.

Looking at the disassembly, the int16 and int32 versions are unrolled 
and vectorized by clang 12.0, the int8 and int64 are not... Why? How do 
we ensure that common compiler optimize this routine as expected? 
Personally, I have no idea.


As for why xsimd rather than hand-written intrinsics, it's a middle 
ground in terms of maintainability and readability. Code using 
intrinsics quickly gets hard to follow except for the daily SIMD 
specialist, and it's also annoying to port to another architecture (even 
due to gratuitous naming differences).

As for why xsimd is not very much used accross the codebase, the initial 
intent was to have more SIMD-accelerated code, but nobody actually got 
around to do it, due to other priorities. In the end, we spend more time 
adding features than hand-optimizing the existing code.

Regards

Antoine.



> 
> With that in mind, I'd like to propose the following strategy:
> 1. Write a single source file with simple, element-at-a-time for loop
> implementations of each function.
> 2. Compile this same source file several times with different compile flags
> for different vectorization (e.g. if we're on an x86 machine that supports
> AVX2 and AVX512, we'd compile once with -mavx2 and once with -mavx512vl).
> 3. Functions compiled with different instruction sets can be differentiated
> by a namespace, which gets defined during the compiler invocation. For
> example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2 and then
> for something like elementwise addition of two arrays, we'd call
> arrow::AVX2::VectorAdd.
> 
> I believe this would let us remove xsimd as a dependency while also giving
> us lots of vectorized kernels at the cost of some extra cmake magic. After
> that, it would just be a matter of making the function registry point to
> these new functions.
> 
> Please let me know your thoughts!
> 
> Thanks,
> Sasha Krassovsky
> 

Re: [C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

> Is this in general, or specific to compiler flags being used.
In general. As far as I'm aware, autovectorization will only happen if you
have some sort of simd enabled, and I don't see that anywhere among the
flags except for this specific cases.

> If these aren't due to SIMD differences, I'm kind of curious what they
are from.
My theory is that this is due to loop unrolling, but comparing it to the
assembly generated by a simple for loop I think there's a lot of
performance left on the table. I can look more closely at the
generated code between scalar and AVX2 versions tomorrow if anyone would
find that interesting (I do :) ).

>  would this include dynamic dispatch for all kernels as well?
Yes, it would. As an example, let's take adding two arrays together. We
would have a file like so (let's call it vector_add.cpp)
namespace ARCH
{
void VectorAdd(size_t n, int64_t *a, int64_t *b, int64_t *out)
{
    for(size_t i = 0; i < n; i++)
        out[i] = a[i] + b[i];
}
}

We would also have a header file vector_add.h
void VectorAdd(size_t n, int64_t *a, int64_t *b, int64_t *out);

Then we would compile it several times like so (obviously depending on
which architectures we'd want to enable):
g++ vector_add.cpp -O3 -mavx2 -DARCH=AVX2 -o vector_add_avx2.o
g++ vector_add.cpp -O3 -mavx512vl -DARCH=AVX512 -o vector_add_avx512.o
g++ vector_add.cpp -O3 -mfpu=neon -DARCH=NEON -o vector_add_neon.o
g++ vector_add.cpp -O3 -o vector_add_scalar.o

Now our global VectorAdd that would perform the dynamic dispatch would
check the SIMD level and call the appropriate function.
Note that we have to forward declare each of these functions, which we can
do like so:
namespace AVX2
{
#include "vector_add.h"
}
namespace AVX512
{
#include "vector_add.h"
}
namespace NEON
{
#include "vector_add.h"
}
namespace SCALAR
{
#include "vector_add.h"
}
void VectorAdd(SimdLevel simd_level, int64_t *a, int64_t *b, int64_t *out)
{
    switch(simd_level)
    {
        case AVX2:
            return AVX2::VectorAdd(n, a, b, out);
        case AVX512:
            return AVX512::VectorAdd(n, a, b, out);
        case NEON:
            return NEON::VectorAdd(n, a, b, out);
        default:
            return SCALAR::VectorAdd(n, a, b, out);
    }
}

The idea is to have the same source file be compiled into several different
compilation units. Obviously this can be adapted more to match the current
infrastructure and to support more types (like we definitely would template
all of these simple functions on type).
This idea could also be refactored to use fewer lines of code, such as by
having each of the implementations be in an array of function pointers
indexed by simd level. These details can be left for later.

> Last time we discussed this I believe we agreed we'd use and build up
Arrow's dynamic dispatch instead of using XSIMDs.
If that's the case, then you'd have to do something like this anyway.
Compiler will refuse to emit the instructions corresponding to the
intrinsics that xsimd generates
if you don't enable the proper compiler flags.

> However, this raises the issue about how fragile auto-vectorization can
be at times (and also based on compilers).
This is a fiar point. I guess in such a scenario xsimd could be useful. I
wouldn't mind too much if it were used sparingly (i.e. in cases where we
showed the compiler did a bad job).
For the kernels I'm thinking of, such as element-wise addition,
multiplication, comparison etc, I can almost guarantee that any compiler
worth its salt would autovectorize it given the chance to.

>  if Arrow builds become too difficult to adapt to other build-systems
because of CMake magic, I don't think that is a good outcome.
I think "cmake magic" might've been the wrong word choice, it definitely
sounds much scarier than what I'm actually proposing 😅
It's just invoking compiler several times on the same source file with
different flags.

Sasha

On Tue, Mar 29, 2022 at 9:04 PM Micah Kornfield <em...@gmail.com>
wrote:

> >
> > So in summary: As far as I can tell, we currently don't do any
> > autovectorization, and we use xsimd in a spot where autovectorization
> would
> > do the same job, but without the added dependency.
>
> Is this in general, or specific to compiler flags being used.  As a pont of
> reference the original PR that did optimiziation for aggregates [1] only
> shows results when AVX2 is required to see performance speedups, it is
> possible there has been a regression since its introduction.  If these
> aren't due to SIMD differences, I'm kind of curious what they are from.
> One of the challenges is that pre-released binaries need to support a wide
> variety of ISAs so acceleration would require dynamic dispatch.  I'm not
> sure I understand your proposal exactly but would this include dynamic
> dispatch for all kernels as well?  Maybe an example of your proposal for
> one kernel would help the discussion?
>
> 2) xsimd limits the freedom an optimizer has to select instructions and do
> > other optimizations, as it's just a thin wrapper over normal intrinsics.
> > One concrete example would be if we wanted to take advantage of the
> dynamic
> > dispatch instruction set xsimd offers, the loop strides would no longer
> be
> > compile-time constants, which might prevent the compiler from performing
> > loop unrolling (how would it know that the stride isn't just 1?)
> >
> Last time we discussed this I believe we agreed we'd use and build up
> Arrow's dynamic dispatch instead of using XSIMDs.
>
> The whole point of manually
> > writing tuning code is to extract maximum performance from the hardware
> > that you're targeting.
>
> I think there are different levels to this. For most optimal performance,
> yes you need to target an ISA, it also is the least generalizable.  I
> believe we've seen examples where using XSIMD has improved both Intel and
> Arm performance over whatever the compiler was generating. This could be
> due to using a pattern that was auto-vectorization friendly and maybe there
> are better ones.   However, this raises the issue about how fragile
> auto-vectorization can be at times (and also based on compilers).
>
> For the record, I don't have a strong opinion on removing or keeping XSIMD,
> but if Arrow builds become too difficult to adapt to other build-systems
> because of CMake magic, I don't think that is a good outcome.
>
> Cheers,
> Micah
>
> [1] https://github.com/apache/arrow/pull/7871
>
>
>
> >
>
>
> On Tue, Mar 29, 2022 at 8:05 PM Sasha Krassovsky <
> krassovskysasha@gmail.com>
> wrote:
>
> > As far as I can tell, we currently have no simd for any of our kernels.
> The
> > only source files compiled with e.g. AVX2 support are ones having to do
> > with the hash table used for group by and join (and one called
> > `aggregate_basic_avx2.cc`, which, looking at the disassembly for MinMax
> is
> > filled with instructions that decidedly don't use AVX2 for MinMax. I
> can't
> > really tell what it's doing).
> > Compilers are plenty smart already for most of the scalar kernels we
> would
> > want to add, we just don't use it. And we don't really use xsimd for
> > anything currently except for "bpacking", which, looking at godbolt, gets
> > autovectorized just fine.
> >
> > As for code that isn't autovectorizable, I'm going to have to hard
> disagree
> > that an abstraction library is the best way. The whole point of manually
> > writing tuning code is to extract maximum performance from the hardware
> > that you're targeting. This can only happen if you develop your
> algorithms
> > for the specific instruction set. Using something like xsimd will hide
> the
> > instructions that are actually being invoked. It may be that there is a
> > native instruction for something on x86 but not on NEON, and vice versa.
> By
> > using xsimd, it would appear to work well on both architectures but you'd
> > be shooting yourself in the foot by emulating one architecture's simd
> with
> > another's. In fact, I don't see any equivalent in xsimd for AVX's swizzle
> > instructions on NEON. These instructions are heavily used by AVX
> > algorithms. The point is: you design the algorithm around the instruction
> > set, not the other way around.
> >
> > So in summary: As far as I can tell, we currently don't do any
> > autovectorization, and we use xsimd in a spot where autovectorization
> would
> > do the same job, but without the added dependency.
> >
> > Sasha
> >
> > On Tue, Mar 29, 2022 at 6:47 PM Yibo Cai <Yi...@arm.com> wrote:
> >
> > > Hi Sasha,
> > >
> > > Thanks for the advice. I didn't quite catch the point. Would you
> explain
> > a
> > > bit the purpose of this proposal?
> > >
> > > We do prefer compiler auto-vectorization to explicit simd code, even if
> > > the c++ code is slower than simd one (20% is acceptable IMO). And we do
> > > support runtime dispatch kernels based on target machine arch.
> > >
> > > Then what is left to talk is how to deal with codes that are not
> > > auto-vectorizable but can be manually optimized with simd instructions.
> > > Looks your proposal is to do nothing more than adding appropriate
> > compiler
> > > flags and wait for compilers become smarter in the future. I think this
> > is
> > > a reasonable approach, probably is many cases. But if we do want to
> > > manually tune the code, I believe a simd library is the best way.
> > >
> > > To me there's no "replacing" between xsimd and auto-vectorization, they
> > > just do their own jobs.
> > >
> > > Yibo
> > >
> > > -----Original Message-----
> > > From: Sasha Krassovsky <kr...@gmail.com>
> > > Sent: Wednesday, March 30, 2022 6:58 AM
> > > To: dev@arrow.apache.org; emkornfield@gmail.com
> > > Subject: Re: [C++] Replacing xsimd with compiler autovectorization
> > >
> > > xsimd has three problems I can think of right now:
> > > 1) xsimd code looks like normal simd code: you have to explicitly do
> > loads
> > > and stores, you have to explicitly unroll and stride through your loop,
> > and
> > > you have to explicitly process the tail of the loop. This makes
> writing a
> > > large number of kernels extremely tedious and error-prone. In
> comparison,
> > > writing a single three-line scalar for loop is easier to both read and
> > > write.
> > > 2) xsimd limits the freedom an optimizer has to select instructions and
> > do
> > > other optimizations, as it's just a thin wrapper over normal
> intrinsics.
> > > One concrete example would be if we wanted to take advantage of the
> > > dynamic dispatch instruction set xsimd offers, the loop strides would
> no
> > > longer be compile-time constants, which might prevent the compiler from
> > > performing loop unrolling (how would it know that the stride isn't just
> > 1?)
> > > 3) Lastly, if we ever want to support a new architecture (like Power9
> or
> > > RISC-V), we'd have to wait for an xsimd backend to become available. On
> > the
> > > other hand, if SiFive came out with a hot new chip supporting RV64V,
> all
> > > we'd have to do to support it is to add the appropriate compiler flag
> > into
> > > the CMakeLists.
> > >
> > > As for using an external build system, I'm not sure how much complexity
> > it
> > > would add, but at the very least I suspect it would work out of the box
> > if
> > > you only wanted to support scalar kernels. Otherwise I don't think it
> > would
> > > add much more complexity than we currently have detecting architectures
> > at
> > > buildtime.
> > >
> > > Sasha
> > >
> > > On Tue, Mar 29, 2022 at 3:26 PM Micah Kornfield <emkornfield@gmail.com
> >
> > > wrote:
> > >
> > > > Hi Sasha,
> > > > Could you elaborate on the problems of the XSIMD dependency?  What
> you
> > > > describe sounds a lot like what XSIMD provides in a prepackaged form
> > > > and without the extra CMake magic.
> > > >
> > > > I  have to occasionally build Arrow with an external build system and
> > > > it sounds like this type of logic could add complexity there.
> > > >
> > > > Thanks,
> > > > Micah
> > > >
> > > > On Tue, Mar 29, 2022 at 3:14 PM Sasha Krassovsky <
> > > > krassovskysasha@gmail.com>
> > > > wrote:
> > > >
> > > > > Hi everyone,
> > > > > I've noticed that we include xsimd as an abstraction over all of
> the
> > > > > simd architectures. I'd like to propose a different solution which
> > > > > would
> > > > result
> > > > > in fewer lines of code, while being more readable.
> > > > >
> > > > > My thinking is that anything simple enough to abstract with xsimd
> > > > > can be autovectorized by the compiler. Any more interesting SIMD
> > > > > algorithm
> > > > usually
> > > > > is tailored to the target instruction set and can't be abstracted
> > > > > away
> > > > with
> > > > > xsimd anyway.
> > > > >
> > > > > With that in mind, I'd like to propose the following strategy:
> > > > > 1. Write a single source file with simple, element-at-a-time for
> > > > > loop implementations of each function.
> > > > > 2. Compile this same source file several times with different
> > > > > compile
> > > > flags
> > > > > for different vectorization (e.g. if we're on an x86 machine that
> > > > supports
> > > > > AVX2 and AVX512, we'd compile once with -mavx2 and once with
> > > -mavx512vl).
> > > > > 3. Functions compiled with different instruction sets can be
> > > > differentiated
> > > > > by a namespace, which gets defined during the compiler invocation.
> > > > > For example, for AVX2 we'd invoke the compiler with
> -DNAMESPACE=AVX2
> > > > > and then for something like elementwise addition of two arrays,
> we'd
> > > > > call arrow::AVX2::VectorAdd.
> > > > >
> > > > > I believe this would let us remove xsimd as a dependency while also
> > > > giving
> > > > > us lots of vectorized kernels at the cost of some extra cmake
> magic.
> > > > After
> > > > > that, it would just be a matter of making the function registry
> > > > > point to these new functions.
> > > > >
> > > > > Please let me know your thoughts!
> > > > >
> > > > > Thanks,
> > > > > Sasha Krassovsky
> > > > >
> > > >
> > > IMPORTANT NOTICE: The contents of this email and any attachments are
> > > confidential and may also be privileged. If you are not the intended
> > > recipient, please notify the sender immediately and do not disclose the
> > > contents to any other person, use it for any purpose, or store or copy
> > the
> > > information in any medium. Thank you.
> > >
> >
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Micah Kornfield <em...@gmail.com>]

>
> So in summary: As far as I can tell, we currently don't do any
> autovectorization, and we use xsimd in a spot where autovectorization would
> do the same job, but without the added dependency.

Is this in general, or specific to compiler flags being used.  As a pont of
reference the original PR that did optimiziation for aggregates [1] only
shows results when AVX2 is required to see performance speedups, it is
possible there has been a regression since its introduction.  If these
aren't due to SIMD differences, I'm kind of curious what they are from.
One of the challenges is that pre-released binaries need to support a wide
variety of ISAs so acceleration would require dynamic dispatch.  I'm not
sure I understand your proposal exactly but would this include dynamic
dispatch for all kernels as well?  Maybe an example of your proposal for
one kernel would help the discussion?

2) xsimd limits the freedom an optimizer has to select instructions and do
> other optimizations, as it's just a thin wrapper over normal intrinsics.
> One concrete example would be if we wanted to take advantage of the dynamic
> dispatch instruction set xsimd offers, the loop strides would no longer be
> compile-time constants, which might prevent the compiler from performing
> loop unrolling (how would it know that the stride isn't just 1?)
>
Last time we discussed this I believe we agreed we'd use and build up
Arrow's dynamic dispatch instead of using XSIMDs.

The whole point of manually
> writing tuning code is to extract maximum performance from the hardware
> that you're targeting.

I think there are different levels to this. For most optimal performance,
yes you need to target an ISA, it also is the least generalizable.  I
believe we've seen examples where using XSIMD has improved both Intel and
Arm performance over whatever the compiler was generating. This could be
due to using a pattern that was auto-vectorization friendly and maybe there
are better ones.   However, this raises the issue about how fragile
auto-vectorization can be at times (and also based on compilers).

For the record, I don't have a strong opinion on removing or keeping XSIMD,
but if Arrow builds become too difficult to adapt to other build-systems
because of CMake magic, I don't think that is a good outcome.

Cheers,
Micah

[1] https://github.com/apache/arrow/pull/7871



>


On Tue, Mar 29, 2022 at 8:05 PM Sasha Krassovsky <kr...@gmail.com>
wrote:

> As far as I can tell, we currently have no simd for any of our kernels. The
> only source files compiled with e.g. AVX2 support are ones having to do
> with the hash table used for group by and join (and one called
> `aggregate_basic_avx2.cc`, which, looking at the disassembly for MinMax is
> filled with instructions that decidedly don't use AVX2 for MinMax. I can't
> really tell what it's doing).
> Compilers are plenty smart already for most of the scalar kernels we would
> want to add, we just don't use it. And we don't really use xsimd for
> anything currently except for "bpacking", which, looking at godbolt, gets
> autovectorized just fine.
>
> As for code that isn't autovectorizable, I'm going to have to hard disagree
> that an abstraction library is the best way. The whole point of manually
> writing tuning code is to extract maximum performance from the hardware
> that you're targeting. This can only happen if you develop your algorithms
> for the specific instruction set. Using something like xsimd will hide the
> instructions that are actually being invoked. It may be that there is a
> native instruction for something on x86 but not on NEON, and vice versa. By
> using xsimd, it would appear to work well on both architectures but you'd
> be shooting yourself in the foot by emulating one architecture's simd with
> another's. In fact, I don't see any equivalent in xsimd for AVX's swizzle
> instructions on NEON. These instructions are heavily used by AVX
> algorithms. The point is: you design the algorithm around the instruction
> set, not the other way around.
>
> So in summary: As far as I can tell, we currently don't do any
> autovectorization, and we use xsimd in a spot where autovectorization would
> do the same job, but without the added dependency.
>
> Sasha
>
> On Tue, Mar 29, 2022 at 6:47 PM Yibo Cai <Yi...@arm.com> wrote:
>
> > Hi Sasha,
> >
> > Thanks for the advice. I didn't quite catch the point. Would you explain
> a
> > bit the purpose of this proposal?
> >
> > We do prefer compiler auto-vectorization to explicit simd code, even if
> > the c++ code is slower than simd one (20% is acceptable IMO). And we do
> > support runtime dispatch kernels based on target machine arch.
> >
> > Then what is left to talk is how to deal with codes that are not
> > auto-vectorizable but can be manually optimized with simd instructions.
> > Looks your proposal is to do nothing more than adding appropriate
> compiler
> > flags and wait for compilers become smarter in the future. I think this
> is
> > a reasonable approach, probably is many cases. But if we do want to
> > manually tune the code, I believe a simd library is the best way.
> >
> > To me there's no "replacing" between xsimd and auto-vectorization, they
> > just do their own jobs.
> >
> > Yibo
> >
> > -----Original Message-----
> > From: Sasha Krassovsky <kr...@gmail.com>
> > Sent: Wednesday, March 30, 2022 6:58 AM
> > To: dev@arrow.apache.org; emkornfield@gmail.com
> > Subject: Re: [C++] Replacing xsimd with compiler autovectorization
> >
> > xsimd has three problems I can think of right now:
> > 1) xsimd code looks like normal simd code: you have to explicitly do
> loads
> > and stores, you have to explicitly unroll and stride through your loop,
> and
> > you have to explicitly process the tail of the loop. This makes writing a
> > large number of kernels extremely tedious and error-prone. In comparison,
> > writing a single three-line scalar for loop is easier to both read and
> > write.
> > 2) xsimd limits the freedom an optimizer has to select instructions and
> do
> > other optimizations, as it's just a thin wrapper over normal intrinsics.
> > One concrete example would be if we wanted to take advantage of the
> > dynamic dispatch instruction set xsimd offers, the loop strides would no
> > longer be compile-time constants, which might prevent the compiler from
> > performing loop unrolling (how would it know that the stride isn't just
> 1?)
> > 3) Lastly, if we ever want to support a new architecture (like Power9 or
> > RISC-V), we'd have to wait for an xsimd backend to become available. On
> the
> > other hand, if SiFive came out with a hot new chip supporting RV64V, all
> > we'd have to do to support it is to add the appropriate compiler flag
> into
> > the CMakeLists.
> >
> > As for using an external build system, I'm not sure how much complexity
> it
> > would add, but at the very least I suspect it would work out of the box
> if
> > you only wanted to support scalar kernels. Otherwise I don't think it
> would
> > add much more complexity than we currently have detecting architectures
> at
> > buildtime.
> >
> > Sasha
> >
> > On Tue, Mar 29, 2022 at 3:26 PM Micah Kornfield <em...@gmail.com>
> > wrote:
> >
> > > Hi Sasha,
> > > Could you elaborate on the problems of the XSIMD dependency?  What you
> > > describe sounds a lot like what XSIMD provides in a prepackaged form
> > > and without the extra CMake magic.
> > >
> > > I  have to occasionally build Arrow with an external build system and
> > > it sounds like this type of logic could add complexity there.
> > >
> > > Thanks,
> > > Micah
> > >
> > > On Tue, Mar 29, 2022 at 3:14 PM Sasha Krassovsky <
> > > krassovskysasha@gmail.com>
> > > wrote:
> > >
> > > > Hi everyone,
> > > > I've noticed that we include xsimd as an abstraction over all of the
> > > > simd architectures. I'd like to propose a different solution which
> > > > would
> > > result
> > > > in fewer lines of code, while being more readable.
> > > >
> > > > My thinking is that anything simple enough to abstract with xsimd
> > > > can be autovectorized by the compiler. Any more interesting SIMD
> > > > algorithm
> > > usually
> > > > is tailored to the target instruction set and can't be abstracted
> > > > away
> > > with
> > > > xsimd anyway.
> > > >
> > > > With that in mind, I'd like to propose the following strategy:
> > > > 1. Write a single source file with simple, element-at-a-time for
> > > > loop implementations of each function.
> > > > 2. Compile this same source file several times with different
> > > > compile
> > > flags
> > > > for different vectorization (e.g. if we're on an x86 machine that
> > > supports
> > > > AVX2 and AVX512, we'd compile once with -mavx2 and once with
> > -mavx512vl).
> > > > 3. Functions compiled with different instruction sets can be
> > > differentiated
> > > > by a namespace, which gets defined during the compiler invocation.
> > > > For example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2
> > > > and then for something like elementwise addition of two arrays, we'd
> > > > call arrow::AVX2::VectorAdd.
> > > >
> > > > I believe this would let us remove xsimd as a dependency while also
> > > giving
> > > > us lots of vectorized kernels at the cost of some extra cmake magic.
> > > After
> > > > that, it would just be a matter of making the function registry
> > > > point to these new functions.
> > > >
> > > > Please let me know your thoughts!
> > > >
> > > > Thanks,
> > > > Sasha Krassovsky
> > > >
> > >
> > IMPORTANT NOTICE: The contents of this email and any attachments are
> > confidential and may also be privileged. If you are not the intended
> > recipient, please notify the sender immediately and do not disclose the
> > contents to any other person, use it for any purpose, or store or copy
> the
> > information in any medium. Thank you.
> >
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

As far as I can tell, we currently have no simd for any of our kernels. The
only source files compiled with e.g. AVX2 support are ones having to do
with the hash table used for group by and join (and one called
`aggregate_basic_avx2.cc`, which, looking at the disassembly for MinMax is
filled with instructions that decidedly don't use AVX2 for MinMax. I can't
really tell what it's doing).
Compilers are plenty smart already for most of the scalar kernels we would
want to add, we just don't use it. And we don't really use xsimd for
anything currently except for "bpacking", which, looking at godbolt, gets
autovectorized just fine.

As for code that isn't autovectorizable, I'm going to have to hard disagree
that an abstraction library is the best way. The whole point of manually
writing tuning code is to extract maximum performance from the hardware
that you're targeting. This can only happen if you develop your algorithms
for the specific instruction set. Using something like xsimd will hide the
instructions that are actually being invoked. It may be that there is a
native instruction for something on x86 but not on NEON, and vice versa. By
using xsimd, it would appear to work well on both architectures but you'd
be shooting yourself in the foot by emulating one architecture's simd with
another's. In fact, I don't see any equivalent in xsimd for AVX's swizzle
instructions on NEON. These instructions are heavily used by AVX
algorithms. The point is: you design the algorithm around the instruction
set, not the other way around.

So in summary: As far as I can tell, we currently don't do any
autovectorization, and we use xsimd in a spot where autovectorization would
do the same job, but without the added dependency.

Sasha

On Tue, Mar 29, 2022 at 6:47 PM Yibo Cai <Yi...@arm.com> wrote:

> Hi Sasha,
>
> Thanks for the advice. I didn't quite catch the point. Would you explain a
> bit the purpose of this proposal?
>
> We do prefer compiler auto-vectorization to explicit simd code, even if
> the c++ code is slower than simd one (20% is acceptable IMO). And we do
> support runtime dispatch kernels based on target machine arch.
>
> Then what is left to talk is how to deal with codes that are not
> auto-vectorizable but can be manually optimized with simd instructions.
> Looks your proposal is to do nothing more than adding appropriate compiler
> flags and wait for compilers become smarter in the future. I think this is
> a reasonable approach, probably is many cases. But if we do want to
> manually tune the code, I believe a simd library is the best way.
>
> To me there's no "replacing" between xsimd and auto-vectorization, they
> just do their own jobs.
>
> Yibo
>
> -----Original Message-----
> From: Sasha Krassovsky <kr...@gmail.com>
> Sent: Wednesday, March 30, 2022 6:58 AM
> To: dev@arrow.apache.org; emkornfield@gmail.com
> Subject: Re: [C++] Replacing xsimd with compiler autovectorization
>
> xsimd has three problems I can think of right now:
> 1) xsimd code looks like normal simd code: you have to explicitly do loads
> and stores, you have to explicitly unroll and stride through your loop, and
> you have to explicitly process the tail of the loop. This makes writing a
> large number of kernels extremely tedious and error-prone. In comparison,
> writing a single three-line scalar for loop is easier to both read and
> write.
> 2) xsimd limits the freedom an optimizer has to select instructions and do
> other optimizations, as it's just a thin wrapper over normal intrinsics.
> One concrete example would be if we wanted to take advantage of the
> dynamic dispatch instruction set xsimd offers, the loop strides would no
> longer be compile-time constants, which might prevent the compiler from
> performing loop unrolling (how would it know that the stride isn't just 1?)
> 3) Lastly, if we ever want to support a new architecture (like Power9 or
> RISC-V), we'd have to wait for an xsimd backend to become available. On the
> other hand, if SiFive came out with a hot new chip supporting RV64V, all
> we'd have to do to support it is to add the appropriate compiler flag into
> the CMakeLists.
>
> As for using an external build system, I'm not sure how much complexity it
> would add, but at the very least I suspect it would work out of the box if
> you only wanted to support scalar kernels. Otherwise I don't think it would
> add much more complexity than we currently have detecting architectures at
> buildtime.
>
> Sasha
>
> On Tue, Mar 29, 2022 at 3:26 PM Micah Kornfield <em...@gmail.com>
> wrote:
>
> > Hi Sasha,
> > Could you elaborate on the problems of the XSIMD dependency?  What you
> > describe sounds a lot like what XSIMD provides in a prepackaged form
> > and without the extra CMake magic.
> >
> > I  have to occasionally build Arrow with an external build system and
> > it sounds like this type of logic could add complexity there.
> >
> > Thanks,
> > Micah
> >
> > On Tue, Mar 29, 2022 at 3:14 PM Sasha Krassovsky <
> > krassovskysasha@gmail.com>
> > wrote:
> >
> > > Hi everyone,
> > > I've noticed that we include xsimd as an abstraction over all of the
> > > simd architectures. I'd like to propose a different solution which
> > > would
> > result
> > > in fewer lines of code, while being more readable.
> > >
> > > My thinking is that anything simple enough to abstract with xsimd
> > > can be autovectorized by the compiler. Any more interesting SIMD
> > > algorithm
> > usually
> > > is tailored to the target instruction set and can't be abstracted
> > > away
> > with
> > > xsimd anyway.
> > >
> > > With that in mind, I'd like to propose the following strategy:
> > > 1. Write a single source file with simple, element-at-a-time for
> > > loop implementations of each function.
> > > 2. Compile this same source file several times with different
> > > compile
> > flags
> > > for different vectorization (e.g. if we're on an x86 machine that
> > supports
> > > AVX2 and AVX512, we'd compile once with -mavx2 and once with
> -mavx512vl).
> > > 3. Functions compiled with different instruction sets can be
> > differentiated
> > > by a namespace, which gets defined during the compiler invocation.
> > > For example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2
> > > and then for something like elementwise addition of two arrays, we'd
> > > call arrow::AVX2::VectorAdd.
> > >
> > > I believe this would let us remove xsimd as a dependency while also
> > giving
> > > us lots of vectorized kernels at the cost of some extra cmake magic.
> > After
> > > that, it would just be a matter of making the function registry
> > > point to these new functions.
> > >
> > > Please let me know your thoughts!
> > >
> > > Thanks,
> > > Sasha Krassovsky
> > >
> >
> IMPORTANT NOTICE: The contents of this email and any attachments are
> confidential and may also be privileged. If you are not the intended
> recipient, please notify the sender immediately and do not disclose the
> contents to any other person, use it for any purpose, or store or copy the
> information in any medium. Thank you.
>

RE: [C++] Replacing xsimd with compiler autovectorization

[Yibo Cai <Yi...@arm.com>]

Hi Sasha,

Thanks for the advice. I didn't quite catch the point. Would you explain a bit the purpose of this proposal?

We do prefer compiler auto-vectorization to explicit simd code, even if the c++ code is slower than simd one (20% is acceptable IMO). And we do support runtime dispatch kernels based on target machine arch.

Then what is left to talk is how to deal with codes that are not auto-vectorizable but can be manually optimized with simd instructions. Looks your proposal is to do nothing more than adding appropriate compiler flags and wait for compilers become smarter in the future. I think this is a reasonable approach, probably is many cases. But if we do want to manually tune the code, I believe a simd library is the best way.

To me there's no "replacing" between xsimd and auto-vectorization, they just do their own jobs.

Yibo

-----Original Message-----
From: Sasha Krassovsky <kr...@gmail.com>
Sent: Wednesday, March 30, 2022 6:58 AM
To: dev@arrow.apache.org; emkornfield@gmail.com
Subject: Re: [C++] Replacing xsimd with compiler autovectorization

xsimd has three problems I can think of right now:
1) xsimd code looks like normal simd code: you have to explicitly do loads and stores, you have to explicitly unroll and stride through your loop, and you have to explicitly process the tail of the loop. This makes writing a large number of kernels extremely tedious and error-prone. In comparison, writing a single three-line scalar for loop is easier to both read and write.
2) xsimd limits the freedom an optimizer has to select instructions and do other optimizations, as it's just a thin wrapper over normal intrinsics.
One concrete example would be if we wanted to take advantage of the dynamic dispatch instruction set xsimd offers, the loop strides would no longer be compile-time constants, which might prevent the compiler from performing loop unrolling (how would it know that the stride isn't just 1?)
3) Lastly, if we ever want to support a new architecture (like Power9 or RISC-V), we'd have to wait for an xsimd backend to become available. On the other hand, if SiFive came out with a hot new chip supporting RV64V, all we'd have to do to support it is to add the appropriate compiler flag into the CMakeLists.

As for using an external build system, I'm not sure how much complexity it would add, but at the very least I suspect it would work out of the box if you only wanted to support scalar kernels. Otherwise I don't think it would add much more complexity than we currently have detecting architectures at buildtime.

Sasha

On Tue, Mar 29, 2022 at 3:26 PM Micah Kornfield <em...@gmail.com>
wrote:

> Hi Sasha,
> Could you elaborate on the problems of the XSIMD dependency?  What you
> describe sounds a lot like what XSIMD provides in a prepackaged form
> and without the extra CMake magic.
>
> I  have to occasionally build Arrow with an external build system and
> it sounds like this type of logic could add complexity there.
>
> Thanks,
> Micah
>
> On Tue, Mar 29, 2022 at 3:14 PM Sasha Krassovsky <
> krassovskysasha@gmail.com>
> wrote:
>
> > Hi everyone,
> > I've noticed that we include xsimd as an abstraction over all of the
> > simd architectures. I'd like to propose a different solution which
> > would
> result
> > in fewer lines of code, while being more readable.
> >
> > My thinking is that anything simple enough to abstract with xsimd
> > can be autovectorized by the compiler. Any more interesting SIMD
> > algorithm
> usually
> > is tailored to the target instruction set and can't be abstracted
> > away
> with
> > xsimd anyway.
> >
> > With that in mind, I'd like to propose the following strategy:
> > 1. Write a single source file with simple, element-at-a-time for
> > loop implementations of each function.
> > 2. Compile this same source file several times with different
> > compile
> flags
> > for different vectorization (e.g. if we're on an x86 machine that
> supports
> > AVX2 and AVX512, we'd compile once with -mavx2 and once with -mavx512vl).
> > 3. Functions compiled with different instruction sets can be
> differentiated
> > by a namespace, which gets defined during the compiler invocation.
> > For example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2
> > and then for something like elementwise addition of two arrays, we'd
> > call arrow::AVX2::VectorAdd.
> >
> > I believe this would let us remove xsimd as a dependency while also
> giving
> > us lots of vectorized kernels at the cost of some extra cmake magic.
> After
> > that, it would just be a matter of making the function registry
> > point to these new functions.
> >
> > Please let me know your thoughts!
> >
> > Thanks,
> > Sasha Krassovsky
> >
>
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

Re: [C++] Replacing xsimd with compiler autovectorization

[Sasha Krassovsky <kr...@gmail.com>]

xsimd has three problems I can think of right now:
1) xsimd code looks like normal simd code: you have to explicitly do loads
and stores, you have to explicitly unroll and stride through your loop, and
you have to explicitly process the tail of the loop. This makes writing a
large number of kernels extremely tedious and error-prone. In comparison,
writing a single three-line scalar for loop is easier to both read and
write.
2) xsimd limits the freedom an optimizer has to select instructions and do
other optimizations, as it's just a thin wrapper over normal intrinsics.
One concrete example would be if we wanted to take advantage of the dynamic
dispatch instruction set xsimd offers, the loop strides would no longer be
compile-time constants, which might prevent the compiler from performing
loop unrolling (how would it know that the stride isn't just 1?)
3) Lastly, if we ever want to support a new architecture (like Power9 or
RISC-V), we'd have to wait for an xsimd backend to become available. On the
other hand, if SiFive came out with a hot new chip supporting RV64V, all
we'd have to do to support it is to add the appropriate compiler flag into
the CMakeLists.

As for using an external build system, I'm not sure how much complexity it
would add, but at the very least I suspect it would work out of the box if
you only wanted to support scalar kernels. Otherwise I don't think it would
add much more complexity than we currently have detecting architectures at
buildtime.

Sasha

On Tue, Mar 29, 2022 at 3:26 PM Micah Kornfield <em...@gmail.com>
wrote:

> Hi Sasha,
> Could you elaborate on the problems of the XSIMD dependency?  What you
> describe sounds a lot like what XSIMD provides in a prepackaged form and
> without the extra CMake magic.
>
> I  have to occasionally build Arrow with an external build system and it
> sounds like this type of logic could add complexity there.
>
> Thanks,
> Micah
>
> On Tue, Mar 29, 2022 at 3:14 PM Sasha Krassovsky <
> krassovskysasha@gmail.com>
> wrote:
>
> > Hi everyone,
> > I've noticed that we include xsimd as an abstraction over all of the simd
> > architectures. I'd like to propose a different solution which would
> result
> > in fewer lines of code, while being more readable.
> >
> > My thinking is that anything simple enough to abstract with xsimd can be
> > autovectorized by the compiler. Any more interesting SIMD algorithm
> usually
> > is tailored to the target instruction set and can't be abstracted away
> with
> > xsimd anyway.
> >
> > With that in mind, I'd like to propose the following strategy:
> > 1. Write a single source file with simple, element-at-a-time for loop
> > implementations of each function.
> > 2. Compile this same source file several times with different compile
> flags
> > for different vectorization (e.g. if we're on an x86 machine that
> supports
> > AVX2 and AVX512, we'd compile once with -mavx2 and once with -mavx512vl).
> > 3. Functions compiled with different instruction sets can be
> differentiated
> > by a namespace, which gets defined during the compiler invocation. For
> > example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2 and then
> > for something like elementwise addition of two arrays, we'd call
> > arrow::AVX2::VectorAdd.
> >
> > I believe this would let us remove xsimd as a dependency while also
> giving
> > us lots of vectorized kernels at the cost of some extra cmake magic.
> After
> > that, it would just be a matter of making the function registry point to
> > these new functions.
> >
> > Please let me know your thoughts!
> >
> > Thanks,
> > Sasha Krassovsky
> >
>

Re: [C++] Replacing xsimd with compiler autovectorization

[Micah Kornfield <em...@gmail.com>]

Hi Sasha,
Could you elaborate on the problems of the XSIMD dependency?  What you
describe sounds a lot like what XSIMD provides in a prepackaged form and
without the extra CMake magic.

I  have to occasionally build Arrow with an external build system and it
sounds like this type of logic could add complexity there.

Thanks,
Micah

On Tue, Mar 29, 2022 at 3:14 PM Sasha Krassovsky <kr...@gmail.com>
wrote:

> Hi everyone,
> I've noticed that we include xsimd as an abstraction over all of the simd
> architectures. I'd like to propose a different solution which would result
> in fewer lines of code, while being more readable.
>
> My thinking is that anything simple enough to abstract with xsimd can be
> autovectorized by the compiler. Any more interesting SIMD algorithm usually
> is tailored to the target instruction set and can't be abstracted away with
> xsimd anyway.
>
> With that in mind, I'd like to propose the following strategy:
> 1. Write a single source file with simple, element-at-a-time for loop
> implementations of each function.
> 2. Compile this same source file several times with different compile flags
> for different vectorization (e.g. if we're on an x86 machine that supports
> AVX2 and AVX512, we'd compile once with -mavx2 and once with -mavx512vl).
> 3. Functions compiled with different instruction sets can be differentiated
> by a namespace, which gets defined during the compiler invocation. For
> example, for AVX2 we'd invoke the compiler with -DNAMESPACE=AVX2 and then
> for something like elementwise addition of two arrays, we'd call
> arrow::AVX2::VectorAdd.
>
> I believe this would let us remove xsimd as a dependency while also giving
> us lots of vectorized kernels at the cost of some extra cmake magic. After
> that, it would just be a matter of making the function registry point to
> these new functions.
>
> Please let me know your thoughts!
>
> Thanks,
> Sasha Krassovsky
>