Hi,

On Fri, 11 Nov 2022 18:51:03 -0500
Jason McKesson via Std-Proposals <std-proposals_at_[hidden]> wrote:

> On Fri, Nov 11, 2022 at 5:12 PM Lénárd Szolnoki via Std-Proposals
> <std-proposals_at_[hidden]> wrote:
> >
> > Hi,
> >
> > I suppose this applies to unsized ranges. But range does not have
> > to be random access to have std::ranges::size, which is O(1) and
> > meant to be cheap.
> >
> > For sized ranges it absolutely makes sense to do the preallocation,
> > and it doesn't require traversing the range twice.
> >
> > I would say that for unsized ranges it makes more sense to not do
> > this, and do the usual multiple reallocations.
>
> I disagree. For most ranges that don't have a size, traversal is
> inexpensive next to the cost of memory allocations (and the requisite
> copying/moving of data). Even complex views that need to invoke some
> functor (like `filter_view` and the like) will generally be cheaper
> than doing potentially dozens of memory allocations. Indeed, it's
> pretty rare to find a forward range for whom iteration is so slow that
> multiple memory allocation is preferred.

I'm quite surprised on this benchmark's results, but here you go:

https://quick-bench.com/q/usHB_TCGMgB8b7lnjettooYGVnc

Some notes:
* The cost of the extra allocations is indeed amortized, but I didn't
  need a lot of elements, the array size is only 1024.
* The filter is very simple, and the data in the array (all zeros) are
  in favor of the branch predictor.
* int being trivially copyable is in favor of the low cost vectorized
  data copying on reallocation.

Cheers,
Lénárd