What kind of setups use over 256 TiB of RAM?

Does std::deque support random access?

In principle it's not that different that deque, though:

(1) deque uses fixed-sized blocks, not increasing-size blocks. (2) dequeue supports prepending, which adds another level of indirection internally.

I don't know the precise details of how deques are implemented in C++, but given the most popular stack overflow explanation of them, some immidiate pitfalls are that the T* map itself sounds unbounded and if each chunk allocates only a fixed constant size it's probably horrible for fragmentation or overallocation. The indexing also seems dependent on division.

With this power of twos approach you can't really truly delete from the front of the array but the amount of pointers you store is constant and the memory fragmentation is better. (Though OP never claimed to want to support deque behavior, it shouldn't be that hard to modify, though indexing seems like it has to go thru more arithmetic again)

I haven't used OP's array, but I have been bit plenty of times with std::deque's memory allocation patterns and had to rewrite with raw arrays and pointer tracking.

std::deque details vary by implementation and is largely considered unusable for MSVC.

MSVC uses a too small block size making it worthless. libc++ block size is 16 elements or 4096 bytes.

It is generally better to use a container you can actually understand the implementation details and control.

I would not call it a variant of std::deque myself. Not wrong. But not a helpful observation imho.

What's all that icons on the diagram that illustrates 5-level paging - snowflakes and triangles?

Unfortunately std::deque is hobbled in the Microsoft implementation. Its block size is such that if T is larger than 8 bytes it devolves to a linked list.

And it can't be fixed due to binary compatibility.

https://github.com/microsoft/STL/issues/147

By contrast the GNU implementation has a block size of 512 bytes

Fortunately in high performance systems the times where you actually want an unbounded queue are limited.

Yeah, with less runtime overhead, so long as you're ok with the ~4kB minimum allocation size.

This mention this alturnative in the article, and also point out how it does not work in embeded contexts or with WASM

If you do that, you lose those stable pointers.

feel free to call it a "levelwise-allocated pile"

Yeah, the limitation that it can't be just dumped into anything that expects a C array is a large one. You need to structure your code around the access primitives this project implements.

The POSIX name for the function is clz() [the C23 name is stdc_leading_zeros(), because that's how the committee names things now, while the GCC intrinsic is __builtin_clz()]. The name of the x86 instruction, on the other hand, is BSR (80386+) or LZCNT (Nehalem+, K10+) depending on what semantics you want for zero inputs (keep in mind that early implementations of BSF/BSR are very slow and take time proportional to the output value). The compiled code uses BSR. (All of these are specified slightly differently, take care if you plan to actually use them.)

> The Way in C

Is it though? (Ab)using C macros so you can write obviously-not-C stuff like (from the example):

SegmentArray(Entity) entities = {0};

Seeing that kind of thing in example C code just makes my hair stand on end because you know it's someone who actually wants to write C++ but for whatever reason has decided to try to implement their thing in C and be clever about it. And I'm going to have to go parse through multiple levels of macro indirection to just understand what the hell is going on.

Seems like a useful data structure, despite the shortcoming that it can't be accessed like a regular array. Normally auto-expanding arrays involves realloc which is tricky with arena allocation. But jeez, just pass void pointers + size and have it assert if there's a mismatch.

> Also, from a strictly prose point of view, isn't it strange that the `clz` instruction

It's using the `bsr` instruction which is similar (but worse). The `lzcnt` instruction in x86_64 is a part of the BMI feature introduced in Intel Haswell. The compiler does not generate these instructions by default so it runs on any x86_64.

If you add `-mbmi` or `-march=haswell` or newer to the compiler command line, you should get `clz`/`lzcnt` instead.

Make sure the create the segment_array.h file. Mine outputted just fine on Mac M4

  Desktop gcc main.c        
  Desktop ./a.out 

entities[0].a = 1 entities[0].a = 1 entities[1].a = 2

I believe I've seen problems like this also solved with arena allocators. You have certain very special allocations have an arena unto themselves.

Same re: virtual memory systems (using guard pages), that is an old idea that works well but it did once produce a really unpleasant bug in production... But that was an unfortunate implementation mishap.

For an expanding array in a 64 bit address space, reserving a big region and mmaping it in as you go is usually the top performing solution by a wide margin. At least on Linux, it is faster to speculatively mmap ahead with MAP_POPULATE rather than relying on page faults, too.

And, if you find you didn't reserve enough address space, Linux has mremap() which can grow the reserved region. Or map the region to two places at once (the original place and a new, larger place).

I would not call it “non-contiguous”. It’s more like “mostly contiguous”. Which for large amounts data is “amortized contiguous” just like a regular vector has “amortized constant” time to add an element.

1. The image at the top of the article makes it clear the segments aren't contiguous

2. iterating a 4 billion item segmented array would have 26 cache misses. Not a big deal.

They link to an old article [1] that was featured in HN [2] somewhat recently, in which there's a workaround for older standards with regards to typeof.

[1]: https://danielchasehooper.com/posts/typechecked-generic-c-da...

[2]: https://news.ycombinator.com/item?id=44425461

It is a GNU extension, supported by both GCC and Clang.

It's always better - the increase in indexing complexity is negligible, and it completely eliminates resizing of the top-level array. It also reduces the number of calls to `malloc` while keeping capacity proportional to active size.

I think they mentioned it's for an arena, where stability is necessary. You might happen to use said arena for a hash table

A lot of standard libraries have tried to implement ropes for things like strings and it usually is reverted for a simpler structure.

Those 10 instructions are for one access, not for a tight loop. A tight loop could be done with a much more complex macro that iterates separately in each segment, amortizing the overhead.