Processor cache
- First question: (2) utilizes the processor cache better because it
only scans
a
once. (1) has twice the number of cache misses. - Second question: (3) utilizes the processor cache better because it
takes advantage of what's already in the cache, instead of switching
back and forth between
a
andb
. However, this solution has more branches.
Data Structure cache performance
Best workloads for each structure:
- 1D Array: Best if keys are small integers and most keys exist.
- 2D Array: Good if accessing values by rows. Horrible if accessing by columns.
- Singly-linked list: Best for small sets with a big keyspace (but never really that good).
- Hash tables: good for big keyspaces with medium-to-large numbers of elements.
- Binary search tree: hash tables are preferred, UNLESS ordering is important for keys (so you might want to “getnext(key)”—get the next key after a given key), which hash tables cannot handle.