3 ms·

But he's using 8 cores, which are all parallely addressing memory. Which of the items being processed gets stored in this cache? When one processor takes contro

But he's using 8 cores, which are all parallely addressing memory. Which of the items being processed gets stored in this cache? When one processor takes control over the memory bus, it's going to be needing memory data from a completely different part of memory, no?

newt0311 18y ago
But some of the processor's cache is devoted to storing code. The original loop constantly switched the feature being compared. Since the different features (presumably) used significantly different code, the processor would end up with unnecessarily large number of cache flushes for code. By aggregating the features one by one, he reduced code-cache flow significantly which makes a big difference in performance. Much bigger than some people realize.
- malkia 18y ago
  Usually that's a different cache, but even if it's the same, the code is usually smaller. 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.
scott_s 18y ago
Honestly, I'm not sure what you're getting at. So I'll try to explain what I think might not be clear. 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.
- lbrandy 18y ago
  Author here. You almost have it completely right. 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.
  - liuliu 18y ago
    hi, if I got you right, are you using some kind of decision tree-based boosting method for feature extraction & compare? It looks like so. Just curious, if you do not want to answer, never mind.
  - scott_s 18y ago
    Thanks for the clarification. I admit I was having to make assumptions because I didn't know your data structures.
queensnake 18y ago
Each core has its own cache.

newt0311 18y ago

But some of the processor's cache is devoted to storing code. The original loop constantly switched the feature being compared. Since the different features (presumably) used significantly different code, the processor would end up with unnecessarily large number of cache flushes for code. By aggregating the features one by one, he reduced code-cache flow significantly which makes a big difference in performance. Much bigger than some people realize.

malkia 18y ago
Usually that's a different cache, but even if it's the same, the code is usually smaller. 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.

scott_s 18y ago

Honestly, I'm not sure what you're getting at. So I'll try to explain what I think might not be clear. 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.

lbrandy 18y ago
Author here. You almost have it completely right. 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.
- liuliu 18y ago
  hi, if I got you right, are you using some kind of decision tree-based boosting method for feature extraction & compare? It looks like so. Just curious, if you do not want to answer, never mind.
- scott_s 18y ago
  Thanks for the clarification. I admit I was having to make assumptions because I didn't know your data structures.

queensnake 18y ago

Each core has its own cache.