Intuitive Random Selection (with Marc LeBlanc)
After the ECS interview, Mahk shared a new random selection that's much more intuitive than the one typically used in game development.
Suppose you want to pick a random element from a set that is difficult to iterate. Perhaps the candidate elements are embedded in a spatial hierarchy, and only determined by a complex predicate.
One obvious way to solve this problem is to first build a “filtered” array of all the candidate elements, then pick a random index into that array. This always works, and is fair (assuming the RNG is fair) — but it requires reserving space for a potentially-large array, and uses up bandwidth and cache space each time a random selection is made.
A non-obvious-but-common alternative is to use a statistical method where random numbers are chosen during the initial iteration to continuously “retain or replace” a running selection. The random numbers must be carefully constructed, and typically require a modulus on each step. Proof of the fairness of the method is not obvious, and requires knowledge of the relevant underlying math.
In short, while it works, and is likely more efficient than the array method, it has drawbacks.
Inspired by the way you might write such a query in SQL, Marc “Mahk” LeBlanc shared with me a new arrayless picking method that has none of these drawbacks. It’s very similar to the statistical methods version, but without any of the drawbacks.
In this video, Mahk presents the algorithm in a series of steps, starting from a “worst” random selector, and ending with his new one.
The "highest score" version of the random selection algorithm reminds me of a similar algorithm for parallel graph coloring:
Each graph node gets assigned a random number as a score. While there are uncolored nodes, assign a new color to all nodes with a score higher than all its neighbors. Repeat until all nodes are colored.
In each iteration, no two adjacent nodes are chosen, since one would have a higher score than the other (assuming some tie-breaking scheme), and therefore all nodes chosen in an iteration can be assigned the same color.
Using the score comparisons to decide which nodes to color in each iteration allows the algorithm to parallelize nicely since every node can be checked fully independently based on the read-only scores.
The algorithm doesn't make any optimality guarantees for the coloring, but it is intuitive and has minimal synchronization, so it works well with large numbers of cores.
I heard about this algorithm from this post, which has some more details: https://developer.nvidia.com/blog/graph-coloring-more-parallelism-for-incomplete-lu-factorization/
This expert-to-expert format exposes a particularly rich seam of historical context and technical information.
I understand not every influential long-timer can sit an interview for 3+ hours. Nevertheless, you are, perhaps, uniquely positioned to do this type of thing well, and I welcome whatever further contributions you're willing to make to posterity in this vein.
If we do happen to go through an LLM-induced Dark Age in programming, then may this oeuvre fuel the Rennaissance.