I agree plots would be nicer (maybe I'll add them)
regarding the last column it's the number of iterations, google benchmark will make less iterations if individual iterations take more time.
The benchmark is time-limited, looks like to about 0.75 seconds (= time * iterations). It ran the test that many times in that duration, each iteration taking on average the amount in the time/cpu column.
I’ve done similar benchmarks some time ago for Java with exactly same conclusions. Due to the way CPUs reads and caches memory the only case for linked lists is doing a lot of in the middle inserts and deletes while iterating the list.
Array copying is really optimized on current hardware.
The redeeming factor (IMO) is that LinkedList implements a lot of useful interfaces: List, Queue AND Deque. If you are doing something like a graph traversal algorithm, breadth-first search or some relative, it's sometimes a justifiable choice for storing nodes-to-be-explored. ArrayDeque is marginally faster, but honestly not by much.
In intrusively linked lists (the one usually used in kernels), you typically already have a pointer to the object, and therefore, to its next/prev pointers. For example, removing a task from the scheduler's RUN list and appending to the WAITING list is O(1), because you already have a pointer to the task, because the system's architecture is structured in such a way that you don't have to traverse the RUN list to find the pointer to the task's entry.
It depends on who's getting billed for the traversal to the point of insertion/deletion:
If all you're doing is "Remove the mth item of the list" takes O(m) time to traverse and O(1) to do the removal if you're starting from the head.
On the other hand, if you already have the pointer to the list element for some other reason, somebody else has already been billed for the traversal and the insert or removal is O(1).
You see linked lists used a lot in e.g. the kernel where the traversal has been paid for to get a pointer to an element that has then been used for a bunch of things before a deletion or insertion happens.
They also have the advantage that in the face of other threads mutating the list, the address of the elements remains constant. If you have a pointer ti an element in an array, and another thread comes along and does an insertion or deletion that moves it, now you have a problem.
Single-threaded performance isn't the only criteria for picking a data structure.
In the real world it's almost certain that somebody else already paid the traversal cost in making the decision of what to act on. The only common cases where that doesn't apply are removing the head (think queue) and adding the tail. The latter case can be handled by keeping a pointer to the tail in your control structure.
A queue very well might be best implemented as a linked list rather than an array.
For example you have a list of points that define a linestring, and have to make sure that no two points are further apart than some value. It's really simple to iterate over linked list, insert a midpoint into the list, stay at the same step and redo the calculations(because p0-midpoint can still be longer than some value).
But other than that i don't think i had to do many random inserts/removals in non-DB contexts.
one of the benefits of a linkedlist is having the ability to remove an element from a list in O(1) by having reference to an item that is stored in the list. This is allowed since a linked list node can remve itself in constant time. This is a common pattern in linked lists used in C code for example.
javas linkedlists don't allow for this benefit. since in java you have to perform a search for the node to be removed and pay a O(n) penalty on a O(1) operation.
About the search benchmark, caches alone do not explain 2 orders of magnitude difference. It's also the prefetcher.
CPU cores have a special functional block which observes addresses of cache lines requested from memory, detects sequential access pattern, and when detected pre-loads data into caches (including L1d) in advance. The RAM access pattern of std::vector search benchmark is an awesome use case for that thing.
Yes, cache misses are a big factor in algorithm speed. I've been working on some search algorithms recently. It's actually faster to read more bytes, as long as they're close, and make a better quality shift based on that rather than reading fewer bytes and making a less informed decision. The cost of reading bytes close by is negligible.
When are linked lists actually good? Everything I read about them suggests they have rotten performance, yet I see them employed in various places all the time, by competent engineers who are definitely aware of their limitations.
One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?
> A linked list element won't move once allocated.
only pertains to languages like C. In a virtual machine language like java, this isn't a property that can exist (there's no such thing as an address - at least as far as the language is concerned).
A reference in Java can essentially be thought of as a pointer into a virtual address space. The JVM can move around the location of an object in the system's actual memory, but as far as anything holding reference is concerned nothing has changed.
And a reference to an object that's in an array won't be invalidated if that object is moving around the array or even removed entirely. It's still a C concern.
Anytime you do something that is immutable with probable change somewhere inside that is not easy to handle with far mor complex datastructure. In particular linked list are great for heterogeneous cells type.
Vectors and arrays have the problem of needing contiguous memory. If an inner cell can have different size, or worse change it mid work, things get ugly really fast.
Which is what happens in most modern languages. The items in your list are objects--which internally are just pointers to the data. There's no performance penalty for having variable-sized objects in the list.
They're also more useful on microcontrollers where there's no cache, no prefetcher, etc. Less code needed for the data structure means more free space for business logic, and there's no performance penalty for bad cache locality on a system without any cache. Also a hash table has to hash each input, which is a significant amount of work for many microcontrollers.
I think the problem is that we're thinking about linked lists like they are taught in intro to algorithms. Like
ListNode* a = new ListNode('A');
ListNode* b = new ListNode('B');
ListNode* c = new ListNode('C');
a.next = b;
b.next = c;
That's a dumb way of implementing a linked list with no redeeming features outside of explaining the concept.
This is a linked list with the same shape as the list above, but with completely different performance characteristics:
int* data = new int[3];
data[0] = 'A';
data[1] = 'B';
data[2] = 'C';
int* links = new int[3];
links[0] = 1;
links[1] = 2;
links[2] = -1;
With some elaboration (say exchange the arrays for a mmap-call, turn it into a tree instead of a list) and you're basically looking at the guts of a DMBS or a file system.
Is there a reason the keep the data and the indices in different arrays? Unless you're navigating to an item by its position in the linked list, you're going to be checking the data at each node and then reading the next index to traverse forward. Since you're reading both, wouldn't it be better to make the index of the next node intrusive?
The design is mostly to provide a clear enough example, you can of course interlace them.
It depends on the use case.
If you're doing a lot of navigating over links before you reach the destination, maybe you want them separate. Could also be the data is large, even maybe stored on disk while the links are in memory, or whatever. There's a thousand different scenarios with different optimal arrangements.
It allows you to reorder the data, say sorting it, without moving the actual data. If the element type is say a struct, this can be a huge performance win.
It also allows you to keep multiple different lists to the same data, say sorted by different fields in the struct.
Sounds a lot like “draw the rest of the damn owl.” [0] :-)
DBMSs and file systems use (extremely sophisticated) tree structures under the hood. Not sure that “linked lists are useful if the linking topology is much more complicated than a simple line” is a ringing endorsement of them.
My point is that this general sketch of a layout with arrays of offset pointers roughly generalizes to something like a B or B+-tree fairly well, and that's a fairly simple data structure. You can absolutely implement a file system with passable performance with either of those tree structures.
This has the same issues as just using an array to store the data. If you remove a node in the list now you have to rewrite all the values in the links array. If you don't do that then you have to implement your own garbage collector and pay the penalty periodically.
> If you remove a node in the list now you have to rewrite all the values in the links array.
You actually don't. You can just keep two lists within the same structure, one for occupied nodes and one for free nodes, and just move deletions to the head of the free nodes list.
Example List:
Data: [ a, 0, c, d, e ]
Links: [ 2, -1, 3, 4, -1 ]
Head of occupied nodes: 0
Head of free nodes: 1
I believe they can also be useful to share data between instances in the case of immutable structure. Prepending to an immutable linked list is quasi-free in terms of memory usage.
>One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?
Yes, and constant time insertions/deletions in the middle of the list, assuming you know the address ahead of time.
This makes them great as backing queues in an LRU cache: given some key/value pairs, have a linked list whose nodes map to each key. Additions to the K/V store gets appended to the LL. This lets you easily remove the oldest n elements in the K/V store, by traversing from the head of the LL. It also lets you efficiently remove arbitrary elements from the K/V store, if you store the addresses of each LL node as values in the K/V, since deletions in the middle of the LL are constant time.
>yet I see them employed in various places all the time
I agree, however, that most LL applications (like the one I just mentioned) are fairly niche. LLs are overused because they’re dead simple to implement and commonly taught in intro CS classes.
Operating systems where you need to be able to atomically insert or remove from a list. Because the links are just pointers and the memory can be managed after the swap you can use atomics to compare and swap pointers. This allows for the RCW mechanisms the linux and NT kernels depend on to work.
This also technically applies to lockless data structures for some high performance code too. But those tend to be much much more tightly tuned for performance and the specific CPU they are intended to run on.
I have seen highly successful proprietary trading firms implement their order books using linked lists (more like a linked list for each level of the order book, with the levels themselves arranged in a linked list). Obviously they use a custom allocator or an object pool to make sure that the cache performance isn't completely atrocious.
When the use case requires insertion/removal from the middle of the list. An LRU cache is about the most common use case I've run across. (The "LRU" part requires it to often bump an item to the end of the list, so LL's excel here, as we can shift the element's position in the list in O(1) time. An LRU structure would normally pair the LL with a HashMap, which maps the cached item to its LL entry, so that we've also got a O(1) search into the LL, and don't hit the problem in the article.)
> yet I see them employed in various places all the time, by competent engineers who are definitely aware of their limitations.
I see them employed very, very rarely. Vectors¹ are by far more common in every codebase I've ever worked on. (And should be one's default, IMO, if all you need is a container of stuff that you're going to iterate over, which is the usual case, for the reasons in the article.)
¹ignoring cases where a hash(map|set) is required; then our codebase uses that, b/c that's what's needed.
This is exactly correct, since at least in C++, adding elements to any other data structure can invalidate the stored iterators/references in your hashmap. std::list will mean you pay a slight cost when adding new entries, which if your cache is working is hopefully not so often, or the malloc is already dominated by whatever is being cached.
In c++, std::deque is better than std::list as an address preserving backing store as it requires less memory allocations, less space overhead and objects will be closer together.
> std::deque is better than std::list as an address preserving backing store
std::deque will invalidate iterators in some cases. Since my example above was an LRU cache, the cache's removal of an item from the middle of the list (to shift it to the end) is one of those actions that would invalidate iterators in a std::deque.
(Not to malign std::deque: it is a useful datastructure in its own right, and if you need queue-like semantics (e.g. cheap remove from front), it's a better choice than a LL, and both are better than vectors for that purpose. I find deque's internals to be a bit weird … my goto would normally be a ringbuffer, but the STL provides deque instead, so eh, it's good enough, if a bit odd IMO.)
Your question is more accurate than you realize! Because the answer is... the past.
Up until about the 486/50MHz era, CPUs and memory were attached to each other; one CPU cycle was approximately equal to one memory access. I don't mean that you could reach out to RAM in exactly one cycle and get a value, there were still some CPU caches and other considerations, but it was much closer to that ideal than on modern systems. And if you go back in time even farther, that actually was the case (Commodore 64, for instance).
(I don't know if there was ever a "true" 486/66 system, but I remember that as the CPU/clock speed where the CPU finally and definitively detached from RAM speed because that was generally a double-clocked 486/33 from the RAM's perspective. I can't quite remember the marketing term that was used. It's a dead term now because everything works that way.)
In those circumstances, traversing a linked list was not necessarily that much more expensive than a vector, and you could win on the other things a linked list can do faster than a vector, like insert in the middle, especially an insert in the middle when you were traversing the list anyhow. You could also win on a linked list containing a relatively large value organized just by pointers; a sort on the linked list manipulating just the pointers could win versus a sort that was trying to move around larger values constantly during the sort. And so on.
When memory accesses aren't hundreds and hundreds of CPU cycles, when your hardware doesn't have prefecting implemented, when your pointers aren't 64bits wide, when you aren't on modern systems essentially designed to make vector-based access go zoom, linked lists make a lot more sense.
This is how they got embedded in curricula so hard that they are taught to this day. They used to be a very important data structure. Now they're an antipattern. It happened gradually, though, and it doesn't help that linked lists are just about the easiest non-trivial data structure to teach and I'm not sure they could get removed from the standard curriculum for that reason alone.
"One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?"
Another problem linked lists have is that if you know that's what you're going to do, you can build vector-based solutions to that problem that work just fine. Vector-based stacks, for instance, are trivial, and O(1)-amortized for push and pop, which is good enough in practice. (A bit more care is needed than an only-growing vector but IIRC it can be done.) You need not just something linked lists are better at, but some bizarre cocktail of all the things they're just barely better at, and you still need to construct a win out of the combo. It's nearly impossible. Not quite impossible. I assume without looking that the Linux kernel still has some linked lists for good reason, as I'm sure if they could win on performance by removing them they would. But very hard.
Circular buffers (your fancy implementation) are far superior for queues. Pretty much any modern vector like data structure is already going to have grow logic so adding head and tail pointers isn't too hard. However, as this article mentions, keeping memory compact is pretty important to speed, and circular buffers are able to do that while linked lists aren't.
By data structure standards, the requisite amount of "fanciness" to implement a queue in a vector is table stakes, hardly even worth 10 minutes of class time at the sophomore level, if not simply given out as homework. It is no problem at all to put a queue in a vector. You'd need a doubly-linked list for this, too, and as the article mentions, your linked-list queue is likely to lose just on malloc & free (or local equivalents) versus the vector.
(The best optimization you could do in such a case would be to allocate multiple slots per pointer, to amortize the malloc/free time. Then you'd want to run benchmarks to tell what the optimal amount of slots would be. If a vector is optimal, as I strongly expect it would be, the answer would come out to be, "all of them".)
Modern processors move chunks of RAM around really quickly. They're really optimized for it. It is one of the major things I'm referring to when I say our systems have been optimized for C. I often wonder about what an architecture designed in a world where linked lists were dominant would look like. However, it is certainly not this world.
ringbuffers are just needed for concurrent access or tiny/static ram/kernels.
his tests are just simple ordinary perf tests for the cost of pointer chasing. That's why deques were invented, to give you the best of both. Similar to a B-Tree.
Thats right. Though in reality, programs behave in a complex way. You rarely have to insert something in the middle of a list in practice. You rarely do random behaviors, at least in my field. Let me explain.
In the game industry, we use contiguous-allocated intrusive free list memory pools. For enemies or projectiles as an example. Those things live and die (they are removed from the free list and inserted in the "live" list or put back in the free list when they die) in such a way the locality is kept good.
Admitedly I dont have sources nor benchmarks and never did. But its obvious it at least invalidates author's point in the sense that benchmarks gota be done in real life programs.
Linked lists only perform poorly if you iterate them, or otherwise access multiple items at once.
If you use them as a single-linked free list they are faster than a vector since you only need to fetch a cache line for the object rather than a cacheline for the object and one for the vector storing free objects.
Even this doesn't give you optimal locality. Objects in the same pool are closer than if they were randomly fragmented from a global allocator, but if you're accessing them in the list order, you're not accessing adjacent addresses to take advantage of memory prefetch. If the pool is large, it may not even fit in the cache.
When performance needs to be maximized, games switch to entity component systems and switch from arrays-of-structs to structs-of-arrays. This enables processing all objects as a vector, linearly from start to end, and often without needing to fetch any irrelevant bytes that aren't processed in a given pass. This sometimes also helps utilize SIMD for data spanning more than one entity, which you can't do when using linked lists.
Linked lists are often used as a "secondary" structure, i.e intrusively linked lists of objects that whose main references come from elsewhere. Just wondering, are there any alternative solutions to those kinds of cases?
I did not see whether there is a noticeable (or even measured) effect vs load on the cpu. I would thing that cache misses increase with load as multiple processes compete for the memory resources. Perhaps modern machines can schedule around this but it should still be tested.
Or, perhaps, this is saying (again) that one should code then tune? Pick data structures that facilitate the design you’re trying for rather than for theoretical elegance? Chips are cheap while developers are not, and having a cleaner, saner design is a win. Unless your software price per core is so high that people won’t license more.
It may use less power as it is spending more time stalled, waiting for memory. But it could be still using as much time as the OS scheduler is willing to give it.
Geometry/topology is very often presented as soup of pointers, (think of doubly connected edge list, Quad-edge, etc.) I have personnally always implemented these with pointers, because it's at the tip of my skills and that's how they are presented on the internet ; but I'm curious to know if people more confortable with topologies and meshes use a different memory representation.
I usually keeping these things as indexed meshes: std::vector<Vector3> for positions, and std::vector<std::array<uint32_t,3>> for the triangles. As a nice side effect, the representation is compatible with GPUs, matches VRAM layout of the vertex/index buffers.
For some simple algorithms which need adjacency information, that’s everything needed. For instance, to compute per-vertex normals, nothing else is required, create an std::vector for the per-vertex accumulators, and iterate over the triangles.
For complicated algorithms which need adjacency information, I build special indices over the same data. To find triangles connected to specific triangle, a hash map with uint64_t keys (two sorted uint32_t vertex IDs in the lower/upper half of the integer) and a structure of two uint32_t values (triangle IDs, good meshes are guaranteed to have exactly 2 triangles for each edge, with opposite winding directions). To find triangles by vertex, a multimap from uint32_t vertex to uint32_t triangle.
For algorithms which need to modify these meshes, sometimes I generate new meshes instead of modifying old ones. Other times I replace erased elements with special values (like UINT_MAX for integer indices), append new elements to the end of the vectors, and when the algorithm is complete I re-index the mesh while removing unused vertices/triangles.
I think, that they presented on Internet as a soup of pointers, because it is the obvious and general way to do it. Other ways like connectivity matrix are less general: if you have a lot of nodes, and by several orders of magnitude less then N^2 edges, then the most of matrix elements will be empty. Moreover it is not obvious way, you need to explain it also on top of your goal to explain what you are explaining about geometry/topology. So if you tried to do it you'd spend all the allotted time talking about pros and cons of different representations of topology.
I believe that if someone tried to talk about topology while using Rust as a language for sample code, he/she would use some other representation, because a soup of pointers is a PITA in Rust. It is easier to claim that we will be using a connectivity matrix, or a Vec of edges, and to explain how it works, than to juggle with pointers.
If the *only* thing you need is to move along the list then pointers are probably the best answer.
However, in my limited experience with such things I have always found myself needing both walking around and a big-picture list of items. Thus I have always implemented such things as a list of elements and storing indexes rather than pointers.
Big-O notation relies on several simplifying assumptions which are wrong in practice. It's not useless, but it's for analyzing algorithmic complexity, not for analyzing algorithmic performance.
Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been. Some instructions take more cycles than others.
Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes.
Etc, etc. An algorithm's complexity is loosely correlated with its performance, but the two are not identical.
Indeed. I do think knowing about big-O and keeping it in mind is important though.
Yes this loop is fast now with my 1000 items, but what if the input grows to 100000 or more?
Keeping it in mind can also help you avoid accidentally writing O(n^2) loops or worse. More than once I've been unsure about the complexity of a library call, so I check the code and it's say O(n) rather than O(1), potentially turning my own O(n) into a O(n^2).
>Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been
Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior.
>Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes.
This is definitely something to keep in mind when analyzing algorithms, but that does not imply asymptotic complexity is not useful when analyzing performance. There are other measures (e.g. how an algorithm performs on a random small input, or maybe your domain is restricted somewhat) and sometimes those measures areore useful than big O, but big O remains useful, it just is not the end all be all.
> Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior.
This assumption is demonstrably broken if the first multiplication is a cache miss but the other multiplications then aren't -- an easy example is when the other two multiplications have data on the same cache line as the first multiplication's data.
That is probably a reason big-O is used, the big-O definition which says that they most be upper-bounded by a linear multiplier. So even if the second and third multiplication is faster it will not change the asymptotic behavior.
Actually, things like merge-join can benefit from the hierarchical aspect of something like a Btree, making not only the individual accesses/seeks more efficient, but also saving more in the first place
You're free to use other compuational models in algorithm analysis, which define what costs you're assigning to which operations. If you use big-O on top, then the actual numbers won't matter, but which operations you count certainly do.
This is part of algorithms analysis that a lot of developers skip: these are just tools, there's many models available to use with them, or if you want to, just use wall-clock, with all of the pain that comes with that.
Some algorithmic competitions (eg. Polish Olympiad in Informatics) go even further, and judge programs not on execution time, but on executed instruction count, effectively emulating processor with very large amount of RAM.
A practical example that counts instructions is EVM. Gas usage is counted deterministically to limit computation overhead, and smart contracts are designed to optimize away every unit of gas since they cost real money.
> Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been. Some instructions take more cycles than others.
No, it only assumes that there is a constant factor between the fastest and slowest "operations". It does not matter that one instruction can take a thousand times more cycles than another, if you have n² fast instructions and n slow ones, the running time will still be dominated by the n² fast ones for large n.
> Big-O assumes that only asymptotic behavior matters.
Yes, and this is the only simplification that it does.
Machines don't do infinity. This article isn't about an imaginary computer with an infinitely long paper tape from a thought experiment, it's about a real computer, just like the ones many HN readers work with every day.
As a result k*N can actually be bigger than N^2 when in fact N isn't "an integer" in a mathematical sense but merely a 32-bit machine integer, for example - simply by k being more than 4 billion in that case.
> This article isn't about an imaginary computer with an infinitely long paper tape from a thought experiment, it's about a real computer, just like the ones many HN readers work with every day.
If you're determined to throw out any concepts which technically only apply to theoretical computers with unbounded memory, then go all the way. Your actual physical computer can trivially iterate through all of its possible states in a fixed amount of time. The halting problem is trivially solvable for all programs that your actual physical computer can execute. Your actual physical computer isn't even Turing complete.
> Your actual physical computer can trivially iterate through all of its possible states in a fixed amount of time.
Nope. You're in an imaginary world again. This universe will cease to support computation a long time before it would be possible for the computer to try all possible states.
Sure, but that's like saying that your computer could experience power outages or hardware failures at any time. That's true, but we don't normally consider those as limitations to the computational capabilities of your computer.
It's a difference in kind. The computer could experience a power outage, it could experience a hardware failure, but regardless it and all other real computers will cease to operate long before it would be able to explore all possible states.
I don’t think it’s a difference in kind. Given some specific physical computer, how would you determine an n such that n states are iterable on that computer but n+1 states are not iterable due to the universe’s ability to support computation?
Algorithms and programs are different things. An implementation of the algorithm is called a program. Big-O is used for comparing of algorithms. An algorithm can be implemented in different ways. Performance of the program can be measured precisely. Different implementations of the same algorithm will have different performance. When precise information is available, assumptions are useless. When precise information is not available, at design stage, assumptions are used to compare different algorithms.
I think that makes sense only for smaller n. At some point your "sufficiently large constant" will need to essentially be computed from the "worse big-O" algorithm to slow the "better big-O" algorithm down enough. E.g. making an O(N) as slow as an O(N^2) algorithm would require a sufficiently large constant roughly equivalent to N^2, at which point you really just have turned the O(N) into O(N^2) in practice.
There is something of a bounded limit on how long a single operation could possibly take, assuming your hardware isn't just plain faulty.
Yes, for the purposes of Big O, we define operations such that they aren't simply 1:1 instructions to the hardware, but they should be basic commands offered by your programming language.
If the basic commands in your language are taking extremely high bounded amounts of time, that's a sign your programming language is extremely poorly optimized, not that Big O isn't useful.
The idea behind Big-O notation is how the time generally varies as you increase the number of items for a given algorithm on a given data structure/data set. That is if you plot a graph `y=f(x)` where `f(x)` is the time taken to perform that operation and x is the number of items you are performing it on. You can then match that resulting curve to a polynomial or other mathematical expression, and Big-O is the dominant term in that expression without any associated scale factors (e.g. for 6x^3 + 2x^2 + 7 you have an O(n^3) algorithm).
Sure, you can choose a large constant such that numerically it is equal to or smaller than O(n^2) for a given n, but as you vary n then O(1) should approximate a flat `y=N` line, while O(n^2) should approximate a parabola and would result in values larger and smaller than N as you vary it.
That's not how constants work in mathematics. You have to give the constant first and cannot change it later. That is what it means for a quantity to be constant.
> Big-O assumes all "operations" are equally costly.
This is a big misconception about "Big-O". It does not "assume" anything. It's just not what people think it is.
It's an asymptotic upper bound on counting something. In sorting algorithms you count the number of comparisons expressed as a function of collection size. In collection insertion algorithms on some underlying data structure, it's counting some not-very-clearly-defined atomic operations that are being executed when inserting an element.
Where the assumptions come from is if you start using the notation to give performance comparisons and also start assuming things about Big-O that are just not true. But that has nothing to do with "Big-O".
There is a family of symbols, called the Landau symbols, of which Big-O is only one. There is a lot of misuse of the symbol and in many cases what people actually mean is Theta(N) or Omega(N).
This is a pattern of discussion I see a lot on HN:
"People who believe in X are wrong because A, B, C."
"No, X is actually right, because if you know about these obscure parts of X-theory which laypersons never hear about, you will see that it addresses A, B and C."
Of course, both these comments are right, because in addition to the fact that X-theory does in fullness address those issues, few people know how it does.
I see it mentioned somewhat frequently by learners on 'learn-to-code' platforms when discussing code. Even when thinking about it wrongly, it can useful.
I don't know when the original article was published, but Jon Bentley's book Programming Pearls (IIRC) contains essentially this same essay (actually, reversing an array) and was published in 1986.
Weird, we didn't get into complexity theory until CS 350. Before that we mostly focused on logic, data structures, and languages (with a bit of computing thrown in). This was at Portland State in the late 2000s though.
It isn't CS 101. You are being overly dismissive and even CS people from top schools get this stuff wrong.
The courses that introduce big-O are often the weeder courses, they don't aim to education, they aim to flunk out the people that might be hard to teach so that CS departments can gate keep.
When you have top CS researchers having to give talks to remind people that layout matters more than instruction selection, the CS as a whole has focused on the wrong things.
> The courses that introduce big-O are often the weeder courses, they don't aim to education, they aim to flunk out the people that might be hard to teach so that CS departments can gate keep.
That is an often re-iterated conspiracy theory. In practice nothing could be further from the truth. Professors have nothing to gain from weeding out students. They have to gain by ensuring a certain standard. By the way it is also better for a student to encounter the difficult parts of their subject as early as possible, so that they can decide whether they have chosen their subject wisely. On the other hand, not failing students on fundamentals means complicating advanced subjects even further --- for everybody.
At some point in life students have to accept that neither their time in university nor their time in the industry will consist only of externally motivating tiny bites of tasks that are awesome. In order to understand complicated matters, you have to put in the work. Spending hours in the gym is also quite boring, but most people accepts that it is necessary for certain results.
I've been involved with undergrad teaching in a University. And the amount of time we spend on finding ways to teach and test better was way more than I could have expected as a student myself. On the other hand I couldn't have imagined the arrogance and sometimes stupidity of first year student claiming to know already what they will need in there career and what not.
> That is an often re-iterated conspiracy theory. In practice nothing could be further from the truth. Professors have nothing to gain from weeding out students. They have to gain by ensuring a certain standard. By the way it is also better for a student to encounter the difficult parts of their subject as early as possible, so that they can decide whether they have chosen their subject wisely. On the other hand, not failing students on fundamentals means complicating advanced subjects even further --- for everybody.
So much to unpack there. Some rhetorical hyperbole, other false dichotomy and we are both arguing from anecdote.
Weeder courses exist and as you even admit, they aren't solely meant to educate. That is the point. Anything that is designed to test students resolve as well as not waste professors time is not designed to educate, it is designed to reduce the size and shape of the student population. I applaud that CS departments are adding more and more courses for non-majors. But lets look at the syllabus for a 10 week quarter for the first UW CS course, Foundations of Computing [1] which also expects the students to layout their homework (proofs) in LaTex. Jesus. This is mostly a hazing ritual. In my 3 minute sampling of Reddit, most CS students rank 311 as the hardest course in the major and it is the first. [2]
> At some point in life students have to accept that neither their time in university nor their time in the industry will consist only of externally motivating tiny bites of tasks that are awesome.
I never said anything of the sort, you putting words in my mouth.
> But lets look at the syllabus for a 10 week quarter for the first UW CS course, Foundations of Computing [1] which also expects the students to layout their homework (proofs) in LaTex.
Your argument might make more sense if 311 were the first CS course, but it's not. You can easily verify that by looking at the course listings which reveals it has a prereq, CSE143, which has a prereq of CSE142. So short of skipping those, it's the third course at the earliest.
You are being overly pedantic and arguing for the sake of arguing. The rhetorical language you are using "might make more sense" and "easily verify" is demeaning and insulting and doesn't add to the discussion.
311 is the first course of the major and is also by the sample of folks in the reddit discussion also the hardest, covering the most advanced material in the shortest amount of time. It is a weeder course for the major. The 100 level classes are open to everyone.
> In collection insertion algorithms on some underlying data structure, it's counting some not-very-clearly-defined atomic operations that are being executed when inserting an element.
Nailed it. My frustration is that those words are rarely mentioned, and that atomic isn’t really atomic except in the context of the problem statement and solution.
> This is a big misconception about "Big-O". It does not "assume" anything. It's just not what people think it is.
In my experience, we all spend more of our time dealing with what people think things are than what they really are. Even if reality tends to pop its head up now and then.
I think the root comment is correctly describing "how people talk about Big-O" - even though, as you point out, they are mischaracterizing it.
I find this is often a more vexing problem than the underlying performance questions: how do we find good ways to talk about the use (and mis-use) of analysis in a way that produces good tools?
Not to mention that it is overemphasized in education. Probably because teachers often are somewhat disjointed from practice.
Similarly “competitive programming”, A&D and coding puzzles which I find fun but only tangentially useful, will typically completely neglect engineering constraints. The shape, size frequency and variations of data can almost always be at least estimated in the real world, or simply assumed.
I don't remember my education over-emphasized Big-O too much - I mostly started thinking about it when I was preparing to do interviews at the end of my undergrad education. I suspect there's been a back-and-forth between industry and schools where industry seeks to weed out very weak programmers (i.e. those who fail fizz-buzz, people who write accidentally exponential code) and schools seek to over-prepare against those easy checks.
Real assessments of performance go far beyond the depth and breadth of expertise that most students get in undergrad - so it's a fools errand to try and junior engineers about concepts like that. Big-O has a lot of flaws but I get why it seems so useful to all the groups that use it.
Assessment of performance can be practiced and taught in the small.
It’s really just about making decent estimates, testing and some profiling. There’s of course potential mastery here, specific knowledge and tooling, you can dig down almost indefinitely, but the basic motions can be taught with simple projects. You don’t need Google scale to encounter performance problems and potential improvements.
I know this because I work on small scale things, and had to learn this kind of thing on the job. I can imagine a ton of educational projects that teach this.
Complexity analysis and A&D are very useful when you need them, but they are just two of several tools.
Big O-notation is literally "first-order approximation" (in a complex polynomial, take the "first-order term", which most clearly defines asymptotic behavior, and ignore the rest of the terms as details). It's a simple, silly name for an extremely useful (didactic) tool. I don't think it is teaching that has become disjoint from practice, but practice has become disjoint from the teaching: if I say "first-order approximation" out loud, colloquially people understand it to be "a rough estimate" and plan accordingly, but sometimes in practice people hear "Big O notation" and don't think "this is a rough estimate of just a single term in the equation of complexity of the operation".
Similarly the term we use is often "N" and "N" could mean anything, and in practice you need to know what "N" you are optimizing for/against. That's where the engineering constraints fit in. It doesn't matter of you pick an algorithm with good Big-O in time (where n represents number of operations, for instance) if your are constrained in space (memory size; cache size; cache locality) and vice versa. Big O notation is an approximation with respect to some function and that n among a selection of choices of different functions/different "ns", that complexity function itself can vary a lot based on your trade-offs. (Which also gets back into Big O is only one such tool, as well. Sometimes you really need to know worst case "Omega notation" and not really Big O notation, if your constraints include lots of worst case things. And so forth.)
Estimation isn't "destiny": know what you are estimating, why you are estimating it, and with respect to what constraints you are estimating it. Big O notation is "back of the envelope math" for algorithms. It serves some great uses, especially in practice, but you need to know what you are estimating and why.
Big-O/Theta/etc. are just tools for analyzing functions. But it also matters which function you are analyzing.
Typically a program is evaluated in terms of something like the "Random-access machine" where every instruction has a constant cost.
There's a bunch of additional assumptions hidden in this machine model!
In the real world, the speed of light and the Bekenstein bound conspire to make constant-time random-access to a memory of unlimited size impossible. In practice, a random memory access takes O(sqrt(N)) time. We like to pretend that there's a constant worst-case access time, but that only works out because our machines have a limited amount of memory -- it's not really appropriate for an asymptotic analysis.
So complexity theory based on the "Random-access machine" is just measuring a theoretical instruction count that doesn't necessarily correspond to the real-world run-time. There's other models that get closer, e.g. the "cache-oblivious model".
But it still falls down so quickly that the smart money is on actually paying attention to the Devil (the details).
In its own constructed universe, orders of complexity doesn't obey basic physics. Imagine I'm trying to sort a billion unique books alphabetically by content. In order for the books to be unique, m > logn. For many big problems logn < m < sqrt(n) but for a lot of the rest n < m on day one, and stays that way for quite some time. For large objects, an algorithm that avoids comparisons can be faster with real data even if its complexity is n(logn)^2.
Where we fuck up is pretending that mathematical operations are O(1) when they are O(logn) on a good day and O(n) on a bad one. + and - are constant if the numbers fit into a single integer. [] is only constant for n < L1 cache size, and even then only if no other tasks are happening. And as I've just described, < and == are not constant time either. We need better math for these sorts of things.
Agreed. I'd go a step further, there's a real-world heuristic that this implies.
Initially, prefer to task CPU over memory allocation. Crufty allocation generally will always have a real negative impact felt by the end-user. A low memory footprint is always a win, while going for a (theoretical) fast running time may be effort wasted.
At the extreme ends, there are two kinds of slow computations.
1. A small computation that you perform many, many times.
2. A very, very large computation.
For #2, big-O can still generally tell most of the story. (Example: 100 insertions in the middle of a list with a billion elements.) For #1, big-O almost irrelevant, and benchmarking is key. (Example: a billion insertions into the middle of length-100 lists.) So knowing which situation you're in is important.
As you go up the scale the Big-O values are almost always dominant. It's very rare to see a situation where you would choose the algorithm with the higher value.
However, when two algorithms have the same Big-O there can still be a big difference in performance, especially in the face of how a cache influences things.
(There are cases where the memory accesses are so important that they can make the "bad" approach better. A while back I did some time testing and found the Sieve of Eratosthenes inferior to brute force because of all the cache misses.)
At a certain point your best bet is really to profile the two approaches to see which performs better.
But if you are starting out with nothing built and only have time to write one, you can't really go wrong by going with the one with the better Big O. If it's the same, coin toss I guess. :)
> Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes
Well I did have a CS teacher that said that O(log n) is basically O(1) because in practice, n usually will fit it in a 32bit and log n then is 32 at most :D
It might have been said in jest in part but really it's not that far fetched.
And similarly, very few algorithms are better than O(n), because something as simple as adding 2 numbers can be O(n) where n is the size of the number in bits :)
But big-O is not an equivalence relation on functions, because it isn't an equivalence relation. A big-O relationship is not symmetric: if f(x) = x² and g(x) = x³, you can see immediately that f(x) = O( g(x) ), but it is not true that g(x) = O( f(x) )
Big-O is a statement about the limit of a function as the input goes to infinity. f(x) = O( g(x) ) is the statement that the limit (f/g)(x) exists as x goes to infinity. f(x) = o( g(x) ) is the stronger statement that the same limit exists and is equal to zero.
In practice the difference between constant factors is usually between 10 and 10^4, while input size can go up to 10^10 and more, so factors of sqrt(n) or higher will usually always matter, while factors of log(n) or lower will often not matter, and factors in between will depend.
Be careful - many people here hang an entire identity on their high status, high paid jobs which were earned by memorising the answers to theoretical algorithms questions. It is important to their self worth that that stuff is relevant to the real world.
You'll get a similar reaction to if you try to show people who won money on crypto art or tesla that they are lucky early members of a pyramid scheme.
A bunch of operations classically represented as O(1) are O(logn) with step functions. They are only constant time for ranges of values, and eventually the response curve smoothes back out into a logn line.
And the usual argument is, "well, it's understood..." which is a terrible argument because the whole notion of ignoring constant factor C is that it's supposed to go to the noise floor as n approaches infinity. So if you're going to claim that we didn't mean n approaches infinity, we meant "n fits into a CPU word and the data set fits into memory" then you're trying to have it both ways and that's pure nonsense.
You're assigning agency to a notation, which is not very productive. Big-O doesn't "assume" anything, doesn't depend on what "matters", or try to achieve anything. It's well defined and you need to understand what Big-O is to understand its result.
If you want a better overview of algorithms for practical reasons, you can use o(), O(), average case and ammortised complexity, or just provide histograms of runtimes for algorithms you're comparing.
Yeah, we should teach this to undergrads. If you want high performance for a dynamic list, you end up making a lot of tradeoffs with tricks like:
- Use blocks of multiple elements per actual list element that fit your cache line size. Blocks also have the benefit of potentially allowing SIMD processing of your data.
- Allocate blocks out of a vector or some other structure that reduces your actual number of allocation calls. Maintain a free list threaded through this vector.
- Tombstone list elements in their blocks on removal instead of repacking the entire list. This allows for fast deletions and fast insertions at specific locations (in that you can always insert a new block between existing blocks containing only a single element or get lucky and re-use a tombstoned slot).
Note that most of these optimizations trade some memory efficiency for speed. This is a common theme in optimization. Using more memory, but using it more intelligently such that you are potentially accessing less of it and accessing it sequentially where possible.
I find it's best to write readable, straightforward code at first, and when performance really matters, benchmark to find places where you can eke out the percentage points that matter. Premature optimization can waste valuable hours when you don't know what how production workloads will stress your application.
This. I always write for readability and only pay attention to performance when it's something that's going to be repeated often and it matters on the big-O scale. Optimizing beyond that should only be done with the profiler to guide you.
I don't know -- most implementations on popular architectures only have two (low order) bits for tagging due to alignment issues, so there may not be room. Might be easier in the case of a RISC V with the tagging extension.
Also it would be possible to implement such an approach in a C++ list container where you don't need boxing (the content type is known).
I’m not an expert in Linux but I would be surprised if Linux didn’t do the same. RAM costs have plummeted. The losses from RAM usage overhead of LFH became insignificant compared to the issues caused by the fragmentation.
To be pedantic, Linux doesn't care about how malloc is implemented. That's purely userspace's concern.
But yes, the default glibc allocator does have dedicated areas for specific sizes of allocation:
> The normal bins are divided into "small" bins, where each chunk is the same size, and "large" bins, where chunks are a range of sizes[1]
But fixing heap fragmentation doesn't make linked lists suddenly fast. You still have your cache bloated with the overhead bytes needed for allocation. List elements can still be allocated non-contiguously, giving the prefetcher a bad day.
This is a common misunderstanding of computational complexity: It does not measure runtime, but how runtime changes depending on the input. Take the following two algorithms to find the square root of an int:
result=None
for i in 0...INT_MAX
if i*i==searched
result=i
return i
and
for i in 0...searched
if i*i==searched
return i
The first algorithm is O(1), the second is O(sqrt(searched)). Despite this, the second will clearly be faster in actual execution time. However, if your number range changes from 0-100 to 100,000,000-250,000,000 , the former will still take the same time while the latter will take a lot longer. Now, in this example, this is quite obvious, but in the real world, you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity - it was never designed to perfectly measure or predict execution speed. This is also the reason constants are dropped in the notation.
For real world performance, benchmarking is the key. Computers are very complex beasts and there are a lot of potential speedups or slowdowns you might never think of - memory bank order, thermal throttling and compiler optimizability can drastically change the results, just to name a few. Computational complexity is totally fine as an angle to find new possible optimizations, but in the end, you need to compare it to the other approaches and see what actually works.
I would probably argue that either the first algorithm is incorrect (because searched can be larger than INT_MAX) or the complexity of the second algorithm is bound both by O(searched) (or sqrt(searched), if implemented with more vigour) and O(1) (because the value of 'searched' is bound by a constant).
If you assume that it's unbounded, then either the algorithms aren't solving the same problem or the first one is wrong, so it doesn't make sense to compare them.
> For real world performance, benchmarking is the key.
Only it's not enough. When you benchmark an O(N^2) algo may seem fine but then three years later the data has changed and is now an order of magnitude larger. So you need not only know your data, you also need to spend time thinking about how large it can become.
True. But I do highly recommend watching Ben Deane's 2015 talk about testing Battle.net. In it he briefly touches upon benchmarks and estimating algorithmic complexity. It's somewhat difficult to suss-out the details of it. But the short version is basically to run the benchmark with a few different sizes and then estimate the complexity growth from that.
You seem to be agreeing with the parent comment's point. For example, there's this bit of their comment, which is almost verbatim what you replied back with:
> ... you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity ...
It seems like you're disagreeing only because you pulled out the one quote about benchmarking. But they were just saying that you need benchmarking to bootstrap the meaning of O(...) of an algorithm. That's the point that the original article missed, which is presumably why they described it as key.
I would have a huge problem describing the first one as O(1). Technically the complexity is min(searched, INT_MAX), but the algorithm would also fail to produce a result if it reaches INT_MAX.
Functionally, though, I would describe this algorithm as O(N). It's just a straight up linear scan of the problem space. It's unbounded, with a worst case of O(Infinity) and no upper limit on what searched can be, but it's functionally O(N) regardless.
O(1) needs to basically be something like a hash key/pointer to memory address to get the result you're looking for. It will not increase linearly as the problem space increases, whereas your first example increases exactly linearly.
This is incorrect. Putting a finite bound on n does not reduce n to 1. n is always meant to be a finite arbitrarily large value. n=INT_MAX qualifies as arbitrarily large, especially on a 64-bit system.
That’s just not how complexity analysis works, if there’s a bound anywhere, it is O(1). The behaviour below that bound may be of more practical importance, but it’s not how O-notation works. The parent comment doesn’t make a great deal of sense for other reasons, but your objections don’t hold either.
By this logic, all programs that we run are O(1), since any data structure is in practice bounded in size by your available address space (+ disk space if we want to be pedantic). So, you can replace any loop over the elements of a DS with a loop over all memory in the address space, and you will get an O(1) algorithm.
In the end, it's just not a useful way of modelling the problem.
Yes, so ordinarily we analyse an idealised algorithm running on idealised machine. However if an upper bound is clearly introduced to this idealised setting, as in the root comment, then it can’t be ignored.
But playing tricks with the INT_MAX limit ignores(or, more accurately, spits in the face of) the fact that we want our computers to pretend to be idealized machines.
Floats aren’t real numbers but we treat them like the mathematical object that they model for most purposes.
Of course, being aware of the limits of our models are important, but abusing the tragic finitness of our models to “well actually” someone is generally not helpful.
It looks like you intended your first snippet to end with `return result` not `return i`, right?
Mixing real-machine finitude with big-O theory often gives unexpected or unhelpful results. Once in an interview I argued that since hash tables have a finite number of buckets, at large enough scale they really have O(n) worse-case performance. That didn't go over very well. :-)
A linked list is going to be more costly where objects are simple integers and a single array access can load multiple adjacent elements. In practice, list nodes are more often than not complex objects, where loading a single object will flood the cache anyways.
Furthermore, the author is masking the true cost of an array resize, which often happens in a running system where a finite array is completely full and needs to be resized to append an additional element. This is the scenario where linked lists are most useful.
You can also simply have a pointer to the value, so a node is just three pointers (prev, val, next) in a fixed sized structure. This gets you 2 nodes / CL. Add a fixed sized hash of value (key) if you want to search the list without chasing the val pointer, and your node still fits in a 64b CL. Pad it with 24b (yes, sacrifice a bit of space for performance gain) and your nodes will cache align.
Resize point is fair but we still options here. A segmented approach for very large collections may also help, with tuning knobs of array size / segment. The smallish top level ds maintaining segment ptrs will be super hot and very likely ever present in L2.
It really all depends on how many items are involved and how the data needs to be accessed and used.
> STL list […] the mallocs cost will still be greater.
This is a narrow view of the costs of the STL::list container class, not of linked lists in general.
Linked lists are at their best when they are internal storage, meaning the links are part of the class being stored, in order to prevent unnecessary mallocs. STL::list is an external storage container, which automatically compromises some of the potential benefits of a linked list. Linked lists are also best when you don’t malloc to build the list at all, but maintain things already in memory. Linked lists are best used in places where using vectors is impractical or impossible, like the insides of a memory manager.
I don’t feel like timing many inserts using STL::list says a lot about linked lists at all, and what it does say is mostly focusing on the wrong things. Definitely use vector when you can, especially if you’re just comparing container classes.
Intrusive lists are better, sure, but pointer-jumping will still throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful. And avoiding pointer-jumping is not an automatic win from using intrusive lists — you still need to allocate/lay out your stack conscientiously. And a very similar argument can be made for bounded arrays as an alternative to std::vector.
Also, I only skimmed it, but the article seems to ignore the fact that even for an unbounded/growing array like std::vector, the growth strategy does not free+malloc/realloc on each insertion in practice, as the growth strategy will leave unused capacity for future insertions, and in such cases the cost is just memmove (for simple types at least). Maybe I missed that part, but it seems like an important point worth highlighting.
> pointer-jumping will throw away the (absolutely astonishingly large) benefits of the cache, unless you’re careful.
Right! Yes, that’s part of my point, STL::list isn’t being careful with cache, or with allocations. Really it just rarely makes sense to even compare STL::list to STL::vector as if they’re otherwise equal choice. Usually the choice is (or should be) driven by constraints, not by which has a slight perf edge, right? Inside a memory manager, use of a vector isn’t usually considered a choice. Maybe it’s possible to build a free page vector, but I think isn’t common, and people usually pay the costs of pointer chasing on the free list because there aren’t practical alternatives.
> the <vector> growth strategy does not free+malloc/reallocate on each insertion
Yeah very good point. Does STL::list do the same for the container of pointers? I don’t even know, but maybe it can’t, and maybe the primary perf advantage of STL::vector over STL::list is due to vector’s amortized mallocs?
I’d heavily bet against std::list having any kind of “extra capacity” logic, as it would have to be some kind of free list of Node types — best leave that to the general purpose allocator.
I think the list vs vector comparison is fair, as most people are taught to “just use the standard library, don’t be a hero, don’t commit a NIH crime”. I have done this myself at times, but in fairness, mostly when discussing adaptations of existing code, where there were bigger structural issues. And it cannot be repeated enough, that vector is far better than list, even at prepends or random insertions, for a surprisingly large number of elements (it was at least thousands of int32-s when I checked it about a decade ago). Typically the justification for a list is that the workload is prepend/random insert heavy, but in my experience there is more often than not a bound on the size that strongly favors vector.
IIRC, the Borland C++ STL implementation made use of buckets of consecutively allocated entries so you would generally find consecutively inserted items next to each other in memory. You can also define your own allocator that does something similar.
It seemed like this person was talking about an intrusive linked list with an arena allocator of some sort, which isn't ideal but still fairly cache friendly.
STL list is great because it the only STL structure you can insert into without potentially invalidating iterators and references since it doesn't call resize. If you want a performant list-alike, you use a deque.
Yeah I was taken aback when they talked about “linked lists” and instead of banging out a simple linked list they used an STL container that isn’t necessarily optimized for the use case. It’s malloc-heavy and uses full sized pointers instead of indices. There’s a lot more to the array vs list argument than this.
When I was a kid and took programming lessons in high school, they taught us about linked lists,using Pascal or C.
Back then, there weren't any list like data structures backed by arrays, like List from C# and Vector from C++.
But learning linked lists was a good thing, we also had to learn about pointers and how memory is layed out, so we also knew that sequential access to memory is faster. Also, learning about stack vs heap, CPU caches, made a big difference in how we wrote programs and how we continued to write programs 25 years later.
So I think I was lucky starting with Pascal and C, continuing with C++ instead of starting with Python or Javascript.
My general experience with education is that one is well served by knowing things a bit deeper than one actually uses them. Going one more layer down in education makes the stuff you actually do use make much more sense.
I got schooled on this topic a while back. I was arguing in a discussion that ArrayList was always better than LinkedList in Java.
Most of the time it is, but note that ArrayList has to occasionally allocate a new array when the list outgrows the array inside it, then copy the list.
When the list gets huge, that operation of reallocating and copying gets disruptive as it puts a lot of pressure on the cache, memory allocation system, etc.
I believe it corresponds to the traditionally learnt O(n) lookup, O(1) insertion/deletion of linked lists, whereas the reverse is true of arrays (having to move the items).
Though in practice I find that unless you are often deleting elements from the middle, modern CPUs will really prefer copying a huge amount of serial data, so an arraylist may still be faster all around then LinkedLists. (The CPU will recognize you moving values in a given direction and will have the best pipeline it can have)
Most of the time that is right. In fact, there was a revolution in how people write query processing systems in the 2010s where people realized that the performance of a processing pipeline that reads columnar data structures straight through is amazing, particularly if you can use SIMD instructions.
On the other hand, pointer chasing often isn't as bad as you think it might be. That is, modern allocator/garbage collectors often end up laying out the parts of a linked list in a predictable way such that access is somewhat strided and the fetcher is reasonably efficient at traversing the list.
> On the other hand, pointer chasing often isn't as bad as you think it might be.
It kinda really is, though. In addition to cache line locality, serial access also benefits from being speculatable. The CPU can't very effectively speculate past a pointer chase (and on arm little cores it doesn't even try), so those become pipeline stalls.
Even if the pointer happened to be close-ish, it's still going to end up being a stall more often than not.
And an allocator / GC is only going to lay out a linked list in any sort of predictable way if the linked list is built up all at once, in which case a linked list is obviously not the right data structure anyway ;)
> I was arguing in a discussion that ArrayList was *always better*
Tsk tsk. A critical rule for flame wars that also applies to mere discussions among common folk is that you should avoid using absolute terms, as it gives your opponent an easy opening. Instead, couch your statements in vague and wishy washy terms like 'usually' and 'often'.
This also helps when your opponent produces a valid counterexample - you can petulantly retreat to safer ground while grumbling about how of course there are occasional exceptions and then, if you wish, you can sidetrack the argument into a debate about how often it really happens. From there you can feign boredom and exit, think up a snarky, mic-drop conclusion, etc.
- As taught in Raised on the streets of BBSs and USENET
No seriously, once you recognize the components of Rhetorical Combat, you can determine if you are going to have a civilized discussion, or if the parties will weasel their way around for sport or entertainment.
If someone attacks my argumentation with uncharitable takes, my discourse with them is over.
I personally would rather arrive that the truth and be wrong, than win an argument and let the truth escape.
The overhead of ArrayList reallocations is no more disruptive at small scales than it is at large scales. (Of course, the total memory needed at large scales can be disruptive, but that's fundamental. If you've got a lot of elements, you need a lot of memory for them.)
ArrayLists grow by allocating a new buffer whose size is a multiple of the current size. This means that as the buffer size gets bigger, the reallocations become less frequent.
The end result is that appending to an ArrayList has constant time amortized complexity, even though it will periodically do increasingly large copies.
> (Of course, the total memory needed at large scales can be disruptive, but that's fundamental. If you've got a lot of elements, you need a lot of memory for them.)
But in case of a linked list that large amount of memory doesn't have to be contigous, and you don't have to perform a lot of copying all at once which kills responsiveness.
> But in case of a linked list that large amount of memory doesn't have to be contigous
True! Though in rare cases where that becomes a problem, you are probably better off doing a hybrid solution where you store the data in a relatively small number of chunks or pages. If you have so much data that you are having trouble getting a contiguous allocation, you probably also can't afford the overhead of an additional pointer for each element, which is what a linked list would give you.
> you don't have to perform a lot of copying all at once which kills responsiveness.
I believe there are ArrayList implementations that distribute the copy across a series of operations to mitigate this, but, yes, latency can be an issue for some use cases. (In general, though, my experience is that people overestimate how long it takes to copy a contiguous block of memory.)
ArrayList is still better in your case. Having to do log(n) contiguous copies when reallocating is much better than having a copying GC copy n live objects that are 5x as large as the element by itself or a mark and sweep collector mark n live objects.
Thing is that in a pointer heavy environment like Java (or Python, JS, C#, even C++ with too much OOP), it does not matter that much.
The ArrayList will be a nice flat chunk of memory... of pointers to the data, so you'll have to do a lookup for each element anyway. The LinkedList will have two lookups still, but it's not an order of magnitude anymore. Now it's more of a tradeoff between bit slower reads / bit faster updates.
If the worst case latency of ArrayList is a deal breaker, then almost certainly the average case latency of LinkedList is also a deal breaker.
You maybe want something like a linked array, but it's staggeringly difficult to find a scenario where a Java LinkedList or c++ std::list is ever the optimal choice. You should pretty much always start with an ArrayList or std::vector and go from there if/when it ever turns out to be a hotspot in benchmarks or profiling
265 comments
[ 4.2 ms ] story [ 297 ms ] threadIn the first table:
the last column makes no sense. Is that an error sorting the data or I'm misunderstanding what it mean?Array copying is really optimized on current hardware.
i thought that was the point of linked lists: O(1) insertion & deletion.
If all you're doing is "Remove the mth item of the list" takes O(m) time to traverse and O(1) to do the removal if you're starting from the head.
On the other hand, if you already have the pointer to the list element for some other reason, somebody else has already been billed for the traversal and the insert or removal is O(1).
You see linked lists used a lot in e.g. the kernel where the traversal has been paid for to get a pointer to an element that has then been used for a bunch of things before a deletion or insertion happens.
They also have the advantage that in the face of other threads mutating the list, the address of the elements remains constant. If you have a pointer ti an element in an array, and another thread comes along and does an insertion or deletion that moves it, now you have a problem.
Single-threaded performance isn't the only criteria for picking a data structure.
A queue very well might be best implemented as a linked list rather than an array.
For example you have a list of points that define a linestring, and have to make sure that no two points are further apart than some value. It's really simple to iterate over linked list, insert a midpoint into the list, stay at the same step and redo the calculations(because p0-midpoint can still be longer than some value).
But other than that i don't think i had to do many random inserts/removals in non-DB contexts.
one of the benefits of a linkedlist is having the ability to remove an element from a list in O(1) by having reference to an item that is stored in the list. This is allowed since a linked list node can remve itself in constant time. This is a common pattern in linked lists used in C code for example.
javas linkedlists don't allow for this benefit. since in java you have to perform a search for the node to be removed and pay a O(n) penalty on a O(1) operation.
CPU cores have a special functional block which observes addresses of cache lines requested from memory, detects sequential access pattern, and when detected pre-loads data into caches (including L1d) in advance. The RAM access pattern of std::vector search benchmark is an awesome use case for that thing.
[0]: https://www.systemverilog.io/ddr4-basics
One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?
only pertains to languages like C. In a virtual machine language like java, this isn't a property that can exist (there's no such thing as an address - at least as far as the language is concerned).
Vectors and arrays have the problem of needing contiguous memory. If an inner cell can have different size, or worse change it mid work, things get ugly really fast.
They're also more useful on microcontrollers where there's no cache, no prefetcher, etc. Less code needed for the data structure means more free space for business logic, and there's no performance penalty for bad cache locality on a system without any cache. Also a hash table has to hash each input, which is a significant amount of work for many microcontrollers.
This is a linked list with the same shape as the list above, but with completely different performance characteristics:
With some elaboration (say exchange the arrays for a mmap-call, turn it into a tree instead of a list) and you're basically looking at the guts of a DMBS or a file system.It depends on the use case.
If you're doing a lot of navigating over links before you reach the destination, maybe you want them separate. Could also be the data is large, even maybe stored on disk while the links are in memory, or whatever. There's a thousand different scenarios with different optimal arrangements.
It also allows you to keep multiple different lists to the same data, say sorted by different fields in the struct.
Sounds a lot like “draw the rest of the damn owl.” [0] :-)
DBMSs and file systems use (extremely sophisticated) tree structures under the hood. Not sure that “linked lists are useful if the linking topology is much more complicated than a simple line” is a ringing endorsement of them.
[0] https://pbs.twimg.com/media/Bs13i6LCcAAvwCf.jpg
( Here's an enjoyably lucid explanation on how to draw such an owl: https://www.youtube.com/watch?v=aZjYr87r1b8 )
You actually don't. You can just keep two lists within the same structure, one for occupied nodes and one for free nodes, and just move deletions to the head of the free nodes list.
Example List:
Link shape: To Delete C: This changes the data such: New shape:Yes, and constant time insertions/deletions in the middle of the list, assuming you know the address ahead of time.
This makes them great as backing queues in an LRU cache: given some key/value pairs, have a linked list whose nodes map to each key. Additions to the K/V store gets appended to the LL. This lets you easily remove the oldest n elements in the K/V store, by traversing from the head of the LL. It also lets you efficiently remove arbitrary elements from the K/V store, if you store the addresses of each LL node as values in the K/V, since deletions in the middle of the LL are constant time.
>yet I see them employed in various places all the time
I agree, however, that most LL applications (like the one I just mentioned) are fairly niche. LLs are overused because they’re dead simple to implement and commonly taught in intro CS classes.
This also technically applies to lockless data structures for some high performance code too. But those tend to be much much more tightly tuned for performance and the specific CPU they are intended to run on.
Inserting an element in middle is probably only legit use but it is kinda rare to have large enough data that you frequently insert in mid
When the use case requires insertion/removal from the middle of the list. An LRU cache is about the most common use case I've run across. (The "LRU" part requires it to often bump an item to the end of the list, so LL's excel here, as we can shift the element's position in the list in O(1) time. An LRU structure would normally pair the LL with a HashMap, which maps the cached item to its LL entry, so that we've also got a O(1) search into the LL, and don't hit the problem in the article.)
> yet I see them employed in various places all the time, by competent engineers who are definitely aware of their limitations.
I see them employed very, very rarely. Vectors¹ are by far more common in every codebase I've ever worked on. (And should be one's default, IMO, if all you need is a container of stuff that you're going to iterate over, which is the usual case, for the reasons in the article.)
¹ignoring cases where a hash(map|set) is required; then our codebase uses that, b/c that's what's needed.
std::deque will invalidate iterators in some cases. Since my example above was an LRU cache, the cache's removal of an item from the middle of the list (to shift it to the end) is one of those actions that would invalidate iterators in a std::deque.
(Not to malign std::deque: it is a useful datastructure in its own right, and if you need queue-like semantics (e.g. cheap remove from front), it's a better choice than a LL, and both are better than vectors for that purpose. I find deque's internals to be a bit weird … my goto would normally be a ringbuffer, but the STL provides deque instead, so eh, it's good enough, if a bit odd IMO.)
(Cf. https://en.cppreference.com/w/cpp/container/deque)
Your question is more accurate than you realize! Because the answer is... the past.
Up until about the 486/50MHz era, CPUs and memory were attached to each other; one CPU cycle was approximately equal to one memory access. I don't mean that you could reach out to RAM in exactly one cycle and get a value, there were still some CPU caches and other considerations, but it was much closer to that ideal than on modern systems. And if you go back in time even farther, that actually was the case (Commodore 64, for instance).
(I don't know if there was ever a "true" 486/66 system, but I remember that as the CPU/clock speed where the CPU finally and definitively detached from RAM speed because that was generally a double-clocked 486/33 from the RAM's perspective. I can't quite remember the marketing term that was used. It's a dead term now because everything works that way.)
In those circumstances, traversing a linked list was not necessarily that much more expensive than a vector, and you could win on the other things a linked list can do faster than a vector, like insert in the middle, especially an insert in the middle when you were traversing the list anyhow. You could also win on a linked list containing a relatively large value organized just by pointers; a sort on the linked list manipulating just the pointers could win versus a sort that was trying to move around larger values constantly during the sort. And so on.
When memory accesses aren't hundreds and hundreds of CPU cycles, when your hardware doesn't have prefecting implemented, when your pointers aren't 64bits wide, when you aren't on modern systems essentially designed to make vector-based access go zoom, linked lists make a lot more sense.
This is how they got embedded in curricula so hard that they are taught to this day. They used to be a very important data structure. Now they're an antipattern. It happened gradually, though, and it doesn't help that linked lists are just about the easiest non-trivial data structure to teach and I'm not sure they could get removed from the standard curriculum for that reason alone.
"One case that seems to make sense is any time you want to do constant-time pops/appends… maybe?"
Another problem linked lists have is that if you know that's what you're going to do, you can build vector-based solutions to that problem that work just fine. Vector-based stacks, for instance, are trivial, and O(1)-amortized for push and pop, which is good enough in practice. (A bit more care is needed than an only-growing vector but IIRC it can be done.) You need not just something linked lists are better at, but some bizarre cocktail of all the things they're just barely better at, and you still need to construct a win out of the combo. It's nearly impossible. Not quite impossible. I assume without looking that the Linux kernel still has some linked lists for good reason, as I'm sure if they could win on performance by removing them they would. But very hard.
Every pop moves the whole list unless you get fancy an implement it as an array with head and tail pointers and grow logic.
If you keep a tail pointer inserts are likewise O(1).
You rarely traverse them.
(The best optimization you could do in such a case would be to allocate multiple slots per pointer, to amortize the malloc/free time. Then you'd want to run benchmarks to tell what the optimal amount of slots would be. If a vector is optimal, as I strongly expect it would be, the answer would come out to be, "all of them".)
Modern processors move chunks of RAM around really quickly. They're really optimized for it. It is one of the major things I'm referring to when I say our systems have been optimized for C. I often wonder about what an architecture designed in a world where linked lists were dominant would look like. However, it is certainly not this world.
The term I remember was 486DX2-66 , so was it DX2?
https://en.wikipedia.org/wiki/Intel_DX2
In the game industry, we use contiguous-allocated intrusive free list memory pools. For enemies or projectiles as an example. Those things live and die (they are removed from the free list and inserted in the "live" list or put back in the free list when they die) in such a way the locality is kept good.
Admitedly I dont have sources nor benchmarks and never did. But its obvious it at least invalidates author's point in the sense that benchmarks gota be done in real life programs.
If you use them as a single-linked free list they are faster than a vector since you only need to fetch a cache line for the object rather than a cacheline for the object and one for the vector storing free objects.
When performance needs to be maximized, games switch to entity component systems and switch from arrays-of-structs to structs-of-arrays. This enables processing all objects as a vector, linearly from start to end, and often without needing to fetch any irrelevant bytes that aren't processed in a given pass. This sometimes also helps utilize SIMD for data spanning more than one entity, which you can't do when using linked lists.
From 2012. std::deque does very well.
Suspect the difference is fairly anaemic.
Usually if you're choosing data structures, you pick a "good enough choice," (any of the three).
Or, if it matters, you pull out your profiler and pick the "exact" right one.
Or, perhaps, this is saying (again) that one should code then tune? Pick data structures that facilitate the design you’re trying for rather than for theoretical elegance? Chips are cheap while developers are not, and having a cleaner, saner design is a win. Unless your software price per core is so high that people won’t license more.
It may use less power as it is spending more time stalled, waiting for memory. But it could be still using as much time as the OS scheduler is willing to give it.
For some simple algorithms which need adjacency information, that’s everything needed. For instance, to compute per-vertex normals, nothing else is required, create an std::vector for the per-vertex accumulators, and iterate over the triangles.
For complicated algorithms which need adjacency information, I build special indices over the same data. To find triangles connected to specific triangle, a hash map with uint64_t keys (two sorted uint32_t vertex IDs in the lower/upper half of the integer) and a structure of two uint32_t values (triangle IDs, good meshes are guaranteed to have exactly 2 triangles for each edge, with opposite winding directions). To find triangles by vertex, a multimap from uint32_t vertex to uint32_t triangle.
For algorithms which need to modify these meshes, sometimes I generate new meshes instead of modifying old ones. Other times I replace erased elements with special values (like UINT_MAX for integer indices), append new elements to the end of the vectors, and when the algorithm is complete I re-index the mesh while removing unused vertices/triangles.
I believe that if someone tried to talk about topology while using Rust as a language for sample code, he/she would use some other representation, because a soup of pointers is a PITA in Rust. It is easier to claim that we will be using a connectivity matrix, or a Vec of edges, and to explain how it works, than to juggle with pointers.
However, in my limited experience with such things I have always found myself needing both walking around and a big-picture list of items. Thus I have always implemented such things as a list of elements and storing indexes rather than pointers.
Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been. Some instructions take more cycles than others.
Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes.
Etc, etc. An algorithm's complexity is loosely correlated with its performance, but the two are not identical.
Yes this loop is fast now with my 1000 items, but what if the input grows to 100000 or more?
Keeping it in mind can also help you avoid accidentally writing O(n^2) loops or worse. More than once I've been unsure about the complexity of a library call, so I check the code and it's say O(n) rather than O(1), potentially turning my own O(n) into a O(n^2).
Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior.
>Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes.
This is definitely something to keep in mind when analyzing algorithms, but that does not imply asymptotic complexity is not useful when analyzing performance. There are other measures (e.g. how an algorithm performs on a random small input, or maybe your domain is restricted somewhat) and sometimes those measures areore useful than big O, but big O remains useful, it just is not the end all be all.
This assumption is demonstrably broken if the first multiplication is a cache miss but the other multiplications then aren't -- an easy example is when the other two multiplications have data on the same cache line as the first multiplication's data.
[1] https://isocpp.org/blog/2014/12/efficiency-with-algorithms-p...
For example you could count only non-cached memory accesses on a particular model cpu. See "Idealized Cache Model" from https://en.m.wikipedia.org/wiki/Cache-oblivious_algorithm for example.
This is part of algorithms analysis that a lot of developers skip: these are just tools, there's many models available to use with them, or if you want to, just use wall-clock, with all of the pain that comes with that.
Everyone seems to forget this. It's more a measure of how an algorithm will scale rather than performance.
e.g. an O(n) algorithm will most likely outperform an O(n^2) algorithm, but two different O(n) algorithms can still perform quite differently.
But you're right, it's meant for comparing scaling.
https://github.com/sio2project/sio2jail/blob/master/src/perf...
No, it only assumes that there is a constant factor between the fastest and slowest "operations". It does not matter that one instruction can take a thousand times more cycles than another, if you have n² fast instructions and n slow ones, the running time will still be dominated by the n² fast ones for large n.
> Big-O assumes that only asymptotic behavior matters.
Yes, and this is the only simplification that it does.
As a result k*N can actually be bigger than N^2 when in fact N isn't "an integer" in a mathematical sense but merely a 32-bit machine integer, for example - simply by k being more than 4 billion in that case.
If you're determined to throw out any concepts which technically only apply to theoretical computers with unbounded memory, then go all the way. Your actual physical computer can trivially iterate through all of its possible states in a fixed amount of time. The halting problem is trivially solvable for all programs that your actual physical computer can execute. Your actual physical computer isn't even Turing complete.
Nope. You're in an imaginary world again. This universe will cease to support computation a long time before it would be possible for the computer to try all possible states.
Yes, for the purposes of Big O, we define operations such that they aren't simply 1:1 instructions to the hardware, but they should be basic commands offered by your programming language.
If the basic commands in your language are taking extremely high bounded amounts of time, that's a sign your programming language is extremely poorly optimized, not that Big O isn't useful.
Sure, you can choose a large constant such that numerically it is equal to or smaller than O(n^2) for a given n, but as you vary n then O(1) should approximate a flat `y=N` line, while O(n^2) should approximate a parabola and would result in values larger and smaller than N as you vary it.
This is a big misconception about "Big-O". It does not "assume" anything. It's just not what people think it is.
It's an asymptotic upper bound on counting something. In sorting algorithms you count the number of comparisons expressed as a function of collection size. In collection insertion algorithms on some underlying data structure, it's counting some not-very-clearly-defined atomic operations that are being executed when inserting an element.
Where the assumptions come from is if you start using the notation to give performance comparisons and also start assuming things about Big-O that are just not true. But that has nothing to do with "Big-O".
There is a family of symbols, called the Landau symbols, of which Big-O is only one. There is a lot of misuse of the symbol and in many cases what people actually mean is Theta(N) or Omega(N).
"People who believe in X are wrong because A, B, C."
"No, X is actually right, because if you know about these obscure parts of X-theory which laypersons never hear about, you will see that it addresses A, B and C."
Of course, both these comments are right, because in addition to the fact that X-theory does in fullness address those issues, few people know how it does.
Also probably a part of a course many people snooze through.
The courses that introduce big-O are often the weeder courses, they don't aim to education, they aim to flunk out the people that might be hard to teach so that CS departments can gate keep.
When you have top CS researchers having to give talks to remind people that layout matters more than instruction selection, the CS as a whole has focused on the wrong things.
https://www.youtube.com/watch?v=7g1Acy5eGbE
Figure how to build people up, not tear them down.
That is an often re-iterated conspiracy theory. In practice nothing could be further from the truth. Professors have nothing to gain from weeding out students. They have to gain by ensuring a certain standard. By the way it is also better for a student to encounter the difficult parts of their subject as early as possible, so that they can decide whether they have chosen their subject wisely. On the other hand, not failing students on fundamentals means complicating advanced subjects even further --- for everybody.
At some point in life students have to accept that neither their time in university nor their time in the industry will consist only of externally motivating tiny bites of tasks that are awesome. In order to understand complicated matters, you have to put in the work. Spending hours in the gym is also quite boring, but most people accepts that it is necessary for certain results.
I've been involved with undergrad teaching in a University. And the amount of time we spend on finding ways to teach and test better was way more than I could have expected as a student myself. On the other hand I couldn't have imagined the arrogance and sometimes stupidity of first year student claiming to know already what they will need in there career and what not.
So much to unpack there. Some rhetorical hyperbole, other false dichotomy and we are both arguing from anecdote.
Weeder courses exist and as you even admit, they aren't solely meant to educate. That is the point. Anything that is designed to test students resolve as well as not waste professors time is not designed to educate, it is designed to reduce the size and shape of the student population. I applaud that CS departments are adding more and more courses for non-majors. But lets look at the syllabus for a 10 week quarter for the first UW CS course, Foundations of Computing [1] which also expects the students to layout their homework (proofs) in LaTex. Jesus. This is mostly a hazing ritual. In my 3 minute sampling of Reddit, most CS students rank 311 as the hardest course in the major and it is the first. [2]
> At some point in life students have to accept that neither their time in university nor their time in the industry will consist only of externally motivating tiny bites of tasks that are awesome.
I never said anything of the sort, you putting words in my mouth.
[1] https://courses.cs.washington.edu/courses/cse311/21sp/
[2] https://www.reddit.com/r/udub/comments/cdb5kp/cse_311_cse_33...
Your argument might make more sense if 311 were the first CS course, but it's not. You can easily verify that by looking at the course listings which reveals it has a prereq, CSE143, which has a prereq of CSE142. So short of skipping those, it's the third course at the earliest.
https://www.cs.washington.edu/education/courses
311 is the first course of the major and is also by the sample of folks in the reddit discussion also the hardest, covering the most advanced material in the shortest amount of time. It is a weeder course for the major. The 100 level classes are open to everyone.
Nailed it. My frustration is that those words are rarely mentioned, and that atomic isn’t really atomic except in the context of the problem statement and solution.
In my experience, we all spend more of our time dealing with what people think things are than what they really are. Even if reality tends to pop its head up now and then.
I think the root comment is correctly describing "how people talk about Big-O" - even though, as you point out, they are mischaracterizing it.
I find this is often a more vexing problem than the underlying performance questions: how do we find good ways to talk about the use (and mis-use) of analysis in a way that produces good tools?
Similarly “competitive programming”, A&D and coding puzzles which I find fun but only tangentially useful, will typically completely neglect engineering constraints. The shape, size frequency and variations of data can almost always be at least estimated in the real world, or simply assumed.
Real assessments of performance go far beyond the depth and breadth of expertise that most students get in undergrad - so it's a fools errand to try and junior engineers about concepts like that. Big-O has a lot of flaws but I get why it seems so useful to all the groups that use it.
It’s really just about making decent estimates, testing and some profiling. There’s of course potential mastery here, specific knowledge and tooling, you can dig down almost indefinitely, but the basic motions can be taught with simple projects. You don’t need Google scale to encounter performance problems and potential improvements.
I know this because I work on small scale things, and had to learn this kind of thing on the job. I can imagine a ton of educational projects that teach this.
Complexity analysis and A&D are very useful when you need them, but they are just two of several tools.
Similarly the term we use is often "N" and "N" could mean anything, and in practice you need to know what "N" you are optimizing for/against. That's where the engineering constraints fit in. It doesn't matter of you pick an algorithm with good Big-O in time (where n represents number of operations, for instance) if your are constrained in space (memory size; cache size; cache locality) and vice versa. Big O notation is an approximation with respect to some function and that n among a selection of choices of different functions/different "ns", that complexity function itself can vary a lot based on your trade-offs. (Which also gets back into Big O is only one such tool, as well. Sometimes you really need to know worst case "Omega notation" and not really Big O notation, if your constraints include lots of worst case things. And so forth.)
Estimation isn't "destiny": know what you are estimating, why you are estimating it, and with respect to what constraints you are estimating it. Big O notation is "back of the envelope math" for algorithms. It serves some great uses, especially in practice, but you need to know what you are estimating and why.
Typically a program is evaluated in terms of something like the "Random-access machine" where every instruction has a constant cost. There's a bunch of additional assumptions hidden in this machine model!
In the real world, the speed of light and the Bekenstein bound conspire to make constant-time random-access to a memory of unlimited size impossible. In practice, a random memory access takes O(sqrt(N)) time. We like to pretend that there's a constant worst-case access time, but that only works out because our machines have a limited amount of memory -- it's not really appropriate for an asymptotic analysis.
So complexity theory based on the "Random-access machine" is just measuring a theoretical instruction count that doesn't necessarily correspond to the real-world run-time. There's other models that get closer, e.g. the "cache-oblivious model".
In its own constructed universe, orders of complexity doesn't obey basic physics. Imagine I'm trying to sort a billion unique books alphabetically by content. In order for the books to be unique, m > logn. For many big problems logn < m < sqrt(n) but for a lot of the rest n < m on day one, and stays that way for quite some time. For large objects, an algorithm that avoids comparisons can be faster with real data even if its complexity is n(logn)^2.
Where we fuck up is pretending that mathematical operations are O(1) when they are O(logn) on a good day and O(n) on a bad one. + and - are constant if the numbers fit into a single integer. [] is only constant for n < L1 cache size, and even then only if no other tasks are happening. And as I've just described, < and == are not constant time either. We need better math for these sorts of things.
Initially, prefer to task CPU over memory allocation. Crufty allocation generally will always have a real negative impact felt by the end-user. A low memory footprint is always a win, while going for a (theoretical) fast running time may be effort wasted.
1. A small computation that you perform many, many times.
2. A very, very large computation.
For #2, big-O can still generally tell most of the story. (Example: 100 insertions in the middle of a list with a billion elements.) For #1, big-O almost irrelevant, and benchmarking is key. (Example: a billion insertions into the middle of length-100 lists.) So knowing which situation you're in is important.
As you go up the scale the Big-O values are almost always dominant. It's very rare to see a situation where you would choose the algorithm with the higher value.
However, when two algorithms have the same Big-O there can still be a big difference in performance, especially in the face of how a cache influences things.
(There are cases where the memory accesses are so important that they can make the "bad" approach better. A while back I did some time testing and found the Sieve of Eratosthenes inferior to brute force because of all the cache misses.)
But if you are starting out with nothing built and only have time to write one, you can't really go wrong by going with the one with the better Big O. If it's the same, coin toss I guess. :)
Well I did have a CS teacher that said that O(log n) is basically O(1) because in practice, n usually will fit it in a 32bit and log n then is 32 at most :D
It might have been said in jest in part but really it's not that far fetched.
Big-O is a statement about the limit of a function as the input goes to infinity. f(x) = O( g(x) ) is the statement that the limit (f/g)(x) exists as x goes to infinity. f(x) = o( g(x) ) is the stronger statement that the same limit exists and is equal to zero.
You'll get a similar reaction to if you try to show people who won money on crypto art or tesla that they are lucky early members of a pyramid scheme.
And the usual argument is, "well, it's understood..." which is a terrible argument because the whole notion of ignoring constant factor C is that it's supposed to go to the noise floor as n approaches infinity. So if you're going to claim that we didn't mean n approaches infinity, we meant "n fits into a CPU word and the data set fits into memory" then you're trying to have it both ways and that's pure nonsense.
If you want a better overview of algorithms for practical reasons, you can use o(), O(), average case and ammortised complexity, or just provide histograms of runtimes for algorithms you're comparing.
- Use blocks of multiple elements per actual list element that fit your cache line size. Blocks also have the benefit of potentially allowing SIMD processing of your data.
- Allocate blocks out of a vector or some other structure that reduces your actual number of allocation calls. Maintain a free list threaded through this vector.
- Tombstone list elements in their blocks on removal instead of repacking the entire list. This allows for fast deletions and fast insertions at specific locations (in that you can always insert a new block between existing blocks containing only a single element or get lucky and re-use a tombstoned slot).
Note that most of these optimizations trade some memory efficiency for speed. This is a common theme in optimization. Using more memory, but using it more intelligently such that you are potentially accessing less of it and accessing it sequentially where possible.
Immutable, singly linked lists (aka cons lists) are a different beast entirely, and don't benchmark well in languages with heap fragmentation issues.
Also it would be possible to implement such an approach in a C++ list container where you don't need boxing (the content type is known).
Microsoft has solved most of these issues on Windows, couple decades ago. The feature was introduced in WinXP, and enabled by default in Vista and all newer versions: https://docs.microsoft.com/en-us/windows/win32/memory/low-fr...
I’m not an expert in Linux but I would be surprised if Linux didn’t do the same. RAM costs have plummeted. The losses from RAM usage overhead of LFH became insignificant compared to the issues caused by the fragmentation.
But yes, the default glibc allocator does have dedicated areas for specific sizes of allocation:
> The normal bins are divided into "small" bins, where each chunk is the same size, and "large" bins, where chunks are a range of sizes[1]
But fixing heap fragmentation doesn't make linked lists suddenly fast. You still have your cache bloated with the overhead bytes needed for allocation. List elements can still be allocated non-contiguously, giving the prefetcher a bad day.
[1]: https://sourceware.org/glibc/wiki/MallocInternals#Arenas_and...
For real world performance, benchmarking is the key. Computers are very complex beasts and there are a lot of potential speedups or slowdowns you might never think of - memory bank order, thermal throttling and compiler optimizability can drastically change the results, just to name a few. Computational complexity is totally fine as an angle to find new possible optimizations, but in the end, you need to compare it to the other approaches and see what actually works.
[0] https://news.ycombinator.com/item?id=21743424
> to find the square root of an int:
so the value can't exceed INT_MAX :)
Overall, I know the two algorithms aren't perfect, but they're a simple minimal example to show the difference between complexity and runtime.
Only it's not enough. When you benchmark an O(N^2) algo may seem fine but then three years later the data has changed and is now an order of magnitude larger. So you need not only know your data, you also need to spend time thinking about how large it can become.
So you start with benchmarking your current data. You still need to always think about how your data will grow.
True. But I do highly recommend watching Ben Deane's 2015 talk about testing Battle.net. In it he briefly touches upon benchmarks and estimating algorithmic complexity. It's somewhat difficult to suss-out the details of it. But the short version is basically to run the benchmark with a few different sizes and then estimate the complexity growth from that.
https://youtu.be/OPoZWnYIcP4?t=1035
The GTA Online loading screen bug is a recent example of this problem, with its in-game purchasable items growing larger over time: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
> ... you might encounter cases where a quadratic complexity solution is completely fine, until you have a lot of data and then suddenly your code slows to a crawl [0]. That's why we need computational complexity ...
It seems like you're disagreeing only because you pulled out the one quote about benchmarking. But they were just saying that you need benchmarking to bootstrap the meaning of O(...) of an algorithm. That's the point that the original article missed, which is presumably why they described it as key.
If your data changes, and you care about performance, then your data structures and algorithms should be reevaluated.
Functionally, though, I would describe this algorithm as O(N). It's just a straight up linear scan of the problem space. It's unbounded, with a worst case of O(Infinity) and no upper limit on what searched can be, but it's functionally O(N) regardless.
O(1) needs to basically be something like a hash key/pointer to memory address to get the result you're looking for. It will not increase linearly as the problem space increases, whereas your first example increases exactly linearly.
If an algorithm will always take 1 billion years to complete regardless of the input, then it's still O(1).
The behaviour does flatline as n approaches infinity
In the end, it's just not a useful way of modelling the problem.
Floats aren’t real numbers but we treat them like the mathematical object that they model for most purposes.
Of course, being aware of the limits of our models are important, but abusing the tragic finitness of our models to “well actually” someone is generally not helpful.
Mixing real-machine finitude with big-O theory often gives unexpected or unhelpful results. Once in an interview I argued that since hash tables have a finite number of buckets, at large enough scale they really have O(n) worse-case performance. That didn't go over very well. :-)
Furthermore, the author is masking the true cost of an array resize, which often happens in a running system where a finite array is completely full and needs to be resized to append an additional element. This is the scenario where linked lists are most useful.
Resize point is fair but we still options here. A segmented approach for very large collections may also help, with tuning knobs of array size / segment. The smallish top level ds maintaining segment ptrs will be super hot and very likely ever present in L2.
It really all depends on how many items are involved and how the data needs to be accessed and used.
This is a narrow view of the costs of the STL::list container class, not of linked lists in general.
Linked lists are at their best when they are internal storage, meaning the links are part of the class being stored, in order to prevent unnecessary mallocs. STL::list is an external storage container, which automatically compromises some of the potential benefits of a linked list. Linked lists are also best when you don’t malloc to build the list at all, but maintain things already in memory. Linked lists are best used in places where using vectors is impractical or impossible, like the insides of a memory manager.
I don’t feel like timing many inserts using STL::list says a lot about linked lists at all, and what it does say is mostly focusing on the wrong things. Definitely use vector when you can, especially if you’re just comparing container classes.
Also, I only skimmed it, but the article seems to ignore the fact that even for an unbounded/growing array like std::vector, the growth strategy does not free+malloc/realloc on each insertion in practice, as the growth strategy will leave unused capacity for future insertions, and in such cases the cost is just memmove (for simple types at least). Maybe I missed that part, but it seems like an important point worth highlighting.
Right! Yes, that’s part of my point, STL::list isn’t being careful with cache, or with allocations. Really it just rarely makes sense to even compare STL::list to STL::vector as if they’re otherwise equal choice. Usually the choice is (or should be) driven by constraints, not by which has a slight perf edge, right? Inside a memory manager, use of a vector isn’t usually considered a choice. Maybe it’s possible to build a free page vector, but I think isn’t common, and people usually pay the costs of pointer chasing on the free list because there aren’t practical alternatives.
> the <vector> growth strategy does not free+malloc/reallocate on each insertion
Yeah very good point. Does STL::list do the same for the container of pointers? I don’t even know, but maybe it can’t, and maybe the primary perf advantage of STL::vector over STL::list is due to vector’s amortized mallocs?
I think the list vs vector comparison is fair, as most people are taught to “just use the standard library, don’t be a hero, don’t commit a NIH crime”. I have done this myself at times, but in fairness, mostly when discussing adaptations of existing code, where there were bigger structural issues. And it cannot be repeated enough, that vector is far better than list, even at prepends or random insertions, for a surprisingly large number of elements (it was at least thousands of int32-s when I checked it about a decade ago). Typically the justification for a list is that the workload is prepend/random insert heavy, but in my experience there is more often than not a bound on the size that strongly favors vector.
No, if you want a list with amortized malloc, that's a std::deque
Back then, there weren't any list like data structures backed by arrays, like List from C# and Vector from C++.
But learning linked lists was a good thing, we also had to learn about pointers and how memory is layed out, so we also knew that sequential access to memory is faster. Also, learning about stack vs heap, CPU caches, made a big difference in how we wrote programs and how we continued to write programs 25 years later.
So I think I was lucky starting with Pascal and C, continuing with C++ instead of starting with Python or Javascript.
Most of the time it is, but note that ArrayList has to occasionally allocate a new array when the list outgrows the array inside it, then copy the list.
When the list gets huge, that operation of reallocating and copying gets disruptive as it puts a lot of pressure on the cache, memory allocation system, etc.
Though in practice I find that unless you are often deleting elements from the middle, modern CPUs will really prefer copying a huge amount of serial data, so an arraylist may still be faster all around then LinkedLists. (The CPU will recognize you moving values in a given direction and will have the best pipeline it can have)
On the other hand, pointer chasing often isn't as bad as you think it might be. That is, modern allocator/garbage collectors often end up laying out the parts of a linked list in a predictable way such that access is somewhat strided and the fetcher is reasonably efficient at traversing the list.
It kinda really is, though. In addition to cache line locality, serial access also benefits from being speculatable. The CPU can't very effectively speculate past a pointer chase (and on arm little cores it doesn't even try), so those become pipeline stalls.
Even if the pointer happened to be close-ish, it's still going to end up being a stall more often than not.
And an allocator / GC is only going to lay out a linked list in any sort of predictable way if the linked list is built up all at once, in which case a linked list is obviously not the right data structure anyway ;)
Tsk tsk. A critical rule for flame wars that also applies to mere discussions among common folk is that you should avoid using absolute terms, as it gives your opponent an easy opening. Instead, couch your statements in vague and wishy washy terms like 'usually' and 'often'.
This also helps when your opponent produces a valid counterexample - you can petulantly retreat to safer ground while grumbling about how of course there are occasional exceptions and then, if you wish, you can sidetrack the argument into a debate about how often it really happens. From there you can feign boredom and exit, think up a snarky, mic-drop conclusion, etc.
- As taught in Raised on the streets of BBSs and USENET
Senior Architect?
No seriously, once you recognize the components of Rhetorical Combat, you can determine if you are going to have a civilized discussion, or if the parties will weasel their way around for sport or entertainment.
If someone attacks my argumentation with uncharitable takes, my discourse with them is over.
I personally would rather arrive that the truth and be wrong, than win an argument and let the truth escape.
ArrayLists grow by allocating a new buffer whose size is a multiple of the current size. This means that as the buffer size gets bigger, the reallocations become less frequent.
The end result is that appending to an ArrayList has constant time amortized complexity, even though it will periodically do increasingly large copies.
https://en.wikipedia.org/wiki/Amortized_analysis
I bombed an interview once because my interviewers didn't understand amortized analysis and I wasn't able to get them to understand it.
But in case of a linked list that large amount of memory doesn't have to be contigous, and you don't have to perform a lot of copying all at once which kills responsiveness.
True! Though in rare cases where that becomes a problem, you are probably better off doing a hybrid solution where you store the data in a relatively small number of chunks or pages. If you have so much data that you are having trouble getting a contiguous allocation, you probably also can't afford the overhead of an additional pointer for each element, which is what a linked list would give you.
> you don't have to perform a lot of copying all at once which kills responsiveness.
I believe there are ArrayList implementations that distribute the copy across a series of operations to mitigate this, but, yes, latency can be an issue for some use cases. (In general, though, my experience is that people overestimate how long it takes to copy a contiguous block of memory.)
The ArrayList will be a nice flat chunk of memory... of pointers to the data, so you'll have to do a lookup for each element anyway. The LinkedList will have two lookups still, but it's not an order of magnitude anymore. Now it's more of a tradeoff between bit slower reads / bit faster updates.
You maybe want something like a linked array, but it's staggeringly difficult to find a scenario where a Java LinkedList or c++ std::list is ever the optimal choice. You should pretty much always start with an ArrayList or std::vector and go from there if/when it ever turns out to be a hotspot in benchmarks or profiling