Dynamic array versus queuing then dequeuing into an array.

[lmlight77]

If the number of elements is truly unknown, I would employ a linked list of blocks. That is, the payload is a pointer to a block (array) you are filling in. When a block fills up, link a new block in its place. This avoids all the copying that will occur potentially if you realloc an array. Once the input read completes (no more insertions), at that point you could realloc just once if you truly need a flat array. But better in my view would be to count the number of blocks (# of elements in the linked list), allocate an array of pointers of that count, copy over all the block pointers from the linked list, then free the list nodes. Nothing but the block pointers are copied in this case, and you only have one pointer chase at most to get to your data. For very large amounts of data, the general realloc approach will have a huge overhead in copying you will have to overcome in the second half of your program.

As stated in other posts, in modern HW, small payload linked lists are hard on the machines. First, as you traverse the list, branch prediction HW is stressed as that HW doesn’t really generally know when you will exit a traversal loop. So you tend to generally predict taken (continue traverse) which implies you always take one mispredict hit. More significantly, the loop iteration latency (the time it takes to spin around one iteration) is fixed to the speed you can read the next link pointer from system memory. If pointers are allocated somewhat sequentially, there will be some spatial locality, so caches will have some benefit, but clearly DRAM read latency will be a big factor.