19 ms·

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. Many years ago I was

Algorithms are important but are especially powerful in combination of knowing computer architecture and programming language intricacies. Many years ago I was asked to look at the program written in C++ that calculated Kendall-tau correlation matrix for a large amount of data. Basically Kendall Tau is a robust replacement for Pearson correlation and it had to be calculated for 0.5M^2 elements and calculation of each element needed calculation of Kendall Tau on two series of numerical data of length N. Both M and N were on an order of few thousand and naive implementation has the complexity O(N^2 x M^2). The program ran for 6+ hours. After looking at C++ I realized that a lot of time is spent just copying data needlessly (a result of not knowing the difference between passing a vector and reference to it) and needless memory allocations and deallocations. I did a rewrite from scratch, keeping the tests, but not copying anything and allocating a minimum amount of memory only once, employing the cache locality, spreading the calculation with OpenMP and finally - realizing that Kendall Tau can be done in O(M^2 x Nlog(N)) I found that out on my own, just by squinting and realizing that calculation of Kendall tau for two series is essentially sorting, but later found out that e.g. scipy implementation uses the same approach. The resulting program ran for 4 minutes on a 2-core and 4 threads.

brilee 6y ago
I realized the same thing when trying to compute F1-optimized thresholds; scanning through all possible threshold scores is O(n^2) but computing f1 score inline while scanning through the sorted array is O(n). https://www.moderndescartes.com/essays/auc_intuition/ https://www.moderndescartes.com/essays/auc_intuition/ is my writeup on why the sorting approach is the most economical way to approach this sort of problem
- Phemist 6y ago
  Interesting! Thanks for the write-up. In the field of Biometrics we often use the library BOB to compute scores like AUC's and EER's, or other measures over stuff like DET curves. For some practical work I was doing, BOB (and SK learn) proved too slow for my liking. I am currently unable to provide much more detail, but I used a similar insight to yours (mine was the amortization of sorting costs to have a better average time complexity) in a library I built for calculating empirical, bootstrapped, confidence intervals for EER's. https://github.com/feerci/feerci https://github.com/feerci/feerci For massive amounts of decision scores, like millions, this method can give you confidence intervals on EER's where no other library currently in use can. Unfortunately, I have not yet found a theoretical basis for this method, and suspect it might actually break down under some trivial smaller cases. Also, DET curves and their derived measures remain a tough cookie to crack. Considering AUC's and EER's are somewhat tightly related, I'm thinking this method could also be applied to AUC's.
neves 6y ago
This is a usual problem with C++ and why I hate it. There's a lot going on under the hoods, and you must be really knowledgeable of the language to prevent stupid things. Following some idioms you can really avoid it, but it is useless since your coworkers will fall into the language traps.
- qayxc 6y ago
  I'd argue that not knowing the language you're working with is a problem that's not exclusive to C++. There's so much more going on under the hood of more high level languages, that writing faster code is straight up black magic [1]. [1] https://stackoverflow.com/questions/28723658/python-why-is-it-faster-to-iterate-over-a-list-than-iterating-over-an-xrange https://stackoverflow.com/questions/28723658/python-why-is-i...
  - throwaway894345 6y ago
    Yes, you must always know your language, but mastering (for example) Go is a lot easier than getting a cursory understanding of C++ (i.e., enough to write correct code for non-toy applications). You can get a cursory understanding of Go in a few hours and you can master it in 1-2 months. It would be months and years in C++, respectively. C++ is just a much larger, more complex language, so there is a lot more to know. It's not that C++ is inherently bad--some of that complexity allows C++ to be faster and more powerful than Go; however, we can't pretend that the two are equivalent with respect to their ease of learning or number of footguns.
    - qayxc 6y ago
      I agree in general, but knowing the difference between pass-by reference and pass-by value is C++ 101. Mastering C++ isn't even required to be productive using it, since there's no need to use all the language features simply because they exist. This also avoids the majority of footguns.
      - throwaway894345 6y ago
lmm 6y ago
So did you measure how much of the speed improvement came from your careful memory copying tuning and how much came from the algorithmic change?
- TYMorningCoffee 6y ago
  Yeah. The commenter only gave the numbers when both the constant factor and the improved algorithm were applied. It would be interesting to see them applied separately. The commenters claim that both are important has not been shown by his example yet. However the results are impressive. Great job with the solution.
- mynegation 6y ago
  At the time, yes, but I do not have those numbers anymore. Trying my best to remember - I would estimate that the speedup of 360 / 4 = 90x is approximately: 4x multithreading (it was pretty linear speedup), 7x the algorithm and 3x the memory inefficiencies. EDIT: fixed my math, thank you andruby
  - andruby 6y ago
    Sorry to correct your math here, but going from 6 hours (6*60=360 minutes) to 4 minutes is a 90x improvement, not 900x.
    - ath92 6y ago
      Interestingly, a speedup of 2 orders of magnitude seems to be about what you'd expect if you only apply the algorithmic optimization (going from N^2 to Nlog(N) with N being in the range of a few thousand, like OP said)
      - mynegation 6y ago
        Like I mentioned - my memory is pretty hazy about the specific speedups. Yes, N^2 to NlogN feels like it should be a bigger factor, but remember that constants in front of this matter. You are replacing 2-level nested but very straightforward loops that rip through cached memory at blazing speed without any disruption to CPU pipelines with a single loop that involves quite a bit of condition checking and array element swaps (cache is busted, pipelines are busted - conditions are very hard to predict). You gain some, you lose some.
mumblemumble 6y ago
makes me think of https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/ https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/
- antisthenes 6y ago
  That was a great read for someone who's used VBA to solve business cases, including InStr. Anecdata, but most of my strings were indeed short (searching for manufacturer SKUs inside arrays of other SKUs).
- mynegation 6y ago
  Ha! Great story, thank you! Clearly shows that computational complexity by itself is not very useful without knowing the assumptions. It is one thing to see substring search and immediately pattern match it to something from CS course like Boyer-Moore or Knuth-Morris-Pratt, but these algorithms require pre-processing that makes sense only if you know you are going to search for the same pattern repeatedly. Pure library function cannot make that assumption, and REPNE instruction is just an icing on a cake.
  - ghusbands 6y ago
    > pre-processing that makes sense only if you know you are going to search for the same pattern repeatedly The pre-processing is typically worth it if you're searching through a large string, even just once.
- monksy 6y ago
  That was a great write up explaining about not seeing the forest for the trees. However, it is still infuriating that we're getting these leetcode questions in interviews to see how much you can hack and optimize a toy problem. (As if you had lots of time to think about it and work through it)
8ytecoder 6y ago
This is at the very least a clever and involved optimization. Let me tell you the story of my similar 10h to 10min fix. We had this cronjob that was supposed to run every hour, detect all changes to the customers and related table and sync with the marketing saas tool. It was written in Rails and took 10 mins at first. As we grew the time taken by this job also grew linearly. To a point where it took 10 hours and we could only sync the data twice a day. As it turns out the job was loading each user and then scanning for changes. We switched it into a somewhat complex sql query and MySQL ran it in a few mins. Add the additional processing and the whole job now took 10 mins.
- mesarvagya 6y ago
  Sounds like classic n+1 problem
  - stouset 6y ago
    Or more likely, the classic “fetch an entire table from the database and work on it locally” problem that seems endemic in code written by people who don’t understand the capabilities of SQL. Works great in dev with a local sqlite instance and ten rows. Not so great in prod.
- tetha 6y ago
  This is when being the guy knowing a few database tricks is fun. We had one reporting query that ran for 13 hours or so, in a normal web request. Not very successful, but it tried its best. Running this through explain while thinking of daloks revealed some dependent subqueries. Those are the devil in mysql because they are evaluated per row in the outer query. That takes a lot of time very quickly. Eventually we wrangjangled the dependency into a terrifying group by such that the dependent query could be precomputed and the outer query just joins with the result. Boom, runtime down to 2 minutes. In another case everyone panicked ... until one of my dudes added an index - which took about a day - and slashed runtimes from 18 hour to 12 minutes. Learning to optimize queries on your RDBMS of choice is very powerful.
  - 6y ago
hinkley 6y ago
I was asked once in an interview what the hardest part of programming was, and I said it wasn't Order of Complexities, it was the C constant within it. Interviewer was not subtle in thinking that was stupid. My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are diffuse - they're literally everywhere, and they don't always show up on a flame graph. On one project I got a 2x improvement in overall performance by fixing issues that weren't visible in the perf output, and would have been invisible on a flame graph (this was before flame graphs). C is particularly a bigger issue once you consider Amdahl's law. A 20% slowdown in a linear part of the code can show up as a second-for-second slowdown in response times, while a search algorithm that's only a small part of an overall process, or parallelized, you can make it 10 times faster and might only see a 2% improvement in response times. If you avoid allocating more servers, for a new feature, nobody celebrates your achievement. You have to do it wrong the first time for anyone to notice you.
- kadoban 6y ago
  I'd argue that none of that is the hardest part of programming, or at least what I'd focus on in terms of what comes up the most and what effects users and developers and suits the most. Judging by those, the most important hard parts are around planning and estimating work, and correctly understanding when those make no sense, and in validating code for correctness, especially over time. If we ignore importance and just go with what's the hardest single task: naming things.
  - hinkley 6y ago
    First, there is no one answer here. When we specialize we take on some 'hard parts' and delegate other hard parts to other people. Civilization is predicated on you and I having different definitions of 'difficult'. But I think they're of a piece. All of these things are "meatspace" problems. We are constantly fighting the temptation to try to intellectualize the whole process of making software because the center of the problem is trying to interact with a machine. Some don't fight that temptation at all. You see this problem when people fight automation because they expect everyone to execute a manual process perfectly every time, even when the consequences of failure are very high. They insist that everybody white-knuckle everything and think less of you if you don't agree. They victim-blame. When they're the founding or oldest surviving members of a project, you're gonna have a bad time. People who could fix the problem move on to other jobs. Naming things is really the same class of problem. A bad name calls to mind assumptions that are not relevant, and you are in constant danger of making category errors every time you think about that part of the code. A bad name becomes a sort of attractive nuisance. The C problem is a matter of motivating people to do the right thing. Because it's difficult to spot, it's an invisible sin. It rarely comes up in code reviews, so nobody will call you out on it, nobody will make you fix it, finding it after the fact is daunting, and the only people who will care (eg sales) are so often the source of other problems that pleasing them is almost a character flaw. If performance is a feature, then constant time regressions are one of our worst games of whack-a-mole (behind security and internationalization, maybe ahead of sane logging). [ETA:] I'm just a weirdo who likes to tilt at some kinds of problems I find hard, instead of dumping them on someone else.
sdenton4 6y ago
Meanwhile, there's a perception that machine learning is hardware-bound for speed increases, which just isn't true. I work on a pretty heavy ML system, which a year ago took about a month to 'fully' train. Today we're down to 25 hours training time using the same hardware, based mostly on improvements to the model. The improvements are coming from a combination of signal processing tricks and tricksy model changes. Inference is similarly much faster, too...
- EmbarrassedFuel 6y ago
  Sounds interesting, would you be able to share anything about the signal processing tricks?

brilee 6y ago

I realized the same thing when trying to compute F1-optimized thresholds; scanning through all possible threshold scores is O(n^2) but computing f1 score inline while scanning through the sorted array is O(n). https://www.moderndescartes.com/essays/auc_intuition/ https://www.moderndescartes.com/essays/auc_intuition/ is my writeup on why the sorting approach is the most economical way to approach this sort of problem

Phemist 6y ago
Interesting! Thanks for the write-up. In the field of Biometrics we often use the library BOB to compute scores like AUC's and EER's, or other measures over stuff like DET curves. For some practical work I was doing, BOB (and SK learn) proved too slow for my liking. I am currently unable to provide much more detail, but I used a similar insight to yours (mine was the amortization of sorting costs to have a better average time complexity) in a library I built for calculating empirical, bootstrapped, confidence intervals for EER's. https://github.com/feerci/feerci https://github.com/feerci/feerci For massive amounts of decision scores, like millions, this method can give you confidence intervals on EER's where no other library currently in use can. Unfortunately, I have not yet found a theoretical basis for this method, and suspect it might actually break down under some trivial smaller cases. Also, DET curves and their derived measures remain a tough cookie to crack. Considering AUC's and EER's are somewhat tightly related, I'm thinking this method could also be applied to AUC's.

neves 6y ago

This is a usual problem with C++ and why I hate it. There's a lot going on under the hoods, and you must be really knowledgeable of the language to prevent stupid things. Following some idioms you can really avoid it, but it is useless since your coworkers will fall into the language traps.

qayxc 6y ago
I'd argue that not knowing the language you're working with is a problem that's not exclusive to C++. There's so much more going on under the hood of more high level languages, that writing faster code is straight up black magic [1]. [1] https://stackoverflow.com/questions/28723658/python-why-is-it-faster-to-iterate-over-a-list-than-iterating-over-an-xrange https://stackoverflow.com/questions/28723658/python-why-is-i...
- throwaway894345 6y ago
  Yes, you must always know your language, but mastering (for example) Go is a lot easier than getting a cursory understanding of C++ (i.e., enough to write correct code for non-toy applications). You can get a cursory understanding of Go in a few hours and you can master it in 1-2 months. It would be months and years in C++, respectively. C++ is just a much larger, more complex language, so there is a lot more to know. It's not that C++ is inherently bad--some of that complexity allows C++ to be faster and more powerful than Go; however, we can't pretend that the two are equivalent with respect to their ease of learning or number of footguns.
  - qayxc 6y ago
    I agree in general, but knowing the difference between pass-by reference and pass-by value is C++ 101. Mastering C++ isn't even required to be productive using it, since there's no need to use all the language features simply because they exist. This also avoids the majority of footguns.
    - throwaway894345 6y ago

lmm 6y ago

So did you measure how much of the speed improvement came from your careful memory copying tuning and how much came from the algorithmic change?

TYMorningCoffee 6y ago
Yeah. The commenter only gave the numbers when both the constant factor and the improved algorithm were applied. It would be interesting to see them applied separately. The commenters claim that both are important has not been shown by his example yet. However the results are impressive. Great job with the solution.
mynegation 6y ago
At the time, yes, but I do not have those numbers anymore. Trying my best to remember - I would estimate that the speedup of 360 / 4 = 90x is approximately: 4x multithreading (it was pretty linear speedup), 7x the algorithm and 3x the memory inefficiencies. EDIT: fixed my math, thank you andruby
- andruby 6y ago
  Sorry to correct your math here, but going from 6 hours (6*60=360 minutes) to 4 minutes is a 90x improvement, not 900x.
  - ath92 6y ago
    Interestingly, a speedup of 2 orders of magnitude seems to be about what you'd expect if you only apply the algorithmic optimization (going from N^2 to Nlog(N) with N being in the range of a few thousand, like OP said)
    - mynegation 6y ago
      Like I mentioned - my memory is pretty hazy about the specific speedups. Yes, N^2 to NlogN feels like it should be a bigger factor, but remember that constants in front of this matter. You are replacing 2-level nested but very straightforward loops that rip through cached memory at blazing speed without any disruption to CPU pipelines with a single loop that involves quite a bit of condition checking and array element swaps (cache is busted, pipelines are busted - conditions are very hard to predict). You gain some, you lose some.

mumblemumble 6y ago

makes me think of https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/ https://ericlippert.com/2020/03/27/new-grad-vs-senior-dev/

antisthenes 6y ago
That was a great read for someone who's used VBA to solve business cases, including InStr. Anecdata, but most of my strings were indeed short (searching for manufacturer SKUs inside arrays of other SKUs).
mynegation 6y ago
Ha! Great story, thank you! Clearly shows that computational complexity by itself is not very useful without knowing the assumptions. It is one thing to see substring search and immediately pattern match it to something from CS course like Boyer-Moore or Knuth-Morris-Pratt, but these algorithms require pre-processing that makes sense only if you know you are going to search for the same pattern repeatedly. Pure library function cannot make that assumption, and REPNE instruction is just an icing on a cake.
- ghusbands 6y ago
  > pre-processing that makes sense only if you know you are going to search for the same pattern repeatedly The pre-processing is typically worth it if you're searching through a large string, even just once.
monksy 6y ago
That was a great write up explaining about not seeing the forest for the trees. However, it is still infuriating that we're getting these leetcode questions in interviews to see how much you can hack and optimize a toy problem. (As if you had lots of time to think about it and work through it)

8ytecoder 6y ago

This is at the very least a clever and involved optimization. Let me tell you the story of my similar 10h to 10min fix. We had this cronjob that was supposed to run every hour, detect all changes to the customers and related table and sync with the marketing saas tool. It was written in Rails and took 10 mins at first. As we grew the time taken by this job also grew linearly. To a point where it took 10 hours and we could only sync the data twice a day. As it turns out the job was loading each user and then scanning for changes. We switched it into a somewhat complex sql query and MySQL ran it in a few mins. Add the additional processing and the whole job now took 10 mins.

mesarvagya 6y ago
Sounds like classic n+1 problem
- stouset 6y ago
  Or more likely, the classic “fetch an entire table from the database and work on it locally” problem that seems endemic in code written by people who don’t understand the capabilities of SQL. Works great in dev with a local sqlite instance and ten rows. Not so great in prod.
tetha 6y ago
This is when being the guy knowing a few database tricks is fun. We had one reporting query that ran for 13 hours or so, in a normal web request. Not very successful, but it tried its best. Running this through explain while thinking of daloks revealed some dependent subqueries. Those are the devil in mysql because they are evaluated per row in the outer query. That takes a lot of time very quickly. Eventually we wrangjangled the dependency into a terrifying group by such that the dependent query could be precomputed and the outer query just joins with the result. Boom, runtime down to 2 minutes. In another case everyone panicked ... until one of my dudes added an index - which took about a day - and slashed runtimes from 18 hour to 12 minutes. Learning to optimize queries on your RDBMS of choice is very powerful.
- 6y ago

hinkley 6y ago

I was asked once in an interview what the hardest part of programming was, and I said it wasn't Order of Complexities, it was the C constant within it. Interviewer was not subtle in thinking that was stupid. My rationale was - and is - that C is not sexy. It's hard to motivate people to look into it, and it's often hard work because a sort algorithm or a lookup table tend to be compartmentalized, while C issues are diffuse - they're literally everywhere, and they don't always show up on a flame graph. On one project I got a 2x improvement in overall performance by fixing issues that weren't visible in the perf output, and would have been invisible on a flame graph (this was before flame graphs). C is particularly a bigger issue once you consider Amdahl's law. A 20% slowdown in a linear part of the code can show up as a second-for-second slowdown in response times, while a search algorithm that's only a small part of an overall process, or parallelized, you can make it 10 times faster and might only see a 2% improvement in response times. If you avoid allocating more servers, for a new feature, nobody celebrates your achievement. You have to do it wrong the first time for anyone to notice you.

kadoban 6y ago
I'd argue that none of that is the hardest part of programming, or at least what I'd focus on in terms of what comes up the most and what effects users and developers and suits the most. Judging by those, the most important hard parts are around planning and estimating work, and correctly understanding when those make no sense, and in validating code for correctness, especially over time. If we ignore importance and just go with what's the hardest single task: naming things.
- hinkley 6y ago
  First, there is no one answer here. When we specialize we take on some 'hard parts' and delegate other hard parts to other people. Civilization is predicated on you and I having different definitions of 'difficult'. But I think they're of a piece. All of these things are "meatspace" problems. We are constantly fighting the temptation to try to intellectualize the whole process of making software because the center of the problem is trying to interact with a machine. Some don't fight that temptation at all. You see this problem when people fight automation because they expect everyone to execute a manual process perfectly every time, even when the consequences of failure are very high. They insist that everybody white-knuckle everything and think less of you if you don't agree. They victim-blame. When they're the founding or oldest surviving members of a project, you're gonna have a bad time. People who could fix the problem move on to other jobs. Naming things is really the same class of problem. A bad name calls to mind assumptions that are not relevant, and you are in constant danger of making category errors every time you think about that part of the code. A bad name becomes a sort of attractive nuisance. The C problem is a matter of motivating people to do the right thing. Because it's difficult to spot, it's an invisible sin. It rarely comes up in code reviews, so nobody will call you out on it, nobody will make you fix it, finding it after the fact is daunting, and the only people who will care (eg sales) are so often the source of other problems that pleasing them is almost a character flaw. If performance is a feature, then constant time regressions are one of our worst games of whack-a-mole (behind security and internationalization, maybe ahead of sane logging). [ETA:] I'm just a weirdo who likes to tilt at some kinds of problems I find hard, instead of dumping them on someone else.

sdenton4 6y ago

Meanwhile, there's a perception that machine learning is hardware-bound for speed increases, which just isn't true. I work on a pretty heavy ML system, which a year ago took about a month to 'fully' train. Today we're down to 25 hours training time using the same hardware, based mostly on improvements to the model. The improvements are coming from a combination of signal processing tricks and tricksy model changes. Inference is similarly much faster, too...

EmbarrassedFuel 6y ago
Sounds interesting, would you be able to share anything about the signal processing tricks?