Comment by justusw | Hacker News Reader

Comment by justusw | Hacker News Reader

This article points out a few right things, but also skips over the wrong parts.

Namely, the amortised time complexity of dynamic lists.

Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an ArrayList will be in O(1) given enough insert operations.

Essentially, you over-allocate in order to save time. You're trading time complexity for space complexity.

A really good explanation on amortised analysis can be found here on Wikipedia, which explicitly treats ArrayList:

https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr...

As always, a look into the source code of your language of choice helps. In Python, a list object over-allocates using a very peculiar, but finely tuned formula: https://github.com/python/cpython/blob/09dc3ec1713c677f71ba7...

The nuance you're missing here is that the author is always inserting at the front of the arraylist. So even though the list grows dynamically, it still needs to move every value one spot over.

e.g. arraylist: [0][1][2][3][ ]

Even though there is space left in the array, we still need to move all the values one index to the right to be able to insert at the front, which takes O(n) time. In contrast, inserting at the front of a linked list is simply a matter of moving pointers and therefore constant time.

Can't you just imagine it is reversed, where the_array[num_things-1] is the first ?

Yes, then it would be a discussion about append performance instead of insert performance. Might be handy to do if you know that all the changes to an array will be inserts at the front, then you can just write the array in reverse and also read in reverse.

But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data.

The OP is discussing inserts at the start just because it is the worst-case scenario for arrays, then a positive result will still be true if some of the inserts are in the midddle or even near the end.

Afaik, if you read in reverse, then you will miss cache optimization since it only works forward.

Intel cache prediction will detect both forward, backward, and some odd movement patterns. It has not been only forward prediction for a very long time.

Do you know how the popular ARM based chips fare in comparison?

> But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data.

This is true if you already have a reference to the middle of the list. If you don't (say, because you want to insert while preserving the fact that the list is sorted), then inserting into a linked list is O(n) just like the array is.

Memory reads and memory writes are not the same. Linked list insert in the middle needs to do only O(1) writes. But because linked lists preclude memory prefetch, they should not be used these days.

Stay strong.

The awful thing about writing benchmarks is that if you don't give the worst case example, people give you shit for coming up with metrics that say whatever you want to say.

If you give metrics for the case that should be worst for your argument, people give you shit about using such a stupid example.

There's no way to avoid someone giving you grief no matter what you do.

Um, give both?

Then both groups agree that your examples are terrible ;)

Some languages, such as Perl, start the array in the middle to avoid exactly this situation.

This point should be understood very clearly: The article isn't wrong that an ArrayList has O(n) for a single insertion. However, the article misses that amortized analysis shows that the same structure can be made to have O(n) for n insertions as well. In effect, ArrayLists can be thought to have O(1) insertion time in practice meaning that all you are comparing are the differences in constants between the two structures.

I think the biggest takeaway from this isn't that big-O can fool you (which it very well can), but that misunderstanding analysis can lead to poor decisions.

A better argument for big-O fooling you can be found using Quicksort and any proper O(n Log(n)) sorting algorithm. Quicksort will outperform most in practical cases, but is technically O(n^2) in the worst case (average case O(n Log(n)).

Isn't that an argument for average case performance being a better predictor of average cases than worst case performance?

Well except quick sorts worst case is very easy to hit. Hence why you don't use it in CS101 form.

Amortising allocation won't help the article's example, which is insertion at the front, unless you have a quite unorthodox implementation of your array list (e.g. implementing something like a deque using a circular buffer).

The Python growth allocation doesn't look peculiar to me. It's just calculating exponential growth without floating point operations. Whether you over-allocate in 50%, 25%, 12.5%, or whatever proportional increments (all trivial to calculate using bit shifts), they are all enough to make dynamic growth of the array O(n) over time. Any exponential growth will do. If anything, Python's list growth looks to me like it trades off slightly too much time to save space. Actual results will vary depending on realloc implementation etc of course.

Would be interesting to see the performance of Python's overallocation algo compared to a simpler one like Lua's, which just overallocates to the next power of 2 (so if you have a list with 4 items and want to add, it jumps to 8, then 16, then 32). I can't imagine the bitwise operations adding up to that much time added in Python, but Lua needs to increase size much less the larger the list (after 7 iterations Lua has room for 64 items, Python only 46 according to that link). Interesting choices, wonder which optimizes for what.

Would love to get Ierusalimschy and van Rossum in a room together and let them talk it out.

Even with only 25% growth per realloc, you hit logarithmic overhead (only with a higher k because more actual copying.)

I think what you are saying is only true if you insert at the end of the ArrayList, (or at the beginning if you have one which leaves open space at either end)

If you insert into arbitrary positions, or the front of these particular array lists, it will be O(n) even ignoring the growth issue, because every element has to be copied over 1 spot.

Insertion at the head of a dynamic list avoids the issue of amortized complexity, though, since every element in the array needs to be copied on every insert, whether a new array needed to be allocated or not. Unless you're concerned about the time complexity of the memory allocator?

Reply on news.ycombinator.com