been developed over the past 30 years
with varying performance characteristics, and the list is too long, tedious,
and boring to address in depth here.
The main considerations are how
long does it take, in the best, worst,
and average cases, to:
˲ Add an element to the data structure (insertion time).
˲ Remove an element.
˲ Find an element.
Personally, I never bother with
the best case, because I always expect that, on average, everything will
be worst case. If you are lucky, there
is already a good implementation of
the data structure and algorithm you
need in a different box from the one
you are using now, and instead of
having to open the box and see the
goo, you can choose the better box
and move on to the next bottleneck.
No matter what you are doing when
optimizing code, better choice of algorithms nearly always trumps higher frequency or core count.
In the end, it comes back to measurement driving algorithm selection, followed by more measurement,
followed by more refinement. Or you
can just open your wallet and keep
paying for supposedly faster hardware that never delivers what you
think you paid for. If you go the latter
route, please contact KV so we can set
up a vendor relationship.
KV the Loudmouth
10 Optimizations on Linear Search
Thomas A. Limoncelli
Computing without Processors
George V. Neville-Neil ( firstname.lastname@example.org) is the proprietor of
Neville-Neil Consulting and co-chair of the ACM Queue
editorial board. He works on networking and operating
systems code for fun and profit, teaches courses on
various programming-related subjects, and encourages
your comments, quips, and code snips pertaining to his
Copyright held by author.
past five years, particularly as a result
of NUMA (non-uniform memory access) and all the convoluted security
mitigations that have sapped the life
out of modern systems to deal with
Spectre and the like. There are days
when KV longs for the simplicity of
a slow, eight-bit microprocessor,
something one could understand
by looking at the stream of assembly flying by. But those days are over,
and, honestly, no one wants to look
at cat videos on a Commodore 64, so
it is just not a workable solution for
the modern Internet.
Since I have discussed measurement before, let’s discuss now the
importance of algorithms. Algorithms are at the heart of what we as
software engineers do, even though
this fact is now more often hidden
from us by libraries and well-traveled
APIs. The theory, it seems, is that hiding algorithmic complexity from programmers can make them more productive. If I can stack boxes on top
of boxes—like little Lego bricks—to
get my job done, then I do not need
to understand what is inside the boxes, only how to hook them together.
The box-stacking model breaks down
when one or more of the boxes turns
out to be your bottleneck. Then you
will have to open the box and understand what is inside, which, hopefully, does not look like poisonous
A nuanced understanding of algorithms takes many years, but there
are good references, such as Donald
Knuth’s book series, The Art of Computer Programming, which can help
you along the way. The simplest way
to start thinking about your algorithm is the number of operations
required per unit of input. In undergraduate computer science, this is
often taught by comparing searching and sorting algorithms. Imagine
that you want to find a piece of data
in an array. You know the value you
want to find but not where to find
it. A naive first approach would be
to start from element 0 and then
compare your target value to each
of the elements in turn. In the best
case, your target value is present at
element 0, in which case you have
executed a very small number, perhaps only one or two instructions.
The worst-case scenario is that your
target element does not exist at all
in the array and you will have executed many instructions—one comparison for every element of the array—only to find that the answer to
your search is empty. This is called a
For many data structures and algorithms, we want to know the best,
worst, and average number of operations it takes to achieve our goal. For
searching an array, best is 1, worst is
N (the size of the array), and average
is somewhere in the middle. If the
data you are storing and searching
is very small—a few kilobytes—then
an array is likely your best choice.
This is because even the worst-case
search time is only a few thousand
operations, and on any modern processor, that is not going to take a
long time. Also, arrays are very simple to work with and understand. It
is only when the size of the dataset
grows into megabytes or larger that
it makes sense to pick an algorithm
that, while it might be more complex, is able to provide a better average number of operations.
One example might be to pick a
hash table that has an average search
time of one operation and a worst
search time of N—again the number
of elements in the table. Hash tables
are more complex to implement than
arrays, but that complexity may be
worth the shorter search time if, indeed, searching is what your system
does most often. There are data structures and search algorithms that have
I never bother
with the best case,
because I always
be worst case.