From my experience the greatest optimization gains can be achieved by introducing more domain knowledge into the code. Heuristics that cut the number of executions of some expensive function, shortcuts that introduce good enough approximations, pre-computing and memoizing certain values that are actually constant in the processed data. Things like that.
And in programs that had never been optimized it's usually very easy to fire up the profiler and find some obviously terrible things. Like reinitializing in a tight loop some expensive object that can easily be a singleton (or at least a thread local object). I've once spent a month on a decent piece of code and brought down the CPU cost by literally 100x (nobody had optimized the code before).
Also, always, first create a reliable framework for measuring progress (cpu instruction retired counters in Intel CPUs are very good and don't need a lot of execution repetitions to bring the p-values low), and only then start optimizing.
Low-level, hardcore optimization rarely pays out (not never, but rarely).
And in programs that had never been optimized it's usually very easy to fire up the profiler and find some obviously terrible things. Like reinitializing in a tight loop some expensive object that can easily be a singleton (or at least a thread local object). I've once spent a month on a decent piece of code and brought down the CPU cost by literally 100x (nobody had optimized the code before).
Also, always, first create a reliable framework for measuring progress (cpu instruction retired counters in Intel CPUs are very good and don't need a lot of execution repetitions to bring the p-values low), and only then start optimizing.
Low-level, hardcore optimization rarely pays out (not never, but rarely).