Not only did I profile it, put a lot of time into optimization and learned how to use cloud computing, but I also learned a new language (Julia) and ported the whole application. :)
In Julia I can use things as data oriented design (few cache misses) to further reduce runtime. I'm not sure you get much out of such efforts in Python.
This. Having tight control over memory layout + heap allocations + vector instructions can literally decrease runtume by several orders of magnitude. Performance is so much more than having the "right algorithm". The low-level details matter so much.