4 ms·
The changes to the IR data structures in this release are really neat- whole trees and graphs fit in a small fixed number of flat arrays. This saves on allocati
by Rusky 5y ago
The changes to the IR data structures in this release are really neat- whole trees and graphs fit in a small fixed number of flat arrays. This saves on allocations, saves on total memory usage, and makes them trivial to serialize because there are no pointers.
I recently arrived at a similar design for manipulating NFAs as adjacency matrices, as a replacement for more pointer-y adjacency lists, by way of sparse matrix data structures. Rather than Zig's performance angle, I found that it made whole-graph operations much easier to implement and reuse.
I've also seen similar approaches from array languages like APL, for example this project for running this kind of stuff on GPUs: https://github.com/Co-dfns/Co-dfns https://github.com/Co-dfns/Co-dfns
And, I've seen it in Rust as a "workaround" for the borrow checker, where that framing tends to make it feel like cheating or settling, which IMO is unfortunate since when people arrive at it for other reasons it seems to have a lot of other benefits!
There are probably more contexts I'm not familiar with- anyone have any good examples from domains they've worked in?
- gnuvince 5y ago> And, I've seen it in Rust as a "workaround" for the borrow checker, where that framing tends to make it feel like cheating or settling, which IMO is unfortunate since when people arrive at it for other reasons it seems to have a lot of other benefits! Great point! I've been using Rust for 4–5 years now and putting objects in Vecs and using integers as "pointers" felt a lot like cheating (i.e., "I'm doing the wrong™ thing!"), but every time I tried to "fix" things to use references my code ended up uglier, harder to understand, and sometimes slower. In time, I've learned that it's perfectly fine way to structure data. And as you point out, it makes it easier to work on a large structure structure itself rather than having to go through its individual components (e.g., you can manipulate all the nodes in a graph with a simple for loop rather than having to do a DFS/BFS traversal).
- oconnor663 5y agoThis is basically what an Entity Component System is, right? I always find myself linking back to this talk: https://youtu.be/aKLntZcp27M https://youtu.be/aKLntZcp27M
- b3morales 5y agoCan you point out the section of the release notes that discusses this change? I'd like to read more and I'm not able to figure out what you're referring to.
- raphlinus 5y agoIt's how the internal "AST" for Markdown is represented in pulldown-cmark - a Vec of a node enum. A major motivation was reducing the allocation cost (it's extremely common to do one allocation per node for this kind of thing), but another benefit is that a tricky "splice" information for inline markup (basically, moving a sequence of text spans, possibly with their own emphasis, between two asterisks into a subtree) is pretty easy to represent.
- jodrellblank 5y ago> "his saves on allocations, saves on total memory usage" Co-Dfns is Aaron Hsu's project, and he has a talk[1] on a compiler implemented in a nano-pass style, once in Racket, once in Chez Scheme[2] and once in Dyalog APL, each using CPU and GPU. For compiling an AST with ~16 million nodes, he gives benchmark figures that Dyalog APL takes 64MB RAM to hold it, Racket takes 1051MB and Chez Scheme takes 1485MB. His provocative statement for the talk is "pointers are the refined sugar of programming". The APL version is 1/50th of the lines of code[4], runs typically 9x faster on the CPU, 50x-200x faster on the GPU, despite being interpreted by Dyalog vs compiled Scheme. There are benchmarks where the APL version loses in runtime, under 1k lines of code (which he calls "tiny tiny") so lots of startup overhead and not enough big arrays to gain ground on. He has one talk (available on YouTube) about his approach to using arrays to working with tree structures in a high-performance way in APL[3]. [1] https://www.youtube.com/watch?v=UDqx1afGtQc https://www.youtube.com/watch?v=UDqx1afGtQc [2] he used to be on the Scheme R6RS steering committee, so he's not new/inexperienced with it http://www.r6rs.org/steering-committee/election/electorate.html http://www.r6rs.org/steering-committee/election/electorate.h... [3] https://www.youtube.com/watch?v=hzPd3umu78g https://www.youtube.com/watch?v=hzPd3umu78g [4] 17 lines of code which took a PhD researcher (him) 5-10 years to write, mind you.
- sitkack 5y agoTwo issues here, we are at a memory wall, and if system X takes 64MB and system Y takes 1024MB, that is 4 doublings. So the 9x faster number holds. APL in this case is like being 4 Moore Units ahead of everyone else. The other one is that, separating the thing from the representation of the links between things is not unlike a set of basis functions forming a high dimensional space. The indices into the store forming a point in that space. Some say Petgraph is a hack, I think Petgraph is a mathematical sculpture.