Protip: Compute the size before you allocate

I've lost track of how many times I've seen code that uses a dynamically-expanding array when it could've easily calculated the correct size and allocated exactly the right amount. See: string appending, tokenising, just about everything written in JavaScript, etc.

No wonder software is so slow and bloated...

>>15
Trees are even worse when you need to process the data sequentially.

>>17-22
I know it's "amortised constant time", but that doesn't say anything about the constant.

Suppose each resize or allocate costs 20 clock cycles (which is extremely low), and a resize costs 1 cycle for each array element copied. You're adding 128 elements, one at a time, to a resizeable array that starts out at 1 element and doubles in size afterwards. Adding each element takes 1 clock cycle. Counting the elements ahead of time takes 10 clock cycles.

Resizing:
1 + 20 + 2 + 20 + 4 + 20 + 8 + 20 + 16 + 20 + 32 + 20 + 64 + 20 = 127 + 140 = 267

Counting and allocating: 30

>>21
This too.

If you can figure out how big it's going to get ahead of time, then do that; but if it's data coming off a stream or something else, then it can't be helped.