undefined | Better HN

0 pointsmunificent4y ago0 comments

> It's not great to have to double your memory usage while you reallocate your array.

You don't have to use a growth factor of 2. Any constant multiple of the current size will give you amortized constant complexity.

> On more limited devices (see games consoles or mobile devices) you'll end up fragmenting your memory pretty quickly if you do that too often and the next time you try to increase your array you may not have a contiguous enough block to allocate the larger array.

If fragmentation is a concern, you can pre-allocate a fixed capacity. Or you can use a small-block allocator that avoids arbitrary fragmentation at some relatively minor cost in wasted space.

> Why copy these objects and incur that cost if you can choose a datastructure that meets their requirements without this behaviour.

We have an intuition that moving stuff around in memory is slow, but copying a big contiguous block of memory is quite faster on most CPUs. The cost of doing that is likely to be lower than the cost of cache misses by using some non-contiguous collection like a linked list.

> as its really not suited to the constraints of games and the systems they run on.

For what it's worth, I was a senior software engineer at EA and shipped games on the DS, NGC, PS2, Xbox, X360, and PC.

0 comments

superrad4y ago

When you reallocate your array you will in memory have your old array and your new larger array while you move your data over. At the very least you're using 2x and the extra memory for your expansion.

For your other points if you'd mentioned them in the interview you'd probably have been better received. Copying is really only that fast for POD objects (your objects copy constructors may need to do reallocation themselves or worse) so if you're suggesting a general solution you should be aware of that (or at least mention move constructors if they were available at the time) .

I would be surprised if any of the games you worked on actually shipped with an amortised resize of dynamic arrays (at least not for anything that didn't matter in the first place) so I don't know why you'd suggest it as a general solution in a game dev context.

btilly4y ago

A linked list needs a pointer for every piece of data. If the data is small, this will also be a 2-fold memory impact. Plus impacts on cache coherency.

hnfong4y ago

A typical C implementation would be using realloc():

The realloc() function tries to change the size of the allocation pointed to by ptr to size, and returns ptr. If there is not enough room to enlarge the memory allocation pointed to by ptr, realloc() creates a new allocation, copies as much of the old data pointed to by ptr as will fit to the new allocation, frees the old allocation, and returns a pointer to the allocated memory.

Worst case definitely 2x memory. But not necessarily always.

j / k navigate · click thread line to collapse