Hidden library costs

Why this matters

A single line of code can hide a lot of work. The line s += piece looks like one step. The line items.insert(0, x) looks like one step too. Each of them may do far more work than it appears to, depending on the size of the data and on how the library is built.

Students usually learn the cost of their own loops first. A loop that runs n times is easy to spot. The harder part is the cost inside the library call. The call is written by someone else, and the reader cannot see the loop that runs inside it.

This lesson looks at three common cases: building a string by adding to it in a loop, inserting at the front of a list, and checking whether a value is in a list with in. For each one you will count the work, time the code, and see when the cost becomes a problem. The lesson on best, average and worst case explains why we name the input that makes each case slow. The lesson on hash table costs explains why a set is fast to search, and this lesson only uses that fact as a comparison.

The examples are in Python. The ideas apply to other languages too, and where a point is only true in another language, the lesson says so and does not show code for it.

A simple way to count hidden work

When a library call hides a loop, you can count the work by asking one question: how many items does the call touch each time it runs? If the answer is "one", the call is cheap. If the answer is "every item already stored", the call costs in step with the size of the data. If the call runs inside your own loop, the total is the cost per call multiplied by the number of calls.

Here is a small example before we go further. Suppose you add one item to the end of a list 1000 times. Each addition touches one slot. The total work is about 1000 steps. Now suppose you add one item to the front of a list 1000 times. Each addition moves every item already in the list one place along. The first addition moves 0 items, the second moves 1, and the last moves 999. The total is about 500,000 moves. The same loop of 1000 calls does about 500 times more work, and the only change is where the new item goes.

Keep that example in mind. Most of this lesson is about finding that kind of gap.

Example 1: building a string with plus-equals in a loop

A common task is to build a long text from many small pieces. Here is the simplest way to write it.

abcdef
5

The code is short and clear. The question is what s += piece does underneath. A string is a fixed block of characters. Strings cannot grow in place in some languages, so the language must build a new string that holds the old characters followed by the new piece. If the language does that every time, each step copies everything built so far.

To see the copying, count how many characters are written in total. Each time the loop adds one character to a string that already holds k characters, it writes k + 1 characters. The total over n steps is 1 + 2 + 3 and so on up to n, which is n times (n + 1) divided by 2.

n = 1000 characters written: 500500
n = 2000 characters written: 2001000
n = 4000 characters written: 8002000

Doubling n makes the copy count about four times larger. That is the growth pattern of a loop inside a loop: the work is roughly n squared. A string of 100,000 pieces would need about 5 billion character writes if every step made a full copy.

Now the timing. The next program builds the same string with += and with a list that is joined once at the end. The list version collects the pieces and then calls "".join, which builds the final string in one pass.

n=20000  += loop: 0.44 ms   join: 0.34 ms
n=40000  += loop: 0.87 ms   join: 0.71 ms
n=80000  += loop: 1.76 ms   join: 1.26 ms

These numbers were measured on one machine, so the exact times will differ on yours. Look at the pattern instead. Both versions grow about in step with n, and the += loop does not blow up here. This is a surprise, and it needs an explanation. CPython, the usual Python program, has an optimisation for s += "x". When the string has only one reference, CPython can extend it in place and skip the copy. That is a detail of one implementation, not a rule of the language, so the speed depends on how the code is written.

The next program keeps a second reference to the old string on each step. A second reference is a second name that points at the same string. That blocks the in-place trick, and the copy comes back.

n=20000  += with a second reference: 2.67 ms
n=40000  += with a second reference: 12.17 ms
n=80000  += with a second reference: 47.29 ms

Each time n doubles, the time goes up about four times. That is the quadratic pattern (work that grows with n squared) from the copy count. The same += line that looked fast in the first run is slow in the second, and the only change is one extra reference.

Other languages make the cost plain. In Java, a String cannot change after it is made, so s += piece in a loop creates a new string on every pass. The copying is the rule there, not an accident. The fix is the same in both languages: collect the pieces and join them once. In Java that is StringBuilder, and in Python it is a list with "".join. Both copy the pieces into the final text once, at the end, so the work stays in step with the total length.

The rule to take from this example: plus-equals on a string in a loop can be fast or slow depending on the language and on details of the code. A join at the end is slow in no case, so it is the safe choice.

Example 2: inserting at the front of a list

A list keeps its items in one block of memory, one after another. Adding at the end is cheap, because the next free slot is right there. Adding at the front is different. To make room in slot 0, every existing item must move one place to the right.

The next program counts the moves. Each call to insert(0, i) moves every item that is already in the list.

n = 1000 element shifts: 499500
n = 2000 element shifts: 1999000
n = 4000 element shifts: 7998000

The count for n insertions is n times (n minus 1) divided by 2. For n = 1000, that is 1000 times 999 divided by 2, which is 499,500, and the output matches. Doubling n makes the count about four times larger.

Here is the same idea timed, next to the cost of adding at the end.

n=50000  insert(0): 187.0 ms   append: 0.7 ms
n=100000  insert(0): 775.0 ms   append: 1.9 ms
n=200000  insert(0): 3159.7 ms   append: 6.2 ms

At 200,000 items, inserting at the front took about 3 seconds, while appending took about 6 milliseconds. Each doubling of n made the front insert about four times slower, and the append stayed close to linear. The gap grows with the size of the data.

The same cost applies in Java's ArrayList and in most array-based lists. Calling add(0, x) shifts the existing items in the same way. This lesson has not run Java code, so that statement describes how the array list works and is not a timing.

When you need to add and remove at the front, use a structure built for that job. In Python, collections.deque has appendleft and popleft, which do not move the other items. The check below confirms that the deque keeps the items in the order you expect.

[4, 3, 2, 1, 0]

The deque does not shift a block of items on each insert. The lesson on stacks and queues covers when to choose each structure.

Example 3: checking contains on a list

The in operator asks whether a value is in a collection. On a list, Python must look at each item until it finds a match. If the value is missing, every item is checked, so a miss costs as much as the list is long.

A common mistake comes from a loop that removes duplicates by checking each new item against the list of items kept so far. Here is that version.

[3, 1, 2]

The in check inside the loop scans the kept list. The kept list grows with each new unique value. The total work is about the number of items times the size of the kept list, which is roughly n squared when most items are unique. The next program times it on lists that grow.

n=5000  unique_list: 31.9 ms
n=10000  unique_list: 130.9 ms
n=20000  unique_list: 549.0 ms

Each doubling makes the time about four times larger, which is the quadratic pattern again. The fix is to keep a set alongside the list. A set answers "is this value already here?" in about the same time whatever its size, because it looks the value up with a hash. The lesson on hash table costs explains how that lookup works. Here the point is only the comparison: the set makes the membership check cheap, and the list makes it expensive.

The next program compares a list and a set on the same missing values. The set is built once, and the 200 lookups hit values that are not stored.

n=10000  200 misses, list: 4.87 ms   set: 0.003 ms
n=20000  200 misses, list: 10.19 ms   set: 0.003 ms
n=40000  200 misses, list: 20.52 ms   set: 0.003 ms

For the list, doubling the data doubles the time for the same 200 lookups. For the set, the time stays the same. The gap is large enough to decide the design of any code that checks membership often.

Common mistakes

Assuming a library call is one step. A call that reads like a single operation may hide a loop. Before you use insert, in, remove or string += inside a loop, ask how many items the call touches.

Building a string with += in a loop and trusting one fast timing. The first timing above was fast only because of a CPython detail. Adding a second reference, which can happen in any real program, brings back the copy. Use a join for work that grows.

Inserting at the front in a loop. A loop of n front inserts moves about n squared divided by 2 items. For 100,000 inserts, that is 4,999,950,000 moves. Use a deque, or build the list at the end and reverse it once.

Searching a list inside a loop. Each in check on a list may read the whole list. Keep a set next to the list when you need the membership check repeated many times.

Mixing types in a join or a plus. Adding a string and a number with + is an error, and the message tells you the types involved.

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only concatenate str (not "int") to str

The message names both types. Turn the number into text with str(5) or use an f-string such as f"Total: {5}". The error is a clear one. The cost mistakes in this lesson are the quiet ones, because the program still gives the right answer while getting slower.

Practice

Exercise 1. A loop builds a string of 10,000 pieces, each one character long, with s += piece and no second reference. Using the copy count from this lesson, how many characters are written in total?

Show the answer

The total is 1 + 2 + ... + 10,000, which is 10,000 times 10,001 divided by 2. That is 50,005,000 characters. The copied_characters run for n = 1000 gave 500,500, which matches 1000 times 1001 divided by 2.

Exercise 2. You need to build a text report from 1,000 lines. Which approach is the safer choice, += in the loop or collecting the lines in a list and joining them once? Give a reason that does not depend on the CPython detail.

Show the answer

Joining once is the safer choice. The join makes one pass over the pieces at the end, so its work stays in step with the total length. The += loop is fast only when the language or the interpreter can extend the string in place, and a second reference to the old string can take that away.

Exercise 3. A program calls insert(0, x) 100,000 times on an empty Python list. How many element shifts does it do in total?

Show the answer

The total is 100,000 times 99,999 divided by 2, which is 4,999,950,000 shifts. The count for n = 1000 in this lesson, 499,500, follows the same formula. A deque with appendleft avoids this total.

Exercise 4. A program has 50,000 known ids in a list. For each of 50,000 incoming ids, it checks id in known_ids. Assume every incoming id is missing from the list. Roughly how many comparisons does the program make? What would you change?

Show the answer

Each miss scans all 50,000 items, so the total is about 50,000 times 50,000, which is 2.5 billion comparisons. Store the known ids in a set. Each membership check then takes about the same time whatever the size of the set, and the total work is in step with the 50,000 incoming ids.

Exercise 5. The first += timing in this lesson grew only about in step with n. The timing with a second reference grew about four times each time n doubled. Explain the difference in two or three sentences.

Show the answer

In the first run, CPython can extend the string in place because only one reference to it exists, so no full copy happens on each step. In the second run, the keep variable holds a second reference to the old string, so CPython must copy the string on every step. Copying the whole string each time is the quadratic pattern.

Summary

• A library call can hide a loop, so count how many items each call touches before you put it inside your own loop.
• Adding to a string with += in a loop can copy the whole string each time, which makes the total work grow quadratically. A join at the end avoids this.
• Inserting at the front of a Python list or an array list moves every existing item, so n inserts cost about n squared divided by 2 moves. Use a deque for front insertion.
• x in some_list reads the list until it finds a match, so a miss costs the length of the list. A set answers the same question in about the same time whatever its size.