ensureAllocatedSize bug?


#1

I got into a discussion with the folks in ##c++-general on IRC and a couple of the smart folks in there noticed that ArrayAllocationBase::ensureAllocatedSize does some weird rounding if you pass it a number other than 1:

    void ensureAllocatedSize (int minNumElements)
    {
        if (minNumElements > numAllocated)
            setAllocatedSize ((minNumElements + minNumElements / 2 + 8) & ~7);

        jassert (numAllocated <= 0 || elements != nullptr);
    }

passing it 99 spits out 152.
What’s the expected behavior supposed to be? should it allocate 104, the next multiple of 8 that is above 99? it seems kinda wasteful if you’re asking for space for 99 things, and it makes space for 152, no?


#2

If you’re certain there will be exactly 99 items in that juce::Array, then sure allocating 104 items would be enough. But if you keep adding items, ArrayAllocationBase::ensureAllocatedSize will have to reallocate memory and copy all items (which is a very costly operation) every 8 items. That’s really wasteful.

Dynamically allocated arrays (such as juce::Array and std::vector) usually use a growth rate of 1.5 (plus a constant in the case of ArrayAllocationBase::ensureAllocatedSize). You can read more about growth rate of dynamically allocated arrays here: https://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array


#3

You should reserve the word “bug” for something that’s actually a mistake, not for things that you don’t understand :slight_smile:

Yep, growing at 1.5x is generally seen as a sensible rate for growing a container.

And although there are lots of different types of allocator, most of them deal with blocks that are rounded to a granularity of at least 16 bytes, so there’s no point in asking for a size smaller than that, which would leave some wasted bytes at the end. I guess this could be a bit smarter and take into account the size of the object itself rather than just using a multiple of 8 of them, but it probably doesn’t make much difference.