GitHub - Fusion/slotmachine: Find a free slot in a slice, quick, in Go

Slot Machine

What is this?

I wrote this small library for a very specific use case.

I needed:

• A way to get a free network port to bind an application to, quickly
• Support for coroutines
• Allowing near-instant booking, release and slot-finding

Limitations

Many. The worst one? Expressing the type being stored in a slot. It is awkward, and not compile-time safe. Therefore, using this librry beyond its "slot available?" scope could prove a bit hazardous.

Short explanation: this is due to Generics not (yet?) supporting declaring types in method signatures.

Usage

Import:

import (
    "github.com/fusion/slotmachine"
)

Create your slice, and pass it to the Slot Machine.

The second parameter is used to represent an "empty" value in the slice. It does not impact the algorithm's behavior.

The third parameter is how wide a bucket should be. This has a direct impact on the number of buckets and layers. You can play with this setting to achieve maximum performance, based on your slice size.

workSlice := make([]uint16, 32768)
sm, err := slotmachine.New[uint16, uint16](
    slotmachine.ChannelConcurrency,
    &workSlice,
    0,
    uint8(bucketSize),
    nil)

For performance reasons, the library insists on workSlice's size, as well as bucketSize's value, being powers of 2. It also insists that a bucket fit in the slot index type, so bucketSize may not exceed the bit width of the first type parameter.

You may limit your usable slot range using boundaries:

workSlice := make([]uint16, 65536)
sm, err := slotmachine.New[uint16, uint16](
    slotmachine.ChannelConcurrency,
    &workSlice,
    0,
    uint8(bucketSize),
    &slotmachine.Boundaries{5000, 50000})

Boundaries must be non-negative, ordered, inside the slice, and representable by the slot index type; New rejects them otherwise. Slots outside the boundaries are booked at construction time, so allocation never has to consider them.

Directly booking and setting a slot:

available, err := sm.Set(uint16(i), 1)

Note: you can check that this call was successful, being within pre-defined boundaries, etc., if it returns an error.

Set is idempotent: setting a slot that is already booked overwrites its value and reports no error, so it cannot be used to detect that somebody else already holds the slot. Use BookAndSet when you need a slot nobody has claimed.

Releasing a slot:

available, err := sm.Unset(uint16(i))

Releasing a slot that is already free is a no-op.

Finding and booking a slot:

added, available, err := sm.BookAndSet(2)

This call will return an error about the slice being full if you have used all the slots within your defined boundaries.

Booking several slots at once:

added, available, err := sm.BookAndSetBatch(5, 2)

The batch is all-or-nothing: if it cannot be filled completely, nothing is booked and the error is returned. The slots handed back are the lowest free ones, so they are only consecutive when the range they came from was unfragmented.

When you are done with a machine, close it:

Close is idempotent. It is a no-op for NoConcurrency and SyncConcurrency, but ChannelConcurrency runs a transactor goroutine that lives until you close it -- skip the call and both the goroutine and the slice it references leak. Operations attempted after Close return slotmachine.ErrClosed.

Close is also synchronous: it does not return until the transactor has actually stopped. That matters if you intend to read your slice directly afterwards, since a transaction still in flight would otherwise be writing to it while you read.

In the previous examples, I have used ChannelConcurrency as my concurrency model of choice.

In some instances, e.g. when creating a massive number of goroutines, mutexes can go in "starvation mode" due to the active goroutines not holding the mutex.

In other cases, you may need the flexibility of using a simple mutex, and not need channels.

Finally, you may also not need any concurrency management at all.

For these reasons, you can ask the library to follow one of three concurrency models:

• NoConcurrency
• SyncConcurrency
• ChannelConcurrency

Try different concurrency models and pick the one that works best for your use case!

To get a sense of the performance, both processing and storage-wise, that you are getting, based on your settings:

This will display information such as number of layers, number of buckets per layer, etc.

Performance

The benchmarks live in perf_test.go:

go test -run XXX -bench . -count=10

I recently did a deep dive into some of the shortcomings I had made a note to "some day" address, and, turns out, this library could definitely be tuned quite a lot beyond its previous performance levels.

Everything below compares commit 0db7aba which was the original implementation and already served me well, against the current code, on an Apple M4 Max with go1.26.4 and GOMAXPROCS=16, run ten times each and summarised with benchstat. Your absolute numbers will be different. The ratios are the part worth looking at.

Finding and booking a slot

One operation here is a BookAndSet plus the Unset that gives the slot back, on a slice of 1Mi slots with a bucket size of 8.

"Clustered" means the low slots are the taken ones. That is what you actually end up with in practice, because BookAndSet always hands back the lowest free slot. "Scattered" means the same number of slots are taken, but at random indices.

The old code walked every layer, but at each one it started counting buckets from zero again instead of from the bucket its parent had just picked. So the last layer it looked at was the widest one, and it scanned that from the beginning. The new code descends from the root, picking a child at each layer, which is what the layers were built for in the first place.

That explains the gap between the two halves of the table. A leaf bucket is only skipped when all 8 of its bits are set, so with holes scattered around, the old scan tripped over a usable bucket almost immediately and looked fine. Pile the taken slots up at the bottom, which is what this library does to itself, and the scan has to cross all of them.

Filling a machine up

Same thing from the other end: how long it takes to book every slot in an empty 64Ki machine, one BookAndSet at a time.

The old cost grows with the square of the slice size, so this gets worse the bigger you go. I kept it at 64Ki because 1Mi took long enough to be annoying.

Releasing and re-booking in place

No searching involved here, just the bookkeeping that walks back up the layers.

Two things were going on. Unset cleared its parents' bits all the way to the root on every single call, even though a parent only ever has a bit set for a child that is full -- so once you reach a parent that was not full, there is nothing above it to clear. It now stops there, which is where the second row comes from.

The rest is arithmetic. Working out which parent bit to touch used to divide the slot index by the layer width and then divide again to get the offset. The parent bucket and its bit offset are just the child bucket number divided by the bucket size and the remainder, so that is what it does now.

Batches

BookAndSetBatch of 64 slots, then releasing them, on a 1Mi machine with no concurrency management.

It now checks whether there are enough free slots before it starts, rather than booking its way into a wall and unwinding.

Concurrency models

One goroutine per core, all booking and releasing against the same 1Mi machine.

Worth noticing that the mutex is the quicker of the two here by a good margin. The channel model will still win when you run more goroutines than cores, causing mutex starvation, so this is an important design choice.

In addition, the channel model was doing too much blocking, with every send/receive watching a shutdown channel. This added a non-negligible potential latency cost. The updated implementation takes a read lock for the length of a transaction, while Close takes a write lock.

Building the machine

Small trade-off: building the machine takes somewhat longer now, as it is a one-time operation.

New used to hand back a set of empty layers and leave it at that, which is cheap because it is not doing the work. Boundaries were checked one call at a time, on the way in.

Slots outside your boundaries are now booked while the machine is being built, and that fullness is carried up through the layers. After that the boundaries are just part of the shape of the tree and nothing on the hot path has to think about them.

So, yes, you may like the old way better if you are never going to perform more than 50K bookings. But, in this case, what do you need this library for?

Across all of the benchmarks the geometric mean goes from 2.372 µs to 670 ns.

FAQ

Q: How does this work?

A: The library maintains a reference to your "managed" slice.

It builds several representational layers, increasingly smaller, to create a "path" to the slice's slots.

As each layer's buckets fill up, their parent layers are updated, and fill up as well. This allows us to find an empty slot very fast by avoiding "traffic jams."

This library eschews the use of trees to preserve maximum locality, and thus memory access performance.

Q: Is this memory efficient?

A: Somewhat. It could always improve, though.

The only guarantee is that your storage size will be no worse than going from O(N) to O(Nlogn)