Poor performance scaling with allocation size with vsg::IntrusiveAllocator

[AnyOldName3]

Describe the bug
While vsg::IntrusiveAllocator is comparable to std::malloc/operator new for really small allocations, for larger ones, even if they're still pretty small, it's much slower.

Running a profiler shows nearly all the CPU time is spent in IntrusiveAllocator::MemoryBlock::allocate checking the status of the slot at memory[freePosition] here https://github.com/vsg-dev/VulkanSceneGraph/blob/master/src/vsg/core/IntrusiveAllocator.cpp#L135 (which is probably really the fact that it's got to load memory[freePosition].status into a register).

The stair stepping in the graph happens every eight bytes. I'm running this on a CPU documented as having 64-byte L1 cache lines, so that makes the allocator's alignment the likely source of that number.

To Reproduce

Here's a nice simple test app:

#include <vsg/all.h>

#include <chrono>
#include <iostream>

int main(int argc, char** argv)
{
    // set up defaults and read command line arguments to override them
    vsg::CommandLine arguments(&argc, argv);

    // Allocaotor related command line settings
    size_t size = 1;
    arguments.read("--size", size);
    size_t count = 100000000;
    arguments.read("--count", count);
    bool malloc = arguments.read("--malloc");
    bool operatorNew = arguments.read("--new");

    if (malloc && operatorNew)
    {
        std::cerr << "Cannot test malloc and operator new at the same time.";
        return 1;
    }

    auto start = vsg::clock::now();
    if (malloc)
    {
        for (size_t i = 0; i < count; ++i)
            std::malloc(size);
    }
    else if (operatorNew)
    {
        for (size_t i = 0; i < count; ++i)
            operator new(size);
    }
    else
    {
        for (size_t i = 0; i < count; ++i)
            vsg::Allocator::instance()->allocate(size);
    }
    auto end = vsg::clock::now();

    double duration = std::chrono::duration<double, std::chrono::milliseconds::period>(end - start).count();
    std::string allocator = malloc ? "malloc" : (operatorNew ? "operator new" : "vsg::Allocator");
    std::cout << "It took " << duration << " ms to allocate " << count << " " << size << "-byte objects with " << allocator << "." << std::endl;
}

Expected behavior
It not taking much longer to do small allocations than tiny allocations.

Screenshots
Here's a graph of allocation size vs time in milliseconds for a hundred million allocations of that size:

Desktop (please complete the following information):

• OS: Windows, but I'd be very surprised if that matters
• Browser: I think this probably shouldn't be a field in the issue template.
• Version: All the relevant files are identical to the tip of master.

Additional context
This might not have mattered most of the time - if the cost was just that it was loading memory into L1 when allocating it, then as most of the time, memory is written to as soon as it's allocated, there'd be activity for the same memory range anyway. To confirm this one way or the other, I altered the test to call std::memset on the memory returned by each allocation. This made it a little slower, so the memset call wasn't optimised out, but mallocing and memsetting loads of memory was still far cheaper than doing the same with vsg::IntrusiveAllocator, so that's a strong indication that this is a real problem.

[robertosfield]

The VSG is a scene graph, it's optimized for high performance and stable frame rates when rendering. As such the VSG isn't a memory allocation performance API, it's memory usage performance API. Comparing allocation performance is isn't the type of performance metrics that are usually critical for real-time graphics application.

Now, if you have a test case which illustrations a performance issue in the context of a running graphics application rather than a standalone pure memory allocation performance test then you'll have my attention and it'll be worthy of spending our time trying to optimize.

As things stand I don't know if you're just kicking tyres for the sake of it, or actually trying to chase down a real problem.

[AnyOldName3]

The gist is that I was checking the potential performance impacts of another change that meant some allocations were a little larger, but the advantage of ref_ptr over shared_ptr when it came to scengraph traversals due to the pointer object being half as big was still maintained without having to lose some of the other performance benefits STL smart pointers have (like being able to use a custom allocator and being able to lock a weak_ptr without locking a mutex, which we've seen have significant costs in real applications). That meant that I was measuring times with the vsggroups traversal timing example, and I noticed that while the actual traversal times were unaffected, the application's runtime increased significantly due to the effect I've reported here.

That does mean that I'm several proxies for a real-world application deep before I'm getting a nice graph like the one above, but vsggroups is one of your performance testing apps, and it was testing that where I first noticed this. Ideally, they wouldn't be sensitive to changes that should make no meaningful difference to apps.

With a bit more testing, though, I've noticed something potentially interesting. The performance gap between vsg::IntrusiveAllocator seems to be very dependent on the number of allocations that have already happened, and the number where that starts making a difference is dependent on the allocation size, too, but not exactly on the total size already allocated. It takes around $2^{24}$ 128-byte allocations (i.e. 2 GiB) for malloc to be twice as fast as the VSG allocator, whereas to get the same speed ratio with 65536-byte allocations, it needs 2048 of them, which is just 128 MiB. It's pretty unrealistic to expect a real app to allocate multiple gigabytes of tiny things, but wanting to load 2048 128x128 RGBA textures in a hurry isn't quite so ludicrous. Either way, this means that this is less likely to be a meaningful problem for real-world applications than I initially thought.

[AnyOldName3]

Thinking about it some more, it's even less of a problem with the vsggroups example than I thought, as there's no reason to test traversal time with more levels (and therefore more allocations) than it defaults to as it already exceeds any modern CPU's last-level cache size (even AMD's vcache parts) with the default number of levels, so it already covers the situation it's designed to model without changing that parameter. When the default number of levels are used, it doesn't reach the threshold where this slow-allocation behaviour kicks in, so it can't skew the results.