How to optimize histogram statistics with neon int

Question

I want to optimize histogram statistic code with neon intrinsics.But I didn't succeed.Here is the c code:

#define NUM (7*1024*1024)
uint8 src_data[NUM];
uint32 histogram_result[256] = {0};
for (int i = 0; i < NUM; i++)
{
    histogram_result[src_data[i]]++;
}

Historam statistic is more like serial processing.It's difficult to optimize with neon intrinsics.Does anyone know how to optimize?Thanks in advance.

Answer 1

You can't vectorise the stores directly, but you can pipeline them, and you can vectorise the address calculation on 32-bit platforms (and to a lesser extent on 64-bit platforms).

The first thing you'll want to do, which doesn't actually require NEON to benefit, is to unroll the histogram array so that you can have more data in flight at once:

#define NUM (7*1024*1024)
uint8 src_data[NUM];
uint32 histogram_result[256][4] = {{0}};
for (int i = 0; i < NUM; i += 4)
{
    uint32_t *p0 = &histogram_result[src_data[i + 0]][0];
    uint32_t *p1 = &histogram_result[src_data[i + 1]][1];
    uint32_t *p2 = &histogram_result[src_data[i + 2]][2];
    uint32_t *p3 = &histogram_result[src_data[i + 3]][3];
    uint32_t c0 = *p0;
    uint32_t c1 = *p1;
    uint32_t c2 = *p2;
    uint32_t c3 = *p3;
    *p0 = c0 + 1;
    *p1 = c1 + 1;
    *p2 = c2 + 1;
    *p3 = c3 + 1;
}

for (int i = 0; i < 256; i++)
{
    packed_result[i] = histogram_result[i][0]
                     + histogram_result[i][1]
                     + histogram_result[i][2]
                     + histogram_result[i][3];
}

Note that p0 to p3 can never point to the same address, so reordering their reads and writes is just fine.

From that you can vectorise the calculation of p0 to p3 with intrinsics, and you can vectorise the finalisation loop.

Test it as-is first (because I didn't!). Then you can experiment with structuring the array as result[4][256] instead of result[256][4], or using a smaller or larger unroll factor.

Applying some NEON intrinsics to this:

uint32 histogram_result[256 * 4] = {0};
static const uint16_t offsets[] = { 0x000, 0x001, 0x002, 0x003,
                                    0x000, 0x001, 0x002, 0x003 };
uint16x8_t voffs = vld1q_u16(offsets);
for (int i = 0; i < NUM; i += 8) {
    uint8x8_t p = vld1_u8(&src_data[i]);
    uint16x8_t p16 = vshll_n_u8(p, 16);
    p16 = vaddq_u16(p16, voffs);
    uint32_t c0 = histogram_result[vget_lane_u16(p16, 0)];
    uint32_t c1 = histogram_result[vget_lane_u16(p16, 1)];
    uint32_t c2 = histogram_result[vget_lane_u16(p16, 2)];
    uint32_t c3 = histogram_result[vget_lane_u16(p16, 3)];
    histogram_result[vget_lane_u16(p16, 0)] = c0 + 1;
    c0 = histogram_result[vget_lane_u16(p16, 4)];
    histogram_result[vget_lane_u16(p16, 1)] = c1 + 1;
    c1 = histogram_result[vget_lane_u16(p16, 5)];
    histogram_result[vget_lane_u16(p16, 2)] = c2 + 1;
    c2 = histogram_result[vget_lane_u16(p16, 6)];
    histogram_result[vget_lane_u16(p16, 3)] = c3 + 1;
    c3 = histogram_result[vget_lane_u16(p16, 7)];
    histogram_result[vget_lane_u16(p16, 4)] = c0 + 1;
    histogram_result[vget_lane_u16(p16, 5)] = c1 + 1;
    histogram_result[vget_lane_u16(p16, 6)] = c2 + 1;
    histogram_result[vget_lane_u16(p16, 7)] = c3 + 1;
}

With the histogram array unrolled x8 rather than x4 you might want to use eight scalar accumulators instead of four, but you have to remember that that implies eight count registers and eight address registers, which is more registers than 32-bit ARM has (since you can't use SP and PC).

Unfortunately, with address calculation in the hands of NEON intrinsics, I think the compiler can't safely reason on how it might be able to re-order reads and writes, so you have to reorder them explicitly and hope that you're doing it the best possible way.