Unsurprisingly, the biggest performance gains came from algorithmical changes, not micro optimisations (like if instead of switch.)
The lesson is always the same: leave micro optimisations for later and spend more time learning about data structures that can improve your code locality.
Correct. However I did find that just working on the codebase getting small wins was enough to put my mind into thinking about it and hence able to make that leap to the larger gains.
For the super tight loops scc uses the micro optimisations still add up though so it wasn’t wasted effort and in the end it all came together nicely.
Once you are somewhat experienced with optimization, the difficult part isn't getting into the mindset of optimizing, but in holding off on it until your features are in.
Before you have the features, you mostly want to find the boundaries on the problem so that you can slice it up into modules and optimize those independently. It's unusual in contemporary programming to have to do a whole-program micro-optimization pass, but that's the only kind you can do within a small program, so it's common to get the wrong idea and start shaving off bytes and cycles before the architecture is ready for it. In a large program, it's specific combinations of features that create performance spikes, and those tend to be addressed by building a new custom code path. When you scale up the data changes, so your view of the problem changes too, and you start being able to optimize by creating a codepath that combines a whole bunch of specific processing steps.
The caveat working that way is that you can end up working towards a local optimum, and lose sight of the forest for the trees when it comes to making the bigger algorithmic changes.
The lesson is always the same: leave micro optimisations for later and spend more time learning about data structures that can improve your code locality.