How slow push! is?

question
faq

#1

suppose you need to build an array of unknown size. elements come in one by one, then an eof comes. the question is, how bad push!() is from performance viewpoint? the performant way to do this is to preallocate the array to a reasonable size, and grow it by chunks as needed, all while keeping track of the actual item count. can i expect Julia to kinda do this for me in the background with push!() or the array will be physically reallocated every time?


#2

The vector is grown by a constant factor every time.


#3

Given that the question doesn’t specify the scale of speed, it’s worthy to point out that push!, although being much slower than preallocation, is still considerably faster than any I/O read. If the eof is expected e.g. from a file in the hard disk, I wouldn’t bother optimizing the RAM side of the array building process.


#4

push! is reasonably fast. It grows the array allocation geometrically as needed (currently by a factor of 2). As a result, pushing n elements one at a time to an empty array has O(n) cost and allocates O(n) storage total — only O(log n) physical re-allocations are performed.

I feel like this should be documented in the help for push!, since it seems to be a FAQ.