4 ms·

Is this a technical impossibility or just it hasn't been done yet? Could a library support generating intrinsics for a large set of architectures?

loeg 5mo ago
Google Highway gets mentioned in the article.
mattip 5mo ago
There is google’s highway, that provides an abstraction layer. It is used by NumPy.
jandrewrogers 5mo ago
The full scope of what SIMD is used for is much larger than parallelizing evaluation of numeric types and algorithms. For example, it is used for parallel evaluation of complex constraints on unrelated types simultaneously while packed into a single vector. Think a WHERE clause on an arbitrary SQL schema evaluated in full parallel in a handful of clock cycles. SIMD turns out to be brilliant for this but it looks nothing like auto-vectorization. None of the SIMD libraries like Google Highway cover this case.
- camel-cdr 5mo ago
  I don't quite get how something like highway doesn't cover this, while intrinsics do. Can you explain the usecase more concretely?
  - jandrewrogers 5mo ago
    Almost literally what I stated. Consider a row in Postgres table or similar. Convert the entire WHERE clause across all columns in that table into a very short sequence of SIMD instructions against the same memory. All of the columns, regardless of type, are evaluated simultaneously using SIMD. For many complex constraints you can match rows in single digit clock cycles even across many unrelated types. This is much faster than using secondary indexes in many cases. It isn’t hypothetical, I’ve shipped systems that worked this way. You can match search patterns across a random dozen columns across a schema of hundreds of columns at essentially full memory bandwidth.
    - camel-cdr 5mo ago
      OK, I thought it couldn't be that, because that should be doable with std::simd or a SIMD abstraction. Well, unless you JIT it, in which case intrinsics wouldn't help either. > You can match search patterns across a random dozen columns across a schema of hundreds of columns at essentially full memory bandwidth Do I underatand it correctly, that this would only work, if you have multiple of the same comparisons (e.g. equality check with same sized data) in the WHERE clause and the relevant collumns are within one multiple of the SIMD width of each other?
      - jandrewrogers 5mo ago
        Every column has its own independent constraint: equality, order, range intersection, bit sets, etc that is evaluated concurrently in single operations. Independent per column in parallel. It does require handling the representation of columns to enable it but that isn’t onerous in practice. It isn’t intuitive but it is one of those things that is obvious in hindsight once you see how it works. The gap is that people struggle to understand how to make this something SIMD native, especially in high-performance systems.
        camel-cdr 5mo ago
        Ah, so you're just doing SoA or AoSoA layout? It sounded like you where doing something more special than the standard SIMD usecase. This does easily work with SIMD abstractions and even length-agnostic vector ISAs, unless you're doing AoSoA and your storage format has to match your memory format and it has the be the same on all machines. In which case you probably want to do something like 4K blocks anyways, in which case you can make it agnostic for all vector length anybody reasonably cares about for this type of application anyways.

loeg 5mo ago

Google Highway gets mentioned in the article.

mattip 5mo ago

There is google’s highway, that provides an abstraction layer. It is used by NumPy.

jandrewrogers 5mo ago

The full scope of what SIMD is used for is much larger than parallelizing evaluation of numeric types and algorithms. For example, it is used for parallel evaluation of complex constraints on unrelated types simultaneously while packed into a single vector. Think a WHERE clause on an arbitrary SQL schema evaluated in full parallel in a handful of clock cycles. SIMD turns out to be brilliant for this but it looks nothing like auto-vectorization. None of the SIMD libraries like Google Highway cover this case.

camel-cdr 5mo ago
I don't quite get how something like highway doesn't cover this, while intrinsics do. Can you explain the usecase more concretely?
- jandrewrogers 5mo ago
  Almost literally what I stated. Consider a row in Postgres table or similar. Convert the entire WHERE clause across all columns in that table into a very short sequence of SIMD instructions against the same memory. All of the columns, regardless of type, are evaluated simultaneously using SIMD. For many complex constraints you can match rows in single digit clock cycles even across many unrelated types. This is much faster than using secondary indexes in many cases. It isn’t hypothetical, I’ve shipped systems that worked this way. You can match search patterns across a random dozen columns across a schema of hundreds of columns at essentially full memory bandwidth.
  - camel-cdr 5mo ago
    OK, I thought it couldn't be that, because that should be doable with std::simd or a SIMD abstraction. Well, unless you JIT it, in which case intrinsics wouldn't help either. > You can match search patterns across a random dozen columns across a schema of hundreds of columns at essentially full memory bandwidth Do I underatand it correctly, that this would only work, if you have multiple of the same comparisons (e.g. equality check with same sized data) in the WHERE clause and the relevant collumns are within one multiple of the SIMD width of each other?
    - jandrewrogers 5mo ago
      Every column has its own independent constraint: equality, order, range intersection, bit sets, etc that is evaluated concurrently in single operations. Independent per column in parallel. It does require handling the representation of columns to enable it but that isn’t onerous in practice. It isn’t intuitive but it is one of those things that is obvious in hindsight once you see how it works. The gap is that people struggle to understand how to make this something SIMD native, especially in high-performance systems.
      - camel-cdr 5mo ago
        Ah, so you're just doing SoA or AoSoA layout? It sounded like you where doing something more special than the standard SIMD usecase. This does easily work with SIMD abstractions and even length-agnostic vector ISAs, unless you're doing AoSoA and your storage format has to match your memory format and it has the be the same on all machines. In which case you probably want to do something like 4K blocks anyways, in which case you can make it agnostic for all vector length anybody reasonably cares about for this type of application anyways.