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 4 days ago | parent | next [-]

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 3 days ago | parent [-]

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.

	▲	KapKap66 3 days ago \| parent [-]
		If I understand the article right, if this is an issue I think you can get around it by redesigning your approach to first retrieve the segment and segment length directly and then access the data within the segment like a traditional array, instead of going through your accessor functions every time. Should help with the problem a bit.

▲

forrestthewoods 4 days ago | parent | prev [-]

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.