remix logo

Hacker Remix

Flattening ASTs and other compiler data structures (2023)

157 points by aw1621107 1 week ago | 49 comments

jgrowl 1 week ago

I thought a reddit comment on this article had an interesting point:

https://www.reddit.com/r/rust/comments/1d3b356/my_new_favori...

[–]Timzhy0 3 points 7 months ago

Btw I think one can go a step further than the author, there is no need to keep two explicit ExprRef baked in a binary node (lhs, rhs). You can exploit locality, basically the AST, seen it the LISP way, is just an arbitrarily nestable list, where elements are atoms or other lists. Hence all you need to know is where each list ends (and if it's an atom you can assume it spans one node) and actually one bit to know if it is the last entry in the list is quite ergonomic as well (because then you can distinguish whether moving next slot in the AST means there is a sibling). Basically it's easier to keep it sync while constructing and takes up less memory per node. I pay 40 bits per node, stored interleaved for best cache locality (some unaligned accesses but I think it's still worthwhile), 8 bits for the tag, 32 for the data, if data is bigger, 32 is an index into some auxiliary segment (basically a ptr).

catgary 1 week ago

An arbitrarily nestable list is a tree, no?

dmagyari 1 week ago

"Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array." Zig compiler pipeline (AST, Zir, Air, Sema) does exactly this on all layers. Not only contiguous, but instead of array-of-structs it is struct-of-arrays, so walking the tree is even more cache friendly. For AST see: https://github.com/ziglang/zig/blob/master/lib/std/zig/Ast.z...

gritzko 1 week ago

I work on a C dialect where everything is flattened. JSON and other trees in particular. Binary heaps are flat, merge sort and iterator heaps are absolutely great, can build LSM databases with that. Stacks, circular buffers, hash maps, etc, all flat. Templated output (PHP like) is done by a flat data structure.

https://github.com/gritzko/librdx/blob/master/abc/B.md

Apart from locality and lifetimes, these flat data structures improve composability. When every data structure is a flat buffer, you can mmap them or zip them or send them by the network, all by the same routine. They are uniform like bricks, in a sense.

rurban 1 week ago

I worked in a language where all datastructures were "flattened", could be trivially serialized to disk, and read in again. Called print and read. The language was called lisp. All flat, just parens.

Some of my compilers export the AST as lisp trees. Much smaller and more readable than json, and it can be executed. Uniform like bricks

vanderZwan 1 week ago

> All flat, just parens.

So not flat then. Prefix is not postfix. Forth, and most concatenative languages, are much closer to actually bein, flat.

Lisp is trivial to flatten, but that's not the same thing.

agumonkey 1 week ago

Makes me wonder if people in APL/J/K community have not been influenced or influencing this kind of technique. IIRC Aaron Hsu does tree processing through arrays (but i'm not skilled enough to analyze his code)

gsf_emergency 1 week ago

Do you have a link to such an example of Aaron's code? Thank you in advance!

082349872349872 1 week ago

https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-...

Iverson's 1962 book also mentions tree representations, see pp45-62: https://archive.org/details/aprogramminglanguage1962/page/n6...

gsf_emergency 7 days ago

Thanks. Was hoping for low-level code that might even blow a deue(I?)ng(m?)ker's mind on THE semantics-syntax duality..

This was closest: https://www.dyalog.com/blog/2018/01/stackless-traversal/

Your links should still be useful for orienteering!

agumonkey 1 week ago

Can't remember where exactly but he did demo his code in talks/conferences with links.

gsf_emergency 7 days ago

I've given up on finding relevant low-level CUDA(? tacit? asm??!!) code from Hsu*, but I did push the following to my to-watch stack

https://youtu.be/z8MVKianh54

Does APL need a type system

Guess it's time to reverse whatever else I can find

https://www.dyalog.com/uploads/conference/dyalog16/prerequis...

*Bad faith, or just a run o' the mill, aka compleatly forgiveable profiteering?

gsf_emergency 6 days ago

Ahh apologies

https://news.ycombinator.com/item?id=13797797

https://news.ycombinator.com/item?id=13576176

082349872349872 5 days ago

He must be referring to https://dl.acm.org/doi/pdf/10.1145/2935323.2935331 ?

Just looking at refs for the moment: Henglein and Hinze's discriminators are interesting, whenever you come back up for air. (are they also amenable to sorting codata?)

The oft-cited R Bernecky is, IIRC, also known as "Boolean Bob" for his SWAR-style algos. EDIT: nope, confused him with R Smith: https://aplwiki.com/wiki/Bob_Smith

(I once asked Boolean Bob if any of his tricks went back to the card processing days —I could even believe the keyed tree* might?— but he was too young to know, and the people he'd have liked to ask are no longer available.)

EDIT: Aardappel also has some interesting languages: https://strlen.com/#programming-languages

* for manipulating Bills of Materials despite the linearity of card decks?

EDIT2: compare "§3.2.1 Constructing Node Coordinates" (p34) with [T in "Table 1.19 Full list matrices of the tree of Fig. 1.16" in A Programming Language (p50): https://archive.org/details/aprogramminglanguage1962/page/n6...

        Fc
  1 0 0 0 0
  1 1 0 0 0
  1 1 1 0 0
  1 1 1 1 0
  1 1 1 1 1
  1 1 1 1 2
  1 1 1 1 3
  1 1 2 0 0
  1 1 2 2 0
        Ec
  1 0 0
  1 1 0
  1 1 1
  1 1 2
  1 1 3
  1 2 0
  1 3 0
  1 3 4
  1 3 5
  1 3 6
[all three appear to be 1-origin, probably due to the phenomenon mentioned in the footnote on p49 of APL]

gsf_emergency 5 days ago

Thanks!

[Too low global b/w to feel the adrenalin.. wow.. what was your deduction chain for figuring how BoMs was next item on my stack? Guessing you started from assumption that pure bits mongering are not on the boundary of my ikigais(yet)]

On the heap, I (re)surfaced "Typed Array Intermediate Language" slides, but too low (local) b/w to try to find out^W^W^W^W sus out if this or smth v similar is already in dyalog.com's workflow.

https://news.ycombinator.com/item?id=11974936

>Bernecky

https://news.ycombinator.com/item?id=11963548

What were those slides about formalizing Euclid ?

[Medium b/w vibing that multiplicity of edits is a precise estimate of flow-of-war, ~ webpage memory usage is an accurate estimate of just how well run the entire organization is..]

082349872349872 3 days ago

still haven't refound the slides — every 5 or 6 weeks I get a new idea of who it might have been, but so far to no avail...

[BoMs were complete coincidence]

gsf_emergency 3 days ago

Edit: really appreciated WvO recording his early hopes.. have seen undergrads doing this, but a doc? a first for me!

https://www.weizmann.ac.il/mcb/alon/sites/mcb.alon/files/use...

gsf_emergency 3 days ago

Slides & conspiracies..

For an vulpine organ they speak very confidently of the f-o-w

https://xcancel.com/benln/status/1873459290562056566

082349872349872 1 day ago

Using kendō vocab I think what they're trying to say with f-o-w is to avoid 2 of the 4 fails: 疑, and (or at least?) 惑.

(interesting that 平常心 is unmarked, while in english the desired state of mind[heart] is marked)

No slides yet, but I finally dug up the quotation I'd promised you last year: Körner, The Pleasures of Counting (1996) p.413 ch.17 "Time and chance" in a footnote (arrived at via a path starting with Enigma decodes!):

> Social Darwinism applies the Darwinian doctrine of survival of the fittest to human society. Rich social Darwinists take wealth as the best indication of fitness to survive, academic social Darwinists take intellectual achievements as the best indication and so on. They are often haunted by the fear that the unfit do not understand this and may outbreed the fit.

gsf_emergency 10 hours ago

Update:

What sort of [social-]darwinist might KDA be??? (Ditto for Angus Deaton)

(Just trying to find out how I'd come across .. not as an organizational darwinist ???? ))

https://www.project-syndicate.org/commentary/us-skilled-immi...

TIL: JS modelled Luggnagg on 蓬莱 (& thus struldbrugs on Tensens??? )

Edit: my oftcited dream of future days took place in a cavernous, subtidal (glass of scifi strength) shopping mall (consumerist pleasure dome) of the same (near) future..

On Jeju island

gsf_emergency 14 hours ago

疑 is a common failure mode for foxes, yes. 惑 might be interesting for me to consider in the musk-jobs case studies (roughly corresponding to where the confidence shall be reconsidered?) How about OCD? Subset of 惑? Could lead to failure-to-ship for designers..

https://www.thepsmiths.com/p/review-reentry-by-eric-berger

>Part of what makes “founder mode” so effective is that startup founders have both a compensation structure and social permission that lets them treat every single issue that comes up at work as if their family is about to die

(The field promotions and war stories also remind me of 1796-1797)

Aha thanks.

a quick de-Maistre-style counter response before I dive in

  social-darwinists.ch
Would you say (the proddy part of) CH culture is largely pre-1939 compared to the most of the rest of teutonia (some hills of ostmark excepted..& liechtenstein)

(Or even pre XVIII, leaving out AT et al if we review the antisemitism?)

Edit

非常口,平常心?

torginus 1 week ago

I guess Rust's contribution to high performance programming is that its borrow checker is so loathsome that it pushes people into using ideas like ECS or arenas just to not have to bother with it.

kazinator 1 week ago

> Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array.

This happens naturally if you bump-allocate them in a garbage-collected run-time, particularly under a copying collector. Free lists also tend to co-locate because they are produced during sweep phases of GC which run through heaps in order of address.

Don't make me bring out the L word for the billionth time.

> A flat array of Exprs can make it fun and easy to implement hash consing

OK, it's not a case of L-ignorance, just willful neglect.

samps 1 week ago

FWIW I did acknowledge this in the article:

> A sufficiently smart memory allocator might achieve the same thing, especially if you allocate the whole AST up front and never add to it

> Again, a really fast malloc might be hard to compete with—but you basically can’t beat bump allocation on sheer simplicity.

layer8 1 week ago

And if you don’t need more than 32 GB of heap space, the JVM also gives you the ability to reduce reference sizes to 32 bits, with compressed references. (Due to alignment requirements, the lower 3 bits of a pointer are zero and hence do not need to be stored, which effectively gives you a 35-bit address space.) Of course, the presence of object headers counteracts this to a certain extent.