Introducing PgVA aka PostgresVectorAcceleration using SIMD vector instructions starting with hex_encode

INTENTION

Inspired by the effort to integrate JIT for executor acceleration I thought selected simple algorithms working with array-oriented data should be drastically accelerated by using SIMD instructions on modern hardware.

I want to introduce this style of programming with the example of hex_encode:
- operates on arrays (bytea)
- simple algorithm
- in some situations partially limiting the performance (e.g pg_dump)

IMPLEMENTATION GUIDELINES

The main goal ist to accelerate common cases on the most common hardware by exploiting all the resources the hardware delivers.
The following guidelines took me to a first implementation:

- restrict on 64 -bit architectures
These are the dominant server architectures, have the necessary data formats and corresponding registers and operating instructions
- start with Intel x86-64 SIMD instructions:
This is the vastly most used platform, available for development and in practical use
- don’t restrict the concept to only Intel x86-64, so that later people with more experience on other architectures can jump in and implement comparable algorithms
- fallback to the established implementation in postgres in non appropriate cases or on user request (GUC)
- implementation of leaf function/procedures in assembly language
These consist mostly of a central loop without calling subroutines or doing additionally branching

- coding for maximum hardware usage instead of elegant programming
Once tested, the simple algorithm works as advertised and is used to replace most execution parts of the standard implementaion in C

- isolated footprint by integrating it only in the specific subroutine (here hex-encode)
This ensures that the requirements for fast execution are met (e.g. buffer sizes) and no repeated checks are needed like in a library use case.

- trying to keep both vector execution ports always doing useful work by avoiding waits for latencies

- trying to access memory in linear fashion (reading from input buffer, writing to output buffer) to avaoid internal cache problems
- focus optimization for the most advanced SIMD instruction set: AVX512
This provides the most advanced instructions and quite a lot of large registers to aid in latency avoiding

- if possible provide fallback implementations on older SIMD standards (e.g. AVX2 or SSE2)
This is usefull on many older servers and client processors, but due to their too little number of registers latency avoiding or full execution queues cannot be fully achieved.

IMPLEMENTATION DETAILS

- The loops implementing the algorithm are written in NASM assembler:
NASM is actively maintained, has many output formats, follows the Intel style, has all current instrucions implemented and is fast.

- The loops are mostly independent of operating systems, so all OS’s basing on a NASM obj output format are supported:
This includes Linux and Windows as the most important ones

- The algorithms use advanced techniques (constant and temporary registers) to avoid most unnessary memory accesses:
The assembly implementation gives you the full control over the registers (unlike intrinsics)

- Multiple dependency chains work interleaved to minimize latencies:
Coding is often interspersed and using almost all registers available.

- Some instructions (Moves, zeroing) are executed outside the processor execution ports:
These don’t consume execution cyles on a port but their latency has to be considered.

- Some vector instructions (multiply add) have latencies of 5 for example:
This means that after the instruction is issued, the processor has to wait 5 cycles until the result can be used in the same dependency chain. To avoid this and keep all vector execution ports (p0 and p5) busy you have to have 9 other instructions in between doing work on other streams of the algorithm to maximize hardware usage and overall performance.

- All loops are implemented as separate C-callable functions (according to the OS calling convention):
They are all leaf functions by calling no other subroutines.

- The decision which implementation is choosen is done at the caller side by a special dispatcher routine:
The caller handles the architectural capabilites (instruction sets available) and knows the required work: There is often a suitable minimum amount of work required for efficently calling a provided implementation.

- Loops should be run at least 2-4 times to compensate for initializing overhead:
This implicits a certain amount of minimum work count based on the specific SIMD implementations

- The loops terminate after detecting an error (e.g. wrong input data) and return the succesfull completed amount of work:
The standard linear implementation takes over with the already established error-handling.

- The loops work optimally with some extra output buffer space at the end to be able to overshoot in the last round:
Nonethless the correct amount of work is returned to the caller and a vector size of output buffer following the real result is zeroed out (Currently disabled!)

- the loop may preload some data after the input buffer but assures that the following page boundary is never crossed to avoid any access violation:
This makes no harm to the memory system because the output buffer has a supplemental buffer at the end, but this could be changed to leaving the tail handling to the standard implementaion if deemed unsupportable (as for now).

(to be continued...)