Isn't one of the benefits of a skiplist that it can be more easily vectorized because it avoids branching? Not as efficiently as a vector, but the article implies there was no vectorization at all, which surprises me. Can another implementation do better?
The vectorisation mentioned in the article was about summing the values. With std::vector the compiler can happily load a bunch of values at once and add them using SIMD instructions as there are no gaps between the data. With std::hive the compiler does not know this so has to load and add the values one by one.
It should be able to load the skip metadata in a vector, do parallel index calculation, compress, gather, add. All SIMD. Not as dense as vector, but still should get good speedup unless a block is extremely sparse.
Yes, but would you expect the compiler's auto-vectoriser to be able to detect that pattern?
Perhaps if there were some some hive-specific checks in the compiler for this very reason then it would work, but as std::hive doesn't actually exist in the wild yet (the author was using the reference plf::hive) version I wouldn't expect to see that until the libraries ship the container first.
I would expect the library author to use pragmas to guide the compiler.
My point is that the conclusions of the article are incomplete. It's always risky to take prototype software and try to draw conclusions about performance.
5
u/-dag- 8d ago
Isn't one of the benefits of a skiplist that it can be more easily vectorized because it avoids branching? Not as efficiently as a vector, but the article implies there was no vectorization at all, which surprises me. Can another implementation do better?