7 ms·

Optimizations on Linear Search (2016)

73 points by YesThatTom2 6y ago

Kednicma 6y ago
I understand the rhetorical dodges here, but as both a career SRE and a student of CS, I don't see anything here which invalidates the theoretical asymptotic behavior. All of the nuance added here is a complement, not a replacement, for traditional theory. It is certainly true that the number of elements needs to be quite high before the question is theoretically interesting. The author is right to point out that L2 cache is quite large. Today's GPUs are also quite large in onboard RAM and have integer ALUs, so even millions of elements are not a problem for a basic consumer-grade video card. (Yes, I know that that sounds stupid, but GPUs and now TPUs in the datacenter are a real thing, even if they're quite unfair!)
dahart 6y ago
> Donald Knuth famously wrote that premature optimization is the root of all evil. It’s funny how often Knuth’s actual point is left out of the re-telling of this quote. The actual point he was making was “we should not pass up our opportunities [to optimize] in that critical 3%.“ He wasn’t suggesting the avoidance of optimization, he was suggesting the avoidance of premature optimization.
- voxl 6y ago
  The word "premature" is inside your quote.
  - gameswithgo 6y ago
    What gets me about the way people use this quote, is that it is tautological. "premature optimization is bad". Yes, it must be or it would not be premature. But when a kid or new programmer posts on the internet about what is faster, or how to make a thing faster, why do we tell them this? (Most programming communities, it is inevitable that they will be told this). How do the commenters know whether the optimization is premature? Why are they worried about it, when the person is just learning/curious? Let them get good!
    - a1369209993 6y ago
      > How do the commenters know whether the optimization is premature? > when the person is just learning/curious Not that the code being bad matters in such a case, but if something is just for learning/curiousity, then it is by definition not critically important. Sometimes trying to optimize it is the terminal goal, but it's basically never a relevant instrumental goal.
      - gameswithgo 6y ago
        A lot of software would be better if more programmers had built up some intuition about performance issues by being encouraged, rather than discouraged, when learning. A lot of kids coming out of college have absolutely no exposure to anything low level, or with regard to constant factor performance improvements.
  - dahart 6y ago
    Right- exactly! If you read the article, it ignored the word premature, and used the quote as a narrative suggestion that people should/would avoid any optimization based on this (incomplete) quote, and based on optimizing taking effort. It was using Knuth as a counter-point, pretending that he was saying not to optimize, and then countering with reasons to consider optimizing anyway.
- staticassertion 6y ago
  It's also Knuth quoting Tony Hoare, a man who I highly recommend everyone familiarize themselves with, he's a wonderful speaker and is extremely intelligent. The context of the quote from both Hoare and Knuth is critical, and is always left out. "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." ie: 3% of the time you should absolutely care about 'small' efficiencies. Given that most programs spend almost all of their time in a few places, this is hardly surprising, and 3% is actually a fairly sizable amount of code to optimize to the degree which the paper is discussing (most people are rarely dropping to tools like goto for performance). And, from the same paper (Structured Programming with goto Statements): "The conventional wisdom shared by many of today's software engineers calls for ignoring efficiency in the small; but I believe this is simply an overreaction to the abuses they see being practiced by pennywise-and-pound-foolish programmers, who can't debug or maintain their "optimized" programs. In established engineering disciplines a 12 % improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering. Of course I wouldn’t bother making such optimizations on a one-shot job, but when it’s a question of preparing quality programs, I don’t want to restrict myself to tools that deny me such efficiencies." In other words, we should not write slower code when we can help it. Small efficiencies are well worth attaining in the general case, and the fears of writing 'unreadable' code because it's fast are mostly unfounded. I believe this has never been truer. It's easier than ever to create highly tuned code that's hidden behind a 0 cost abstraction, and it's well worth it to tune that code for simple and obvious wins - we should never strive for inefficiency, as so many seem to advocate.
jonstewart 6y ago
This is such a mashup of conflicting advice. Don’t optimize! Use SIMD! If you’re reading from disk you’re I/O bound! I am embarrassed for the ACM.
- hhmc 6y ago
  It’s also strange to advocate for using a stdlib provided sort. It’s hard to imagine a stdlib worth it’s salt that provides ‘sort’ but not some kind of ‘linear search’ (and the stdlib implementation would likely use SIMD).
  - Joker_vD 6y ago
    Well, Go's standard library has no linear search routine. But it does have both sort and binary search.
  - gameswithgo 6y ago
    standard libraries are only just now starting to use SIMD at all. .NET has been working hard on SIMDifying their core libraries lately. Do any C++ implementations of the std do so? Or do they just lean on llvm/gcc to autovectorize when possible?
    - formerly_proven 6y ago
      There's really no point providing a hand-rolled SIMD implementation for stuff like std::max_element. It's a very trivial loop that any compiler can and will vectorize. Auto-vectorization in general "just works" for basic stuff. It's only the complex stuff where you can really benefit from hand-rolled SIMD implementations; you'll know it when you see it.
- kevinventullo 6y ago
  It doesn’t inspire much confidence in a candidate’s ability to write software of even moderate complexity if their reasoning for using sort instead of a 5-liner was that their 5-liner could contain bugs.
Kapura 6y ago
I love this article. >If N=16,000, then the entire dataset fits in the L1 cache of the CPU, assuming the CPU was made in this decade. This means the CPU can scan the data so fast it will make your hair flip. If N=64,000, then the data will fit in a modern L2 cache, and your hair may still do interesting things. If the computer wasn't made in this decade, I would recommend that my friend reconsider working for this company. Great stuff. So much of it speaks directly to how I see my own development process. It's understanding not only what you are doing, but why you are doing it. It's the difference between solving the bridge you're building and fixing the highway system to route the traffic more efficiently. It's seeing the trees, the forest, and all the birds and bats flying around. There are a million ways to skin the cat, and the difference between ok engineers and great ones is knowing which method to use, and when the cat is good enough with the skin on.
formerly_proven 6y ago
Why is he discarding compsci literally in the introduction? Does he really think "big O" is all there is, presumably because those ivory tower compsci people have no clue about computers? There are some good bits of advice in the article, too, though. > I conducted some simple benchmarks in Go to find how much data can be processed in 200 ms. A linear search can scan 13 million elements in less than 200 ms on a three-year-old MacBook laptop, and 13 million is no small feat. It's funny how slow languages have shifted perceptions. Scanning 13 million elements to find the biggest element among 32 bit ints in 200 ms is slow. That's 250 MB/s, or about 50 clock cycles per element. Even the most naive and portable C three-liner is almost 100x faster (there is a difference in single-threaded performance, if you assume a very generous 50 % difference, it'd still be 50x faster). maximum = INT_MIN; for(int i = 0; i < N; i++) maximum = elems[i] > maximum ? elems[i] : maximum; So, when you are using C/C++, "small" for this problem is a billion elements. Computers are super-fast. Next time you wait two seconds for some application to compute something, ask yourself: is this problem really eight-billion clock cycles hard?
- higerordermap 6y ago
  Not just that, in a language with reasonable abstractions it is max(elems), maybe in some external module. His arguments about simpler / less buggy code don't apply.
  - secondcoming 6y ago
    Someone has to write the algorithm beneath those abstractions. It's not magic. There's a point in the abstraction call stack where the programmer needed to understand how a CPU actually works.
    - higerordermap 6y ago
      Same applies for his sort example. Someone has to write sort. Except that now also includes sorting. In a language with lazy stream abstraction, the max() function can be pretty efficient.
- 6y ago
gameswithgo 6y ago
>Anything that takes less than 200 ms is perceived to be instantaneous by the human brain Negative, ghost rider. What is perceived as instant depends on a lot of things, most studies in the past arrived at a threshold of 100ms, but there are domains where 100ms will feel horrible (first person gaming, VR tracking, conversation audio, etc). We know the brain can see things that are visible for only 13ms: https://news.mit.edu/2014/in-the-blink-of-an-eye-0116 https://news.mit.edu/2014/in-the-blink-of-an-eye-0116 When I am programming if something that doesn't require IO takes even 1ms I immediately take a look and make sure something isn't wrong.
- formerly_proven 6y ago
  Very true, ~200 ms is a good assumption for the conscious reaction time of an attentive human, but that doesn't mean we perceive time in 200 ms increments and can't tell the delay between "click - 2 ms delay - something happens" and "click - 200 ms delay - something happens". The latter is quite obvious.
- staticassertion 6y ago
  > even 1ms I immediately take a look and make sure something isn't wrong. Agreed. I didn't realize this when I was newer to programming, and I think it's in part because I was "thinking in milliseconds". https://gist.github.com/jboner/2841832 https://gist.github.com/jboner/2841832 latency.txt was a game changer for me, as well as starting to measure things in terms of nanoseconds. Side note: is there an updated latency.txt?
  - formerly_proven 6y ago
    > Side note: is there an updated latency.txt? It hasn't changed.
  - antiuniverse 6y ago
    You might also enjoy “Memory Bandwidth Napkin Math”: https://www.forrestthewoods.com/blog/memory-bandwidth-napkin-math/ https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...
dwheeler 6y ago
A fun snarky article. It missed another potential issue: many modern systems use cache prefetching, where they intentionally start loading the "next" memory area. As a result, sequential memory access is often much faster than bouncing around memory. Your mileage may vary.
zvr 6y ago
Needs a " (2016)". methinks.
corysama 6y ago
> To meet the vendor's requirement, most games first load and display a title screen, then ask users to click a button to start the game. What users don't realize is that while they are sitting in awe of the amazing title screen, the game is finishing its preparations. I did exactly this in my first video game. It was an N64 game so the load time requirements from Nintendo were very short and we were 1-2 seconds over the limit. Before the level loaded we already had a UI screen that showed you the map of the level you were about to enter and blinked "OK? (A)" waiting for you to be done checking the map. So, I rendered the map with and without the prompt to the front and back display buffers. Then installed a VBlank signal handler that just flipped the display buffers without actually re-rendering anything. Then the loading started immediately without waiting for the user's OK. (We had no threading back then) The only think that changed when you hit (A) was that the VBlank handler would flip to the No-Prompt screen for the rest of the load time.
- gameswithgo 6y ago
  a lot of games will put up little tips while the levels load, and it can be pretty handy. then i got an ssd and you only have tome to read about half the tip!
jedbrown 6y ago
Fun article. > With four CPU cores, small becomes 4N, or nearly 200 million items. Memory channels do not scale with number of cores, and indeed, peak DRAM bandwidth is often observed with less than the total number of cores (e.g., one core per CCX on Zen2).
ram_rar 6y ago
I am really surprised to read this article on acm. I have nothing against the author. From a technically stand point, I am genuinely disappointed in acm for publishing it. I'm pretty sure, of getting downvotes for these. But heres my critique. 1. Fast enough means different things in different context. If you're building HFT (high frequency trading) system 200ms is eternity. At the same time, for a simple crud application its good enough. Context is everthing! 2. As much as I love Go, its not really a good benchmark as the article suggests. The equivalent C program (without concurrency), will blow those numbers out of the water. This basically tells me, the higher level languages like GO, have skewed perceptions of what is considered fast. The article completely misses one of the most important points. You have to measure/instrument the code before one decides to "optimize" things. Without instrumentation, its really hard to know where the program is spending most of its time. Once you have that data, then focus on optimizing the slowest parts.
kleiba 6y ago
Quite a few comments here already remark on the "computer scientists leaving the room" joke at the beginning of the article. I'd like to add another computer sciency aspect that hasn't been covered yet. If the original question is "what is the fastest algorithm to find the largest number in an unsorted array" you might just answer: "it depends on what you want to do with it afterwards." Sure, in a job interview or in a computer science class you might want to just look at any one problem independent of anything else. In the real world, context matters though. For example, we know that in an unsorted list (which we're dealing with here), an element can be removed by overwriting it with the last element of the list and decrementing the length of the list. So perhaps someone is actually looking at solving a more complex problem, say, processing a list of tasks from highest importance to lowest and removing each task once it has been processed. But they are new to the team, and there is a huge and complicated code base that has been created over years and that they now have to work with. And it just so happens that the actual algorithm is already implemented in the code base, except for one function: while list is not empty: task = find_most_important_task(list) # your TODO process(task) list.remove(task) Now, this is the same question as in the job interview... or is it? Assuming that find_most_important_task is implemented as a linear search, the above algorithm is O(n^2). However, knowing which task you're optimizing for -- that is, the algorithm as a whole -- you can obviously do better. Let's say, your list data structure gets a new flag that is true iff the list is sorted. Then you could use the following implementation for the max search: find_most_important_task(list): if list is not sorted: list.sort() return list[list.length - 1] With this implementation, a single call to find_most_important_task(list) would be much worse in term of O-notation than linear search: O(nlogn) vs. O(n). However, amortized over the whole algorithm, the complexity of find_most_important_task is actually only O(logn)! So, yeah, I don't really know why I wrote all this up. Probably because it is late. Certainly not because it contained anything new. It's also contrived. Oh well. Sorry for wasting anyone's time...
MrYellowP 6y ago
Hm. On my 7300HQ, single channel 2667MHz DDR4 my hand crafted assembly code runs through 512 megs looking for a binary needle (8 bytes length for this example) in random data (mersenne twister) in 59 milliseconds. The needle is, of course, at the end of the 512megs. No SSE, on a single core and it scales nearly perfectly. Not sure what to make of this article. In the end, what truly matters is knowing how a CPU operates and what not to do if you want to have your code running actually fast, not just "perceived fast". That being said, I still consider the 59ms to be slow.
deleted 6y ago
[deleted]

73 points by YesThatTom2 6y ago

I understand the rhetorical dodges here, but as both a career SRE and a student of CS, I don't see anything here which invalidates the theoretical asymptotic behavior. All of the nuance added here is a complement, not a replacement, for traditional theory. It is certainly true that the number of elements needs to be quite high before the question is theoretically interesting. The author is right to point out that L2 cache is quite large. Today's GPUs are also quite large in onboard RAM and have integer ALUs, so even millions of elements are not a problem for a basic consumer-grade video card. (Yes, I know that that sounds stupid, but GPUs and now TPUs in the datacenter are a real thing, even if they're quite unfair!)

dahart 6y ago

> Donald Knuth famously wrote that premature optimization is the root of all evil. It’s funny how often Knuth’s actual point is left out of the re-telling of this quote. The actual point he was making was “we should not pass up our opportunities [to optimize] in that critical 3%.“ He wasn’t suggesting the avoidance of optimization, he was suggesting the avoidance of premature optimization.

voxl 6y ago
The word "premature" is inside your quote.
- gameswithgo 6y ago
  What gets me about the way people use this quote, is that it is tautological. "premature optimization is bad". Yes, it must be or it would not be premature. But when a kid or new programmer posts on the internet about what is faster, or how to make a thing faster, why do we tell them this? (Most programming communities, it is inevitable that they will be told this). How do the commenters know whether the optimization is premature? Why are they worried about it, when the person is just learning/curious? Let them get good!
  - a1369209993 6y ago
    > How do the commenters know whether the optimization is premature? > when the person is just learning/curious Not that the code being bad matters in such a case, but if something is just for learning/curiousity, then it is by definition not critically important. Sometimes trying to optimize it is the terminal goal, but it's basically never a relevant instrumental goal.
    - gameswithgo 6y ago
      A lot of software would be better if more programmers had built up some intuition about performance issues by being encouraged, rather than discouraged, when learning. A lot of kids coming out of college have absolutely no exposure to anything low level, or with regard to constant factor performance improvements.
- dahart 6y ago
  Right- exactly! If you read the article, it ignored the word premature, and used the quote as a narrative suggestion that people should/would avoid any optimization based on this (incomplete) quote, and based on optimizing taking effort. It was using Knuth as a counter-point, pretending that he was saying not to optimize, and then countering with reasons to consider optimizing anyway.
staticassertion 6y ago
It's also Knuth quoting Tony Hoare, a man who I highly recommend everyone familiarize themselves with, he's a wonderful speaker and is extremely intelligent. The context of the quote from both Hoare and Knuth is critical, and is always left out. "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." ie: 3% of the time you should absolutely care about 'small' efficiencies. Given that most programs spend almost all of their time in a few places, this is hardly surprising, and 3% is actually a fairly sizable amount of code to optimize to the degree which the paper is discussing (most people are rarely dropping to tools like goto for performance). And, from the same paper (Structured Programming with goto Statements): "The conventional wisdom shared by many of today's software engineers calls for ignoring efficiency in the small; but I believe this is simply an overreaction to the abuses they see being practiced by pennywise-and-pound-foolish programmers, who can't debug or maintain their "optimized" programs. In established engineering disciplines a 12 % improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering. Of course I wouldn’t bother making such optimizations on a one-shot job, but when it’s a question of preparing quality programs, I don’t want to restrict myself to tools that deny me such efficiencies." In other words, we should not write slower code when we can help it. Small efficiencies are well worth attaining in the general case, and the fears of writing 'unreadable' code because it's fast are mostly unfounded. I believe this has never been truer. It's easier than ever to create highly tuned code that's hidden behind a 0 cost abstraction, and it's well worth it to tune that code for simple and obvious wins - we should never strive for inefficiency, as so many seem to advocate.

jonstewart 6y ago

This is such a mashup of conflicting advice. Don’t optimize! Use SIMD! If you’re reading from disk you’re I/O bound! I am embarrassed for the ACM.

hhmc 6y ago
It’s also strange to advocate for using a stdlib provided sort. It’s hard to imagine a stdlib worth it’s salt that provides ‘sort’ but not some kind of ‘linear search’ (and the stdlib implementation would likely use SIMD).
- Joker_vD 6y ago
  Well, Go's standard library has no linear search routine. But it does have both sort and binary search.
- gameswithgo 6y ago
  standard libraries are only just now starting to use SIMD at all. .NET has been working hard on SIMDifying their core libraries lately. Do any C++ implementations of the std do so? Or do they just lean on llvm/gcc to autovectorize when possible?
  - formerly_proven 6y ago
    There's really no point providing a hand-rolled SIMD implementation for stuff like std::max_element. It's a very trivial loop that any compiler can and will vectorize. Auto-vectorization in general "just works" for basic stuff. It's only the complex stuff where you can really benefit from hand-rolled SIMD implementations; you'll know it when you see it.
kevinventullo 6y ago
It doesn’t inspire much confidence in a candidate’s ability to write software of even moderate complexity if their reasoning for using sort instead of a 5-liner was that their 5-liner could contain bugs.

Kapura 6y ago

I love this article. >If N=16,000, then the entire dataset fits in the L1 cache of the CPU, assuming the CPU was made in this decade. This means the CPU can scan the data so fast it will make your hair flip. If N=64,000, then the data will fit in a modern L2 cache, and your hair may still do interesting things. If the computer wasn't made in this decade, I would recommend that my friend reconsider working for this company. Great stuff. So much of it speaks directly to how I see my own development process. It's understanding not only what you are doing, but why you are doing it. It's the difference between solving the bridge you're building and fixing the highway system to route the traffic more efficiently. It's seeing the trees, the forest, and all the birds and bats flying around. There are a million ways to skin the cat, and the difference between ok engineers and great ones is knowing which method to use, and when the cat is good enough with the skin on.

formerly_proven 6y ago

Why is he discarding compsci literally in the introduction? Does he really think "big O" is all there is, presumably because those ivory tower compsci people have no clue about computers? There are some good bits of advice in the article, too, though. > I conducted some simple benchmarks in Go to find how much data can be processed in 200 ms. A linear search can scan 13 million elements in less than 200 ms on a three-year-old MacBook laptop, and 13 million is no small feat. It's funny how slow languages have shifted perceptions. Scanning 13 million elements to find the biggest element among 32 bit ints in 200 ms is slow. That's 250 MB/s, or about 50 clock cycles per element. Even the most naive and portable C three-liner is almost 100x faster (there is a difference in single-threaded performance, if you assume a very generous 50 % difference, it'd still be 50x faster). maximum = INT_MIN; for(int i = 0; i < N; i++) maximum = elems[i] > maximum ? elems[i] : maximum; So, when you are using C/C++, "small" for this problem is a billion elements. Computers are super-fast. Next time you wait two seconds for some application to compute something, ask yourself: is this problem really eight-billion clock cycles hard?

higerordermap 6y ago
Not just that, in a language with reasonable abstractions it is max(elems), maybe in some external module. His arguments about simpler / less buggy code don't apply.
- secondcoming 6y ago
  Someone has to write the algorithm beneath those abstractions. It's not magic. There's a point in the abstraction call stack where the programmer needed to understand how a CPU actually works.
  - higerordermap 6y ago
    Same applies for his sort example. Someone has to write sort. Except that now also includes sorting. In a language with lazy stream abstraction, the max() function can be pretty efficient.
6y ago

gameswithgo 6y ago

>Anything that takes less than 200 ms is perceived to be instantaneous by the human brain Negative, ghost rider. What is perceived as instant depends on a lot of things, most studies in the past arrived at a threshold of 100ms, but there are domains where 100ms will feel horrible (first person gaming, VR tracking, conversation audio, etc). We know the brain can see things that are visible for only 13ms: https://news.mit.edu/2014/in-the-blink-of-an-eye-0116 https://news.mit.edu/2014/in-the-blink-of-an-eye-0116 When I am programming if something that doesn't require IO takes even 1ms I immediately take a look and make sure something isn't wrong.

formerly_proven 6y ago
Very true, ~200 ms is a good assumption for the conscious reaction time of an attentive human, but that doesn't mean we perceive time in 200 ms increments and can't tell the delay between "click - 2 ms delay - something happens" and "click - 200 ms delay - something happens". The latter is quite obvious.
staticassertion 6y ago
> even 1ms I immediately take a look and make sure something isn't wrong. Agreed. I didn't realize this when I was newer to programming, and I think it's in part because I was "thinking in milliseconds". https://gist.github.com/jboner/2841832 https://gist.github.com/jboner/2841832 latency.txt was a game changer for me, as well as starting to measure things in terms of nanoseconds. Side note: is there an updated latency.txt?
- formerly_proven 6y ago
  > Side note: is there an updated latency.txt? It hasn't changed.
- antiuniverse 6y ago
  You might also enjoy “Memory Bandwidth Napkin Math”: https://www.forrestthewoods.com/blog/memory-bandwidth-napkin-math/ https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...

dwheeler 6y ago

A fun snarky article. It missed another potential issue: many modern systems use cache prefetching, where they intentionally start loading the "next" memory area. As a result, sequential memory access is often much faster than bouncing around memory. Your mileage may vary.

zvr 6y ago

Needs a " (2016)". methinks.

corysama 6y ago

> To meet the vendor's requirement, most games first load and display a title screen, then ask users to click a button to start the game. What users don't realize is that while they are sitting in awe of the amazing title screen, the game is finishing its preparations. I did exactly this in my first video game. It was an N64 game so the load time requirements from Nintendo were very short and we were 1-2 seconds over the limit. Before the level loaded we already had a UI screen that showed you the map of the level you were about to enter and blinked "OK? (A)" waiting for you to be done checking the map. So, I rendered the map with and without the prompt to the front and back display buffers. Then installed a VBlank signal handler that just flipped the display buffers without actually re-rendering anything. Then the loading started immediately without waiting for the user's OK. (We had no threading back then) The only think that changed when you hit (A) was that the VBlank handler would flip to the No-Prompt screen for the rest of the load time.

gameswithgo 6y ago
a lot of games will put up little tips while the levels load, and it can be pretty handy. then i got an ssd and you only have tome to read about half the tip!

jedbrown 6y ago

Fun article. > With four CPU cores, small becomes 4N, or nearly 200 million items. Memory channels do not scale with number of cores, and indeed, peak DRAM bandwidth is often observed with less than the total number of cores (e.g., one core per CCX on Zen2).

ram_rar 6y ago

I am really surprised to read this article on acm. I have nothing against the author. From a technically stand point, I am genuinely disappointed in acm for publishing it. I'm pretty sure, of getting downvotes for these. But heres my critique. 1. Fast enough means different things in different context. If you're building HFT (high frequency trading) system 200ms is eternity. At the same time, for a simple crud application its good enough. Context is everthing! 2. As much as I love Go, its not really a good benchmark as the article suggests. The equivalent C program (without concurrency), will blow those numbers out of the water. This basically tells me, the higher level languages like GO, have skewed perceptions of what is considered fast. The article completely misses one of the most important points. You have to measure/instrument the code before one decides to "optimize" things. Without instrumentation, its really hard to know where the program is spending most of its time. Once you have that data, then focus on optimizing the slowest parts.

kleiba 6y ago

Quite a few comments here already remark on the "computer scientists leaving the room" joke at the beginning of the article. I'd like to add another computer sciency aspect that hasn't been covered yet. If the original question is "what is the fastest algorithm to find the largest number in an unsorted array" you might just answer: "it depends on what you want to do with it afterwards." Sure, in a job interview or in a computer science class you might want to just look at any one problem independent of anything else. In the real world, context matters though. For example, we know that in an unsorted list (which we're dealing with here), an element can be removed by overwriting it with the last element of the list and decrementing the length of the list. So perhaps someone is actually looking at solving a more complex problem, say, processing a list of tasks from highest importance to lowest and removing each task once it has been processed. But they are new to the team, and there is a huge and complicated code base that has been created over years and that they now have to work with. And it just so happens that the actual algorithm is already implemented in the code base, except for one function: while list is not empty: task = find_most_important_task(list) # your TODO process(task) list.remove(task) Now, this is the same question as in the job interview... or is it? Assuming that find_most_important_task is implemented as a linear search, the above algorithm is O(n^2). However, knowing which task you're optimizing for -- that is, the algorithm as a whole -- you can obviously do better. Let's say, your list data structure gets a new flag that is true iff the list is sorted. Then you could use the following implementation for the max search: find_most_important_task(list): if list is not sorted: list.sort() return list[list.length - 1] With this implementation, a single call to find_most_important_task(list) would be much worse in term of O-notation than linear search: O(nlogn) vs. O(n). However, amortized over the whole algorithm, the complexity of find_most_important_task is actually only O(logn)! So, yeah, I don't really know why I wrote all this up. Probably because it is late. Certainly not because it contained anything new. It's also contrived. Oh well. Sorry for wasting anyone's time...

MrYellowP 6y ago

Hm. On my 7300HQ, single channel 2667MHz DDR4 my hand crafted assembly code runs through 512 megs looking for a binary needle (8 bytes length for this example) in random data (mersenne twister) in 59 milliseconds. The needle is, of course, at the end of the 512megs. No SSE, on a single core and it scales nearly perfectly. Not sure what to make of this article. In the end, what truly matters is knowing how a CPU operates and what not to do if you want to have your code running actually fast, not just "perceived fast". That being said, I still consider the 59ms to be slow.

deleted 6y ago

[deleted]