Post

Ok ok this may not make a lot of sense but I am *extremely* happy to have gotten this code working!! So I feel compelled to share. (And yes, I wrote my own macro-assembler for #wasm in JavaScript. That's how much fun I'm having, and yes I mean that sincerely.) 1/x

So, I'm working on compiling @_ohmjs grammars to Wasm. _Recognition_ (does this text match or not) wasn't too bad, and this week I've been working on building parse trees. I'm doing manual memory mgmt (simple bump pointer). This code deals with repetition, which is tricky… 2/x

For many nodes, we know how many children there will be, so we can allocate the correct amount of space directly in the parent node. This is conceptually simple, and cache-friendly too. 3/x

But an iteration node can have any # of children! So when the parent node is allocated, we don't know how big to make it. My solution: • Allocate space for a fixed (power of 2) # of children • If necessary, use the last child slot to point to an overflow node. 4/x

My favourite part is that by using a power of two size, I can: • Use `popcnt` to detect when it's time to grow (when only 1 bit is set) • Use `clz` (count leading zeros) to know how many overflow nodes there are. 5/x

If you're not familiar with these instructions (like me until yesterday 😅) — • popcnt is a Wasm and x86 instruction which counts how many bits are set to 1. • clz (lzcnt on x86) counts the number of leading 0s. Very handy here! 6/x