Once I was asked to look for one project to see that if there is any room for improvement to speed up the program. After I profiled the program with the test data, I saw that program was severely affected by a "size" method call on a lock-free concurrent list. Since the data structure is lock free, size method is not a constant time operation and calling it in a large list takes too much time. It was just there to print some kind of statistics, I changed the code so that it is called only necessary not every time some operation occurs. This immediately made program 2-3 times faster.
There were also some parts I changed with some algorithms with less algorithmic complexith to make it faster. Overall, I made the program 6x faster. So sometimes you need to use fancy algorithms, sometimes you just need to change one line of code after profiling.