Optimizations on Linear Search (2016)

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?

> 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.

> 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.

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.

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.

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...

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!)

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.

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.

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).

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.

Needs a " (2016)". methinks.

>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

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.