More Performance Tidbits for library writers
Rico Mariani has a new blog post up: More Performance Tidbits for library writers:
Principle #6: When creating data structures, pretend that following a pointer is a very costly operation
Actually you don’t have to pretend because it really is costly compared to say going to the next element of an array.
Modern processors can issue multiple instructions per clock when things are going great, but following pointers means more cache misses which means more CPU time spent doing nothing. You especially have to beware of data structures which are built up over a long period of time — if the allocations did not happen near each other in time then the extra benefits of locality that the GC provides can be lost. That means cache misses which brings your average performance way down and an otherwise nice looking data structure ends up killing you.
(Why didn’t they teach us this stuff in college? I genuflected at the Altar of Pointers for years, but none of the High Priests ever brought this up! Of course, it’s obvious in retrospect, but still.)