Earlier quoted context omitted.
Maybe Google's new "Rune" language will become prevalent https://github.com/google/rune , which supports SoA.
What's SoA?
Struct of Arrays
Sorting with SIMD
61–66 of 66 posts
Re: Sorting with SIMD
#62I recently tried to do that as well, but failed. Specifically, I have implemented AA sort [1] but for my use case the performance was about the same as std::sort in C++, for the substantial code complexity cost. I reverted to std::sort. The code is on github [2] Still, in that particular project the vectors being sorted are relatively small, typically under than 100kb, so I have only implemented their “inner” algorit…
We also experimented with 4x4 networks but it's very helpful to use 256 or 512-bit SIMD. You might give our vqsort a try, it's quite a bit faster than std::sort: https://github.com/google/highway/blob/master/hwy/contrib/so...
Re: Sorting with SIMD
#63Re: Sorting with SIMD
#64If you are exclusively moving numbers around in an array, SIMD sorting sounds great. But when you want to actually sort things, it's different. You have objects in an array, the objects will have one member which is a Key that you will sort the objects on. In order to create a sorted permutation of the list, you either need to rearrange the list of object pointers (fast), rearrange the memory of the objects (slow), o…
The original (AFAICT) work on SIMD quick sort, also mentioned in the google post also implemented pointer sort by loading a pointed key using gather instructions and the method can be used for an array of structs. https://github.com/vkrasnov/avx_qsort/blob/master/qsort_AVX2...
Re: Sorting with SIMD
#65If you are exclusively moving numbers around in an array, SIMD sorting sounds great. But when you want to actually sort things, it's different. You have objects in an array, the objects will have one member which is a Key that you will sort the objects on. In order to create a sorted permutation of the list, you either need to rearrange the list of object pointers (fast), rearrange the memory of the objects (slow), o…
It might be easier for SIMD to work by extracting the key value from each object into its own array. Form an array with fixed element size: [ {index0 | key0}, {index1 | key1}, ...], where indices are the element index to the original array of objects and the keys are fixed size. The fat element {index | key} is moved as a whole unit to carry the original index along with the swap during sorting. SIMD can deal with fi…
That would be called a gather operation, which is itself slow, exactly as the OP comment said.
Re: Sorting with SIMD
#66Earlier quoted context omitted.
> Fast integrated GPUs like Apple's allow for directly accessing the main memory without copy, making the GPU more viable for general purposes. My understanding (and I would be very happy for any clarifications/corrections!) is that you must use Metal Buffers (MTLBuffer) with the Apple Silicon GPU. If your data isn't already in a Metal Buffer (why would it be?), you have to do a copy into a buffer (but it will be ext…
> I've been exploring general purpose computing with both CUDA and Apple Silicon and am having a lot better luck using SIMD intrinsics instead What sort of programs are you trying this with?
I am writing some stuff that will hopefully be published next year, so I don't want to get into it too much now.
But it basically started with this sequence of text from "Is Parallel Programming Hard, And, If So, What Can You Do About It?" [0]:
> Parallel programming has earned a reputation as one of the most difficult areas a hacker can tackle.
> However, new technologies that are difficult to use at introduction invariably become easier over time.
> Therefore, if you wish to argue that parallel programming will remain as difficult as it is currently perceived by many to be, it is you who bears the burden of proof
We are now in an era in which is it nearly impossible for the average consumer to buy a computing product that doesn't have multiple cores, SIMD, and a GPGPU. So I felt that it was time to explore how to do it with everyday basic general computing tasks. I was starting with nearly zero experience and writing what I've been learning :)
By the way, even the Raspberry Pi 4 does very nicely with ARM Neon, though it doesn't improve with multiple threads concurrently executing SIMD code like Apple Silicon does!
[0] https://mirrors.edge.kernel.org/pub/linux/kernel/people/paul...