Module small 

A list that stays on the stack until it does not fit.

Every multi key command builds a handful of little vectors before it does any work: the slot each key resolved to, the body each slot points at, the operands sorted by size, a cursor per operand. Each of those is k long, where k is the number of keys the command was given, and k is two or three almost every time. A SINTER of two eight member sets does about two hundred nanoseconds of real work and was paying five mallocs and five frees on top of it.

Small is those vectors without the allocator. Up to N elements it is an array in the caller’s frame, and past that it is a Vec and behaves exactly as it did before, so a SUNIONSTORE over fifty keys is not made worse to make the common one better.

Why T: Copy and why there is no unsafe here

An inline buffer normally needs MaybeUninit, because [T; N] has to be filled with something before the first element is written into it. That means unsafe, and unsafe in a container means getting Drop and panic safety right for a saving measured in nanoseconds.

There is no need for any of it here. Everything this holds is Copy: a slot number, a shared reference to a body, an index, a cursor over a sorted array. So the buffer is filled with a copy of the first element and the elements after len are that first element again, harmlessly. Nothing is ever read out of them, nothing is ever dropped, and the whole type is ordinary safe Rust.

Small::Empty is a variant of its own for the same reason: an inline buffer needs a value to fill itself with, and a list that never saw a T has not got one.

What it is worth

yo-kv’s setops_small bench, nanoseconds per operation over sets of eight and sixty four members, before and after the three vectors inside yo_kv::setops became this:

                    before    after
  inter ints k=2     69.50    44.23
  inter ints k=3     88.34    58.28
  union ints k=2     80.39    69.45
  union ints k=3    122.08   114.71
  inter text k=2    160.58   154.84
  union text k=2    370.17   368.54

The integer intersection is the row that shows it, at about 1.5 times, because a merge over small sorted arrays is a few dozen nanoseconds of real work and three allocator round trips were most of what it was doing. The text rows barely move, because those plans build a hash table sized by the members and that is what they spend their time on.

The bench calls setops directly, so it does not see the two more vectors Keyspace::set_slots and Keyspace::bodies_of used to build per command. A whole SINTER over three small sets went from eleven allocations to none.

Enums

Small

A list of up to N elements on the stack, spilling to the heap past that.