Hacker News new | ask | show | jobs
by dhooper 311 days ago
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.

1 comments

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.
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.