Hacker News Reader

Comment by wyldfire | Hacker News Reader

> In it he describes how a parsed clang AST regularly consumes 50x more memory than the original source code!

I guess that seems like a lot but the context I'm missing is - how good could it get? I mean, if you want to preserve source locations of each token and you need to encode enough information in the AST to properly recover, what's the ideal growth factor over the original? 1.5x? 15x?

View on HN

If you can achieve a memory savings of 30%, say, that would be pretty big news. If you can only achieve a 30% memory savings by doing things to the compiler that make it harder to work on the compiler in the future, then it's probably not worthwhile. But if you can achieve an 80% memory savings by doing violence to the compiler, that might be worth the trouble.

As for what's an ideal source->AST expansion factor for a language that has a user-friendly compiler that's also compiler dev-friendly, that's hard to say. Clearly 50x is workable.

In TFA the 50x expansion factor is used as a motivator for automating a particular type of optimization. It'd be very interesting to see a Rust vec-of-enums that automatically deconstructs enum values into tags and opaque values that it could store in a struct-of-arrays like TFA does in Zig. The places to bury unsafe use into for this would not be many.

Maybe I'm just dumb but isn't the endgame of vec of enums going to be an ECS?

And the end game of ecs is a columnar rdbms

As a point of comparison, I think simdjson tape is only ~3x larger than the original document. Much of this could be saved if one did things like stuffing numbers into only one tape slot or not copying strings that have no escape sequences in them (instead referencing their location in the original document).

The largest overhead you could achieve is apparently 8x for a document that is mostly the characters "[]" or also 8x for a document that is mostly the characters "0,"

There's a ton more context that needs to be held in a clang AST node compared to a JSON doc. Just to mention a few: file source, token range, expr/stmt/decl statements and their relation, macro expansion related info, and tons of diag to be able to walk back to the original source token, and padding added by the compiler in those data structures.

Source code is surprisingly compact.

As for one data point on how much better it can be, here is Zig's own parser, parsing Zig's own parser:

    # Source bytes:       139 KiB
    # Tokens:             24646 (120 KiB)
    # AST Nodes:          10998 (140 KiB)

Each token is 5 bytes which is pretty minimal (1 byte tag + 4 byte file offset). AST Nodes are also encoded compactly and non-uniformly, in this case coming out to roughly 13 bytes each. Despite these minimal encodings, the parse tree comes out to almost 2x the size of the source file in this case. 2x is a lot better than 50x though.

Source: zig ast-check -t lib/std/zig/Parse.zig | head -n7

> 2x is a lot better than 50x though.

the 50x metric was using something like this AST analysis mechanism (and not a system metric like resident set size)?

I think you should just watch the linked talk. It’s excellent. Though they don’t put exact numbers on it iirc (perhaps too early to be confident – they might be small due to missing data they don’t yet realise they’ll need).

Reply on news.ycombinator.com