6 ms·

It is trivial to exceed the L1 cache size and not that uncommon to exceed L2. That brings us to a 100x delta which is worth thinking about, no? Even exceeding L

It is trivial to exceed the L1 cache size and not that uncommon to exceed L2. That brings us to a 100x delta which is worth thinking about, no? Even exceeding L3 isn't horribly rare for average desktop CPUs (let alone mobile devices). There are other dimensions to this too like prefetching, streaming, pipelining, vectorization, etc. In some cases using an array and doing a linear search is faster than any hashmap on a modern CPU. I think the takeaway from this article is not to blindly trust the theoretical big-O numbers for data structures and actually test them with realistic datasets on your target hardware.

aaronbwebber 10y ago
This is a very good point. You should run actual performance tests. The results may surprise you! In my actual work, optimizing in memory searches is not worthwhile because saving half a dozen microseconds on a search is not real valuable when you are about to spend half a dozen milliseconds making a database call (which is technically O(log N), since there's a B-tree index back there). But I do spend quite a bit of time figuring out which of those queries should be moved to an in-memory O(1) cache (redis or memcache, depending). And I actually never think about the perf tradeoff between the DB and the cache being O(log N) vs O(1) - I think of it in terms of the median and 99th %tile times that I know from monitoring our actual production servers. So as xenadu points out, I guess there is some truth in the article, but it's just sort of lost in this somewhat academic discussion of scaling things to infinity and beyond.
- deleted 10y ago
  [deleted]
- AstralStorm 10y ago
  Random percentile abuse. 99% is less useful than a median. The real data is a true histogram as well as maximum time. 99% might mean every 100th customer does not get a service.
- pjc50 10y ago
  In my actual work, optimizing in memory searches is not worthwhile Funnily enough, I had to do this last week. We started from the question "why does it take 160ms to scan 60,000 objects in memory?" and reached the disappointing conclusion that, on this particular platform (iMX6/800MHz/DDR3) a cache miss costs you an astonishing 233ns. I got as far as double-checking all the RAM initialisation parameters before giving up. There is now an index on the in-memory search.
pedrocr 10y ago
>I think the takeaway from this article is not to blindly trust the theoretical big-O numbers for data structures and actually test them with realistic datasets on your target hardware. You have to do this anyway to make sure that the constant factors aren't big enough to change the optimal approach at the size of your dataset. Big-O only really buys you an initial rule to not do things that are obviously wrong.
- wongarsu 10y ago
  Right, an algorithm that always produces an answer right after the heat death of the universe is O(1). Big-O is great for telling you which algorithms/datastructures won't scale, it can't tell you which are actually fast enough.
  - wtetzner 10y ago
    And in fact, some data structures that scale poorly will perform better on small sets of data. For example, a simple list of pairs with linear lookup time can be faster than a hash table for small amounts of data, because it doesn't have to compute the hash.
p4wnc6 10y ago
I would say it differently: you absolutely should trust big O numbers for data structures and use that as a major guiding principle in terms of how to structure a program ... and you should require extraordinary evidence, like a surprising result in a performance test, before navigating away from trusting the big O analysis. What this all says to me is that for an extreme claim (e.g. using an array and doing a linear search will be faster than a hashmap lookup) it should require equally extreme evidence to substantiate it (e.g. the results of performance tests that stand up to heavy scrutiny). I feel there is a trap in which someone might look at this sort of thing and say, a-ha I don't actually need to care about big O reasoning or standard understanding of data structures at all! That would be a tragic misreading of this sort of example.
- nomel 10y ago
  > before navigating away from trusting the big O analysis. I don't think that's the spirit of the article. The spirit is to not assume O(1) is O(1) if you work with a physical computer and care about anything beyond how many times your program counter increments. Make sure to use big O notation that includes the complexities of carrying out those single instructions. If you work with more than 32k of data, you either need to modify your big O to take latency into account, or you're assuming some worst case cache level, which is fine, and what you're doing with an idealistic big O...but that's a terrible assumption if you're actually trying to achieve speed or realistic metrics.
  - p4wnc6 10y ago
    I agree. That's why the article is wrong-headed in its presentation. Generally when you begin working on problems where this sort of thing is relevant, you have to make choices to get something going. You want to avoid premature optimization and you need something on the ground. In short, you have to assume O(1) is O(1) ... and it basically always is, except when there's evidence that it's not. The value of the article is to point out cases when these abstractions break down, and the value of performance testing. But carrying it to an extreme such as, "Never make any assumptions about how any data structures work until you've performance tested every single thing in your application" is of course wildly unproductive.
iheartmemcache 10y ago
Totally with you on 'benchmark everything, who knows when the branch predictor will mispredict or a full cache flush will happen. (Interestingly enough, I rarely try to beat the compiler since ICC is super smart but strategically placed, manually inserted CLFLUSHes have sped up some my work. Go figure.) Eh L1 is bigger than you think. What cache-trashes is context switching. A common technique is shielding processes[1], delegating all interrupts to certain processors. Here's an easy example - since HT has it's own set of caches for both "CPUs" inside the physical CPU [i.e., the ALU (and all the aux AVR registers too) is shared between both], if you're doing anything computationally intensive with an unpredictable set of interrupts, but your crunch pattern is predictable enough do the following-- set the affinity for the 'cruncher' to one CPU with a full shield, and then all other components like interrupts, IO, things that you don't mind re: cache misses, etc. [1] https://rt.wiki.kernel.org/index.php/Cpuset_Management_Utility/tutorial https://rt.wiki.kernel.org/index.php/Cpuset_Management_Utili... This is just one way to do it, but it explains the concept.

aaronbwebber 10y ago

This is a very good point. You should run actual performance tests. The results may surprise you! In my actual work, optimizing in memory searches is not worthwhile because saving half a dozen microseconds on a search is not real valuable when you are about to spend half a dozen milliseconds making a database call (which is technically O(log N), since there's a B-tree index back there). But I do spend quite a bit of time figuring out which of those queries should be moved to an in-memory O(1) cache (redis or memcache, depending). And I actually never think about the perf tradeoff between the DB and the cache being O(log N) vs O(1) - I think of it in terms of the median and 99th %tile times that I know from monitoring our actual production servers. So as xenadu points out, I guess there is some truth in the article, but it's just sort of lost in this somewhat academic discussion of scaling things to infinity and beyond.

deleted 10y ago
[deleted]
AstralStorm 10y ago
Random percentile abuse. 99% is less useful than a median. The real data is a true histogram as well as maximum time. 99% might mean every 100th customer does not get a service.
pjc50 10y ago
In my actual work, optimizing in memory searches is not worthwhile Funnily enough, I had to do this last week. We started from the question "why does it take 160ms to scan 60,000 objects in memory?" and reached the disappointing conclusion that, on this particular platform (iMX6/800MHz/DDR3) a cache miss costs you an astonishing 233ns. I got as far as double-checking all the RAM initialisation parameters before giving up. There is now an index on the in-memory search.

pedrocr 10y ago

>I think the takeaway from this article is not to blindly trust the theoretical big-O numbers for data structures and actually test them with realistic datasets on your target hardware. You have to do this anyway to make sure that the constant factors aren't big enough to change the optimal approach at the size of your dataset. Big-O only really buys you an initial rule to not do things that are obviously wrong.

wongarsu 10y ago
Right, an algorithm that always produces an answer right after the heat death of the universe is O(1). Big-O is great for telling you which algorithms/datastructures won't scale, it can't tell you which are actually fast enough.
- wtetzner 10y ago
  And in fact, some data structures that scale poorly will perform better on small sets of data. For example, a simple list of pairs with linear lookup time can be faster than a hash table for small amounts of data, because it doesn't have to compute the hash.

p4wnc6 10y ago

I would say it differently: you absolutely should trust big O numbers for data structures and use that as a major guiding principle in terms of how to structure a program ... and you should require extraordinary evidence, like a surprising result in a performance test, before navigating away from trusting the big O analysis. What this all says to me is that for an extreme claim (e.g. using an array and doing a linear search will be faster than a hashmap lookup) it should require equally extreme evidence to substantiate it (e.g. the results of performance tests that stand up to heavy scrutiny). I feel there is a trap in which someone might look at this sort of thing and say, a-ha I don't actually need to care about big O reasoning or standard understanding of data structures at all! That would be a tragic misreading of this sort of example.

nomel 10y ago
> before navigating away from trusting the big O analysis. I don't think that's the spirit of the article. The spirit is to not assume O(1) is O(1) if you work with a physical computer and care about anything beyond how many times your program counter increments. Make sure to use big O notation that includes the complexities of carrying out those single instructions. If you work with more than 32k of data, you either need to modify your big O to take latency into account, or you're assuming some worst case cache level, which is fine, and what you're doing with an idealistic big O...but that's a terrible assumption if you're actually trying to achieve speed or realistic metrics.
- p4wnc6 10y ago
  I agree. That's why the article is wrong-headed in its presentation. Generally when you begin working on problems where this sort of thing is relevant, you have to make choices to get something going. You want to avoid premature optimization and you need something on the ground. In short, you have to assume O(1) is O(1) ... and it basically always is, except when there's evidence that it's not. The value of the article is to point out cases when these abstractions break down, and the value of performance testing. But carrying it to an extreme such as, "Never make any assumptions about how any data structures work until you've performance tested every single thing in your application" is of course wildly unproductive.

iheartmemcache 10y ago

Totally with you on 'benchmark everything, who knows when the branch predictor will mispredict or a full cache flush will happen. (Interestingly enough, I rarely try to beat the compiler since ICC is super smart but strategically placed, manually inserted CLFLUSHes have sped up some my work. Go figure.) Eh L1 is bigger than you think. What cache-trashes is context switching. A common technique is shielding processes[1], delegating all interrupts to certain processors. Here's an easy example - since HT has it's own set of caches for both "CPUs" inside the physical CPU [i.e., the ALU (and all the aux AVR registers too) is shared between both], if you're doing anything computationally intensive with an unpredictable set of interrupts, but your crunch pattern is predictable enough do the following-- set the affinity for the 'cruncher' to one CPU with a full shield, and then all other components like interrupts, IO, things that you don't mind re: cache misses, etc. [1] https://rt.wiki.kernel.org/index.php/Cpuset_Management_Utility/tutorial https://rt.wiki.kernel.org/index.php/Cpuset_Management_Utili... This is just one way to do it, but it explains the concept.