[Discussion] the bit unpacking performance

[zombee0]

arrow-avx2.txt
arrow-none.txt

I like the job of #3000 #2353, but i can't reproduce your result,
there are two files, arrow_none.txt is the result of default compile configuration
while arrow_avx2.txt is the result of enable avx2 for arrow,
for result of uint16 and uint32, I found that arrow-avx2 performs better.
my test is done on Intel(R) Xeon(R) Platinum 8269CY CPU @ 2.50GHz
would you be willing to help confirm this? @yingsu00 @Yuhta

[Yuhta]

I just rerun the benchmark and arrow is only a little bit faster (< 13%) in arrow_unpack_fullrows_{1,2,3,4,8}_32 and not others.

[zombee0]

@Yuhta I see the default arrow lib's runtime_simd_level is NONE in velox, have you used the avx2 level for the test?
and from my more test, i see if i change the code, from

static inline void unpack9to15(
    const uint8_t bitWidth,
    const uint8_t* FOLLY_NONNULL& inputBuffer,
    uint64_t numValues,
    uint16_t* FOLLY_NONNULL& outputBuffer) {
  uint64_t pdepMask = kPdepMask16[bitWidth];

  uint8_t bytes2 = bitWidth / 2;
  uint8_t bytes1 = bitWidth - bytes2;

  uint8_t shift1 = bitWidth * 4;
  uint8_t shift2 = bytes1 * 8 - shift1;
  uint64_t valueMask = (1L << shift1) - 1;

  // Process bitWidth bytes (2 * 4 values) a time.
  auto writeEndOffset = outputBuffer + numValues;
  while (outputBuffer + 8 <= writeEndOffset) {
    // Process the first part of bytes1 bytes.
    uint64_t value1 = 0;
    std::memcpy(&value1, inputBuffer, bytes1);
    *reinterpret_cast<uint64_t*>(outputBuffer) =
        _pdep_u64(value1 & valueMask, pdepMask);

    // Process the second part of bytes2 bytes.
    uint64_t value2 = 0;
    std::memcpy(&value2, inputBuffer + bytes1, bytes2);
    *reinterpret_cast<uint64_t*>(outputBuffer + 4) =
        _pdep_u64((value1 >> shift1) | (value2 << shift2), pdepMask);

    inputBuffer += bitWidth;
    outputBuffer += 8;
  }

  numValues = writeEndOffset - outputBuffer;
  unpackNaive(
      inputBuffer,
      (bitWidth * numValues + 7) / 8,
      numValues,
      bitWidth,
      outputBuffer);
}

to

static inline void unpack9to15(const uint8_t* __restrict__ in, uint16_t* __restrict__ out, int64_t num_values,
                               int bit_width) {
    uint64_t pdepMask = kPdepMask16[bit_width];

    uint8_t shift1 = bit_width * 4;
    uint8_t shift2 = 64 - shift1;

    auto writeEndOffset = out + num_values;

    // Process bit_width bytes (8 values) a time.
    while (out + 8 <= writeEndOffset) {
        uint64_t value_0 = *(reinterpret_cast<const uint64_t*>(in));
        uint64_t value_1 = *(reinterpret_cast<const uint64_t*>(in + 8));

        *reinterpret_cast<uint64_t*>(out) = _pdep_u64(value_0, pdepMask);
        *reinterpret_cast<uint64_t*>(out + 4) = _pdep_u64((value_0 >> shift1) | (value_1 << shift2), pdepMask);

        in += bit_width;
        out += 8;
    }
}

The BMI implementation is more faster, I think maybe it's because of the compiler and the usage of the stack and register.
Would you like to have a check?

[Yuhta]

Yes maybe it's due to our build of arrow. I am not using an environment that can easily rebuild arrow though, so would you fix the runtime_simd_level in cmake build and apply any change on the file that can make it faster? The example change is not handling trailing data so cannot be used as it is.

[zombee0]

@Yuhta Yes, the example need extra logic to handle the trailing data, I will try to introduce a pr in velox to make it faster.

[mapleFU]

The BMI implementation is more faster, I think maybe it's because of the compiler and the usage of the stack and register.
Would you like to have a check?

Just curious how the code changed here? Would it better to have a godbolt link to see the asm changes and find out it?

[mapleFU]

Another thing I observed is the datainput size is important, the arrow algorithm might be good for some case that input is long enough. Otherwise the bmi2 would be faster