Module bits 

Bit level kernels: counting, searching, combining and packed fields.

Redis calls a string used this way a bitmap, and it is not a separate type: SETBIT, BITCOUNT, BITOP and BITFIELD all work on the ordinary string a SET would have left behind, which is why this file is kernels over byte slices and nothing else. The keyspace side, which is where a key turns into bytes and where growing a value is decided, is in bitmaps.

Which end a bit is

Bit zero is the top bit of byte zero. That is the convention every one of these commands uses and it is the opposite of the one a language’s shift operators suggest, so it is worth being blunt about it: bit i is

bytes[i / 8] & (0x80 >> (i % 8))

It falls out of wanting BITPOS over a bitmap of user ids to answer in the order the ids were assigned, and it is why a u64 loaded out of the middle of a bitmap has to be read big endian for u64::leading_zeros to mean the distance to the next set bit.

Counting

count is four u64 accumulators fed by count_ones. That is the same shape as Redis’s redisPopcount, which unrolls by four for the same reason: popcnt has a three cycle latency and one per cycle throughput on every x86 since Nehalem, so a loop with one accumulator is latency bound at a third of the rate and four independent chains fill the pipe. On aarch64 there is no scalar popcount at all and LLVM turns the same loop into cnt over a vector register plus a widening add tree, which is why this is written as an ordinary loop rather than as intrinsics: the ordinary loop is what both backends already do well, and an intrinsic version would be two more code paths to keep right for no measured gain.

Combining

combine does BITOP, including the four operations Redis 8.2 added: DIFF, DIFF1, ANDOR and ONE. It works a block at a time over a fixed stack buffer rather than allocating one accumulator per source, so a BITOP over eight sources touches the same two kibibytes of stack whatever the bitmaps weigh, and each block of each source is read once while it is warm. The alternative, folding whole bitmaps one source at a time, walks the destination once per source and that is where a BITOP over big bitmaps spends its time.

Structs

Field

One BITFIELD field type: u8, i37 and so on.

Enums

Op

The operations BITOP takes.

Overflow

What to do about a value that will not fit.

Functions

adding

The value an INCRBY of by should write, or None for FAIL.

combine

Run op over srcs, filling out.

count

How many bits are set.

count_range

How many bits are set in the half open bit range from..to.

find

The first bit equal to set in the half open bit range from..to.

get

The field of f bits at bit at, reading past the end as zeros.

set

Write val into the field of f bits at bit at.

setting

The value a SET of val should write, or None for FAIL.

width

How long the result of op over srcs will be.