One of the first data structures taught in most computer science courses is linked list that may be a great way to practice pointer shenanigans and also demonstrates importance of constant factors in practice. To make the discussion concrete and concise, let’s implement a trivial and not particularly useful List
interface
as a singly linked list
and an array list
Since Go’s slices are backed by dynamic arrays that have amortized O(1)
time cost for appends and singly linked lists have a true O(1)
cost, it would be reasonable to expect both implementations take about the same time or singly linked list to perform better since it does not require expensive reallocations. Let’s put our hypothesis to the test using a straightforward benchmark
And the results are
For those of you who are familiar with true cost of memory access this probably does not come as a surprise, but array-backed implementation is almost 3X faster despite its occasional reallocations. Interestingly the cpu profile makes it look like array list inserts should be more expensive due memory copies involved in growing the slice
and memory profile creates even gloomier picture
So how come array list still significantly outperforms singly linked list implementation? The answer is uncovered by adding -benchmem
flag to a benchmark execution command:
go test -bench=BenchmarkList -benchmem -memprofile memprofile.out
that produces following output
The answer is in the last column - each insert into linked list requires an allocation, whereas array list has 0, since allocations happen only when the slice needs to grow, which, assuming 2X growth factor, results in log(N) allocations to reach size of N.
This potentially surprising cost of memory accesses is the reason why usage of linked lists is highly discouraged in most modern programming languages, but as always don’t take anyone’s word for it - measure performance for your specific use cases to find the most suitable data structure.