7 ms·

Four Kinds of Optimisation

120 points by ltratt 3y ago

gavinhoward 3y ago
This is a great article, and I have some notes. I initially disagreed with the author when he said, "we tend to overestimate how much we know about the software we're working on." I disagreed because that is not my experience; I do know a lot about my software. However, then he said, "We overemphasise the parts of the system we've personally worked on, particularly those we've most recently worked on. We downplay other parts of the system, including the impact of dependencies (e.g. libraries)." Oh. Um, well, this is also not my experience. I work on software alone, and I do not have any dependencies. So the author is right; I just have weird experience. :) I agree with the four kinds of optimization, especially since he focuses on optimization humans do. I think you could even shoehorn compiler optimizations into those four. For example, strength reduction could be considered a "better algorithm." His observations about the differences between best, average, and worst cases are the things programmers need to learn most. At some point, our code will always hit bad cases, and we need to know if it will hit it often. I love his example of Timsort because I've analyzed and implemented it myself. It ended being more comments than code. (Of course, that includes two license header comments, so slightly less comments than code actually.) Timsort is pretty complicated, and Tim isn't the best at naming things, so it took a bit for me to understand what was going on. (The most prominent example is the galloping functions. He named them "gallop_left" and "gallop_right," but they both gallop left and right. I renamed them to "gallop2Leftmost" and "gallop2Rightmost," which is actually what they do.) The author says he biases to writing algorithms and adopting pre-written data structures. This is a good thing. However, after having written data structures (because I work in C, which doesn't have them), I would encourage every programmer to write some. Best, average, and worst cases are easier to learn on data structures than algorithms. Still use pre-written ones though; they are usually better optimized. The trick about reducing memory is crucial. I recently spent an entire refactor just reducing the size of some of the most-used structs. I cut the size of one struct in half. `pahole` is great for this. The part of PyPy is a great example too. A great book to read is Is Parallel Programming Hard, And, If So, What Can You Do About It? The entire point of the book is to make you think, "Okay, I need some concurrency or parallelism; what is the easiest way to get it?" The PyPy example is that same thing with optimization; what's the easiest way to get the performance you need? Every time you run into an optimization problem, ask that question first, and it will get faster to answer every time. And the author's summary reinforces this. [1]: https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.2022.09.25a.pdf https://mirrors.edge.kernel.org/pub/linux/kernel/people/paul...
- dj_mc_merlin 3y ago
  > However, then he said, "We overemphasise the parts of the system we've personally worked on, particularly those we've most recently worked on. We downplay other parts of the system, including the impact of dependencies (e.g. libraries)." > Oh. Um, well, this is also not my experience. > I work on software alone, and I do not have any dependencies. If you work in a company of 100+ engineers with multiple specialties it's impossible to keep up with everything. At <50 engineers if you collaborate and/or switch teams it's possible to know almost everything, but that's the most I think the majority of us have the internal storage/RAM for.
  - gavinhoward 3y ago
    Yes, I said as much in my comment.
  - ska 3y ago
    I suspect your thresholds are far too high, and that some specialties are almost mutually incomprehensible, so rare for one person to properly understand what is going on. Time is a real factor also. How long has this code base been accumulating...
    - dj_mc_merlin 3y ago
      Early on in the company I work we had a practice of collaborating across teams, sharing members etc. so a lot of us knew a lot of the code base from "different angles". If you implemented a backend feature you might write also write the terraform and the frontend that worked with it, with some input from the people experienced in those things. Kind of like random full-stack development? Slower than normal development at first but it makes future collaboration easier. It was quite great, but unsustainable as the amount of people grows. edit: I think in general at the early stages of a company you hire a lot of people who are good at adapting and learning new skills since they might need to fill new roles quickly as new needs arise. So those people are good at this kind of full stack development since it's their niche. As you grow, you hire more specialized or junior people, and they can't do this process quickly enough for it to feel fluid anymore.
llamajams 3y ago
There needs to be more articles like this, far too often the answers on SO and the like is canned and dissimissive; "you don't need to optimize because who cares youre writing a crud app anyway".
- armchairhacker 3y ago
  The very first CS class taught at my undergraduate, where many students get exposed to programming the very first time and solve the simplest problems in functional style (e.g. list map, fold, fibonacci), introduces problems which require optimizations in the later part. No matter how powerful your computer and how small your computer program is, you have to optimize at least the exponential-time algorithms, and sometimes the high-degree-polynomial ones. When writing a real-time or production app you have to optimize many polynomial or even linear-time algorithms. Micro-optimizations like allocation and boxed numbers? Unnecessary unless you need performance, only apply a constant multiplier to your program’s speed. But macro-optimizations which affect time complexity can’t be ignored.
  - saagarjha 3y ago
    Algorithmic time complexity is a very important, but I honestly feel like a typical university education heavily underemphasizes exactly how much the constant factor can matter. Like, consider a simple example: someone's hand-written memcpy in C might achieve, say, 500 MB/s, maybe 1 GB/s if the loop is particularly tight. The one that ships on your system likely does 20-100 GB/s. Same big-O on both, of course. Most cases aren't this easy but there is a lot of performance that comes from constant factor optimization, which can dwarf all sorts of clever algorithms that are theoretically more efficient. Everyone likes to go "ok well if I scale this to a billion users your algorithm takes a month and mine takes a minute" but it is very likely that between now and the billion users the code is probably not even going to look anywhere near the same. But it's likely to be running on the same JVM or the same OS or the same allocator and all of those have been optimized to cut their constant factor down. After all, you don't want to be the guy who has the same algorithmic complexity as your competitor but your cloud bill is twice as much. (This isn't to say you shouldn't do algorithmic improvements, and most of the performance work I do is in fact along those lines, but I do want to clarify that the "micro-optimizations" you're talking about are in fact the difference between a computer from today and the 1990s.)
nerpderp82 3y ago
v = [ random.randrange(0, 100) for _ in range(1000) ] %timeit sorted(v) ## include a free extra allocation 71.2 µs ± 1.99 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
- deleted 3y ago
  [deleted]
morelisp 3y ago
> it's difficult to measure the indirect impact of things like memory locality — I have heard such factors blamed for poor performance much more often than I have seen such factors proven as responsible for poor performance. In general, I only look to such factors when I'm getting desperate. No thanks. Cache-related perf counters are easily measurable, but the impacts are so big you rarely need them.
- deleted 3y ago
  [deleted]
webnrrd2k 3y ago
Its a good post, but I'd add that there isvalso a different kind of optimization where you optimize by minimizing th overall cognitive load of any given code. For example, it's important to develop a feel for data structures. Often, if you choose the right data structure, the algorithm is fairly easy. In other words, when faced with a choice of complex algorithm vs complex data structures, it's generally easier to work with a complex data structure and use a simpler algorithm. Data is fairly static, and therefore easier to reason about, vs a complex and "dynamic" algorithm. Optimization for ease of reading and maintenance is also really important.
- hinkley 3y ago
  A great example of this is Norvig’s sudoku solver. Arranging the data the right way makes solving the problem a mere matter of correct bookkeeping .
  - webnrrd2k 3y ago
    Yes, great example. I forgot about that one.
  - keyle 3y ago
    ref. https://norvig.com/sudoku.html https://norvig.com/sudoku.html
jandrewrogers 3y ago
> it's difficult to measure the indirect impact of things like memory locality — I have heard such factors blamed for poor performance much more often than I have seen such factors proven as responsible for poor performance This particular assertion does not seem to be well-founded. The importance of spatial and temporal locality to software performance on modern hardware is a singular obsession of data-intensive software architectures. Nor is it difficult to measure, these are some of the highest impact optimizations you can make assuming the code isn't naive. There are perf counters and such but the majority of poor locality is visible via simple code inspection. You don't need perf counters until you are doing serious performance engineering. Locality optimization tends to be architectural in nature. If you do not design your software to have good locality characteristics then it will be complex to fix later. An argument can be made that it isn't worth the cost to fix software designs with poor locality after the fact, but the centrality of locality to software optimization is not controversial.
- lmm 3y ago
  Anything that can't be objectively measured will inherently be controversial. You claim you can see poor locality via code inspection; will other people who inspect the same code reach the same conclusions? Why should we believe you rather than anyone else?
  - jmoss20 3y ago
    Agreed with the general point, but it doesn't apply here. Memory locality can be objectively measured (e.g. with last level cache miss counters), and parent comment is correct besides -- it's usually plain to see in the code. There are mysterious boogiemen in performance optimization, but this isn't really one of them.
    - mejutoco 3y ago
      I am happy (good) science does not take the "is obvious" claim as sufficient, and instead focuses on proving things with objective facts. I am not saying these cannot be plain to see in the code, but the best standard IMO is still to measure before and after the optimization. IMHO, again, you can skip that step, but then other people might rightfully ask you what proof you have that the optimization is faster (I would).
orf 3y ago
> For anything but the smallest lists [6], binary search is much quicker than the linear search above. > In my experience, binary search becomes faster than linear search after about 8-12 elements It depends on your data, but CPUs are extremely good at scanning through contiguous vectors. Binary searching might make a difference at tens of thousands of elements. If you’re using Python then it’s different as nothing is contiguous, or you have a complex equality function, but then a simple improvement is to put the data in a numpy array of dataframe.
- hinkley 3y ago
  > or you have a complex equality function This is part of my thesis that Knuth today is wrong to the point of harm. That we need a new complexity theory built on top of Information Theory. We are steering kids wrong more often than right at this point. Data sets we work with are at least six orders of magnitude larger than they were in the eighties. There are almost no comparisons in Real Data that run in constant time, and for big enough n even addition and multiplication are not constant time. For large enough n, storage accesses are sqrt(n). Even in primary storage. Imagine you have a list of a million distinct strings. Case sensitive, alphanumeric. Complexity theory tells us you can sort those in nlogn time. But that’s pure fantasy because n unique strings have an average length of logn, meaning the compares all take logn time. Mergesort for any real data type is n (logn)². Now sort a quintillion unique strings. That takes 65-70 exabytes of space, just for starters, so it’s going to involve Ethernet cables and NVME RAID arrays. Your mergesort is now in the neighborhood of n^1.5 (log n)². Your piece of paper says this might run in hours, while the real implementation runs for weeks. For most purposes, you should multiply every algorithm in TAOC by logn. In some cases, sqrt(n). And as n actually approaches infinity, multiply by both. From another angle, I think the fact that it took 54 years to get from mergesort to Timsort has more to do with sacred cows than Tim’s brilliance. I’d like to see benchmarks on Pentium hardware, maybe even 486. “If I have not seen further it is because giants are stepping on my toes.”
  - mythhabit 3y ago
    The complexity of sorting is done in comparisons. If your system can compare in constant time the complexity is indeed n*log n - if your strings are limited in length there is a constant time upper limit and the complexity holds. Saying that the average length of input strings are log n, seems to be for specific data sets and not a general conclusion. Remember that big-O notation is not about calculating the actual runtimes, but the growths as the input grows. One of the first things you learn in theory is that you must profile this no matter what. Basic complexity theory is not concerned with access times because they work in operations. If your operation involves slow random access over network, then that is the basis. There are branches of complexity theory that takes those exact examples into account. Branches that proves certain time complexity in arbitrary cache hierarchy, or only allow streaming algorithms with no lookback. They all explicitly do this in terms of IO operations. The basic theory is fine, and should be as it is for an introduction. Trying to teach a novice with respect to extremely complex CPUs or broader computer architecture is premature and sure to make many run away screaming. The overarching message should be, and in my experience is, that theory only guides you and profiling is superior.
from-nibly 3y ago
He forgot the most powerful optimization of all. Redirecting to /dev/null. Or in other words just not doing it in the first place. As dumb as it sounds it's really easy to get caught up in optimizing stuff you just flat out don't need to do.
- howenterprisey 3y ago
  Very true. At work we have "the first and most important thing to optimize is the requirements" as a principle and it works well.
- hinkley 3y ago
  The fastest code is the code that never runs.
YoshiRulz 3y ago
> I think that, in general, most programmers struggle to accept that correctness can sometimes be traded-off—personally, it offends a deep internal conviction of mine that programs should be correct. [...] possible incorrectness more often causes problems. I might be happy trading off a bit of image-quality for better compression, but if an ML system rewrites my code and leaves off a "not" I'm unhappy. I'm torn on this point. On the one hand, I'm as fallible as any human, and reading this has made me aware of a bias I've always had but never realised was there. But on the other hand, our field is young, and there are surely better, correct solutions to be found for things like compression and sorting. So with that assumption, I find it tempting to label programmers who trade correctness for speed or size (e.g. using JPEG when QOI and WebP exist) as 'lazy', since "they haven't exhausted all other options". Obviously that's not fair—it ignores practicality and trivialises the discovery of novel algorithms—but I feel there's still some truth in it.
- Karellen 3y ago
  I'm always reminded of the aphorism: If my solution doesn't have to be correct, `return 0` runs in a couple of cycles and uses zero additional memory. The complication, of course, is (as the original author explains) that - with respect to some problems - there are degrees of correctness in the solution space, and some specific, limited trade-offs may be acceptable.
matheusmoreira 3y ago
The linked paper about PyPy's homogeneous collections optimization is extremely interesting: https://tratt.net/laurie/research/pubs/html/bolz_diekmann_tratt__storage_strategies_for_collections_in_dynamically_typed_languages/ https://tratt.net/laurie/research/pubs/html/bolz_diekmann_tr... Would be nice to have a collection of such techniques for increasing performance sorted by effort required...
lifthrasiir 3y ago
> Exactly what constitutes "correct" varies from one situation to another. For example, fast inverse square root approximates multiplicative inverse: for situations such as games, its fast nearly-correct answer is a better trade-off than a slow definitely-correct answer. Amazingly in topic, the famous constant 0x5f3759df from this algorithm was also thought to be derived from an approximate search algorithm because you need ~2^31 calls to determine the maximal relative error for a single constant---a big deal back in 1980s. A better constant 0x5f375a86 was only found in 2003, and took a few more years to be proven optimal (Robertson 2012, Moroz et al. 2016).
say_it_as_it_is 3y ago
I don't agree with this categorization and it leaves out other important considerations: - Data structure and algorithm are of the same "algorithm" topic - Some programming languages like Rust do not have tail-call optimization and so do not perform recursion well. You need to use the strengths of the language and avoid its weaknesses. - IO Optimization is another kind of optimization. Minimizing copies of data in memory, sharing whatever possible - Cache Optimization - design according to how CPU caches work with the operating system
ttfkam 3y ago
I think "use a better data structure" needs to be #1. If you have a bad data structure for your use cases, no algorithm change will save you. If you have a linked list and your use case tends toward non-sequential search and access, tweaking the algorithm only burns cycles that could be spent switching up. If you have an ordered array and need to insert/delete values in the middle, you are similarly hobbled in performance. Then there's cache coherence when interacting with hardware, which is heavily influenced by data structure. Data structures should come first when developing and optimizing.
AtlasBarfed 3y ago
- parallelization

120 points by ltratt 3y ago

This is a great article, and I have some notes. I initially disagreed with the author when he said, "we tend to overestimate how much we know about the software we're working on." I disagreed because that is not my experience; I do know a lot about my software. However, then he said, "We overemphasise the parts of the system we've personally worked on, particularly those we've most recently worked on. We downplay other parts of the system, including the impact of dependencies (e.g. libraries)." Oh. Um, well, this is also not my experience. I work on software alone, and I do not have any dependencies. So the author is right; I just have weird experience. :) I agree with the four kinds of optimization, especially since he focuses on optimization humans do. I think you could even shoehorn compiler optimizations into those four. For example, strength reduction could be considered a "better algorithm." His observations about the differences between best, average, and worst cases are the things programmers need to learn most. At some point, our code will always hit bad cases, and we need to know if it will hit it often. I love his example of Timsort because I've analyzed and implemented it myself. It ended being more comments than code. (Of course, that includes two license header comments, so slightly less comments than code actually.) Timsort is pretty complicated, and Tim isn't the best at naming things, so it took a bit for me to understand what was going on. (The most prominent example is the galloping functions. He named them "gallop_left" and "gallop_right," but they both gallop left and right. I renamed them to "gallop2Leftmost" and "gallop2Rightmost," which is actually what they do.) The author says he biases to writing algorithms and adopting pre-written data structures. This is a good thing. However, after having written data structures (because I work in C, which doesn't have them), I would encourage every programmer to write some. Best, average, and worst cases are easier to learn on data structures than algorithms. Still use pre-written ones though; they are usually better optimized. The trick about reducing memory is crucial. I recently spent an entire refactor just reducing the size of some of the most-used structs. I cut the size of one struct in half. `pahole` is great for this. The part of PyPy is a great example too. A great book to read is Is Parallel Programming Hard, And, If So, What Can You Do About It? The entire point of the book is to make you think, "Okay, I need some concurrency or parallelism; what is the easiest way to get it?" The PyPy example is that same thing with optimization; what's the easiest way to get the performance you need? Every time you run into an optimization problem, ask that question first, and it will get faster to answer every time. And the author's summary reinforces this. [1]: https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.2022.09.25a.pdf https://mirrors.edge.kernel.org/pub/linux/kernel/people/paul...

dj_mc_merlin 3y ago
> However, then he said, "We overemphasise the parts of the system we've personally worked on, particularly those we've most recently worked on. We downplay other parts of the system, including the impact of dependencies (e.g. libraries)." > Oh. Um, well, this is also not my experience. > I work on software alone, and I do not have any dependencies. If you work in a company of 100+ engineers with multiple specialties it's impossible to keep up with everything. At <50 engineers if you collaborate and/or switch teams it's possible to know almost everything, but that's the most I think the majority of us have the internal storage/RAM for.
- gavinhoward 3y ago
  Yes, I said as much in my comment.
- ska 3y ago
  I suspect your thresholds are far too high, and that some specialties are almost mutually incomprehensible, so rare for one person to properly understand what is going on. Time is a real factor also. How long has this code base been accumulating...
  - dj_mc_merlin 3y ago
    Early on in the company I work we had a practice of collaborating across teams, sharing members etc. so a lot of us knew a lot of the code base from "different angles". If you implemented a backend feature you might write also write the terraform and the frontend that worked with it, with some input from the people experienced in those things. Kind of like random full-stack development? Slower than normal development at first but it makes future collaboration easier. It was quite great, but unsustainable as the amount of people grows. edit: I think in general at the early stages of a company you hire a lot of people who are good at adapting and learning new skills since they might need to fill new roles quickly as new needs arise. So those people are good at this kind of full stack development since it's their niche. As you grow, you hire more specialized or junior people, and they can't do this process quickly enough for it to feel fluid anymore.

llamajams 3y ago

There needs to be more articles like this, far too often the answers on SO and the like is canned and dissimissive; "you don't need to optimize because who cares youre writing a crud app anyway".

armchairhacker 3y ago
The very first CS class taught at my undergraduate, where many students get exposed to programming the very first time and solve the simplest problems in functional style (e.g. list map, fold, fibonacci), introduces problems which require optimizations in the later part. No matter how powerful your computer and how small your computer program is, you have to optimize at least the exponential-time algorithms, and sometimes the high-degree-polynomial ones. When writing a real-time or production app you have to optimize many polynomial or even linear-time algorithms. Micro-optimizations like allocation and boxed numbers? Unnecessary unless you need performance, only apply a constant multiplier to your program’s speed. But macro-optimizations which affect time complexity can’t be ignored.
- saagarjha 3y ago
  Algorithmic time complexity is a very important, but I honestly feel like a typical university education heavily underemphasizes exactly how much the constant factor can matter. Like, consider a simple example: someone's hand-written memcpy in C might achieve, say, 500 MB/s, maybe 1 GB/s if the loop is particularly tight. The one that ships on your system likely does 20-100 GB/s. Same big-O on both, of course. Most cases aren't this easy but there is a lot of performance that comes from constant factor optimization, which can dwarf all sorts of clever algorithms that are theoretically more efficient. Everyone likes to go "ok well if I scale this to a billion users your algorithm takes a month and mine takes a minute" but it is very likely that between now and the billion users the code is probably not even going to look anywhere near the same. But it's likely to be running on the same JVM or the same OS or the same allocator and all of those have been optimized to cut their constant factor down. After all, you don't want to be the guy who has the same algorithmic complexity as your competitor but your cloud bill is twice as much. (This isn't to say you shouldn't do algorithmic improvements, and most of the performance work I do is in fact along those lines, but I do want to clarify that the "micro-optimizations" you're talking about are in fact the difference between a computer from today and the 1990s.)

nerpderp82 3y ago

v = [ random.randrange(0, 100) for _ in range(1000) ] %timeit sorted(v) ## include a free extra allocation 71.2 µs ± 1.99 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

deleted 3y ago
[deleted]

morelisp 3y ago

> it's difficult to measure the indirect impact of things like memory locality — I have heard such factors blamed for poor performance much more often than I have seen such factors proven as responsible for poor performance. In general, I only look to such factors when I'm getting desperate. No thanks. Cache-related perf counters are easily measurable, but the impacts are so big you rarely need them.

deleted 3y ago
[deleted]

webnrrd2k 3y ago

Its a good post, but I'd add that there isvalso a different kind of optimization where you optimize by minimizing th overall cognitive load of any given code. For example, it's important to develop a feel for data structures. Often, if you choose the right data structure, the algorithm is fairly easy. In other words, when faced with a choice of complex algorithm vs complex data structures, it's generally easier to work with a complex data structure and use a simpler algorithm. Data is fairly static, and therefore easier to reason about, vs a complex and "dynamic" algorithm. Optimization for ease of reading and maintenance is also really important.

hinkley 3y ago
A great example of this is Norvig’s sudoku solver. Arranging the data the right way makes solving the problem a mere matter of correct bookkeeping .
- webnrrd2k 3y ago
  Yes, great example. I forgot about that one.
- keyle 3y ago
  ref. https://norvig.com/sudoku.html https://norvig.com/sudoku.html

jandrewrogers 3y ago

> it's difficult to measure the indirect impact of things like memory locality — I have heard such factors blamed for poor performance much more often than I have seen such factors proven as responsible for poor performance This particular assertion does not seem to be well-founded. The importance of spatial and temporal locality to software performance on modern hardware is a singular obsession of data-intensive software architectures. Nor is it difficult to measure, these are some of the highest impact optimizations you can make assuming the code isn't naive. There are perf counters and such but the majority of poor locality is visible via simple code inspection. You don't need perf counters until you are doing serious performance engineering. Locality optimization tends to be architectural in nature. If you do not design your software to have good locality characteristics then it will be complex to fix later. An argument can be made that it isn't worth the cost to fix software designs with poor locality after the fact, but the centrality of locality to software optimization is not controversial.

lmm 3y ago
Anything that can't be objectively measured will inherently be controversial. You claim you can see poor locality via code inspection; will other people who inspect the same code reach the same conclusions? Why should we believe you rather than anyone else?
- jmoss20 3y ago
  Agreed with the general point, but it doesn't apply here. Memory locality can be objectively measured (e.g. with last level cache miss counters), and parent comment is correct besides -- it's usually plain to see in the code. There are mysterious boogiemen in performance optimization, but this isn't really one of them.
  - mejutoco 3y ago
    I am happy (good) science does not take the "is obvious" claim as sufficient, and instead focuses on proving things with objective facts. I am not saying these cannot be plain to see in the code, but the best standard IMO is still to measure before and after the optimization. IMHO, again, you can skip that step, but then other people might rightfully ask you what proof you have that the optimization is faster (I would).

orf 3y ago

> For anything but the smallest lists [6], binary search is much quicker than the linear search above. > In my experience, binary search becomes faster than linear search after about 8-12 elements It depends on your data, but CPUs are extremely good at scanning through contiguous vectors. Binary searching might make a difference at tens of thousands of elements. If you’re using Python then it’s different as nothing is contiguous, or you have a complex equality function, but then a simple improvement is to put the data in a numpy array of dataframe.

hinkley 3y ago
> or you have a complex equality function This is part of my thesis that Knuth today is wrong to the point of harm. That we need a new complexity theory built on top of Information Theory. We are steering kids wrong more often than right at this point. Data sets we work with are at least six orders of magnitude larger than they were in the eighties. There are almost no comparisons in Real Data that run in constant time, and for big enough n even addition and multiplication are not constant time. For large enough n, storage accesses are sqrt(n). Even in primary storage. Imagine you have a list of a million distinct strings. Case sensitive, alphanumeric. Complexity theory tells us you can sort those in nlogn time. But that’s pure fantasy because n unique strings have an average length of logn, meaning the compares all take logn time. Mergesort for any real data type is n (logn)². Now sort a quintillion unique strings. That takes 65-70 exabytes of space, just for starters, so it’s going to involve Ethernet cables and NVME RAID arrays. Your mergesort is now in the neighborhood of n^1.5 (log n)². Your piece of paper says this might run in hours, while the real implementation runs for weeks. For most purposes, you should multiply every algorithm in TAOC by logn. In some cases, sqrt(n). And as n actually approaches infinity, multiply by both. From another angle, I think the fact that it took 54 years to get from mergesort to Timsort has more to do with sacred cows than Tim’s brilliance. I’d like to see benchmarks on Pentium hardware, maybe even 486. “If I have not seen further it is because giants are stepping on my toes.”
- mythhabit 3y ago
  The complexity of sorting is done in comparisons. If your system can compare in constant time the complexity is indeed n*log n - if your strings are limited in length there is a constant time upper limit and the complexity holds. Saying that the average length of input strings are log n, seems to be for specific data sets and not a general conclusion. Remember that big-O notation is not about calculating the actual runtimes, but the growths as the input grows. One of the first things you learn in theory is that you must profile this no matter what. Basic complexity theory is not concerned with access times because they work in operations. If your operation involves slow random access over network, then that is the basis. There are branches of complexity theory that takes those exact examples into account. Branches that proves certain time complexity in arbitrary cache hierarchy, or only allow streaming algorithms with no lookback. They all explicitly do this in terms of IO operations. The basic theory is fine, and should be as it is for an introduction. Trying to teach a novice with respect to extremely complex CPUs or broader computer architecture is premature and sure to make many run away screaming. The overarching message should be, and in my experience is, that theory only guides you and profiling is superior.

from-nibly 3y ago

He forgot the most powerful optimization of all. Redirecting to /dev/null. Or in other words just not doing it in the first place. As dumb as it sounds it's really easy to get caught up in optimizing stuff you just flat out don't need to do.

howenterprisey 3y ago
Very true. At work we have "the first and most important thing to optimize is the requirements" as a principle and it works well.
hinkley 3y ago
The fastest code is the code that never runs.

YoshiRulz 3y ago

> I think that, in general, most programmers struggle to accept that correctness can sometimes be traded-off—personally, it offends a deep internal conviction of mine that programs should be correct. [...] possible incorrectness more often causes problems. I might be happy trading off a bit of image-quality for better compression, but if an ML system rewrites my code and leaves off a "not" I'm unhappy. I'm torn on this point. On the one hand, I'm as fallible as any human, and reading this has made me aware of a bias I've always had but never realised was there. But on the other hand, our field is young, and there are surely better, correct solutions to be found for things like compression and sorting. So with that assumption, I find it tempting to label programmers who trade correctness for speed or size (e.g. using JPEG when QOI and WebP exist) as 'lazy', since "they haven't exhausted all other options". Obviously that's not fair—it ignores practicality and trivialises the discovery of novel algorithms—but I feel there's still some truth in it.

Karellen 3y ago
I'm always reminded of the aphorism: If my solution doesn't have to be correct, `return 0` runs in a couple of cycles and uses zero additional memory. The complication, of course, is (as the original author explains) that - with respect to some problems - there are degrees of correctness in the solution space, and some specific, limited trade-offs may be acceptable.

matheusmoreira 3y ago

The linked paper about PyPy's homogeneous collections optimization is extremely interesting: https://tratt.net/laurie/research/pubs/html/bolz_diekmann_tratt__storage_strategies_for_collections_in_dynamically_typed_languages/ https://tratt.net/laurie/research/pubs/html/bolz_diekmann_tr... Would be nice to have a collection of such techniques for increasing performance sorted by effort required...

lifthrasiir 3y ago

> Exactly what constitutes "correct" varies from one situation to another. For example, fast inverse square root approximates multiplicative inverse: for situations such as games, its fast nearly-correct answer is a better trade-off than a slow definitely-correct answer. Amazingly in topic, the famous constant 0x5f3759df from this algorithm was also thought to be derived from an approximate search algorithm because you need ~2^31 calls to determine the maximal relative error for a single constant---a big deal back in 1980s. A better constant 0x5f375a86 was only found in 2003, and took a few more years to be proven optimal (Robertson 2012, Moroz et al. 2016).

say_it_as_it_is 3y ago

I don't agree with this categorization and it leaves out other important considerations: - Data structure and algorithm are of the same "algorithm" topic - Some programming languages like Rust do not have tail-call optimization and so do not perform recursion well. You need to use the strengths of the language and avoid its weaknesses. - IO Optimization is another kind of optimization. Minimizing copies of data in memory, sharing whatever possible - Cache Optimization - design according to how CPU caches work with the operating system

ttfkam 3y ago

I think "use a better data structure" needs to be #1. If you have a bad data structure for your use cases, no algorithm change will save you. If you have a linked list and your use case tends toward non-sequential search and access, tweaking the algorithm only burns cycles that could be spent switching up. If you have an ordered array and need to insert/delete values in the middle, you are similarly hobbled in performance. Then there's cache coherence when interacting with hardware, which is heavily influenced by data structure. Data structures should come first when developing and optimizing.

AtlasBarfed 3y ago

- parallelization