This has been the key for me as well, memory allocation in hot paths is usually the first optimization that I look for. It's quite surprising to see how far very inefficient algorithms (time complexity wise) can go as long as no allocations are made.