The x86 / x86-64 instruction sets have many instructions for comparing IEEE754 floating-point numbers. Casey Muratori recently asked about two of them:

It would be great if someone from Intel would share the rationale behind the immediate bit pattern of the AVX CMP instructions (eg., vcmppd, vcmpps). I've stared at it many times and it just seems "pure banacakes", as Jeff would say.

I can attempt to explain the immediate bit pattern of vcmpps and vcmppd, but it makes most sense to start somewhere else: the comiss and ucomiss instructions. These instructions compare two floats (say A and B) and then set flags based on the result. IEE754 floats have the convenient property that exactly one of these four statements is true:

1. A > B
2. A == B
3. A < B
4. A is unordered with respect to B (i.e. at least one of them is a NaN)

That fourth case is a bit of a mouthful, so I'll write it as A unord B from here on. When comparing A and B, the comiss and ucomiss instructions determine which case applies, and set the CF and ZF flags accordingly:

(These instructions also set PF, but always as PF = CF & ZF, so for our purposes it suffices to look at just CF and ZF.)

The difference between comiss and ucomiss is how "loud" they are with respect to quiet NaNs, where comiss is "signalling" and ucomiss is "quiet". Most people consider loudness to be an obscure corner of IEEE754, but it is a corner which most pieces of hardware implement, and it amounts to running this flow chart before the comparison instruction:

                                       ↓
                               ╔════════════════╗
                           Yes ║ Is any operand ║ No
            ┌───────────────── ║    an sNaN?    ║ ───┐
            │                  ╚════════════════╝    │
            │                                        ↓
            │                             ╔════════════════╗
            │                         Yes ║ Is any operand ║ No
            │                       ┌──── ║    a qNaN?     ║ ───┐
            │                       │     ╚════════════════╝    │
            │                       ↓                           │
            │                ╔══════════════════╗               │
            │     Signalling ║ What loudness is ║ Quiet         │
            │   ┌─────────── ║ the instruction? ║ ──────┐       │
            │   │            ╚══════════════════╝       │       │
            ↓   ↓                                       │       │
          ╔══════════════╗      ╔══════════════╗        │       │
      Yes ║ Is mxcsr.IM  ║ No   ║ Set mxcsr.IE ║        │       │
    ┌──── ║ set to zero? ║ ───→ ║    to one    ║ ─┐     │       │
    │     ╚══════════════╝      ╚══════════════╝  │     │       │
    ↓                                             ↓     ↓       ↓
╔═══════════╗                               ╔══════════════════════╗
║ Raise an  ║                               ║     Execute the      ║
║ exception ║                               ║ instruction normally ║
╚═══════════╝                               ╚══════════════════════╝

That's enough context about comiss and ucomiss, so onward to vcmpps and vcmppd. These instructions operate on multiple SIMD lanes, and hence they can't set flags. Instead they compute a one-bit result per SIMD lane (and then replicate that bit to all 32 or 64 positions within the lane), with a five-bit field within the instruction configuring how to reach that result. If b0 through b4 represent those five bits, a de-novo design might be something like:

0. The loudness is "signalling" if b0 is set, and "quiet" otherwise.
1. If A > B, the one-bit result is b1.
2. If A == B, the one-bit result is b2.
3. If A < B, the one-bit result is b3.
4. If A unord B, the one-bit result is b4.

The actual encoding of vcmpps and vcmppd is ... nothing like that. The reality is:

0. The loudness is "signalling" if b4 ^ b1 ^ b0, and "quiet" otherwise.
1. If A > B, the one-bit result is b2.
2. If A == B, the one-bit result is b2 ^ !b0.
3. If A < B, the one-bit result is b2 ^ b1 ^ b0.
4. If A unord B, the one-bit result is b3 ^ b2 ^ (b1 & b0).

If it isn't immediately obvious that this encoding scheme covers every possibility exactly once, the entire five bits can be determined by:

1. Decide what result you want when A > B, set b2 to this.
2. Set b0 such that b2 ^ !b0 is the result you want when A == B.
3. Set b1 such that b2 ^ b1 ^ b0 is the result you want when A < B.
4. Set b3 such that b3 ^ b2 ^ (b1 & b0) is the result you want when A unord B.
5. Set b4 such that b4 ^ b1 ^ b0 is the desired loudness.

In practice, nobody follows that process to determine the five bits. Instead, they just look up the combination they want from the table of cases:

If this table and the exposition thus far looks like a convoluted mess (a.k.a. "pure banacakes"), it implies that we might be looking at the world from the wrong place. As with many x86 things, part of the perspective is history. In this case, the applicable question is: what if we didn't have five bits to play with, but instead only had two bits? Two bits allows four different cases, so the question can be re-framed as deciding which four cases you consider the most important. You can debate this, but the x86 designers made their choice, and it is the first four rows of the table:

It might look like A > B can't be computed using one of these four, but > and < are symmetric: A > B is the same as B < A, and < can be computed (albeit I'm ignoring that x86 often re-uses the left operand as the result register, and often allows the right operand to come from memory, both of which defeat symmetry).

Orthogonality is a desirable property in instruction sets, and in the context of comparisons it means that whenever you can test for X you should also be able to test for not X. This justifies adding a third bit (b2) which inverts all the results, thus giving us the first eight rows:

This is where pre-AVX CPUs stopped, and for compatibility, cmpps (NB: no v) still stops here on post-AVX CPUs (I did say history was relevant). AVX came along and expanded three bits to five, but obviously the old and new behaviours should coincide when the new bits (b3 and b4) are both zero, as that's how you make the migration as easy as possible for software (i.e. for compilers, disassemblers, etc).

How do you plug in those two extra bits to get from these first eight cases to all 32 cases being covered? Perhaps you wire up one of them (b3) to flip the outcome of A unord B (and nothing else), and wire up the other (b4) to flip between Quiet ↔ Signalling. Doing so gets you exactly the full 32-entry table from earlier (ta da!).

That feels like a reasonable explanation of how vcmpps and vcmppd got to where they are, but how might a CPU actually implement them? Determining loudness from b4 ^ b1 ^ b0 feels reasonable enough, so the interesting question is how to compute the one-bit result. Given the presence of comiss and ucomiss, there could plausibly be a circuit which takes two floats and computes CF and ZF. In the case of comiss and ucomiss, those CF and ZF bits get wired into the flags register, whereas in the case of vcmpps there could be a circuit which takes those two bits along with b3 through b0 and computes the one-bit result. On a modern FPGA, this trivially maps to a single 6:1 LUT. On an ASIC, one cheap trick would be a 4:1 mux whose two control inputs are ZF and CF and four data inputs are b2, b2 ^ !b0, b2 ^ b1 ^ b0, and b3 ^ b2 ^ (b1 & b0). An alternative would be to rotate the mux to make b0 and b1 be the control inputs. If doing that, and ignoring b2 and b3 for a minute, this would require that the four data inputs be:

An equivalent formulation is:

This equivalent formulation feels less intuitive, but the common (ZF ^ CF) term is neat. It also makes it easy to add in b3: in all four cases, the (ZF ^ CF) term just needs to be replaced by ((ZF ^ CF) | b3). Adding in b2 is also easy: conditionally negate the whole lot by having a ^ with b2 after the mux. Finally, if a mux feels like cheating, it can be expanded out to two-input logic gates to give:

tmp1 = (CF & (b0 | b1)) | (ZF & !b0)
tmp2 = ((ZF ^ CF) | b3) ^ (b0 & b1)
result = (tmp1 & tmp2) ^ b2

I've seen lots of chatter about Fil-C recently, which pitches itself as a memory safe implementation of C/C++. You can read the gritty details of how this is achieved, but for people coming across it for the first time, I think there is value in showing a simplified version, as once you've understood the simplified version it becomes a smaller mental step to then understand the production-quality version.

The real Fil-C has a compiler pass which rewrites LLVM IR, whereas the simplified model is an automated rewrite of C/C++ source code: unsafe code is transformed into safe code. The first rewrite is that within every function, every local variable of pointer type gains an accompanying local variable of AllocationRecord* type, for example:

void f() {
  T1* p1;
  T2* p2;
  uint64_t x;
  ...

void f() {
  T1* p1; AllocationRecord* p1ar = NULL;
  T2* p2; AllocationRecord* p2ar = NULL;
  uint64_t x;
  ...

Where AllocationRecord is something like:

struct AllocationRecord {
  char* visible_bytes;
  char* invisible_bytes;
  size_t length;
};

Trivial operations on local variables of pointer type are rewritten to also move around the AllocationRecord*:

When pointers are passed-to or returned-from functions, the code is rewritten to include the AllocationRecord* as well as the original pointer. Calls to particular standard library functions are additionally rewritten to call Fil-C versions of those functions. Putting this together, we get:

  p1 = malloc(x);
  ...
  free(p1);

  {p1, p1ar} = filc_malloc(x);
  ...
  filc_free(p1, p1ar);

The (simplified) implementation of filc_malloc actually performs three distinct allocations rather than just the requested one:

void* filc_malloc(size_t length) {
  AllocationRecord* ar = malloc(sizeof(AllocationRecord));
  ar->visible_bytes = malloc(length);
  ar->invisible_bytes = calloc(length, 1);
  ar->length = length;
  return {ar->visible_bytes, ar};
}

When a pointer variable is dereferenced, the accompanying AllocationRecord* is used to perform bounds checks:

  x = *p1;
  ...
  *p2 = x;

  assert(p1ar != NULL);
  uint64_t i = (char*)p1 - p1ar->visible_bytes;
  assert(i < p1ar->length);
  assert((p1ar->length - i) >= sizeof(*p1));
  x = *p1;
  ...
  assert(p2ar != NULL);
  uint64_t i = (char*)p2 - p2ar->visible_bytes;
  assert(i < p2ar->length);
  assert((p2ar->length - i) >= sizeof(*p2));
  *p2 = x;

Things become more interesting when the value being stored or loaded is itself a pointer. As already seen, local variables of pointer type have their accompanying AllocationRecord* variable inserted by the compiler, which the compiler can do because it has full control and visibility of all local variables. Once pointers exist in the heap rather than just in local variables, things become harder, but this is where invisible_bytes comes in: if there is a pointer at visible_bytes + i, then its accompanying AllocationRecord* is at invisible_bytes + i. In other words, invisible_bytes is an array with element type AllocationRecord*. To ensure sane access to this array, i must be a multiple of sizeof(AllocationRecord*). The extra logic for this is highlighted in green:

  p2 = *p1;
  ...
  *p1 = p2;

  assert(p1ar != NULL);
  uint64_t i = (char*)p1 - p1ar->visible_bytes;
  assert(i < p1ar->length);
  assert((p1ar->length - i) >= sizeof(*p1));
  assert((i % sizeof(AllocationRecord*)) == 0);
  p2 = *p1;
  p2ar = *(AllocationRecord**)(p1ar->invisible_bytes + i);
  ...
  assert(p1ar != NULL);
  uint64_t i = (char*)p1 - p1ar->visible_bytes;
  assert(i < p1ar->length);
  assert((p1ar->length - i) >= sizeof(*p1));
  assert((i % sizeof(AllocationRecord*)) == 0);
  *p1 = p2;
  *(AllocationRecord**)(p1ar->invisible_bytes + i) = p2ar;

One thing we've not yet seen is filc_free, which does something like:

void filc_free(void* p, AllocationRecord* par) {
  if (p != NULL) {
    assert(par != NULL);
    assert(p == par->visible_bytes);
    free(par->visible_bytes);
    free(par->invisible_bytes);
    par->visible_bytes = NULL;
    par->invisible_bytes = NULL;
    par->length = 0;
  }
}

The eagle-eyed will note that filc_malloc made three allocations, but filc_free only frees two of them: the AllocationRecord object isn't freed by filc_free. This gap gets covered by the addition of a garbage collector (GC). You heard that right - this is C/C++ with a GC. The production-quality Fil-C has a parallel concurrent incremental collector, but a stop-the-world collector suffices for a simple model. The collector traces through AllocationRecord objects, and frees any unreachable ones. It also does two more things:

1. Upon freeing an unreachable AllocationRecord, call filc_free on it.
2. If an AllocationRecord has length 0, any pointers to that AllocationRecord will be changed to point at a single canonical AllocationRecord with length 0.

Point 1 means that if you're using Fil-C, forgetting to call free is no longer a memory leak: the memory will be automatically freed by the GC. That isn't to say that calling free is useless, as it allows memory to be freed earlier than the GC might otherwise choose to. Point 2 means that after calling free on something, the accompanying AllocationRecord will eventually become unreachable, and thus itself eventually be freed.

Once a GC is present, it becomes tempting to use it more. One such use is making it safe to take the address of local variables, even if the resultant pointer is used after the local variable goes out of scope. If the compiler sees that a local variable has its address taken, and cannot prove that the address doesn't escape beyond the lifetime of the local variable, then the Fil-C transform will promote that local variable to be heap-allocated via malloc rather than stack-allocated. A matching free doesn't need to be inserted, as the GC will pick it up.

The final thing I want to highlight is the Fil-C version of memmove. This function from the C standard library manipulates arbitrary memory, and the compiler has no knowledge of what pointers might be present in that memory. To get past this problem, a reasonable heuristic is used: any pointers within arbitrary memory need to be completely within arbitrary memory, and need to be correctly aligned. This has the interesting consequence that memmove of eight aligned bytes behaves differently to eight separate 1-byte memmoves of the constituent bytes: the former will also memmove the corresponding range of invisible_bytes, whereas the latter will not.

That wraps up the simplified model. Some of the additional complications in the production-quality version include:

• Threads: Concurrency makes the GC more complex. It also means that filc_free can't immediately free anything, as the free-ing thread might be racing with a different thread trying to access the underlying memory. Atomic operations on pointers also need some extra magic, as the default rewriting of a pointer load or store is to two loads or stores, which breaks atomicity.
• Function pointers: An additional piece of metadata in AllocationRecord is used to denote that the visible_bytes pointer is a pointer to executable code rather than regular data. Calls through a function pointer p1 check that p1 == p1ar->visible_bytes and that p1ar denotes a function pointer. To avoid type confusion attacks on function pointers, the function calling ABI also needs to verify that the type signature is correct. One way of doing this is to make all functions take the same type signature: all parameters are passed as if they were packed into a structure and passed through memory, and at ABI boundaries, every function expects to receive just a single AllocationRecord corresponding to that structure.
• Memory usage optimization: It is very tempting to have filc_malloc avoid immediately allocating invisible_bytes, and instead allocate it on-demand later should it ever be required. It is also tempting to colocate the AllocationRecord and visible_bytes into a single allocation. If the underlying malloc prepends metadata to every allocation, it looks tempting to put that metadata in AllocationRecord instead.
• Performance optimization: Memory safety in Fil-C comes at a performance cost, so it is worth playing various tricks to claw back some of that lost performance.

With the baseline understanding in place, I want to finish on a question: when might you want to use Fil-C? Personally, my answers are:

1. You have a large quantity of C/C++ code which seems to work, but it hasn't been proven memory-safe, and you're willing to introduce a GC and take a large performance hit in exchange for memory safety (perhaps as a temporary measure until you rewrite in Java or Go or Rust).
2. Just like you can run C/C++ code under ASan to find memory bugs, you can run it under Fil-C to find memory bugs.
3. If you have a language with a strong compile-time story, and the compile-time language is the same as the runtime language (for example, Zig), you could use a Fil-C setup for safe compile-time evaluation, even if runtime evaluation is unsafe.
4. Some people like to contemplate pointer provenance. If you've not come across this concept before, here's a nerd-snipe question: assuming p1 and p2 have the same type, is it valid for a compiler to rewrite if (p1 == p2) { f(p1); } to if (p1 == p2) { f(p2); }? In Fil-C, the answer is clearly "no", as it changes which AllocationRecord* gets passed along to f. This makes Fil-C a useful example of a concrete system which has pointer provenance.

Anthropic are currently in the tech news for (re)producing a C compiler using $20,000 of Claude's time, but I'm more interested in their compiler performance take-home challenge from two weeks ago. One part of Anthropic is showing that compiler engineers might be obsolete in the medium term, whereas another part is trying to find and hire the best compiler engineers on the planet. That both things can be simultaneously true is amusing to me, but perhaps not surprising: software engineers should be in the game of automating away their current problems so that they can move onward to new problems. Just as the higher education sector has expert lecturers teaching novice undergraduates, the AI sector can have expert humans teaching novice AIs.

Anyway, enough philosophical musing, I want to look at that compiler take-home challenge. It revolves around this little computation graph:

Several copies of this graph can be chained together vertically ("rounds"), and then multiple copies can be placed side-by-side horizontally ("batch size"). For example, here are two vertical copies and three horizontal copies, along with the initial loads and final stores:

The full challenge involves 16 vertical copies and 32 horizontal copies, meaning 512 copies in total. The challenge is to take this computational graph and schedule it on a hypothetical CPU capable of ~10 instructions per cycle, trying to minimise the total cycle count. For example, scheduling it in 1300 cycles involves considering a grid which is ~10 cells wide and 1300 cells tall, then placing each box from the diagram in one of those cells. Placing boxes into grid cells isn't all that hard, but I've been glossing over an important fact which makes it hard: the ~10 cells in each grid row are not all the same. Each grid row in fact consists of 7½ "valu" cells, 2 "load" cells, 2 "store" cells, and finally 1 "flow" cell. Most of the boxes from the diagram have to go into a "valu" cell, but there are a few exceptions:

• "vload" boxes require one "load" cell and one "flow" cell.
• "vstore" boxes require one "store" cell and one "flow" cell.
• "gather" boxes require eight "load" cells.

What looked simple now looks a bit harder: the 512 total "gather" boxes require 4096 "load" cells, thus requiring a grid at least 2048 cells tall. At this point, if I told you it was possible to make everything fit into a grid less than 1000 cells tall, you might think I was delusional. I assure you it is possible though, courtesy of two main strategies:

1. Reducing the number of boxes on the diagram.
2. Replacing some of the "+ base" and "gather" boxes with alternatives.

I don't have much to say about strategy one, as the majority of the changes can be shown using a single diagram:

Strategy two is more interesting. The gather operation can be replaced with a selection tree: preload the values of every possible idx, and use the output from all earlier & 1 boxes to select the appropriate value out of all the preloaded values. Each binary select operation requires either a single "flow" cell, or one or two "valu" cells. The number of binary select operations required to replace a "+ base" and "gather" then depends on the vertical level within the graph:

More than 280 gathers can be gainfully replaced with selection trees. Doing so massively reduces the number of "load" cells required, at the cost of increasing the number of "flow" cells required. In turn, some of those "flow" cells can be traded for "valu" cells. Part of the challenge is finding just the right instruction mix as to equally balance "valu" and "load" and "flow" in the 7½ : 2 : 1 ratio. If the full graph is considered as a whole, it isn't too hard to balance the overall instruction counts as to hit 7½ : 2 : 1. Unfortunately, this isn't enough: every single one of the ~1000 cycles wants to hit that 7½ : 2 : 1 ratio, which means instruction selection and instruction scheduling are intertwined problems. This is where the real meat of the challenge is found: the space of possible instruction selections and instruction schedules is vast, and so the winner is the person (or system) capable of finding the best point in that search space. If you can find a good point, submit it to the leaderboard (or email Anthropic asking for a job).

You might also ask whether this challenge is a reasonable proxy for actual compiler engineer experience. It is easy to cheat the default test harness, but I'm going to ignore that, as the objective is clearly to find compiler engineers rather than security engineers, and human review of submissions can easily identify the latter. There are also various well-known compiler problems which the challenge doesn't touch: there's no control flow, all instructions have single-cycle latency, memory hazards can be (almost) entirely ignored, there are no cache effects, and no doubt all sorts of other things. The target machine is clearly fictitious, but there is more VLIW hardware in the AI space than many people realise, and that final ½ "valu" slot is an endearing complication. Overall I think it is an OK proxy, though I much prefer it as an unlimited-time challenge rather than its original format of a two-hour timed exam.

Sebastian Aaltonen recently wrote an excellent piece titled No Graphics API, which you should read if you're interested in the mechanics of GPUs and APIs for talking to them. You should especially read it if you're an ambitious young engineer at Microsoft who would like to make your mark on the world by designing and championing DirectX 13. If you're instead a hardware engineer designing a new GPU (or something GPU-adjacent), you should again read it and ensure that your hardware design is amenable to what is described.

Is there anything further which can be stripped away?

The outlined API is already quite thin, but perhaps it could be even thinner still.

Compute-only

If only caring about GPGPU and not at all about graphics, there's a subset of the outlined API which drops the graphics-specific bits. The surviving functions are:

• Memory: gpuMalloc, gpuFree, gpuHostToDevicePointer.
• Pipelines: gpuCreateComputePipeline, gpuFreePipeline.
• Queue: gpuCreateQueue, gpuStartCommandRecording, gpuSubmit.
• Semaphores: gpuCreateSemaphore, gpuWaitSemaphore, gpuDestroySemaphore.
• Commands: gpuMemCpy, gpuBarrier, gpuSignalAfter, gpuWaitBefore, gpuSetPipeline, gpuDispatch, gpuDispatchIndirect.

If you do care about graphics then the rest should obviously be kept, but it is an interesting little thought experiment to consider a useful compute-only subset.

gpuHostToDevicePointer

If a GPU has a sufficiently good MMU, then in most cases, firmware on the GPU and drivers on the host can conspire to set up the GPU-side MMU mapping to make gpuHostToDevicePointer a no-op. If most could be extended to all, then gpuHostToDevicePointer could be removed, but perhaps this is a scenario in which covering 99% of cases is easy, but the final 1% is very hard.

gpuSubmit

If command buffers are always one-shot, then gpuSubmit looks potentially unnecessary: all commands enqueued to a command buffer will eventually execute, so they could be eligible for execution immediately upon being enqueued, with no gpuSubmit call necessary. CUDA works this way: kernels are enqueued with one call; there's no need for separate enqueue and submit. That said, there are a few possible arguments for the two-stage dance:

• Throughput can be improved (at a slight latency cost) by coalescing multiple commands together. For example, perhaps enqueueing can be done entirely in a userspace driver, whereas submission requires doing a system call.
• Though the API synopsis at the end of the blog post doesn't show semaphores interacting with gpuSubmit, an earlier example does. If removing gpuSubmit, there would need to be a different way of doing the semaphore part of submit.
• If doing graphics (rather than just compute), there needs to be some way to tell the GPU that all commands for the current frame are complete, and that the associated render target should be displayed to the human.

uint32x3 for SV_ThreadID and SV_GroupID and SV_GroupThreadID

Do we really need these to be 3D, or does it suffice for them to be 1D? Software can always unravel a 1D index to 3D if it needs to, and the driver might be inserting such an unravel already if the hardware is really only 1D under the hood.

Is there anything else which needs adding?

Though I'm a fan of minimalism, it is possible to be too minimalistic.

Multi-device support

In a system with multiple GPUs, gpuMalloc needs to know which GPU to allocate on, so either an extra argument or a sideband function call to set the active GPU. The same is true for all of gpuTextureSizeAlign, gpuCreateSemaphore, gpuCreate*Pipeline, and gpuCreate*State (some of these cases could instead be lazy and defer the actual GPU-specific resource creation until the first time the resultant object is used with a GpuCommandBuffer, but laziness causes other problems).

A related can of worms is peer-to-peer support between multiple GPUs: can one GPU write to another's memory in the same way it can write to CPU MEMORY_READBACK memory? Is there some form of barrier or signal or semaphore allowing one GPU to wait for work on another to complete? Many further questions are possible.

Multi-process support

Some GPGPU workloads benefit from having a singular GPU memory allocation visible to multiple distinct CPU processes. They might also benefit from being able to create a pipeline and then share the GPU-side state associated with that pipeline between multiple distinct CPU processes, though this is more of a minor optimisation to avoid the same state being created multiple times.

Memory pinning

It is often very convenient to be able to take an arbitrary memory allocation performed by the application (i.e. not through gpuMalloc), and make that memory visible to the GPU as-if gpuMalloc were used with the MEMORY_READBACK flag. In general, making this work requires at least one of:

• UMA.
• A sufficiently good MMU on the GPU.
• An IOMMU on the host.
• The OS to find a suitable range of contiguous physical memory and change which physical memory backs the allocation (only possible for pageable memory).

If relying on at least one of the above isn't viable, an alternative is adding a variant of gpuMemCpy which accepts CPU pointers. It is always possible to implement such an async memcpy API: the driver can do some combination of temporary pinning / splitting one non-contiguous copy into several contiguous ones / bounce buffers / DMA controller scatter-gather lists.

Instruction cache fences

Some hardware contains non-coherent instruction caches which need to be explicitly cleared after loading (or modifying) code and before executing said code. This is an obvious candidate for a gpuBarrier flag / mode. Alternatively, hardware which requires it could have the driver transparently perform the appropriate fence as part of every gpuCreate*Pipeline call, or transparently perform it just before the first gpuSubmit call after a gpuCreate*Pipeline call.

Does anything give me cause for concern?

Most of the outlined API has me thinking "yep, this all seems sensible", but a few areas cause me to think a little bit harder.

Write-combining memory

The approach to memory management is relying on either UMA or PCIe ReBAR. ReBAR doesn't strictly require write-combining memory, but you really want something like WC memory to give CPU → GPU writes acceptable performance. This is fine on x86 / x86-64, but potentially an area of concern for any other CPU architectures which lack the concept of WC. Even where it exists, write combining is not your friend: handing out pointers to write-combining memory to user code comes with lots of potential footguns. Some of these footguns can be mitigated with education and documentation, but not entirely.

Deadlock avoidance

If one command buffer can do a gpuWaitBefore for a gpuSignalAfter from a different command buffer, then commands from the two buffers need to be run in the right order, lest the GPU commit to blocking on the wait command before running the commands which would unblock it. This might look like an easy problem to solve: if a GPU would be blocking on a wait, it should instead actively go looking for other work (from other submitted command buffers) to perform. Actual reality is slightly more annoying: perhaps there are a finite number of hardware command queues, so the GPU driver multiplexes multiple software command buffers onto the same hardware command queue, and if it does that multiplexing in the wrong order, the resultant queue ends up with the wait before the signal. There are many ways to make this problem go away; one such way is to put the onus on the developer, and require that it is valid (even if not optimal) for the GPU to execute submitted command buffers one after another, and commands within each of those buffers in the order they were enqueued, with no reordering anywhere. CUDA happens to design the API to ensure this: streams don't need any explicit submission (so it is valid for the GPU to run commands in the exact order they were enqueued), and cudaEventRecord must be enqueued before cudaStreamWaitEvent is enqueued, as that's just how events work.

Leaving 32 bits behind

In practice, PCIe ReBAR means having a 64-bit operating system. I'm fine with excluding 32-bit operating systems, but perhaps not everybody is.

I have slightly more sympathy for 32-bit programs on 64-bit operating systems. To make them work, gpuHostToDevicePointer would need to return a 64-bit value rather than a pointer. Even then, structure definitions containing pointers could not be shared between CPU and GPU, and the amount of memory allocatable with gpuMalloc would be limited to a few gigabytes. It might be easier to just say that 32-bit programs are a legacy which we're prepared to leave behind.

Conclusion

You'll note that my collection of thoughts takes up far fewer words than the referenced piece. As I said in opening, it is an excellent piece: most of it doesn't require any further commentary.

I'm the kind of person who thinks about the design and implementation of hash tables. One design which I find particularly cute, and I think deserves a bit more publicity, is Robin Hood open-addressing with linear probing and power-of-two table size. If you're not familiar with hash table terminology, that might look like a smorgasbord of random words, but it should become clearer as we look at some actual code.

To keep the code simple to start with, I'm going to assume:

1. Keys are randomly-distributed 32-bit integers.
2. Values are also 32-bit integers.
3. If the key 0 is present, its value is not 0.
4. The table occupies at most 32 GiB of memory.

Each slot in the table is either empty, or holds a key and a value. The combination of properties (1) and (2) allows a key/value pair to be stored as a 64-bit integer, and property (3) means that the 64-bit value 0 can be used to represent an empty slot (some hash table designs also need a special value for representing tombstones, but this design doesn't need tombstones). Combining a key and a value into 64 bits couldn't be easier: the low 32 bits hold the key, and the high 32 bits hold the value.

The structure for the table itself needs a pointer to the array of slots, the length of said array, and the number of non-empty slots. As the length is always a power of two, it's more useful to store length - 1 instead of length, which leads to mask rather than length, and property (4) means that mask can be stored as 32 bits. As the load factor should be less than 100%, we can assume count < length, and hence count can also be 32 bits. This leads to a mundane-looking:

struct hash_table_t {
  uint64_t* slots;
  uint32_t mask;
  uint32_t count;
};

Property (1) means that we don't need to hash keys, as they're already randomly distributed. Every possible key K has a "natural position" in the slots array, which is just K & mask. If there are collisions, the slot in which a key actually ends up might be different to its natural position. The "linear probing" part of the design means that if K cannot be in its natural position, the next slot to be considered is (K + 1) & mask, and if not that slot then (K + 2) & mask, then (K + 3) & mask, and so on. This leads to the definition of a "chain": if K is some key present in the table, CK denotes the sequence of slots starting with K's natural position and ending with K's actual position. We have the usual property of open-addressing: none of the slots in CK are empty slots. The "Robin Hood" part of the design then imposes an additional rather interesting property: for each slot S in CK, Score(S.Index, S.Key) ≥ Score(S.Index, K), where:

• S.Index is the index of S in the slots array (not the index of it in CK).
• S.Key is the key present in slot S (i.e. the low 32 bits of slots[S.Index]).
• Score(Index, Key) is (Index - Key) & mask.

These properties give us the termination conditions for the lookup algorithm: for a possible key K, we look at each slot starting from K's natural position, and either we find K, or we find an empty slot, or we find a slot with Score(S.Index, S.Key) < Score(S.Index, K). In either of the latter two cases, K cannot have been present in the table. In the function below, Score(S.Index, K) is tracked as d. In a language with a modern type system, the result of a lookup would be Optional<Value>, but if sticking to plain C, property (3) can be used to make something similar: the 64-bit result is zero if the key is absent, and otherwise the value is in the low 32 bits of the result (which may themselves be zero, but the full 64-bit result will be non-zero). The logic is thus:

uint64_t table_lookup(hash_table_t* table, uint32_t key) {
  uint32_t mask = table->mask;
  uint64_t* slots = table->slots;
  for (uint32_t d = 0;; ++d) {
    uint32_t idx = (key + d) & mask;
    uint64_t slot = slots[idx];
    if (slot == 0) {
      return 0;
    } else if (key == (uint32_t)slot) {
      return (slot >> 32) | (slot << 32);
    } else if (((idx - (uint32_t)slot) & mask) < d) {
      return 0;
    }
  }
}

If using a rich 64-bit CPU architecture, many of the expressions in the above function are cheaper than they might initially seem:

• slots[idx] involves zero-extending idx from 32 bits to 64, multiplying it by sizeof(uint64_t), adding it to slots, and then loading from that address. All this is a single instruction on x86-64 or arm64.
• key == (uint32_t)slot involves a comparison using the low 32 bits of a 64-bit register, which is a completely standard operation on x86-64 or arm64.
• (slot >> 32) | (slot << 32) is a rotation by 32 bits, which again is a single instruction on x86-64 or arm64.

On the other hand, if using riscv64, things are less good:

• If the Zba extension is present, sh3add.uw is a single instruction for zero-extending idx from 32 bits to 64, multiplying it by sizeof(uint64_t), and adding it to slots. If not, each step is a separate instruction, though the zero-extension can be eliminated with a slight reformulation to encourage the compiler to fold the zero-extension onto the load of table->mask (as riscv64 usually defaults to making sign-extension free, in contrast to x86-64/arm64 which usually make zero-extension free). Regardless, the load is always its own instruction.
• key == (uint32_t)slot hits a gap in the riscv64 ISA: it doesn't have any 32-bit comparison instructions, so this either becomes a 32-bit subtraction followed by a 64-bit comparison against zero, or promotion of both operands from 32 bits to 64 bits followed by a 64-bit comparison.
• If the Zbb extension is present, rotations are a single instruction. If not, they're three instructions, and so it becomes almost worth reworking the slot layout to put the key in the high 32 bits and the value in the low 32 bits.

Moving on from lookup to insertion, there are various different options for what to do when the key being inserted is already present. I'm choosing to show a variant which returns the old value (in the same form as table_lookup returns) and then overwrites with the new value, though other variants are obviously possible. The logic follows the same overall structure as seen in table_lookup:

uint64_t table_set(hash_table_t* table, uint32_t key, uint32_t val) {
  uint32_t mask = table->mask;
  uint64_t* slots = table->slots;
  uint64_t kv = key + ((uint64_t)val << 32);
  for (uint32_t d = 0;; ++d) {
    uint32_t idx = ((uint32_t)kv + d) & mask;
    uint64_t slot = slots[idx];
    if (slot == 0) {
      // Inserting new value (and slot was previously empty)
      slots[idx] = kv;
      break;
    } else if ((uint32_t)kv == (uint32_t)slot) {
      // Overwriting existing value
      slots[idx] = kv;
      return (slot >> 32) | (slot << 32);
    } else {
      uint32_t d2 = (idx - (uint32_t)slot) & mask;
      if (d2 < d) {
        // Inserting new value, and moving existing slot
        slots[idx] = kv;
        table_reinsert(slots, mask, slot, d2);
        break;
      }
    }
  }
  if (++table->count * 4ull >= mask * 3ull) {
    // Expand table once we hit 75% load factor
    table_rehash(table);
  }
  return 0;
}

To avoid the load factor becoming too high, the above function will sometimes grow the table by calling this helper function:

void table_rehash(hash_table_t* table) {
  uint32_t old_mask = table->mask;
  uint32_t new_mask = old_mask * 2u + 1u;
  uint64_t* new_slots = calloc(new_mask + 1ull, sizeof(uint64_t));
  uint64_t* old_slots = table->slots;
  uint32_t idx = 0;
  do {
    uint64_t slot = old_slots[idx];
    if (slot != 0) {
      table_reinsert(new_slots, new_mask, slot, 0);
    }
  } while (idx++ != old_mask);
  table->slots = new_slots;
  table->mask = new_mask;
  free(old_slots);
}

Both of table_set and table_rehash make use of a helper function which is very similar to table_set, but doesn't need to check for overwriting an existing key and also doesn't need to update count:

void table_reinsert(uint64_t* slots, uint32_t mask, uint64_t kv, uint32_t d) {
  for (;; ++d) {
    uint32_t idx = ((uint32_t)kv + d) & mask;
    uint64_t slot = slots[idx];
    if (slot == 0) {
      slots[idx] = kv;
      break;
    } else {
      uint32_t d2 = (idx - (uint32_t)slot) & mask;
      if (d2 < d) {
        slots[idx] = kv;
        kv = slot;
        d = d2;
      }
    }
  }
}

That covers lookup and insertion, so next up is key removal. As already hinted at, this hash table design doesn't need tombstones. Instead, removing a key involves finding the slot containing that key and then shifting slots left until finding an empty slot or a slot with Score(S.Index, S.Key) == 0. This removal strategy works due to a neat pair of emergent properties:

• If slot S has Score(S.Index, S.Key) != 0, it is viable for S.Key to instead be at (S.Index - 1) & mask (possibly subject to additional re-arranging to fill the gap formed by moving S.Key).
• If slot S has Score(S.Index, S.Key) == 0, and S is part of some chain CK, then S is at the very start of CK. Hence it is viable to turn (S.Index - 1) & mask into an empty slot without breaking any chains.

This leads to the tombstone-free removal function, which follows the established pattern of returning either the old value or zero:

uint64_t table_remove(hash_table_t* table, uint32_t key) {
  uint32_t mask = table->mask;
  uint64_t* slots = table->slots;
  for (uint32_t d = 0;; ++d) {
    uint32_t idx = (key + d) & mask;
    uint64_t slot = slots[idx];
    if (slot == 0) {
      return 0;
    } else if (key == (uint32_t)slot) {
      uint32_t nxt = (idx + 1) & mask;
      --table->count;
      while (slots[nxt] && ((slots[nxt] ^ nxt) & mask)) {
        slots[idx] = slots[nxt];
        idx = nxt;
        nxt = (idx + 1) & mask;
      }
      slots[idx] = 0;
      return (slot >> 32) | (slot << 32);
    } else if (((idx - (uint32_t)slot) & mask) < d) {
      return 0;
    }
  }
}

The final interesting hash table operation is iterating over all keys and values, which is just an array iteration combined with filtering out zeroes:

void table_iterate(hash_table_t* table, void(*visit)(uint32_t key, uint32_t val)) {
  uint64_t* slots = table->slots;
  uint32_t mask = table->mask;
  uint32_t idx = 0;
  do {
    uint64_t slot = slots[idx];
    if (slot != 0) {
      visit((uint32_t)slot, (uint32_t)(slot >> 32));
    }
  } while (idx++ != mask);
}

That wraps up the core concepts of this hash table, so now it is time to revisit some of the initial simplifications.

If keys are 32-bit integers but are not randomly-distributed, then we just need an invertible hash function from 32 bits to 32 bits, the purpose of which is to take keys following ~any real-world pattern and emit a ~random pattern. The table_lookup, table_set, and table_remove functions gain key = hash(key) at the very start but are otherwise unmodified (noting that if the hash function is invertible, hash equality implies key equality, hence no need to explicitly check key equality), and table_iterate is modified to apply the inverse function before calling visit. If hardware CRC32 / CRC32C instructions are present (as is the case on sufficiently modern x86-64 and arm64 chips), these can be used for the task, although their inverses are annoying to compute, so perhaps not ideal if iteration is an important operation. If CRC32 isn't viable, one option out of many is:

uint32_t u32_hash(uint32_t h) {
  h ^= h >> 16;
  h *= 0x21f0aaad;
  h ^= h >> 15;
  h *= 0x735a2d97;
  h ^= h >> 15;
  return h;
}

uint32_t u32_unhash(uint32_t h) {
  h ^= h >> 15; h ^= h >> 30;
  h *= 0x97132227;
  h ^= h >> 15; h ^= h >> 30;
  h *= 0x333c4925;
  h ^= h >> 16;
  return h;
}

If keys and values are larger than 32 bits, then the design can be augmented with a separate array of key/value pairs, with the design as shown containing a 32-bit hash of the key and the array index of the key/value pair. To meet property (3) in this case, either the hash function can be chosen to never be zero, or "array index plus one" can be stored rather than "array index". It is not possible to make the hash function invertible in this case, so table_lookup, table_set, and table_remove do need extending to check for key equality after confirming hash equality. Iteration involves walking the separate array of key/value pairs rather than the hash structure, which has the added benefit of iteration order being related to insertion order rather than hash order. As another twist on this, if keys and values are variably-sized, then the design can instead be augmented with a separate array of bytes, with key/value pairs serialised somewhere in that array, and the hash structure containing a 32-bit hash of the key and the byte offset (within the array) of the key/value pair.

Of course, a design can only stretch so far. If you're after a concurrent lock-free hash table, look elsewhere. If you can rely on 128-bit SIMD instructions being present, you might instead want to group together every 16 key/value pairs, keep an 8-bit hash of each key, and rely on SIMD to perform 16 hash comparisons in parallel. If you're building hardware rather than software, it can be appealing to have multiple hash functions, each one addressing its own SRAM bank. There is no one-size-fits-all hash table, but I've found the one shown here to be good for a lot of what I do.