C++ Logo


Advanced search

Re: Colony/hive & unordered vs ordered == operator

From: Henry Miller <hank_at_[hidden]>
Date: Thu, 17 Mar 2022 12:53:54 -0500
On Thu, Mar 17, 2022, at 03:00, Matthew Bentley via SG14 wrote:

> * I think it should probably be specified that copying a container
> Cannot change the iteration order. There is no legitimate performance
> reason not to specify this (as far as I know), as iterative order is
> also memory locality order, hence iterative order is also the fastest
> way to copy. This also makes the copying of sort()'ed hives less
> problematic. If anyone has any objections to this let me know.

I'm not convinced. If there are a lot of memory blocks, the fastest copy may be to spin each to a separate thread: that thread allocates a new block and copies; then piece the new blocks in whatever order the thread returns. Each block keep the same order, but the order of the blocks could change. Or, if there is a "mostly empty" block is may be better reorder that block into others - this makes the copy itself take longer, but not having to enter a mostly empty block on future iterations may make that it worth the cost.

To make the above optimizations (or others not thought of yet) possible I think order after copy should be unspecified for now. At this time I don't see any harm in leaving iteration order unspecified after copy, and it may (or may not) be useful. Or to put it differently, what is the gain to making the iteration order specified - hive is an unordered container so user code shouldn't rely on any order, and if std:: itself relies on order the implementation is free to add a restriction not in the standard.

  Henry Miller

Received on 2022-03-17 17:54:18