Multiple times I have found the impact of cache performance to be dramatic. I find that the usual optimisations in three aspects are usually obvious to achieve

Multiple times I have found the impact of cache performance to be dramatic. I find that the usual optimisations in three aspects are usually obvious to achieve and can bring surprisingly big improvements. The first is that RAM accessed randomly or in the wrong direction performs very poorly compared to sequential access in order. The same is true of cache because its much easier to predict and prefetched data when its accessed serially. The effect is so dramatic that its sometimes worth "accessing" data you don't need to get access to this hardware optimisation to maintain serial access. At times for example I have found Treemaps and listmaps perform better than hashmaps as the cheap search serially and in memory order surprisingly out does the O(log(n)) or O(n) algorithms and the cost of the hash. If you have a data structure that is larger than optimal and overflows cache lines it can have big impacts on cache utilisation and performance if the algorithm doesn't need all the fields. Object orientation impacts quite heavily on this and certain designs can make very large objects and these often get poor cache usage. Unnecessary allocation and deallocation of memory in algorithms often results in the cache getting thrashed and avoiding this and using the same memory can result in better hot cache usage and reducing garbage collection usage. Most profilers can give you a good idea of the allocations but the other two are often harder to find and mostly just show up in cache misses.