Comment by gumby | Hacker News Reader

Comment by gumby | Hacker News Reader

The lisp implementations described here had a small number expensive runtime costs (otherwise lisp can, if you wish, be complied into very fast code).

One was the cost of the gc memory barrier (cleverly managed for commodity hardware by using the mmu and toggling the write bits, I think thought up by Solvobarro). I think a slightly more sophisticated trick could be done with some extra TLB hardware to generalize this for generational collectors for any gc language, say Java. Another smart trick would be to skip transporting unless fragmentation got too bad. In a modern memory model compaction just isn’t what it used to be.

A second one is runtime type analysis. With the RISC-V spec supporting tagged memory this could be speeded up tremendously for Lisp, Python et al. Is anyone dabbing chips with that option?

The nice thing today is that a lot of languages are revisiting ideas originally shaken out by lisp, so speeding those languages up can speed up Lisp implementations too.

Ps: wish this article has mentioned the KA-10 (first PDP-10) which was really the first machine designed with Lisp in mind and with an assembly language that directly implemented a number of lisp primitives.

Tagged memory seems to be the only option left to mitigate C's memory corruption issues.

While Intel borked their MPX implementation, it has been successfully adopted on Solaris SPARC, and has been making their way across ARM implementations (v8+) and Apple's. Microsoft's Phonon might have something similar, but very few details are public available.

What are the advantages of tagged memory as opposed to using the unused bits in a regular pointer as a tag?

Usually, tagged memory at a hardware level, goes along with support for tagged operations in the processor.

In the LISP machines for example, you had an add instruction. Which would happily work correctly on pointers, floats, and integers depending on the data type, at the machine code level. Offers safety and also makes the the compiler simpler.

But where this really shines is in things like, well, lists, since the tags can distinguish atoms from pairs and values like nil, fairly complex list-walking operations can be done in hardware, and pretty quickly too. It also makes hardware implementation of garbage collection possible.

This is just my intuition, but I suspect, these days, it all works out to about the same thing in the end. You use some of the cache for code that implements pointer tagging, or you can sacrifice some die area away from cache for hardwired logic doing the same thing. It probably is in the same ballpark of complexity and speed.

In addition to what retrac wrote, these tag bits would apply to immediates as well, not just pointers.

Speed, like is usual with hw vs software implementations of things. But the difference is these days less than it used to be, because processors spend most of their time stalled on all kinds of things and the ALU processing capacity is underused most of the time.

An interesting question for a modern ISA design would be to figure out how to make tagged words and memory work well with SIMD.

> An interesting question for a modern ISA design would be to figure out how to make tagged words and memory work well with SIMD.

Not sure what the issue might be. Let’s say you’re doing a multiply-add: you’d call the one for the data type you want and if any operand were of the wrong type you’d get a fault. Am I missing something?

That sounds like a lot of mode bits or instruction variants to me. But maybe it wouldn't be a problem.

Consider that your SIMD instruction might itself take a tag mask and the ALU need only do equality on the tag field. In fact it could do that in parallel with the ALU op; on mismatch you could simply discard the current state and abort the operation. However realistically you’d want the same set of SIMD instructions as an I tagged architecture anyway.

Also I expect any compiler would assume that the contents of an array subject to SIMD computation would be homogeneous anyway, perhaps trying to enforce it elsewhere.

In any case this doesn’t seem like a big deal to me…but I could be wrong!

Yep, sounds like a good sketch.

I guess to really get into it a good start would be to work with existing SIMD and take a quantitative approach to what is actually the most hot part of it. I wonder if any existing language implementations (eg Common Lisp) attempt to do these kinds of things in the first place.

Reply on news.ycombinator.com