In working on garbage collection I discovered a very powerful efficiency hack. Let me state the original form and then generalize.
We had to scan pages for pointers. Instead of taking them in simple list order I took two passes. First take each page descriptor and discover if the page is in ram. If it is then scan and mark as scanned. On the second pass scan the pages not scanned in the first pass. This eliminates all kinds of paging, compared to many difficult code hacks it is really awesome.
Now the generalization. There are all kinds of collections which have a prefered order of scan for efficiency. That is you need a method which says do_quickly [some method] which applies the method to all the members in an undefined order which is assumed to be chosen for efficiency alone.