Donald Knuth's Annual Christmas Lecture 2023
learn.stanford.edu
learn.stanford.edu
The talk is going to be about “Dancing Cells”, something about sparse-set representation and backtracking. (https://cs.stanford.edu/~knuth/musings.html)
Looking forward to the talk, and meanwhile I found a couple of good blog posts about the sparse-set representation, and can see why Knuth is interested:
• https://manenko.com/2021/05/23/sparse-sets.html by Oleksandr Manenko
• https://research.swtch.com/sparse "Using Uninitialized Memory for Fun and Profit" by Russ Cox.
Today's talk is a sequel to “Dancing Links” not only in the sense of making backtracking programs run faster, but also one could say “things that would make valgrind / memory sanitizer go crazy”. :-) In a way, the dancing links idea (not freeing the node deleted from the linked list) was a kind of “use-after-free” or memory leak, while the sparse-set representation here is using uninitialized memory. Knuth is not the kind of person to court controversy, but he does seem to enjoy going against the “moralistic preaching” grain in programming, what with his spirited defence and continued use of “goto”, his heart always being with machine/assembly language (not anything higher-level than C), and things like this. :-)
[1] https://j11g.com/knuth.xml
[2] https://j11g.com/2020/12/30/podcast-donald-knuth-lectures-on...