Sometimes, I have the impression that the Rust compiler hates me more than all the mobs in Elden Ring. And there's no I-frames in Rust...
Anyway, that led me to an interesting realization. I needed a simple tree structure to store data for a lexer generator (tool to build a compiler). In any normal language, you'd store the data in each node, along with pointers to the children. But mixing pointers and mutability is complicated in Rust, so I tried another approach and stored all the nodes in a vector (their size increases automatically, so it's easy), using indices to reference the children instead of pointers (*). A quick test showed me that there was at least a x2 speedup vs pointers.
It makes sense, since the locations are contiguous: there's a cache effect that doesn't work well with pointers. If the data are shuffled enough so that successive nodes are far apart in the array, the performance advantage disappears, though it's hard to compare both approaches in that case, since I can't control where nodes are stored in memory with the pointer solution.
(*) I don't need to delete nodes. There are a few tricks if you need to do that with this approach, so it would still be fine.
