First, run a profiler to find out where your code is spending its time.
Then, look at those places to see which ones look easy to optimize.
Look for the easiest fixes that will get the biggest gains first (go for the low-hanging fruit). Don't worry too much about how important it is, precisely. If it's easy, fix it. It will add up. 25 easy fixes might be faster than 1 big fix, and their cumulative effects might be larger. If it's hard, make a note or file a bug report so you can prioritize it later. Don't worry so much about "big" or "little" at this point - just do it, until you get to functions that are using very little time. Once you do this, you should have a better idea of which of the other issues you've uncovered might get the biggest wins for the least time investment.
Don't forget to follow up with profiling after your fixes as a sort of regression test, to verify that your performance changes had the effects you hoped for. Also, don't forget to run your regression suite, to ensure no functionality was broken. Sometimes bad performance indicates work-arounds, and trying to fix the performance will break functionality.
Small functions that can't be optimized but are using a lot of time might still be hints about where to optimize. Why is that function being called so much? Is there a function calling that small function that doesn't need to use it so much? Is work being duplicated, or unnecessary work being done? Look up the stack for the times it gets called until you are confident it should be called that often, and see if you find a larger function with an inefficient algorithm.
Edited to add: Since you have specific functionality that is taking a long time, try doing the steps above with just that specific function being run 10 or so times.