Designing Wild's incremental linking
Whenever I’m about to embark on implementing something even slightly non-trivial, I typically write out a plan for what I’m about to do. Writing it down helps me to uncover things that I hadn’t thought about. Usually, I write these designs only for myself, however this time, I thought I’d try something different, writing a design and sharing it with anyone who might be interested. My hope is that some people might have interesting ideas for variations on this design that I hadn’t considered. If nothing else, hopefully this document will be an interesting read for someone.
If you’ve read my previous posts, you’ll know that I’ve been writing a linker, called Wild, with the goal of being a very fast incremental linker. I didn’t make the linker incremental from the start because I wanted to get it reasonably correct and reasonably fast before adding incremental linking to the mix. Wild is now working well enough that I’ve switched to using it as my default linker. That’s not to say there aren’t things it doesn’t do correctly, e.g. large model stuff, which is needed for very large executables, but it works well enough for compiling Rust code with bits of C or C++ mixed in. It’s also relatively fast - on my laptop, Wild can link itself 48% faster than Mold. If there’s lots of debug info however, Wild is currently often slower. I hope to work on improving the performance of linking debug info eventually.
So I feel that while there’s plenty more that could be done to improve Wild’s non-incremental linking, now is probably a good time to start work on incremental. To that end, this document is my plan for how I intend to go about that.
