Validark
commented
1 year ago - Yes, this implementation should be quite favorable towards embedded.
- Reducing the memory footprint of the AST is one of my goals, which is another step towards supporting 100MB of RAM. Of course the biggest eater of RAM by a longshot is LLVM afaik, so cutting the memory consumption of the initial stages of the compiler by half or 2/3's only helps so much.
- I use SIMD for two things, parallel table lookups (4 bit in a 16 byte vector) for utf8 validation and matching character classes like newlines, quotes, identifier characters, etc. The first one I think would have to be done one-by-one without hardware support. The drawback of no SIMD is you have to not use SIMD, haha. The character classification stuff can be done with SWAR though, and I know how to do this if the compiler can't figure it out automagically. So you'll still get some benefits of operating on 8 (or 4?) bytes at once. It will be much less of a benefit than operating on 64 byte chunks at once on the latest desktop hardware, but it's embedded, I'm guessing you didn't think it would run at the exact same speed as a desktop.
- If you are talking about recursive descent over an AST, it's up to the consumer code whether they want recursive function calls to push and pop from the stack automatically or to do it manually. Even if I provided an iterator to wrap this, the consumer code has to look pretty much the same. The only way to avoid traversing an AST is to skip generating one. Andrew Kelley wants the compiler to solve this by perhaps automatically moving the stack to the heap for potentially infinite recursive calls or just setting a limit at compile time for stack usage and somehow giving back an OutOfMemory error if it comes to that. I personally haven't seen any proposed syntax for that yet so I'm not sure how much Andrew already knows how that's going to look but I think the horse to bet on is recursive function calls. As for my construction of the AST, I am not sure which technique I will ultimately prefer, but it won't matter either way to consumers of the AST.
- Yes, incremental parsing is doable. The main question is which optimizations you're allowed to do in an online context, and which optimizations you can still use in an offline context without making your code bloated and complicated. I would prefer using the technique of just copying all the reusable data over to a new buffer, and not bothering with convoluted tree structures which try to reuse data and would require us to do things in much less efficient ways. Matklad pointed out that Carmack had this idea for video games that you only need two buffers, the previous frame and current frame, and you can copy between them each frame as the one that becomes stale switches. Everything is more efficient with this strategy except having to do the potentially massive copy. Although we're theoretically doubling the peak RAM usage, we can use structures that are far less than half the space and much faster to traverse in memory with this strategy, so it should more than pay for itself. It also means we can use the same logic for offline compilation and it will still be optimal.
- Definitely. I'd be open to help fleshing out an API. I've never looked at Language Server Protocol in any depth so I don't know what API consumers want but I can use my imagination for some of it. I assume LSP will tell me which bytes changed and what they are now but I don't know much else.
matu3ba
I guess you have probably made up your mind about 1-2 with a draft impementation, so I wanted to ask about it.