Respect CPU caches and locality. Keeping your data structures in cache or even packed together can result in a nice performance gain. I've seen benchmarks wher

Respect CPU caches and locality. Keeping your data structures in cache or even packed together can result in a nice performance gain. I've seen benchmarks where inserting into an array was significantly faster than inserting into a linked list. This can be surprising considering most algorithm texts I've seen say the complexity of the latter is better. From what I understand locality is part of the reason inserting into the array is faster.