-
Notifications
You must be signed in to change notification settings - Fork 438
I've got a basic understanding of Symmetric Interaction Combinators at this point, but I'm still trying to understand how HVM overcame the performance issues of a graph representation of interaction nets. From How.md:
This demanded a lot of pointer indirection, making it slow in practice. A new memory format, based on the Interaction Calculus, takes advantage of the fact that inputs are known to be λ-terms, allowing for a 50% lower memory usage, and letting us avoid several impossible cases. This made the runtime 50x (!) faster, which finally allowed it to compete with GHC and similar.
The excessive pointer indirection causing slowness fit my intuition as far as the performance of evaluating a graph, but I'm still unsure how HVM overcomes this. Reading through the excellent comment in memory.rs seems to indicate that everything is still made up of a list of nodes in linear memory that use pointers to reference the other nodes. How does this avoid the pointer indirection problems?
I found this old comment from 2016 by @VictorTaelin that talks about the pointer spaghetti issue, and how the LPU worked around it with "movement rules" which end up a kind of 1D celular automata that will move data between adjacent cells, making each of the cell kernels 100% local.
That idea sounds amazing to me, and seems like it could translate to hardware really well ( from my limited knowledge ), but it doesn't seem to be what HVM uses. It seems from memory.rs that HVM uses pointers again!
I'm trying to figure out what I'm missing: the key to that 50x speed-up that HOW.md talks about.
I'm also curious whether it's possible to efficiently implement interaction nets alone with the same performance, without having to think in terms of lambda calculus, and only deal with interaction nets.
As far as I've read, interaction calculus is just a textual representation of an interaction net, so we should be able to deal with interaction nets directly ( though obviously it'd be hard to write ), without changes if I understand correctly.