[zoogeny]

I think the article buries a significant drawback: contiguity. It is obviously implied by the design but I think this approach would have hard-to-define characteristics for things like cache prefetching. The next address is a function, not an easily predictable change.

One frequent reason to use an array is to iterate the items. In those cases, non-contiguous memory layout is not ideal.

[dhooper]

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.

[teo_zero]

I think the parent poster meant that a compiler might have a hard time understanding when sa_get(..., i) and sa_get(..., i+1) actually access contiguous memory locations, and will thus stop applying nice optimizations. Conversely, accessing a[i] for all 4 billion items of a regular array will be optimized to specialized instructions, not excluding SIMD or SWAR.

[forrestthewoods]

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.