Optimising execution speed - integer rotation

[ian.s]

An interesting optimisation problem in bit manipulation:

I have data in a packet of 16 bytes. However, the "actual" data is 8 lots of I16, encoded such that the first input byte is the MSB of all 8 data, followed by the next bit of all 8 data, down to the last of the 16 bytes which is the LSB of all the data. Essentially it's a bitwise transpose.

Visualisation, where the A[15] represents bit 15 (most significant) of data value A:

I have a simple code example which correctly translates the input to an array of H to A (add another reversal to get A..H if needed).

The problem is that this needs to run at a high speed. While this code is small, neat and readable, booleans are byte sized in desktop LabVIEW creating a bigger 2D intermediate array, and the num to bool function is LSB first creating need for reversal. Overall we have several array memory allocations. I know there are direct optimisations here like parallel for loops, but I feel like there might be a faster a way to do this with some integer bitwise functions (logical shifts etc).

Give it a go if you want, I'd be interested to find a faster algorithm.

[GerdW]

Hi ian,

---

@ian.s wrote:

An interesting optimisation problem in bit manipulation:

I know there are direct optimisations here like parallel for loops, but I feel like there might be a faster a way to do this with some integer bitwise functions (logical shifts etc).

---

Another approach:

(I forgot to configure the BoolArrayToNum correctly to get a U16 output.)

Unfortunately the Rotate-withCarry functions (in Data Manipulation palette) don't support array inputs. So you get stuck with LogicalShift/Rotate and need additional masking operations to handle the bits of a word spread across 16 bytes…

What do you mean by "high speed"?

How do you measure speed?

[GerdW]

Hi Bruno,

another approach, completely in blue:

[altenbach]

---

@ian.s wrote:

Give it a go if you want, I'd be interested to find a faster algorithm.

---

I would if you could attach your snippet as a down-converted LabVIEW 2020 vi. I assume it has typical input default data and works correctly. I don't want to start from scratch.

[Andrey_Dmitriev]

---

@altenbach wrote:

---

@ian.s wrote:

Give it a go if you want, I'd be interested to find a faster algorithm.

---

I would if you could attach your snippet as a down-converted LabVIEW 2020 vi. I assume it has typical input default data and works correctly. I don't want to start from scratch.

---

You're welcome:

[altenbach · Accepted solution]

Avoiding green is a good idea. Here's what I might do:

[altenbach]

---

@Andrey_Dmitriev wrote:
You're welcome:

---

Thanks. One problem with your comparison is that ot requires debugging to be turned on, else the contents of the outer loops gets constant folded.

If I remove the outer loops and substitute my above code, it is consistently about 5x faster than your version (5us vs. 25us). YMMV, of course. Note that my code could be optimized further. The nice thing is that it never goes above 16 bit datatypes.

[Andrey_Dmitriev]

---

@altenbach wrote:

Avoiding green is a good idea. Here's what I might do:

---

Well, we could avoid not only green, but LabVIEW completely by wrapping this code in a DLL. However, for small amounts of data, the overhead of calling the DLL would also be relatively large. In any case, here still a speedup by C code of approximately by factor 4...5 (compiled with CVI 2026):

Code behind:

void decode_scalar_reversed(
    const uint8_t input[static 16],
    int16_t output[static 8])
{
    for (unsigned output_index = 0; output_index < 8; ++output_index) {
        uint16_t value = 0;

        for (unsigned bitplane = 0; bitplane < 16; ++bitplane) {
            const uint16_t bit =
                (uint16_t)((input[bitplane] >> output_index) & 1u);

            value |= (uint16_t)(bit << (15u - bitplane));
        }

        output[output_index] = (int16_t)value;
    }
}

However, I’m not sure whether ian.s is familiar with this approach or not.

[Andrey_Dmitriev]

---

@altenbach wrote:

---

@Andrey_Dmitriev wrote:
You're welcome:

---

Thanks. One problem with your comparison is that ot requires debugging to be turned on, else the contents of the outer loops gets constant folded.

If I remove the outer loops and substitute my above code, it is consistently about 5x faster than your version (5us vs. 25us). YMMV, of course. Note that my code could be optimized further. The nice thing is that it never goes above 16 bit datatypes.

---

Yes, it was just a quick-and-dirty reimplementation of the code shown in the screenshot. I mainly wanted to experiment with SIMD and the Criterion benchmarking crate, but in this case vectorization offered no significant performance advantage. But the AVX2 implementation looks quite elegant because it requires only a single loop with eight iterations and whole 16x16 data fits into single 256-bit register:

pub unsafe fn decode_avx2_reversed(input: &[u8; 16]) -> [i16; 8] {
    let input128 = unsafe {
        _mm_loadu_si128(input.as_ptr().cast::<__m128i>())
    };

    let input256 = _mm256_broadcastsi128_si256(input128);
    let zero = _mm256_setzero_si256();

    let mut out = [0i16; 8];

    for output_index in 0..8 {
        // Generate output words directly in the desired order:
        // output 0 uses input bit 0
        // output 7 uses input bit 7
        let bit_mask = (1u8 << output_index) as i8;
        let mask = _mm256_set1_epi8(bit_mask);

        let selected = _mm256_and_si256(input256, mask);
        let selected_is_zero = _mm256_cmpeq_epi8(selected, zero);

        let zero_mask = _mm256_movemask_epi8(selected_is_zero) as u32;

        // Both 128-bit halves contain the same input, so only the
        // lower 16 bits of the movemask are needed.
        let collected = (!zero_mask & 0xffff) as u16;

        // movemask maps input[0] to bit 0, but input[0] represents
        // output bit 15. Reverse the bitplane positions.
        out[output_index] = collected.reverse_bits() as i16;
    }

    out
}

[altenbach]

Well, I stopped using text based code decades ago, 😮

If I place a chart at the two times (debugging disabled now) and do a continuous run, here is a comparison of our two LabVIEW codes....

Variation is quite large for each. Mine often dips into the ns. (I assume Gerd's code is similar to yours. Not tested).