Base64 encoding with SIMD instructions

An SSE code is more than 2 times faster on Core i7, and around 70% faster on Core i5. Read more...

SIMD-ized searching in unique constant dictionary

The problem: there is a ordered dictionary containing only unique keys. Dictionary is read only, and keys are 32-bit (SSE) or 64-bit (AVX2). Read more

SSE: Generating mask where n leading (trailing) bytes are set

Informal specification:

__m128i mask_lower(const unsigned n) {
    
    assert(n < 16);
    switch (n) {
        case 0: return {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
        case 1: return {0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
        case 2: return {0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
        // ...
        case 14: return {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00};
        case 15: return {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
    }
}

__m128i mask_higher(const unsigned n) {
    
    assert(n < 16);
    return ~mask_lower(15 - n);
}

Read more ...

Speeding up searching in linked list

Sounds crazy, but it's possible in some cases. Here are experiments results - 3 times faster isn't so bad.

list                          :      0.780s, speedup  1.00
array list (4)                :      0.703s, speedup  1.11
array list (8)                :      0.515s, speedup  1.51
SIMD array list (4)           :      0.365s, speedup  2.14
SIMD array list (8)           :      0.258s, speedup  3.03

Conversion number to hexadecimal representation

Conversion numbers to hexadecimal representation - SWAR, plain SSE, and draft of BMI2 implementation.

Article SSSE3: printing hex values describes the same topic but is limited to exploit PSHUFB.

Scalar version of SSE move mask instruction

SSE instruction PMOVMSKB gathers all most significant bits from bytes and stores them as a single 16-bit value; similar action is performed by MOVMSKPD and MOVMSKPS.

Such operation could be easily done using scalar multiplication. Read more ...

Penalties of errors in SSE floating point calculations

SSE provides not widely known control register, called MXCSR. This register plays three roles:

1. controls calculations:
• flag "flush to zero" (described later)
• flag "denormals are zeros" (described later)
• rounding mode (not covered in this text)
2. allow to mask/unmask floating-point exceptions
3. save information about floating-point errors - these flags are sticky, i.e. the programmer is responsible for clearing them.

Floating point errors may cause significant slowdown, some of the flags can silence errors makes a program faster. Read more ...

Extensions to x86 ISA are useless

Intel announced new extension to SSE: instructions accelerating calculating hashes SHA-1 and SHA256. As everything else added recently to x86 ISA, these new instructions address special cases of "something". Number of instructions, encoding modes, etc. is increasing, but do not help in general.

Let see what sha1msg1 xmm1, xmm2 does (type of arguments is packed dword):

 result[0] := xmm1[0] xor xmm1[2]
 result[1] := xmm1[1] xor xmm1[3]
 result[2] := xmm1[2] xor xmm2[0]
 result[3] := xmm1[3] xor xmm2[1]

1. Logical operation "xor" is hardcoded. Why we can't use "or", "and", "not and"? These operations are already present in ISA.
2. Indices to xmm1 and xmm2 are hardcoded too. Instruction pshufd accepts immediate argument (1 byte) to select permutation, why sha1msg1 couldn't be feed with 2 bytes allowing programmer to select any permutations of arguments?
3. Sources of operators are also hardcoded. Why not use another immediate (1 byte) to select sources, for example 00b = xmm1/xmm1, 01b = xmm1/xmm2, 10b = xmm2/xmm1, 11b = xmm2/xmm2.

Such generic instruction would be saved as generic_op xmm1, xmm2, imm_1, imm_2, imm_3 and execute following algorithm:

 for i := 0 to 3 do
  arg1_indice := imm_1[2*i:2*i + 1]
  arg2_indice := imm_2[2*i:2*i + 1]

  if imm_3[2*i] = 1 then
   arg1 := xmm1
  else
   arg1 := xmm2
  end if

  if imm_3[2*i + 1] = 1 then
   arg2 := xmm2
  else
   arg2 := xmm1
  end if

  result[i] := arg1[arg1_indice] op arg2[arg2_indice]
 end for

Then sha1msg1 is just a special case:

 generic_xor xmm1, xmm2, 0b11100100, 0b01001110, 0b01010000

Maybe this example is "too generic", too complex, and would be hard to express in hardware. I just wanted to show that we will get shine new instructions useful in few cases. Compilers can vectorize loops and make use of SSE, but SHA is used in drivers, OS and is encapsulated in libraries --- sha1msg1 and friends will never appear in ordinary programs.

itoa on steroids

Function itoa implemented with SSE instructions is about 3 times faster then scalar CPU version. Read more.

SSSE3 population count vs hardware

Peter Kankowski compared speed of SSE4.2 instructions crc32 and popcnt against software implementations. Hardware CRC32 is significantly faster, but population count is slightly slower than my SSSE3 popcount!

Speedup reversing table of bytes

With help of BSWAP instruction or SSE instructions (PSHUFD, PSHUFLW, PSHUFHW) or SSSE3 instruction (PSHUFB) reversing table can be faster. Speedup depends on three factors:

• table size: larger=faster
• table address: aligned=faster/much faster (15.5 speedup - possible! see chart)
• CPU type

Read full article

Transpose bits in byte using SIMD instructions

Method presented here allows to get any bit permutation, transposition is just one of possible operations. Lookup-based approach would be faster, but algorithm is worth to (re)show.

Algorithm outline for 8-byte vector (with SSE instruction it is possible to get 2 operations in parallel):

1. fill vector with given byte
   [11010001] =>
   [11010001|11010001|11010001|11010001|11010001|11010001|11010001|11010001]
   
2. leave one bit per byte
   [10000000|01000000|00000000|00010000|00000000|00000000|00000000|00000001]
   
3. perform desired transposition ("move" bits around)
   [00000001|000000010|00000000|00001000|00000000|00000000|00000000|10000000]
   
4. perform horizontal OR of all bytes
   [10001011]
   

Here is my old MMX code (polish text); below SSE/SSE5 implementation details.

Ad 1. Series of punpcklbw/punpcklwb/shufps or pshufb if CPU supports SSSE3.

# 1.1
movd      %eax, %xmm0
shufps    $0x00, %xmm0, %xmm0
punpcklbw %xmm0, %xmm0
punpcklwd %xmm0, %xmm0

# 1.2
pxor      %xmm1, %xmm1
movd       %eax, %xmm0
pshufb    %xmm1, %xmm0

Ad 2. Simple pand with mask packed_qword(0x8040201008040201).

pand  MASK1, %xmm0

Ad 3. If plain SSE instructions are supported this step require some work. First each bit is populated to fill whole byte (using pcmpeq - we get negated result), then mask bits on desired positons.

SSE5 has powerful instruction protb that can do perform rotation of each byte with independent amount - so in this case just one instruction is needed.

# SSE
pcmpeq  %xmm1, %xmm0
pandn   MASK2, %xmm0

# SSE5
protb    ROT, %xmm0, %xmm0

Ad 4. Since bits are placed on distinct positions, we can use instruction psadbw, that calculate horizontal sums of bytewide differences from two registers (separately for low and high registers half). If one register is full of zeros, we get sum of bytes from other register.

psadbw  %xmm1, %xmm0
movd    %xmm0, %eax

Depending on instruction set three (SSE) or two (SSE5) additional tables are needed.