How We Made Our Face Recognizer 25x Faster
lbrandy.com
lbrandy.com
His loops probably can be improved further unless the missing bits (he only gives pseudo-code) are a limit.
There's mention of Oprofile, something I didn't knew existed. It looks like a very nice complement for Valgrind (Cachegrind in this scenario.) Yay!
There almost certainly is not enough memory to cache all of the information. But hardware cache friendly algorithms have good locality. This means that once they pull data into the cache, they do everything to it that they need to before it gets kicked out. Cache unfriendly algorithms continually kick out and pull in the same data.
The simplest example of this is iterating over a two-dimensional array in C. Since C stores arrays in row-major format (the rows are contiguous in memory), you want to iterate over the rows first, then the columns:
for (i = 0; i < ROW; ++i)
for (j = 0; j < COL; ++j)
matrix[i][j] = 0;
for (i = 0; i < COL; ++i)
for (j = 0; j < ROW; ++j)
matrix[j][i] = 0;
But you bring a good point - for example on certain platforms (certain game consoles for example), where memory, and cache miss is expensive, often compiling with -O1 rather than -O2 (inline expansion) is better.
Hardware caches are stupid. They are a way to avoid hitting main memory every time a load is issued; the idea is that if you use a bit of memory once, you're likely to use it and memory close it again. Cache lines are usually replaced on a Least Recently Used basis. I say they're "stupid" because they have no knowledge of the algorithm being executed, and can't be told "keep this in the cache." They only react to memory access patterns. If you want something to stay in the cache, use it, and don't use anything else until you're done with it.
And just to be clear, at the hardware level abstractions like "items" don't exist. It's all just bytes - and if you're dealing with caches, then it's going to be cache lines, which are often something like 64 or 128 bytes. If I access a memory location, the entire cache line it's on, gets pulled into the cache with it.
Looking at the article, his iteration order was face1, face2, features. This means that he was fixing the faces being compared, and changing which features he was looking at. So face1 and face2 were (probably) staying in the cache, while the features were not.
In his case, the features are stored in a tree - which means feature n and feature n+1 are not contiguous in memory. Going from one node in the tree to another node will almost certainly result in cache misses. The first algorithm he presented iterated over the entire tree for each face pair.
The second algorithm fixed the feature being looked at, and iterated over the faces. So, for every node in the tree, the algorithm stopped and did all of its work before moving on. So you have one tree traversal instead of N * M, and significantly less cache misses.
Note that his solution doesn't necessarily generalize; the most cache friendly approach depends on the relative sizes of the data. If the faces were significantly larger, then it might be less expensive to navigate through the tree every time, keeping the faces in the cache. Optimizing algorithms for good cache usage requires knowing how your data is laid out in memory, how much of it you're dealing with, and how you're accessing it.
The features are not stored in a tree. They are an ARRAY of trees. So we hold face1 and face2 constant, load up the tree for feature 1, descend it, record the value. Then we load up the tree for feature 2, descend it, record the value. Etc. If we have 1000 of faceA, faceB, and 5000 features, that means we'd do 5000 descensions of -different- trees, then iterate to the next face, a million times.
You are absolutely correct about the data sizes mattering in that the reason this fails is because you cannot, over the course of a million matches, cache all 5000 trees (given their size).
The new algorithm, however, held the tree for feature 1 fixed, and iterated over the faces, which, in this case are simple vectors. This results in using the -same- tree for 1 million consecutive comparisons, then switching trees for feature 2, and so on.
In spite of this correction, pretty much everything you've said is accurate. The primary difference is this scenario is much, much worse on cache than the one you've described.