On Thursday, 9 April 2026 22:10:24 Pacific Daylight Time Simon Schröder via
Std-Proposals wrote:
> > On Apr 10, 2026, at 3:17 AM, Muneem via Std-Proposals
> > <std-proposals_at_[hidden]> wrote:
> >
> > Again, why do flat maps exist, why don't we all optimize maps away if the
> > compiler can figure out that the constant latency of a flat maps is
> > actually gonna be faster.
> Regular maps exist because the performance gap between memory and CPU used
> to be a lot less when they were invented. And there are probably a lot of
> different microprocessors where a regular map is still faster than a flat
> map.

And then of course processors evolve too. For a node size of a few tens of
bytes, the compactness of a flat map or vector no longer matters too much. With
a feature like the Array of Pointers Prefetcher, the CPU learns where the
pointer to the next node is in the node, and prefetches that, with similar
performance as "fetch next cacheline" or linear walking of an array. That
brings the performance of linked lists and RB-trees back up.

-- 
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
  Principal Engineer - Intel Data Center - Platform & Sys. Eng.