Hello

I still think that default approach for constructing vectors from forward
ranges to do double traversal and pre-allocate is good for general case, but
giving the caller control for exceptional cases would be nice.

A simple example of an expensive filter is, say, if we have a list of files
and filter which opens a file and reads its signature to check a file type.

In this case we can easily provide an upper estimate (for example, the size
of the source list) and make sure the list is traversed only once.

The second suggestion to "downgrade" the range type via as_input also solves
the original problem, but probably provides less performance gains. However,
I still feel it is worth to have one maybe for other application areas.

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

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

BTW, std::basic_string constructor (which we also may use in ranges::to and
which also behaves the same, at least in MSVC), will probably show even more
surprising results for input ranges because of SSO. For short strings, where
allocations are basically no-ops and for very long strings, for which
allocations would be amortized, we might get better performance compared to
double-traversal even for relatively inexpensive range traversal.


Sincerely,
Alexander Bessonov
HHD Software Ltd.
-----Original Message-----
From: Lénárd Szolnoki via Std-Proposals
Sent: Saturday, November 12, 2022 3:01 PM
To: std-proposals_at_[hidden]
Cc: LénárdSzolnoki
Subject: Re: [std-proposals] New vector range constructor to improve
performance with forward ranges

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

-- 
Std-Proposals mailing list
Std-Proposals_at_[hidden]
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals