TuQueQue: an MPSC lock-free queue

Showcase
1

Tuqueque

This module provides TuQueQue[1], a lock-free, fallible MPSC queue of fixed size. Lock-free means that writes and reads both proceed without the use of a mutex, or any other lock of indefinite duration. Fallible means that enqueues and dequeues can both fail. MPSC is multiple producer, single consumer: many writers and only one reader. Fixed size is why writes can fail. Writes are why dequeues can fail.

The mechanism is simple and efficient: swap buffers. At any given instant, one buffer is the write queue (the enqueue), the other is the read queue (the dequeue). Writers contend to reserve queue space, using a single atomic word, write to their reservation, then commit the write length. This allows them to leapfrog each other ā€” until the queue is full.

At any instant, the reader (singular!) can dequeue, by swapping which queue is which. Writes may not be committed, in which case the reader must wait until they are. This can time out, but in the absence of enqueue-side use bugs, the dequeue will eventualy succeed, and no further writes will be reserved to that side after a swap.

Once it succeeds, the reader has a slice of whatever the queue carries. It can do reader stuff with the slice, and (after reading, please!) resize the dequeue half of the tuqueque, if desired. It is not a correctness issue for the halves to be unbalanced, temporarily or otherwise.

Tuned appropriately, this is about as good as it gets. All common memory is handled atomically, and cache-isolated to eliminate false sharing.

The most important invariant is that there must only be one reader. To facilitate this, writes are expected to proceed using a WriteHandle, a type-erased pointer to the queue exposing only the write-appropriate functions (and a bit of bookkeeping, itā€™s two words wide).

The library maintains a read lock and will panic in safe modes if two reader-side functions ever overlap. Seriously, donā€™t do it. There are more ways to get the queue into an inconsistent state that way than the assertions can detect and surface.

This library has 100% line coverage, but is hot off the presses and yet to be used in anger. Caveat hacker.

Inspiration

TuQueQue is a port of a Rust library, swap-buffer-queue, many thanks to @wyfo! It makes some different choices, in a way which will be comprehensible to anyone familiar with both languages: the Zig version puts somewhat more responsibility for correct use in the hands of the user, and is able to pick up some small efficiencies in return. In principle, at least: in addition to NO WARRANTY, tuqueque comes with no benchmarks.

  1. Like the cognitive fallacy. Pronounced tu-kyu-kway, if
    possible. You can also say ĀæTu que que?, but you had better know who
    youā€™re saying it to. ā†©ļøŽ

7 Likes
2

Iā€™ve been thinking about how best to implement logging in real time environments. Typical logging interacts with IO so it could introduce large delays in high priority threads. So I would need to queue logs and flush them in a low priority thread.
Do you think this mpsc would be appropriate here?

1 Like
3

Quite possibly, yes. I would think in terms of the logger having an internal buffer which it writes to (the new Writers just do that), which is comfortably larger than either half of the queue.

Logging is naturally ā€˜burstyā€™, and the nature of the data structure is that half of the available space is exposed at any given point. So you want to be clearing queues fast, because a half can only be given back all at once.

That said, I do think a pattern where the logger waits for a null return and then flushes what it has to store could work well. The README covers some of this ground, in the end thereā€™s no substitute for experiment. Iā€™d say it would be a worthwhile experiment to run.

1 Like
4 
Conditions 1. and 2. may, at your option, be fulfilled by the inclusion
of the copyright line, in full, as well as a hyperlink to a copy of the
repository, provided said link is the method in which this software has
been incorporated into the derived work, as, for example, when resolved
by a package manager to fetch and incorporate the work.

Is this your own invention? I havenā€™t heard about the ā€œBSD 3 and Ā½ Clause Licenseā€ before, and canā€™t find any OSI/SPDX references to it, nor other uses. Uncommon licenses/variations introduce uncertainty so Iā€™m curious what problem the half-clause is attempting to solve that established licenses do not. Hyperlinks frequently break, licenses are very long term, so this already feels shaky. For example, I have more than once encountered Zig projects that reference packages in GH/Codeberg repos that no longer exist (if a mirror or fork elsewhere exist, is that still valid?)

5

Yes. Yay someone noticed :slight_smile:

Itā€™s not clear, never has been, that simply naming a BSD style project in a manifest, and then having it incorporated into the work, fulfills the clause requiring that the license be incorporated. This says ā€œyes, thatā€™s fine, but also include the copyright statement itselfā€:

    .dependencies = .{
         // Ā© 2025 Sam Atman <email scrubbed>
        .tuqueque = .{ 
            .url = "https://github.com/mnemnion/tuqueque/archive/refs/tags/v0.0.1.tar.gz",
             // etc
            },
         },
    },

Which I think is a reasonable way to go about things, personally. That may seem like extra work, from my perspective, itā€™s less work than the thing which really should happen but frequently doesnā€™t, which is fully incorporating a copy of the license in any dependencies into the repo using them.

Not a problem here, because it only applies if:

said link is the method in which this software has
been incorporated into the derived work, as, for example, when resolved by a package manager to fetch and incorporate the work

So if youā€™re including it in some other way, source inclusion canonically, great, just include the license as per usual.

To put the whole thing another way: the clause is ā€œat your optionā€, so it must be strictly more free than BSD three clause, because the other clauses impose identical obligations in subtly different language.

Thatā€™s not actually the reason I use a lightly customized license though. If you stare it at long enough, squint perhaps, that reason will become clear.

6

Perhaps, but I have to deal with legal departments occasionally and including anything unusual slows things down (or worse, you get a no simply because itā€™s not a commonly deployed permissive license)

That said, appreciate you sharing the reasoning!

7

Iā€™m certainly willing to sell an additional license to anything Iā€™ve written at the right price.

It isnā€™t explicitly intended as bigcorp-repellant, I wouldnā€™t use a permissive license if that prospect bothered me. But I did ask myself, ā€œdoes it bother me that this might cause problems for unusually paranoid and uptight businesses?ā€ and the answer is no. No it does not. I stand ready to sell indulgences should that be necessary.

The reputation ā€œweird licensesā€ have is well-earned, broadly speaking, but the problems they have are generally obvious ones. The plain language of the license I use is clearly compatible with the Big Three definitions (OSF, Debian, FSF), and if it gets sufficient use that someone wants to shepherd it through the certification process, I have no doubt as to the outcome.

If there were another license with perfect full justification, well, I might use that. Alas the burden of creation fell upon my shoulders.

1 Like
8

Yeah, I feel that sentiment. Most clients Iā€™ve worked with are relatively small and it makes sense for them to reciprocate by upstreaming most (but not necessarily all) changes, since that makes everything easier when itā€™s time to upgrade a dependency. Pragmatic tit for tat. A new license/variation tends to be too much friction for them to even get in that position. Your license getting usage, a legal soundness check, and certification should help it evade the ban hammer most places. Good luck!

1 Like