4 ms·

I agree that "must" is too strict. If I replace linear search with binary search, or hashmap/hashset lookup I don't need to write a benchmark to prove it improv

I agree that "must" is too strict. If I replace linear search with binary search, or hashmap/hashset lookup I don't need to write a benchmark to prove it improves performance. There is math, logic, Big O analysis that allows to reason about performance and speed without microbenchmarks.

bt848 7y ago
If you did that to code in Google search you’d be required to run a special load test to prove you didn’t screw it up. Nobody should assume either of the things you just implied were obvious. In fact linear search is guaranteed to beat binary search for short vectors. O-complexity analysis is good for undergrads but the ONLY aspect of software performance that matters any more is cache behavior.
BeetleB 7y ago
bt848 already said it, but you picked a really poor example. In many real world scenarios, a linear search beats a binary search due to a lack of overhead. Along those lines, in C++, a vector very often performs better than a theoretically better data structure. I learned C++ fairly well from a very experienced guy in the company, and he said that you should always benchmark against a vector. I suspect if I was in his team and he were reviewing my code, he wouldn't let the code pass unless I had benchmarks that show whatever data set I picked is faster than a vector. He wasn't against other data structures - he just wanted proof they would perform better. In quite a few cases, they didn't.
- jsnell 7y ago
  So now the requirement is not just to run a micro benchmark, but to run one with inputs that approximate the distribution of production inputs, along all possible axes. For many sorts of projects, this is totally unreasonable. It's easy to figure out how the code performs with a given input, it is much harder to figure out what the inputs really are like. In this particular case I'd expect the change to be motivated by profiling of the real production instances. And that makes it pretty obvious how the change should be evaluated. "We're spending more time than is reasonable in linear scans, so the worst case inputs must be worse than expected. Switch to a data structure more suited to large inputs, and see if CPU use improves in the next rollout."
- molodec 7y ago
  Yes, the size of the data matters, and linear search may be the right choice for many use cases and may outperform more advanced data structures. You learn it on the job as it is not a topic usually studied in universities. But I don't agree that we need to completely throw away theory, O complexity analysis where N - input size is the main variable. Microbenchmarks are hard to write correctly. Recreating the scenarios occurring in production is not always possible in the microbenchmark settings. You can write a microbenchmark that shows your code works great, but fails to perform in production because the input data is totally different. bt848 mentioned load test, which is not the same as microbenchmark. Load test that simulates production settings is a better tool to validate the optimizations.
  - BeetleB 7y ago
    >But I don't agree that we need to completely throw away theory, O complexity analysis where N - input size is the main variable. No one here is agreeing with that.

bt848 7y ago

If you did that to code in Google search you’d be required to run a special load test to prove you didn’t screw it up. Nobody should assume either of the things you just implied were obvious. In fact linear search is guaranteed to beat binary search for short vectors. O-complexity analysis is good for undergrads but the ONLY aspect of software performance that matters any more is cache behavior.

BeetleB 7y ago

bt848 already said it, but you picked a really poor example. In many real world scenarios, a linear search beats a binary search due to a lack of overhead. Along those lines, in C++, a vector very often performs better than a theoretically better data structure. I learned C++ fairly well from a very experienced guy in the company, and he said that you should always benchmark against a vector. I suspect if I was in his team and he were reviewing my code, he wouldn't let the code pass unless I had benchmarks that show whatever data set I picked is faster than a vector. He wasn't against other data structures - he just wanted proof they would perform better. In quite a few cases, they didn't.

jsnell 7y ago
So now the requirement is not just to run a micro benchmark, but to run one with inputs that approximate the distribution of production inputs, along all possible axes. For many sorts of projects, this is totally unreasonable. It's easy to figure out how the code performs with a given input, it is much harder to figure out what the inputs really are like. In this particular case I'd expect the change to be motivated by profiling of the real production instances. And that makes it pretty obvious how the change should be evaluated. "We're spending more time than is reasonable in linear scans, so the worst case inputs must be worse than expected. Switch to a data structure more suited to large inputs, and see if CPU use improves in the next rollout."
molodec 7y ago
Yes, the size of the data matters, and linear search may be the right choice for many use cases and may outperform more advanced data structures. You learn it on the job as it is not a topic usually studied in universities. But I don't agree that we need to completely throw away theory, O complexity analysis where N - input size is the main variable. Microbenchmarks are hard to write correctly. Recreating the scenarios occurring in production is not always possible in the microbenchmark settings. You can write a microbenchmark that shows your code works great, but fails to perform in production because the input data is totally different. bt848 mentioned load test, which is not the same as microbenchmark. Load test that simulates production settings is a better tool to validate the optimizations.
- BeetleB 7y ago
  >But I don't agree that we need to completely throw away theory, O complexity analysis where N - input size is the main variable. No one here is agreeing with that.