devbug

I did this manually back in Feb 2024[1], but only got "connector A" mapped out and a partially designed SXM2-to-PCIe interposer designed before getting distracted.

During the process, I discovered Facebook's Big Basin JBOG schematics/specs (from Open Compute), which contained a design derived from NVIDIA's DGX-1 reference implementation. Looks like this clears up some gaps in the current reference. It also explains some of the design choices, like the form factor and similar pinout to OpenPOWER.

To give a slightly more detailed description, you allocate two arrays of the extents. One is the dense array of whatever type, say T, and the other is the sparse array of 32 bit or 64 bit integers. The sparse array stores indices into the dense array for extant objects. However, for extinct objects, the indices instead point to the sparse array itself to encode a free-list.

To insert, in O(1), you check the free-list for an unused slot. If there is none, then you grow the sparse array (increment a counter) and use the newly introduced slot. Then you insert (or construct in place) your object at the end of the dense array. Finally, you map that slot in the sparse array to the end of the dense array.

To delete, in O(1), you swap the object you wish to delete with the last in the dense array and decrement the counter (swap and pop). Then you add the index in the sparse array to the free-list. You’ll need to know the index assigned to the object you swapped with to do this, which can either be stored on the object itself or by introducing another array the maintains an inverse mapping.

To iterate, you can treat the dense array like any other array.

This scheme poses some challenges:

- You lose pointer stability because you are relocating your objects. You must access them through indices. If you can defer your deletions, say to a frame boundary, you assume your pointers are stable.

- Indices, without further work, are not safe. They are just as safe as pointers. Usually you don’t expect more than N objects, so you can use log2(N) bits for the forward and reverse mappings between sparse and dense arrays and then use the leftover bits to identify stale indices. You can, and should, encapsulate this in a type-safe handle system. [2][3]

- High churn can cause index invalidation to fail (if you wrap a counter) and performs worse than other data structures.

- “Swap and pop” requires T to be trivially copyable, or ideally, trivially relocatable.

It’s also worth mentioning that you can reorder the dense array to maintain custom invariants. This is really useful if you have dependencies between objects and want to iterate in order.[4]

I've been meaning to implement SGP4 from scratch as a learning exercise. What I found really interesting is how the USAF/NORAD tracks and reports objects in LEO: they publish Two-line Element Sets (TLEs), which are a fixed-width ASCII format derived from punch cards.[1] The format is pretty easy to parse.[2]

These provided MFTs have to meet certain minimum requirements for certification by Microsoft, which amounts to "good enough." Results vary in practice and can be incredibly frustrating (especially encode). It's often better to use the underlying SDKs but that comes with a lot of hassle.

(I've been working on a video capture and sharing app inspired by Shadowplay.)

Windows 10 is also rolling out support for AV1, though not bundled.[4]

I've done it, not out of performance concerns, but because transcoding between proprietary binary formats with types is a lot saner than the alternative.