psykotic

I'm the author of the tweet. Here's some more context:

The main purpose of the testing was to measure compile time scaling on simple code that has straightforward equivalents in all languages. This meant integer and float operations, compound expressions making use of the full range of arithmetic and bitwise operators, local variables, function definitions and calls. So the code wasn't trivial (unlike most of the marketing-oriented tests or benchmarks I came across), but I also wasn't claiming that this was directly representative of a real-world code base of comparable size.

I was working on a fast compiler (which generated machine code somewhere between gcc -O0 and -O1 in code quality) and wanted to have something to compare it across languages and compilers while being able to easily vary test parameters like total code size, size of each module, complexity of the module graph, identifier/whitespace/comment length distribution, etc.

"Lines of code" is a pretty poor metric for engineering but unlike "tokens of code" or "bytes of code" it's something for which programmers have an intuitive sense of scale, so it made more sense for a tweet. Tokens of code is the most useful code size parameter for measuring one-pass compiler performance if you have to pick a single number. In an expression like "x + 1" you can assign the cost of the parsing, type checking and code generation of the expression (separate from the sub-expressions "x" and "1") to the "+" token. Even the cost of lexing is often dominated by the per-token cost (the switch jump on the leading byte is usually a forced branch mispredict of ~15 cycles) if you do the per-byte handling for variable-length tokens like identifiers efficiently. [1] If you fix the token distribution, you get almost-linear scaling with token count. [2]

[1] Identifier bytes make up 60-70% of a typical code base, so micro-optimization can really pay off here if the rest of the compiler is fast. I used a SIMD method with a mispredict-free fast path for identifiers shorter than 16/32 bytes, with vectorized scanning and hashing, and the symbol table lookup/insertion was done at the same time and tuned such that it was mispredict-free 90% of the time for lookups and only had 1 mispredict for inserts which occur the first time a given identifier is seen in a module.

[2] Except for threshold effects when your working set starts pushing you out of a level of the cache hierarchy. There's two factors: the size of your symbol working set, and your utilization of symbol hash tables. E.g. if a region of code is using a tiny subset of a huge symbol table, each loaded cacheline from the hash table is only expected to contain one symbol from your working set due to the pseudo-random distribution of hashes, but that caps out pretty quickly. With 64-byte cachelines and interleaved key/value pairs of 16 bytes, this part can't get worse than 25% cache utilization. So the worst-case footprint from the symbol working set is one 64-byte cacheline per symbol in the working set plus whatever associated symbol data is accessed. This utilization is improved if you put more symbol data directly into the hash table cacheline but unfortunately that would mean you don't have stable pointers to that data when you need to rehash.

(I'm the person he was quoting in the article.)

When I use setjmp/longjmp error handling I almost always want abort semantics but at the library level rather than at the OS process level. [1] Where applicable it's the simplest, most robust model I know. You have a context object that owns all your resources (memory blocks, file handles, etc) which is what lets you do simple and unified clean-up rather than fine-grained scoped clean-up in the manner of RAII or defer. You can see an example in tcc here:

https://github.com/LuaDist/tcc/blob/255ba0e8e34f999ee840407c...

https://github.com/LuaDist/tcc/blob/255ba0e8e34f999ee840407c...

[1] It goes without saying that a well-written library intended for general use is never allowed to kill the process. This presents a conundrum in writing systems-level C libraries. What do you do if something like malloc fails in a deep call stack within the library? Systems-level libraries need to support user-provided allocation functions which often work out of fixed-size buffers so failure isn't a fatal error from the application's point of view. You'd also want to use this kind of thing for non-debug assert failures for your library's internal invariants.

This style of setjmp/longjmp error handling works well for such cases since you can basically write the equivalent of xmalloc but scoped to the library boundary; you don't have to add hand-written error propagation to all your library functions just because a downstream function might have such a failure. I'm not doing this as a work-around for a lack of finally blocks, RAII or defer statements. It's fundamentally about solving the problem at a different granularity by erecting a process-like boundary around a library.

> But doesn't the dynamic linker still have to do extra work to resolve the relocations in the executable, even when the dependency libraries are already loaded?

For dynamic linking there's usually only a single reference that needs to be fixed up in the PLT or GOT for each referenced symbol and the fix-ups are all localized, so that part is typically a very small cost. But this means every call to a dynamically linked library goes through an extra stub function, which adds I$ and BTB pressure compared to static linking.

(If you do things manually with dlsym there's also an extra indirection but it's a little different mechanically since you do an indirect call of a function pointer rather than doing a direct call to a forwarding stub. The advantage of the forwarding stub is that even if there's a BTB miss for either of the two direct calls, you don't suffer a branch mispredict but just a few front-end cycles waiting for the instruction decode, which VTune labels as a "branch resteer". The direct call option also leads to smaller code size for each call site which helps with I$ pressure. Basically it's the difference between CALL rel32 and MOV tmp, [RIP + disp32]; CALL [tmp].)

Wasn't one of the issues with earlier Pi versions that the driver just serialized high-level GLES-like commands to a front-end processor that ran a huge closed firmware blob? All GPUs have built-in command processors but this was closer to a full driver running as a firmware blob on an auxiliary CPU.

The new release of VMware Workstation now works with Hyper-V as its hypervisor but a bunch of people (and I'm one of them) have experienced massive, unacceptable performance regressions for VM guests. I had to disable Hyper-V and hence stop using WSL2 until it's resolved. If the performance issues are intrinsic this will probably be a permanent showstopper for people who rely on VMware or Virtual Box. Hopefully this gets sorted out one way or another.

> In what application are you going to sort an array of a pure scalar type that is native to the machine?

All the time in my experience. This is why radix sort is so useful. Many key types can be packed into 64 bits in a way that's compatible with the bitwise lexicographic ordering. You can pack 9-character low ASCII strings (or 10-character [a-zA-Z_][a-zA-Z0-9_]* identifiers) in 64 bits. [1] You can even do sub-bit packing, e.g. c + 3 * b + 3 * 7 * a for the tuple (a, b, c) with lexicographic ordering where 0 <= c < 3 and 0 <= b < 7. If you wanted to sort ascending on a and c but descending on b you'd replace b by 6 - b in the embedding. For radix sort you can also support 2's complement integers and IEEE-754 floats by simple key transformations. You get the idea: many complex keys are efficiently reducible to machine integers.

My default algorithm for scalar sorting is usually an optimized LSD radix sort. It's inherently branchless; its downside compared to quicksort is worse cache locality for the scattered writes after the histogram phase. Incidentally, quicksort is closely related to MSD radix sort with radix 2, which effectively partitions using data-independent pivots.

[1] For longer strings you would sort on the prefix using this embedding and then do a final pass where you sort among each (hopefully small) set of prefix-colliding strings by a different method, e.g. insertion sort for small sets.

Clojure uses persistent vectors which are essentially trees of array chunks (I think 32 elements per array chunk) that support structure sharing and a version of cons called conj that runs in order log32(n) time. But the language isn't really designed for high performance in practice despite some of the early marketing.

Anyway, caches are only part of the problem with linked lists. The root problem is that they inhibit out of order execution. Work out the data dependencies and scheduling of a simple summation loop for an array compared to a linked list. Assume everything fits in L1. The out-of-order core goes to town with the array code and overlaps the fetches for subsequent iterations of the loop. But the linked list code is serialized with almost no instruction-level parallelism; you can overlap the summation of an element into the accumulator with the start of the deref of the next pointer, but that only saves you one cycle per iteration compared to what an in-order core would do with the same code. Now suppose the data is in L2. In that case the out-of-order core can overlap the loads of the subsequent array elements and the throughput is only diminished by a little if at all compared to the L1 case. The linked list code, on the other hand, works the same as before but because it cannot overlap the fetches for sequential elements due to the dependent loads, you go from say 5 cycles per iteration to 15 cycles per iteration. If you have to go out to L3 or DRAM the chasm dramatically widens even further.

More obviously, linked structures also increase pressure on cache capacity since they have to store their links explicitly. Yet another factor is that modern caches will expend bandwidth on speculative prefetches to reduce latency. This can help for both flat and linked data structures. For example, if you have an AST you should linearly allocate the nodes in the anticipated traversal order to get help from the prefetcher. (And please slim down those fat AST nodes.) If you did that for our linked-list summation example, you'd pay the 15 cycles for the first iteration but then you'd pay 5 cycles for the remaining entries in the same cacheline and also 5 cycles for all remaining entries in other cachelines since the prefetcher will have kicked in. So aside from the startup latency, you're back to running at the same speed as when the list started out in L1. But you're still losing out on the out-of-order execution for the L1 fetches: 4 cycles on a modern core is an opportunity cost of 16 instructions. You're reducing your core to a souped up 486.

By the way, for this particular toy example you should go beast mode with SIMD instructions for the array case which will net you another factor of 4x to 32x depending on the element size and the width of your vector unit and then you parallelize across your cores to get another factor of 4x. While those particulars might not generalize to less simple problems, it illustrates that the major issue with linked structures is that they force serial processing.

You need the Sysinternals utilities to make life tolerable: https://docs.microsoft.com/en-us/sysinternals/downloads/hand... from the command line or Ctrl-F in https://docs.microsoft.com/en-us/sysinternals/downloads/proc... if you prefer a GUI. They do a brute-force search over the open handles in all processes, but it's effective.

> think reparse points, alternate streams, transactions, BitLocker integration, and shrinkable volumes, to name a few.

NTFS's USN change journal (which is separate from the transaction journal) is also useful as a robust offline alternative to ReadDirectoryChangesW file monitoring. Toy example: https://gist.github.com/pervognsen/bcc610d6a5ae6cbc3b2b4f7aa....

Anyway, the problem I've always had when using non-standard file system metadata like alternate streams or sparse files is that they interoperate poorly in practice. There's lots of code and programs out there that wants to treat everything like a plain old file and hence won't preserve alternate streams or sparseness. From my recollections this is true even for several of Windows's built-in utilities. Same issue if you want to transfer files over a socket or pipe or a non-NTFS storage medium like a FAT-formatted USB drive or a NetApp filer or a source control system. As a result this kind of thing is only really useful when deployed in a bubble; I believe WSL uses alternate streams for Unix permission bits and other Unix-specific file properties. Even though those WSL guest files live in a directory tree on a normal NTFS volume, they strongly caution you against touching them directly outside of WSL, presumably for the aforementioned reasons.

Aside from features, NTFS has some performance issues compared to other modern file systems, notably with lots of smaller files.

If you want something more extensive and less dramatized, I'd recommend Kotkin's ongoing multi-volume biography starting with Stalin: Paradoxes of Power, 1878-1928. It's becoming (if it isn't already) the definitive work on Stalin.

> if they were literally at his bed safeguarding information, that seems quite intrusive for someone who did monumental tasks for the government. and it isn't even clear what their gameplan would be in this case.

The British state forcibly sterilized Turing who was instrumental in the allied war effort in a greater or equal capacity to von Neumann. "Quite intrusive" is a monumental understatement of what governments will do to protect their perceived interests.

I consider applicability one of the primary aesthetic qualities in mathematics, but most mathematical applications are internal to mathematics or science, not about solving some highly specific practical problem like improving web search performance. Applications of complex analysis to proving the prime number theorem or to designing airfoils are in the same category for me aesthetically. They both enrich my understanding and appreciation for complex analysis. The applications might be more or less shallow. The applications of complex analysis to number theory go very deep. But potential theory is also a beautiful and theoretically rich subject that extends into higher dimensions, and the airfoil design example is striking because it relies on the non-rigidity of conformal mappings in 2D, which is the main feature of potential theory that fails to extend to higher dimensions. If you study any application, it will invariably improve your understanding of the original ideas.

>Classical measure theory lives in a model divorced from physical reality.

Everything in mathematics is divorced from reality. Unbounded integers are divorced from reality. (Once you move beyond naive realism, bounded integers are divorced from reality, but that's a deeper philosophical debate.) The only question is whether these models are more or less effective for their various theoretical and applied purposes.

> There are better approaches to measure theory which live in different "foundations". For example, you can build measure and probability theory based on the locale of valuations on a locale instead of a sigma-algebra on a topological space.

Better by what definition? According to the practical needs of students, pure and applied mathematicians, etc? I've studied some topos theory and know a little bit about locales from the Topology Via Logic book, but it's hard for me to see that as anything more than a fun curiosity when considering the practical needs of mathematics as a whole. In my mind that kind of thing is much closer to navel-gazing than something like measure theory.

> It is really not the most straightforward approach.

The onus is on critics to do better. Dieudonne/Bourbaki made a valiant and elegant attempt even if they intentionally snubbed the needs of probability theory. And "better" will obviously be judged by the broader community.

It's been forever since I looked at this stuff, sorry. But I think Bourbaki's shortcut to integration theory via continuous linear functionals only works in locally compact spaces. It doesn't let you construct the Wiener measure on a path space corresponding to Brownian motion or other continuous-time stochastic processes. And the example I gave of the conceptual, information-theoretic role played by sigma algebras in stochastic processes shows that sidestepping them is the wrong move for probability theory, even if they weren't used for some of the advanced technical constructions like Wiener measure.

Bourbaki's shortcut to Radon measures is very elegant but it's noteworthy that unlike many other Bourbaki innovations I don't think it was picked up by other textbook authors. Already at that point there was a mathematical consensus that measure theory was a valuable part of the foundations of modern mathematics and shouldn't be eliminated or minimized.

Outside probability theory, measure theory is primarily used as a foundation for integration ("expectation"). There are also more specialist subjects like geometric measure theory; there's an excellent introductory textbook called Measure Theory and Fine Properties of Functions, and if you look at its table of contents you can get an idea of the breadth of topics.

For what it's worth, my professional background is entirely in game development and systems programming. I'm not a professional academic. All the professional work I've done with mathematics is applied.

I think you're overstating some things, but I mostly agree. My main disagreement is with your implicit premise that the best practical theory should exist at the same level of abstraction as practical applications. The real numbers have been a really successful practical theory. Physicists and applied mathematicians know they don't "really" exist, but more "realistic" alternatives are awkward and messy. The same applies to more extravagant theoretical constructions like Hilbert spaces. They're an extremely nice mathematical setting for applications (e.g. optimal control, approximation theory, finite element methods, quantum mechanics). No-one should be losing much sleep over their ubiquity in applications. If your point is that we shouldn't belabor some of their technical details when teaching them to practitioners, sure, but that's already the case.

"Measure theory a la Bourbaki" is probably not what you meant if you did probability theory and statistics. Bourbaki famously sidestepped classical measure theory with sigma algebras by constructing Radon measures as functionals via functional analysis. This is sufficient for many purposes but not for probability theory. First and foremost, sigma algebras in probability theory are not just a technical device to avoid paradoxes with unmeasurable sets. Sigma algebras play a starring role in conditional expectation, stochastic processes and martingale theory.

The best way to appreciate the information-theoretic role of sigma algebras is to look at them in the simplest case, where you have a discrete-time, finite-valued process. Then a sigma algebra is equivalent to a partition of the state space and it represents the information that can be gained from an observation; it's like a random variable without specific values, just the discriminating information from different outcomes. To say that a random variable is measurable with respect to the sigma algebra is to say that its value may only depend on information that can be gained from an observation. A filtration of sigma algebras corresponds to a causal series of observations where the observer learns more information over time.

The conditional expectation of a random variable with respect to a sigma algebra (or partition or other random variable) is another random variable that tells you the expectation over the states consistent with a given observation; this new random variable is measurable with respect to the sigma algebra you conditioned on, which as mentioned earlier means it only depends on the information gained from an observation. The conditional expectation is the best least-squares estimator given the information from an observation in the same way that the usual expectation is the best least-squares estimator given no information.

You represent everything that is wrong with "fans" in entertainment culture and games in particular. Your comment is not only hateful but ignorant and anti-worker. The people who suffer in layoffs are workers, not high-level directors; even if a few directors got laid off, they have a financial cushion and can pick up the phone and have new offers within the week. The directors don't deserve your hate either, but gloating over mass layoffs is especially cruel and stupid.

Does he communicate this poorly within his own organizations? Clarity is the most basic quality in leadership.

The only serious difference between classical AD and newer efforts like this is that they have an intermediate language ("what goes on the tape") with recursion and control flow operators which ideally lets them implement front-ends for normal programming languages.

You can achieve the same effect with classical AD by doing what PyTorch does in its default mode where the dynamic recursion and control flow is normal Python code and large tensor ops are asynchronously scheduled on the target device and an AD tape for that particular dynamic run is constructed each time. But the viability of PyTorch's approach is domain dependent: there are relatively few but large tensor ops, and while host-device synchronization is possible (for making the dynamic control flow dependent on intermediate device-computed results) it's also very costly. Although the first of these would be slightly less critical if the host language executed faster.

But, if you're not trying to achieve the kind of decoupling between host and device which PyTorch and similar frameworks want, then I don't see any particular reason you can't just use normal forward-mode or reverse-mode AD as an alternate scalar execution mode for existing code, which just needs a different interpreter/library, not a different intermediate language. For the purposes of differentiation, the branching and control flow operators don't exist, anyway. E.g. if you represent branching explicitly in your graph/tape as TensorFlow does, the subgradient of if(a, b, c) is just the subgradient of whichever of b or c is selected. The conditional variable a only serves as a selector; if you compute the subgradient with respect to the selector, the answer is always 0 (except for the knife-edge case where it's technically not defined but is treated as 0).

Stochastic and mini-batch gradient descent work as well as they do in supervised learning because the function you're trying to minimize is a sum or other loosely coupled aggregation of losses over individual training samples, so you can update based on one sample or mini-batch at a time. That is, you're trying to do model fitting to a data set rather than minimizing the error of some arbitrary function with a ton of parameters; I'm oversimplifying a bit.

A critical feature of model fitting problems is that the data can be normalized across the training set prior to training. Without something like that, first-order methods are almost unusable as black-box methods; you have to do a ton of custom initialization and normalization work for each problem class. They don't have affine invariance although momentum methods can help. If you don't normalize your data or your model doesn't respond well to the usual forms of random weight initialization, you'll blow up or slow to a crawl on even trivial problems like linear least-squares. It's quite shocking that SGD and variants like coordinate descent work as well as they do, but it's important not to draw undue conclusions about its general applicability by understanding what properties of supervised learning problems contribute to its success.

I'm curious if ML experts reading this would strongly disagree with this general assessment. It's not my own area, but I've done a good deal of experimentation and working through things from scratch. If my conclusions are totally off, I'd want them to be corrected.

Anyway, yes, AD is valuable even if you don't use it for optimization. It has many applications in scientific computing and engineering; it was considered one of the great inventions in scientific computing long before deep learning made it mainstream. I have my own reverse-mode AD library and I recently used it for computing the constraint Jacobians for a multi-body simulator and for deriving the discrete Euler-Lagrange equations of motion for a given Lagrangian that's written as a complex expression across several coordinate systems. The Euler-Lagrange equations are then fed to a symplectic integrator to simulate the system. In a problem like that, traditionally you'd symbolically derive and then hard-code the expressions for the derivatives, but they get very gnarly to the point where you need specialized software just to derive the symbolic expressions. AD is great for rapid prototyping and experimentation in applications like that, and once things are settled you can use code generation to lock it down for efficiency and stand-alone use without the AD library.

If Google is like Facebook in this respect then a senior engineer who "meets expectations" in a performance review stands to make at least 15-20% of their salary as a bonus. If you get below "meets expectations" you are probably going to be fired very soon. Hence your "meets expectations" bonus target is essentially no less guaranteed than the base compensation you would also lose out on if you were fired. The bonus target at companies like this is not an "above and beyond" bonus. There are bonus multipliers (and potentially non-standardized discretionary equity bonuses) for higher than expected performance.

By an operator I just mean a transformation. Certainly linear operators like differential operators qualify. The fact that these have an algebra in their own right goes back to work in the 19th century by Felix Klein and Sophus Lie on transformation groups and to later 20th work on linear algebra and functional analysis. It's stuff pretty much everyone learns as an undergrad nowadays, but the fact that you can do algebra on operators hardly without thinking is a relatively modern perspective.

Indeed. There were 18th century mathematicians like Gauss who realized the importance of the geometric nature of complex numbers, but it didn't become central to the subject until the 19th century. The appearance of imaginary numbers as formal square roots of negative numbers goes back to the mid 16th century. As for Cartesian coordinates, i^2 = -1 has an intrinsic, coordinate-free interpretation in terms that would be instantly recognizable to the ancient Greeks, but it's certainly true that this way of thinking wasn't at the basis of the discovery and initial development of complex numbers, and thinking of geometric operators as generalized numbers would have seemed pretty alien for most of the 19th century as well.

They could call it the MIT Computer Science & Artificial Intelligence Laboratory.

> The borrow checker only cares about memory safety, and index accessors are implemented in a memory safe manner (whether that's panic!ing or returning an Option<>).

Reductio ad absurdum: Implement the entire heap as a single array with typed views and you have the asm.js model. Memory safety is ultimately just another class of bug and it's worth keeping the end goal in mind. (And the asm.js approach is resistant against smashing the return address even if the hosted application has buffer overflows out of every orifice, and of course it provides isolation from the rest of the host process, so segregating the heap into a separate memory space has real security value.) I use indices and tagged handles instead of pointers in low-level C code all the time for sound engineering reasons as it's often the superior solution (and the move to 64-bit pointers created further incentives), but I think skepticism is warranted towards the growing Rust prescription of indexed arrays whenever you're dealing with non-tree-structured data.

Probably the greatest thing about pointers is that they enable generic code without any abstraction cost. It's painful enough to work in a language like Java with object references but without interior pointers to array elements or structure fields. You may feel tempted to introduce a case-specific 'fat pointer' pairing of an array reference with an index, which is not only awkward to work with but puts you in the absurd situation of having an index type which will often round up to 16 effective bytes on a 64-bit platform due to packing alignment for the next value in memory, when often one of the goals of replacing pointers with indices on a 64-bit platform should be to reduce the size from 8 bytes to 4 or 2 bytes.

Memory usually accounted for a majority of the cost in those days, so there's a lot to be said for a unified memory system in home computers. The standard memory architecture for home computers from 8-bits like C64 to 16-bits like Amiga was unified memory with half the memory cycles each going to the CPU and graphics, and PCM playback on later systems could conveniently steal a few graphics memory cycles during hblank. (The C64's VIC-II also stole CPU memory cycles every 8 scanlines and could be forced into stealing a lot more bandwidth with the 'badlines' technique.) ROM-based arcade machines and consoles generally had memory parallelism for their graphics systems. It puts heavy pressure on the chip pin-out and it requires you to physically allocate the RAM/ROM chips onto different buses. I guess theoretically you could put all the memory chips on multiple buses with a configurable arbiter in front of each so you could change the allocation per application, but the PCB for that would be massive and expensive. Instead there was usually a slow, awkward way to access memory from a different bus, e.g. the graphics bus could be accessed by the CPU only with DMA or a pair of memory-mapped addr/data registers with multi-cycle wait states. So, this kind of architecture isn't really suitable for a general-purpose home computer unless you can afford a large allowance of memory for each bus, but it did exist on high-end home computers like the X68000 that were less cost constrained. Also, Amiga did have the option for a kind of RAM expansion called Fast RAM which was only accessible to the CPU, unlike normal Chip RAM which was accessible on the standard chipset bus to the audio and graphics chips in addition to the CPU. Fast RAM didn't speed up the graphics system but it prevented the CPU from stalling when the other chips wanted to steal CPU memory cycles on the chipset bus (they always take precedence since they have hard real-time constraints).

Agreed with your historical information, but the comment about function calls and calling conventions is not without merit. If you have 256 architectural registers you still can't have more than a couple callee-save registers (otherwise non-leaf functions need to unconditionally save/restore too many registers), and so despite the large number of registers you can't really afford many live values across function calls, since callers have to save/restore them. Register renaming solves this problem by managing register dependencies and lifetimes for the programmer across function calls. With a conventional architecture with a lot of architectural registers, the only way you can make use of a sizable fraction of them is with massive software pipelining and strip mining in fully inlined loops, or maybe with calls only to leaf functions with custom calling conventions, or other forms of aggressive interprocedural optimization to deal with the calling convention issue. It's not a good fit for general purpose code.

Another related issue is dealing with user/kernel mode transitions and context switches. User/kernel transitions can be made cheaper by compiling the kernel to target a small subset of the architectural registers, but a user mode to user mode context switch would generally require a full save and restore of the massive register file.

And there's also an issue with instruction encoding efficiency. For example, in a typical three-operand RISC instruction format with 32-bit instructions, with 8-bit register operand fields you only have 8 bits remaining for the opcode in an RRR instruction (versus 17 bits for 5-bit operand fields), and 16 bits remaining for both the immediate and opcode in an RRI instruction (versus 22 bits for 5-bit operand fields). You can reduce the average-case instruction size with various encoding tricks, cf. RVC and Thumb, but you cannot make full use of the architectural registers without incurring significant instruction size bloat.

To make the comparison fair, it should be noted that register renaming cannot resolve all dependency hazards that would be possible to resolve with explicit registers. You can still only have as many live values as there are architectural registers. (That's a partial truth because of memory.)

There are of course alternatives to register renaming that can address some of these issues (but as you say register renaming isn't just about this). Register windows (which come in many flavors), valid/dirty bit tracking per register, segregated register types (like data vs address registers in MC68000), swappable register banks, etc.

I think a major reason register renaming is usually married to superscalar and/or deeply pipelined execution is that when you have a lot of physical registers you run into a von Neumann bottleneck unless you have a commensurate amount of execution parallellism. As an extreme case, imagine a 3-stage in-order RISC pipeline with 256 registers. All of the data except for at most 2 registers is sitting at rest at any given time. You'd be better served with a smaller register file and a fast local memory (1-cycle latency, pipelined loads/stores) that can exploit more powerful addressing modes.

newLISP was the butt of half the jokes on #scheme over a decade ago. I'm surprised it had enough uptake to stick around. Uniquely for a Lisp, all objects are deep-copied by value when passed around. It also doesn't have closures. To get around these and other limitations, it has a notion of contexts that are auto-dereferenced ("default functor calls") so you can pass values by reference with syntactic sugar. At least that's how I remember it--not sure how much has changed. The way you emulate closures in newLISP is morally similar to how cl.el does it for Emacs (true lexical closures are a late addition to Emacs Lisp), namely by generating a completely new function for each closure instance, with the closed-over values in the environment hard-wired into it.

In my opinion, you can find much better versions of this sort of thing in Tcl, if for some reason you really want it.

Props to the author for keeping it going for this long, though.

Yeah, if you use the Moser-de Bruijn sequence for constructing a pairing function you just get bit interleaving. You define the map expand(x_0, x_1, ..., x_n) = (x_0, 0, x_1, 0, ..., 0, x_n), apply it to x and y, multiply expand(y) by 2 to shift it over, and add them to merge the now disjoint even/odd positions. Incidentally, this decomposition of the problem is exactly how you efficiently implement bit interleaving in software except you don't even need addition:

    z = interleave(x, y) = expand(x) | (expand(y) << 1)

For the inverse you define the map compact(x_0, x_1, ..., x_2n) = (x_0, x_2, ..., x_2n) and then

    uninterleave(z) = (compact(z), compact(x >> 1)) = (x, y)

The expand map can be implemented efficiently as a logarithmic number of shift-and-merge stages, and compact can be constructed by inverting each stage separately and composing them in reverse order. A stage has this form:

    x' = x | (x << n)

You sometimes also see it written with xor. That's not necessary. What you care about is that the operation is bitwise (e.g. no carries from addition) and it must have 0 as an identity.

If x has 2n bits then this is reversible: the lower n bits in x and x' are the same, and the upper n bits in x and (x' >> n) are the same, so you can recover all 2n bits of x from x' with low(x') | high(x' >> n). You can cascade stages like this if you alternate them with appropriate masking to allow data-parallel operation. The net effect of the first stage, after masking, is to shift the upper n bits of x up by n bits while leaving the lower n bits in place. The next stage then does the same thing on the two halves in parallel with a shift of n/2, and so on until you're done. The masking prevents cross-talk between subvectors so you can operate on a single vector as if it were a set of independent subvectors. Or put another way, it enforces the precondition for the reversibility of each stage.

Anyway, just some random connections to low-level hacking.

There's a simple recipe for arithmetically encoding recursive algebraic data types (in the functional programming sense) which is related to this.

What you might have seen is Goedel numbering where a finite sequence of natural numbers a_0, a_1, ..., a_n (where n isn't fixed but can vary per sequence) is mapped bijectively onto p_0^a_0 a_1^p_1 ... a_n^p_n where p_0, p_1, ... is an enumeration of the primes.

However, if you want to represent trees instead of sequences, you have a better, simpler option. The key is the existence of a bijective pairing function between N^2 and N, which you can write as <m, n> for m, n in N.

You have a lot of choices for how to construct the pairing function. But a curious fact is that there is essentially one polynomial pairing function and it's the one you saw in class when you learned that the rationals are countable: https://en.wikipedia.org/wiki/Fueter%E2%80%93P%C3%B3lya_theo....

From this perspective it should be clear that bit interleaving provides one such pairing function.

Here's a larger example of how you can use this for encoding algebraic data types. The data type in this article is an unlabeled binary tree:

    data Tree = Leaf | Node Tree Tree

I will use square brackets to denote the encoding. Then

    [Leaf]     = 0
    [Node a b] = 1 + 2*<[a], [b]>

So the tag for the sum type is the residue modulo 2, and if the tag is 1 you can divide by 2 (shift right by one bit) to extract the encoded pair of subtrees. If the sum type had three terms you could use 3 instead of 2:

    data Tree = WhiteLeaf | BlackLeaf | Node Tree Tree

    [WhiteLeaf] = 0
    [BlackLeaf] = 1
    [Node a b]  = 2 + 3*<[a], [b]>

This also works with labeled trees:

    data Tree = Leaf N | Node Tree Tree

    [Leaf n]   = 0 + 2*n
    [Node a b] = 1 + 2*<[a], [b]>

If the label type wasn't a natural number, you'd just recursively encode it.

In the above I treated the <m, n> pairing as a black box that can be implemented in different ways (e.g. Cantor pairing, bit interleaving). You can abstract out the encoding of sums as well. You're looking for a bijection between N and Inl N | Inr N and I made the particular choice

    [Inl n] = 0 + 2*n
    [Inr n] = 1 + 2*n

But you have other options as well, though this is probably the simplest. And once you have an encoding for sums and products you can apply them recursively to encode any recursive algebraic data type.

Note that the sum and pair encoding functions are bijective on the natural numbers, but the corresponding encodings for algebraic data types aren't necessarily bijective, only injective. For the unlabeled binary tree example, the number 2 has a tag of 0 (leaf) but isn't the encoding of any tree. However, the encoding for labeled binary trees is bijective if the label type is bijectively encoded. The problem with this kind of recursively constructed encoding that terminates in finite types is that you obviously cannot have a bijection between a finite set and an infinite set like N.

To tie it back into the article, he uses this encoding:

    data Tree = Leaf | Node Tree Tree

    [Leaf]     = 0
    [Node a b] = 1 + <[a], [b]>

You can extend this to my example with two kinds of leaves:

    data Tree = WhiteLeaf | BlackLeaf | Node Tree Tree

    [WhiteLeaf] = 0
    [BlackLeaf] = 1
    [Node a b]  = 2 + <[a], [b]>

Note that the tag ordering is all-important here. This only works when the tag ordering is "tail recursive". If you used 0 as the tag for Node, then there'd be an ambiguity between leaves and proper subtrees; you wouldn't know if 1 corresponded to a leaf or 0 + encoded_subtree_pair.

So, this kind of prefix-sum encoding is bijective but can only accommodate one unbounded term, which must be assigned the final tag. No tag ordering can work for this:

    data Tree = Leaf | WhiteNode Tree Tree | BlackNode Tree Tree

    [Leaf] = 0
    [WhiteNode a b] = 1 + <[a], [b]>
    [BlackNode a b] = 2 + <[a], [b]> // Wrong!

I haven't thought about ordinals for a long time, but this feels related to the fact that 1 + ω = ω is not equal to ω + 1.