avx_qsort VS rune

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...

I'm the co-author of one of the papers referenced in the blogpost, (Fast Quicksort Implementation Using AVX Instructions), we did write the AVX512 code back in 2015, just had nowhere to run it, at least publicly. The paper also very explicitly says that the lookup tables can be instead replaced by the AVX512 compress instructions. The code for that paper is available in https://github.com/vkrasnov/avx_qsort

There are a few research languages where handling secrets and constant-time operations correctly is a first-class feature. See for example:

https://github.com/google/rune

I can field questions folks might have on DataDraw. I'm not Bill, but I wrote the docs PR that recently overhauled the Rune README to highlight a lot of this interesting info about its use of the DD tool.

Another neat thing about DD -- the Rune compiler/grammar itself are written as DataDraw types, and one of the builtin things you can do is generate PostScript visualizations of them. Check this out:

https://github.com/google/rune/pull/33#issuecomment-13558283...

Maybe Google's new "Rune" language will become prevalent https://github.com/google/rune, which supports SoA.

The Rune Programming Language\ (99 comments)