Loop counting top bits set badly vectorized on X86

[nikic]

Bugzilla Link	46053
Version	trunk
OS	Linux
CC	@Dushistov,@efriedma-quic,@fhahn,@hsivonen,@RKSimon,@rotateright

Extended Description

Originally reported at: rust-lang/rust#72355.

A loop counting the number of bytes with the top bit set:

#include <stddef.h>
#include <stdint.h>

uint64_t count_non_ascii(unsigned *buffer, size_t len) {
    uint64_t count = 0;
    for (size_t i = 0; i < len; i++) {
        count += buffer[i] >= 0x80;
    }
    return count;
}

Gets vectorized to some complicated code: https://c.godbolt.org/z/jTU3rX

While this could be just movmsk + popcnt.

[efriedma-quic]

popcnt can't possibly be the fastest way to vectorize without -mpopcnt. With it, maybe slightly faster.

The reason the generated code is completely ridiculous, though, is related to the width of the reduction variable. The following generates a sane-looking result:

uint64_t count_non_ascii(unsigned char *buffer, size_t len) {
    unsigned char count = 0;
    for (size_t i = 0; i < len; i++) {
        count += buffer[i] >= 0x80;
    }
    return count;
}

[hsivonen]

popcnt can't possibly be the fastest way to vectorize without -mpopcnt. With it, maybe slightly faster.

Movemask and popcnt were faster than the present autovectorization even with emulated popcnt. With the real popcnt instruction, the result was even faster.

I can't speak to what the fastest possible solution would be.

[RKSimon]

From a cost model point of view, x86 already has accurate numbers for CTPOP with/without hardware support. What we don't have is costs for a bitcast from the compare result to iX to feed the popcount.

If the LV generates that then the backend should just work (I think).

[efriedma-quic]

Movemask and popcnt were faster than the present autovectorization even with
emulated popcnt.

Did you try comparing against autovectorization for the code from comment 1? (It's equivalent to the code from comment 0 if len<256.)

[hsivonen]

Did you try comparing against autovectorization for the code from comment 1?
(It's equivalent to the code from comment 0 if len<256.)

Changing the accumulator to an 8-bit unsigned number and letting it overflow (since my test harness tries input whose length is greater) is indeed the fastest version both with the default target CPU capabilities and with newer target CPU capabilities.

(With the default target the 8-bit accumulator is similar to the popcnt version compiled for the Haswell target, but when the 8-bit accumulator version is compiled for the Haswell target, the 8-bit accumulator becomes even faster.)

[hsivonen]

The Haswell improvement for the overflowing 8-bit counter is due to unlocking the ymm registers:

Default target CPU:
https://rust.godbolt.org/z/ErjsJa

Haswell target CPU:
https://rust.godbolt.org/z/LSSaFt

[hsivonen]

On Intel(R) Xeon(R) CPU E5-2637 v4 @ 3.50GHz

Default target CPU:

test bench_epi ... bench: 5,192 ns/iter (+/- 525) = 9329 MB/s
test bench_epi_chunks ... bench: 5,129 ns/iter (+/- 405) = 9444 MB/s
test bench_normal ... bench: 26,640 ns/iter (+/- 2,345) = 1818 MB/s
test bench_overflow ... bench: 1,249 ns/iter (+/- 40) = 38783 MB/s

Haswell target CPU

test bench_epi ... bench: 1,291 ns/iter (+/- 146) = 37521 MB/s
test bench_epi_chunks ... bench: 1,330 ns/iter (+/- 37) = 36421 MB/s
test bench_normal ... bench: 5,647 ns/iter (+/- 403) = 8578 MB/s
test bench_overflow ... bench: 897 ns/iter (+/- 35) = 54002 MB/s