3 ms·

> For real world performance, benchmarking is the key. Only it's not enough. When you benchmark an O(N^2) algo may seem fine but then three years later the dat

by amag 4y ago

> For real world performance, benchmarking is the key. Only it's not enough. When you benchmark an O(N^2) algo may seem fine but then three years later the data has changed and is now an order of magnitude larger. So you need not only know your data, you also need to spend time thinking about how large it can become.

Ozzie_osman 4y ago
That's the point of O-notation though. It helps you know how your computation will degrade as your data grows. So you start with benchmarking your current data. You still need to always think about how your data will grow.
inetknght 4y ago
> Only it's not enough. True. But I do highly recommend watching Ben Deane's 2015 talk about testing Battle.net. In it he briefly touches upon benchmarks and estimating algorithmic complexity. It's somewhat difficult to suss-out the details of it. But the short version is basically to run the benchmark with a few different sizes and then estimate the complexity growth from that. https://youtu.be/OPoZWnYIcP4?t=1035 https://youtu.be/OPoZWnYIcP4?t=1035
robby_w_g 4y ago
> When you benchmark an O(N^2) algo may seem fine but then three years later the data has changed and is now an order of magnitude larger The GTA Online loading screen bug is a recent example of this problem, with its in-game purchasable items growing larger over time: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
- deleted 4y ago
  [deleted]
quietbritishjim 4y ago
You seem to be agreeing with the parent comment's point. For example, there's this bit of their comment, which is almost verbatim what you replied back with: > ... you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity ... It seems like you're disagreeing only because you pulled out the one quote about benchmarking. But they were just saying that you need benchmarking to bootstrap the meaning of O(...) of an algorithm. That's the point that the original article missed, which is presumably why they described it as key.
favorited 4y ago
> the data has changed and is now an order of magnitude larger If your data changes, and you care about performance, then your data structures and algorithms should be reevaluated.

by amag 4y ago

Ozzie_osman 4y ago

That's the point of O-notation though. It helps you know how your computation will degrade as your data grows. So you start with benchmarking your current data. You still need to always think about how your data will grow.

inetknght 4y ago

> Only it's not enough. True. But I do highly recommend watching Ben Deane's 2015 talk about testing Battle.net. In it he briefly touches upon benchmarks and estimating algorithmic complexity. It's somewhat difficult to suss-out the details of it. But the short version is basically to run the benchmark with a few different sizes and then estimate the complexity growth from that. https://youtu.be/OPoZWnYIcP4?t=1035 https://youtu.be/OPoZWnYIcP4?t=1035

robby_w_g 4y ago

> When you benchmark an O(N^2) algo may seem fine but then three years later the data has changed and is now an order of magnitude larger The GTA Online loading screen bug is a recent example of this problem, with its in-game purchasable items growing larger over time: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...

deleted 4y ago
[deleted]

quietbritishjim 4y ago

You seem to be agreeing with the parent comment's point. For example, there's this bit of their comment, which is almost verbatim what you replied back with: > ... you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity ... It seems like you're disagreeing only because you pulled out the one quote about benchmarking. But they were just saying that you need benchmarking to bootstrap the meaning of O(...) of an algorithm. That's the point that the original article missed, which is presumably why they described it as key.

favorited 4y ago

> the data has changed and is now an order of magnitude larger If your data changes, and you care about performance, then your data structures and algorithms should be reevaluated.