C++ Logo


Advanced search

Re: [SG14] Colony Reserve update

From: Ben Craig <ben.craig_at_[hidden]>
Date: Tue, 4 Aug 2020 21:22:53 +0000
I believe your results, but I'm trying to understand the "why" a bit better. Does the addition of reserve() have knock-on effects on the rest of the design of the container? Perhaps because it makes prior, simple invariants more complicated?

How does the container differ in the following cases:
* Reservable design: Start empty, reserve(512) elements, insert 100 elements
* Non-reservable design: Start empty, insert 512 elements, erase 412 elements
* Reservable design: Start empty, insert 100 elements
* Non-reservable design: Start empty, insert 100 elements

Are there extra checks that you need to make during iteration or lookup that reserve forces on you?

> -----Original Message-----
> From: SG14 <sg14-bounces_at_[hidden]> On Behalf Of Jens Maurer via
> SG14
> Sent: Tuesday, August 4, 2020 3:58 PM
> To: sg14_at_[hidden]
> Cc: Jens Maurer <Jens.Maurer_at_[hidden]>
> Subject: [EXTERNAL] Re: [SG14] Colony Reserve update
> Thanks for trying this out.
> Please make sure the below rationale for omitting "reserve"
> is in the prose part of the next update of your paper.
> (prose part = any part other than the to-be normative wording)
> Future generations (such as reviewers in LEWG) should be able to find out
> why "reserve" isn't available.
> Jens
> On 04/08/2020 01.09, Matthew Bentley via SG14 wrote:
> > Just an update regarding the use or presence of reserve() in colony,
> > as discussed in the june meeting, reserve could be useful in the sense
> > of
> > (a) moving allocation cost to non-hot-loop areas of code and
> > (b) preventing the establishment of many smaller-sized element memory
> blocks during singular insertions, if the approximate number of overall
> insertions is known in advance. This in turn increases cache locality for
> elements.
> >
> > The current reserve function only allows for the creation of one
> > memory block, which is of course not suitable for the end specification, as
> the size of memory blocks is limited by various factors and a reserve function
> which does not necessarily reserve the capacity requested is not a good fit
> for the C++ standard.
> >
> > As mentioned in the meeting my previous tests of creating a version which
> allowed for multiple empty memory blocks "in storage" created untenable
> performance detriments, to the tune of 2% on average.
> > In addition such a function necessitates another function to free unused
> memory blocks without reallocating elements (as opposed to shrink_to_fit
> which reallocates).
> >
> > Anyway, I thought I'd try again and see whether I could come up with a
> better solution this time without any performance advantages.
> > I didn't look at the old code, so as to obviate any chance of me recreating
> the same possibly-slower-performing pattern.
> >
> > Unfortunately the same results were found - specifically, 2% slower on
> average for both my general use and 'referencer' (game-scenario)
> benchmarks.
> > But most importantly, in the key areas where colony overtakes all other
> containers/container-adaptations in terms of performance (general use with
> high ratios of insert/erase to iteration), colony became 10-11% slower. I
> believe this was also the case the last time I tried this. This is untenable and
> reserve will be removed from future versions of the specification.
> > I tried many different approaches, comparing their results but no amount
> of optimization would shift this figure significantly.
> >
> > I still have a few more things to implement and test before I release the
> next version of the specification, but it shouldn't be too far off.
> >
> > In terms of the useful aspects of reserve as mentioned above, these can
> be replicated by:
> > (a) using allocators with colony to move the allocation costs away
> > from any hot loops
> > (b) changing the minimum element memory block capacity sizes before
> insertion to guarantee the capacity of the first block allocated.
> >
> > While reserve would've been useful, I believe it's cost in this case
> outweighs its benefits.
> > In case anyone's interested, both the highest-performing version of the
> with-reserve() colony.h, and the spreadsheet of the general use
> performance results are attached. The implementation lacks re-use of
> memory blocks in the range-insert/fill-insert/initializer-list-insert/splice
> functions, and probably a few other functions that weren't critical for
> benchmarking, so is not usable in production.
> >
> > Thanks-
> > Matt
> >
> > _______________________________________________
> > SG14 mailing list
> > SG14_at_[hidden]
> > https://urldefense.com/v3/__https://lists.isocpp.org/mailman/listinfo.
> > cgi/sg14__;!!FbZ0ZwI3Qg!-d7w2n-dvSEKcXNxr3k94gO-uqAuJ0ICL9Ow-
> 8mjRvr_Cm
> > y6m0ea7ZTM5c_A$
> >
> _______________________________________________
> SG14 mailing list
> SG14_at_[hidden]
> https://urldefense.com/v3/__https://lists.isocpp.org/mailman/listinfo.cgi/sg
> 14__;!!FbZ0ZwI3Qg!-d7w2n-dvSEKcXNxr3k94gO-uqAuJ0ICL9Ow-
> 8mjRvr_Cmy6m0ea7ZTM5c_A$

Received on 2020-08-04 16:26:19