3 ms·

I wonder if this will lead to significant speed ups in databases like ElasticSearch, where operations on large bitmaps (each pixel representing a term’s presenc

by btown 7y ago

I wonder if this will lead to significant speed ups in databases like ElasticSearch, where operations on large bitmaps (each pixel representing a term’s presence in a document) are commonplace. Do you have any insight into this?

glangdale 7y ago
I think it can help. Traditional DBs generally worked on the assumption that if you were scanning through records one-by-one you'd already lost, so naive ideas that you can just write Really Good SIMD won't help. But there are plenty of smart people who understand this well and can write SIMD code for what remains. Scanning non-DBMS stuff can benefit a lot from good SIMD (although writing code that's tremendously clever that allows you to run faster than memory bandwidth permits is also fairly self-limiting; the faster you go, the less likely anything can keep you fed).
jandrewrogers 7y ago
It partially depends on the design of the database engine. Some classic designs are not that amenable to it but newer designs do tend to be. Many database operations (like operations on large bitmaps) are effectively memory-bandwidth bound, unless they are running completely out of close CPU cache. Some scenarios where vector intrinsics are commonly used: - Using these instructions to encode/decode compressed data structures where evaluation would otherwise be memory-bound, trading the "free" CPU time to reduce memory bandwidth consumption. Large bitmaps are amenable to this. - Increasing throughput of operations that are CPU bound so that they become (closer to) memory bound, recognizing that the memory bandwidth available to CPU cache-friendly structures may effectively be much higher than RAM bandwidth. Format parsing and cache replacement is a common use case for vector intrinsics in databases for this purpose. - Reducing branch prediction penalties for data structures that don't play well with branch predictors. Commonly used hot path radix-trie structures often have this issue. Some of the intrinsics don't have a direct scalar equivalent and redesigning around them can significantly reduce branching pressure (both number and predictability). - Scan operators for vectors of high-level data types, ironically because they allow you to efficiently use a more complex representation than a simple vector. Pages in databases are large enough these days that this is worth doing and you'll spend much of your CPU time here anyway. I have not (yet) built an operational database kernel that uses AVX-512 intrinsics, though the designs are setup for it, mostly because support is still insufficiently common at the moment. I think the CPU throttling aspects of vector instructions are less of a concern for database engines because good designs tend not to have clock rate as a major throughput limitation in practice, though I've never actually measured it.

by btown 7y ago

glangdale 7y ago

I think it can help. Traditional DBs generally worked on the assumption that if you were scanning through records one-by-one you'd already lost, so naive ideas that you can just write Really Good SIMD won't help. But there are plenty of smart people who understand this well and can write SIMD code for what remains. Scanning non-DBMS stuff can benefit a lot from good SIMD (although writing code that's tremendously clever that allows you to run faster than memory bandwidth permits is also fairly self-limiting; the faster you go, the less likely anything can keep you fed).

jandrewrogers 7y ago

It partially depends on the design of the database engine. Some classic designs are not that amenable to it but newer designs do tend to be. Many database operations (like operations on large bitmaps) are effectively memory-bandwidth bound, unless they are running completely out of close CPU cache. Some scenarios where vector intrinsics are commonly used: - Using these instructions to encode/decode compressed data structures where evaluation would otherwise be memory-bound, trading the "free" CPU time to reduce memory bandwidth consumption. Large bitmaps are amenable to this. - Increasing throughput of operations that are CPU bound so that they become (closer to) memory bound, recognizing that the memory bandwidth available to CPU cache-friendly structures may effectively be much higher than RAM bandwidth. Format parsing and cache replacement is a common use case for vector intrinsics in databases for this purpose. - Reducing branch prediction penalties for data structures that don't play well with branch predictors. Commonly used hot path radix-trie structures often have this issue. Some of the intrinsics don't have a direct scalar equivalent and redesigning around them can significantly reduce branching pressure (both number and predictability). - Scan operators for vectors of high-level data types, ironically because they allow you to efficiently use a more complex representation than a simple vector. Pages in databases are large enough these days that this is worth doing and you'll spend much of your CPU time here anyway. I have not (yet) built an operational database kernel that uses AVX-512 intrinsics, though the designs are setup for it, mostly because support is still insufficiently common at the moment. I think the CPU throttling aspects of vector instructions are less of a concern for database engines because good designs tend not to have clock rate as a major throughput limitation in practice, though I've never actually measured it.