Are noncontiguous arrays performant?

I revolve some of the most central parts of my codebase (an ECS engine) around the type of data structure you described, though it uses smaller contiguous blocks (more like 4 kilobytes instead of 4 megabytes).

It uses a double free list to achieve constant-time insertions and removals with one free list for free blocks that are ready to be inserted to (blocks which aren't full) and a sub-free list inside the block for indices in that block ready to be reclaimed upon insertion.

I'll cover the pros and cons of this structure. Let's start with some cons because there are a number of them:

Cons

1. It takes about 4 times longer to insert a couple hundred million elements to this structure than std::vector (a purely contiguous structure). And I'm pretty decent at micro-optimizations but there's just conceptually more work to do as the common case has to first inspect the free block at the top of the block free list, then access the block and pop a free index from the block's free list, write the element at the free position, and then check if the block is full and pop the block from the block free list if so. It's still a constant-time operation but with a much bigger constant than pushing back to std::vector.
2. It takes about twice as long when accessing elements using a random-access pattern given the extra arithmetic for indexing and the extra layer of indirection.
3. Sequential access doesn't map efficiently to an iterator design since the iterator has to perform additional branching each time it's incremented.
4. It has a bit of memory overhead, typically around 1 bit per element. 1 bit per element might not sound like much, but if you are using this to store a million 16-bit integers, then that's 6.25% more memory use than a perfectly compact array. However, in practice this tends to use less memory than std::vector unless you are compacting the vector to eliminate the excess capacity it reserves. Also I generally don't use it to store such teeny elements.

Pros

1. Sequential access using a for_each function that takes a callback processing ranges of elements within a block almost rivals the speed of sequential access with std::vector (only like a 10% diff), so it's not much less efficient in the most performance-critical use cases for me (most of the time spent in an ECS engine is in sequential access).
2. It allows constant-time removals from the middle with the structure deallocating blocks when they become completely empty. As a result it's generally quite decent at making sure the data structure never uses significantly more memory than necessary.
3. It doesn't invalidate indices to elements which are not directly removed from the container since it just leaves holes behind using a free list approach to reclaim those holes upon subsequent insertion.
4. You don't have to worry so much about running out of memory even if this structure holds an epic number of elements, since it only requests small contiguous blocks which don't pose a challenge for the OS to find a huge number of contiguous unused pages.
5. It lends itself well to concurrency and thread-safety without locking the whole structure, since operations are generally localized to individual blocks.

Now one of the biggest pros to me was that it become trivial to make an immutable version of this data structure, like this:

Ever since then, that opened up all kinds of doors to writing more functions devoid of side effects which made it much easier to achieve exception-safety, thread-safety, etc. The immutability was kind of a thing I discovered I could easily achieve with this data structure in hindsight and by accident, but arguably one of the nicest benefits it ended up having since it made maintaining the codebase much easier.

Noncontiguous arrays don't have cache locality which results in bad performance. However at a 4M block size it seems like there would be enough locality for good caching.

Locality of reference isn't something to concern yourself with at blocks of that size, let alone 4 kilobyte blocks. A cache line is just 64 bytes typically. If you want to reduce cache misses, then just focus on aligning those blocks properly and favor more sequential access patterns when possible.

A very rapid way to turn a random-access memory pattern into a sequential one is to use a bitset. Let's say you have a boatload of indices and they're in random order. You can just plow through them and mark bits in the bitset. Then you can iterate through your bitset and check which bytes are non-zero, checking, say, 64-bits at a time. Once you encounter a set of 64-bits of which at least one bit is set, you can use FFS instructions to quickly determine what bits are set. The bits tell you what indices you should access, except now you get the indices sorted in sequential order.

This has some overhead but can be a worthwhile exchange in some cases, especially if you're going to be looping over these indices many times.

Accessing an item is not quite as simple, there's an extra level of indirection. Would this get optimized away? Would it cause cache problems?

No, it can't be optimized away. Random-access, at least, will always cost more with this structure. It often won't increase your cache misses that much though since you'll tend to get high temporal locality with the array of pointers to blocks, especially if your common case execution paths use sequential access patterns.

Since there is linear growth after the 4M limit is hit, you could have many more allocations than you would ordinarily (say, max of 250 allocations for 1GB of memory). No extra memory is copied after 4M, however I'm not sure if the extra allocations is more expensive than copying large chunks of memory.

In practice the copying is often faster because it's a rare case, only occurring something like log(N)/log(2) times total while simultaneously simplifying the dirt cheap common case where you can just write an element to the array many times before it becomes full and needs to be reallocated again. So typically you won't get faster insertions with this type of structure because the common case work is more expensive even if it doesn't have to deal with that expensive rare case of reallocating huge arrays.

The primary appeal of this structure for me in spite of all the cons is reduced memory use, not having to worry about OOM, being able to store indices and pointers which don't get invalidated, concurrency, and immutability. It's nice to have a data structure where you can insert and remove things in constant time while it cleans itself up for you and doesn't invalidate pointers and indices into the structure.

It's worth noting that C++ already has an equivalent structure by Standard, std::deque. Currently, it's recommended as the default choice for needing a random-access sequence of stuff.

The reality is that contiguous memory is nearly completely unnecessary once the data goes past a certain size- a cache line is just 64 bytes and a page size is just 4-8KB (typical values currently). Once you're starting to talk about a few MB it really goes out the window as a concern. The same is true of allocation cost. The price of processing all that data- even just reading it- dwarfs the price of the allocations anyway.

The only other reason to worry about it is for interfacing with C APIs. But you can't get a pointer to the buffer of a List anyway so there's no concern here.

With a 4M block size, even a single block isn't guaranteed to be contiguous in physical memory; it's larger than a typical VM page size. Locality is not meaningful at that scale.

You will have to worry about heap fragmentation: if the allocations happen such that your blocks are largely non-contiguous in the heap, then when they are reclaimed by the GC, you will end up with a heap that may be too fragmented to fit a subsequent allocation. That's usually a worse situation because failures will occur in unrelated places and possibly force a restart of the application.

When memory chunks are allocated at different points in time, as in the sub-arrays within your data structure, they can be located far from each other in memory. Whether this is a problem or not depends on the CPU and is very hard to predict any longer. You have to test it.

This is an excellent idea, and it is one I have used in the past. Of course you should only use powers of two for your sub-array sizes and bit shifting for division (may happen as part of optimization). I found this type of structure slightly slower, in that compilers can optimize a single array indirection more easily. You have to test, as these types of optimizations change all the time.

The main advantage is you can run closer to the upper limit of memory in your system, as long as you use these types of structures consistently. As long as you are making your data structures larger, and not producing garbage, you avoid extra garbage collections that would occur for an ordinary List. For a giant list, it could make a huge difference: the difference between continuing to run, and running out of memory.

The extra allocations are an issue only if your sub-array chunks are small, because there is memory overhead in each array allocation.

I have created similar structures for dictionaries (hash tables). The Dictionary provided by the .net framework has the same problem as List. Dictionaries are harder in that you need to avoid rehashing as well.