Comment by superrad | Hacker News Reader

Comment by superrad | Hacker News Reader

Parent Full thread

It's not great to have to double your memory usage while you reallocate your array. 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.

There's also the cost of copying objects especially if you don't know if the objects you're copying from your original array to the resized array have an overloaded copy constructor. Why copy these objects and incur that cost if you can choose a datastructure that meets their requirements without this behaviour.

If you're holding pointers to these elements elsewhere re-allocating invalids those, and yes you probably shouldn't do that but games generally are trying to get the most performance from fixed hardware so shortcuts this will be taken, its a least something to talk about in the interview.

I can see why they were confused by your answer as its really not suited to the constraints of games and the systems they run on.

> 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.

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.

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.

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.

> It's not great to have to double your memory usage while you reallocate your array. 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.

That doesn't smell right to me, assuming you're talking about userspace applications on newer hardware. aarch64 supports at least 39-bit virtual addresses [1] and x86-64 supports at least 48-bit virtual addresses [2]. Have you actually had allocations fail on these systems due to virtual address space fragmentation?

Certainly this is something to consider when dealing with low-RAM devices with no MMU or on 32-bit, but the former hasn't applied to the device categories you mentioned in probably 20 years, and in 2021 the latter is at least the exception rather than the rule.

[1] https://www.kernel.org/doc/html/v5.8/arm64/memory.html

[2] https://en.wikipedia.org/wiki/X86-64#Virtual_address_space_d...

Reply on news.ycombinator.com