Deserializable ast nodes

[branchseer]

Deserializable ast nodes (and types in oxc_semantic) open up possibilities for persistent cache in oxc-based bundlers (rolldown/rolldown#802).

Since ast nodes borrow data from the allocator, deserialization is a bit trickier to implement than serialization (requires stateful deserializer). Here are my current findings:

• serde has DeserializeSeed for such case, but it's quite limited and doesn't support nested borrowing types: Collections compatibility with Serde fitzgen/bumpalo#63 (comment).
• bincode2 currently doesn't support stateful deserializer. I managed to implement it in Decode context bincode-org/bincode#710, but I'm not sure if it'll get accepted.
• rkyv supports custom deserializer as a type param D in its Deserialize trait, I think this is doable with something like Deserialize<SomeAstNode<'alloc>, &'alloc Allocator>, although I haven't actually tried it.

Before further digging I want to ask if contributions on this feature are welcomed? If so, I suggest to firstly introduce a central proc macro for (de)serialization attributes, like what swc does, so that whatever deserializing attributes we need up using, we'd only need to add them in one place.

[Boshen]

Interesting, we already have 2 directions that are touching the AST, there may be things you can leverage.

• AST transfer WIP #2457
• WIP: AST Traverse #2987

Given we are going to have 3 PRs touching the AST, and I'm the anti-macro guy on this project, I wonder whether we should start doing some codegen scripts for these kind of things. e.g. https://github.com/facebook/hermes/tree/main/unsupported/hermes/crates/hermes_estree_codegen

I don't mind exploring new things, but I'm kind of busy until end of May, so I may be slow to respond.

If you have questions, you may ask them on discord https://discord.gg/9uXCAwqQZW for quicker feedbacks.

For deserialization, @overlookmotel may have thought about it, but he is busy as well 😅

[Boshen]

Parsing is so fast in Oxc, deserialization may end up being only a few times faster. And most files gets processed in the milliseconds range 🤔

[overlookmotel]

Hi @branchseer. You are bringing up some really interesting issues (this and #2943). I like your style!

I do think this is worth looking into.

I looked into speeding up serializing/deserializing when I made my first attempt at AST transfer (#2457) a couple of years ago on SWC. I found that even rkyv wasn't fast enough for my liking, and ended up building my own serialization library ser_raw - which is gloriously simple, and therefore also extremely fast. I abandoned the effort on SWC in the end as the maintainers weren't interested, and so I never completed ser_raw either, but it might be a useful starting point.

Oxc also has a major advantage over SWC for this kind of thing, in that all the AST data is already clustered together in the arena allocator's buffers. So to write to cache, you could just dump the entire contents of the arena to disk without any serialization step.

For restoring from cache, then it doesn't need deserialization in the usual sense. All you need to do is pull the data back from disk into memory, "rehydrate" the arena, and offset all the pointers in the data (Box, Vec) by new_bump_address - old_bump_address. Then cast pointer to &mut Program, and off you go again.

Correcting the pointers is easier said than done, though. I imagine would need either:

1. write a list of all pointer locations to cache, to know where they are when "rehydrating", or
2. traverse the AST and update pointers when "rehydrating" (difficult because you must avoid treating the AST data as Rust types until after the pointers are updated, or you'd create invalid & refs, which would be UB).

abomination (which ser_raw was inspired by) does something like the latter, but their implementation is unfortunately unsound.

But, either way, if a way of doing it can be found, it would blow the pants off every other ser/deser scheme that's out there. Assuming read speed of the disk containing the cache is fast, no matter how stupendous the speed of Oxc + Rolldown, I imagine that this would still be a significant speed-up, because it'd be doing practically no work.

I hope these thoughts are of some interest to you. Sorry they're a little unfocused. I'm afraid that like Boshen, I am completely tied up for a while so wouldn't be able to give much time to this for a few months, but very happy to trade thoughts if you want to go further with it.

[Boshen]

We can fork or build our own allocator.

[branchseer]

Thank you both for your insights! I understand you are busy. I'll leave my random thoughts here. To pressure to respond ;)

Given we are going to have 3 PRs touching the AST, and I'm the anti-macro guy on this project, I wonder whether we should start doing some codegen scripts for these kind of things. e.g. https://github.com/facebook/hermes/tree/main/unsupported/hermes/crates/hermes_estree_codegen

This reminds me of my little experiment: https://branchseer.github.io/tser. Maybe it could be somewhat helpful to the codegen approach?

Oxc also has a major advantage over SWC for this kind of thing, in that all the AST data is already clustered together in the arena allocator's buffers. So to write to cache, you could just dump the entire contents of the arena to disk without any serialization step.

Very intriguing concept! I wonder how much unused data are in the arena, (like when a Vec grows, the old content won't be collected). I guess not too much and negated by the performance boost?

All you need to do is pull the data back from disk into memory, "rehydrate" the arena, and offset all the pointers in the data (Box, Vec) by new_bump_address - old_bump_address. Then cast pointer to &mut Program, and off you go again.

Is this portable across different arch/os? I mean we don't need think about portability when transfering ast in memory, but it's a good feature for disk caching.

[overlookmotel]

This reminds me of my little experiment: https://branchseer.github.io/tser

Interesting. I think NAPI-RS is basically doing the opposite in reverse - create TS types from Rust types.

I wonder how much unused data are in the arena

Not measured it, but a bit. As you say, when a Vec grows, the old allocation is not freed or reused, so is wasted bytes. But to be honest I don't think it matters too much - it's not enough to make a huge difference.

Is this portable across different arch/os?

No. Also not portable across different versions of Oxc. When the oxc_ast crate is recompiled, the compiler does not guarantee that type layouts won't change (strictly speaking, in practice they don't). However:

1. If the use case is local caching, portability is not a concern. On the same machine, and same version of Oxc, the format would be completely stable (i.e. you can reboot the machine, and then read back cache from disk no problem, only upgrading Oxc would invalidate the cache).
2. It would be helpful for AST transfer if all AST types were #[repr(C)], so that may happen in future. If it did, it would give stronger guarantees that data layout is stable across different versions of Oxc, and also across different machines (as long as the machines all use same pointer size and endianness - not really an issue, who is using 32 bit or big-endian archs?).

For a shared cache, I do wonder if network speed would be a bigger bottleneck than compilation speed. i.e. Maybe Oxc can parse/transform/etc faster than it takes to transfer AST over network. ASTs are pretty big. So I think local cache is a stronger use case.