base: Add bulk insert to flat_tree.

base: Add bulk insert to flat_tree.

This patch adds a bulk insert into flat tree, which does the following:
- Appends new elements to the end of the existing vector
- Sorts the newly added elements
- Does an inplace merge of the two sublists
- Does a unique pass.

Starting with a vector of size N, inserting a range of M elements should be roughly
O(M log M) + O(N + M) + O(N + M)

R=brettw@chromium.org, danakj@chromium.org

[vmpstr, 2017-05-02 18:55:37]

Description was changed from

==========
base: Add bulk insert to flat_tree.

This patch adds a bulk insert into flat tree, which does the following:
- Appends new elements to the end of the existing vector
- Sorts the newly added elements
- Does an inplace merge of the two sublists
- Does a unique pass.

R=brettw@chromium.org, danakj@chromium.org
==========

to

==========
base: Add bulk insert to flat_tree.

This patch adds a bulk insert into flat tree, which does the following:
- Appends new elements to the end of the existing vector
- Sorts the newly added elements
- Does an inplace merge of the two sublists
- Does a unique pass.

Starting with a vector of size N, inserting a range of M elements
should be
O(M log M) + O(N + M) + O(N + M)

R=brettw@chromium.org, danakj@chromium.org
==========

[vmpstr, 2017-05-02 18:55:55]

Description was changed from

==========
base: Add bulk insert to flat_tree.

This patch adds a bulk insert into flat tree, which does the following:
- Appends new elements to the end of the existing vector
- Sorts the newly added elements
- Does an inplace merge of the two sublists
- Does a unique pass.

Starting with a vector of size N, inserting a range of M elements
should be
O(M log M) + O(N + M) + O(N + M)

R=brettw@chromium.org, danakj@chromium.org
==========

to

==========
base: Add bulk insert to flat_tree.

This patch adds a bulk insert into flat tree, which does the following:
- Appends new elements to the end of the existing vector
- Sorts the newly added elements
- Does an inplace merge of the two sublists
- Does a unique pass.

Starting with a vector of size N, inserting a range of M elements should be
O(M log M) + O(N + M) + O(N + M)

R=brettw@chromium.org, danakj@chromium.org
==========

[vmpstr, 2017-05-02 18:59:37]

Please take a look. It's not really a blocker for me, but I found that we use an
std::set for the tabstrip, and it looks like an ideal candidate for flat_set,
since we can estimate a reasonable bound for the number of tabs a user might
have. However, the code does bulk inserts...

Let me know if we should have more tests.

[vmpstr, 2017-05-02 19:00:18]

(or whether there are still concerns about performance that prevent this type of
patch from landing)

[vmpstr, 2017-05-04 15:43:17]

Description was changed from

==========
base: Add bulk insert to flat_tree.

This patch adds a bulk insert into flat tree, which does the following:
- Appends new elements to the end of the existing vector
- Sorts the newly added elements
- Does an inplace merge of the two sublists
- Does a unique pass.

Starting with a vector of size N, inserting a range of M elements should be
O(M log M) + O(N + M) + O(N + M)

R=brettw@chromium.org, danakj@chromium.org
==========

to

==========
base: Add bulk insert to flat_tree.

This patch adds a bulk insert into flat tree, which does the following:
- Appends new elements to the end of the existing vector
- Sorts the newly added elements
- Does an inplace merge of the two sublists
- Does a unique pass.

Starting with a vector of size N, inserting a range of M elements should be
roughly
O(M log M) + O(N + M) + O(N + M)

R=brettw@chromium.org, danakj@chromium.org
==========

[vmpstr, 2017-05-04 15:45:21]

ping, danakj do you think this is worth doing?

[danakj, 2017-05-04 17:59:16]

On 2017/05/04 15:45:21, vmpstr wrote:
> ping, danakj do you think this is worth doing?

You should read the comments from dyaroshev here:
https://codereview.chromium.org/2776793002/ He had some strong opinions about
bulk insert. Let me know what you think from there.

[vmpstr, 2017-05-04 21:24:35]

On 2017/05/04 17:59:16, danakj wrote:
> On 2017/05/04 15:45:21, vmpstr wrote:
> > ping, danakj do you think this is worth doing?
> 
> You should read the comments from dyaroshev here:
> https://codereview.chromium.org/2776793002/ He had some strong opinions about
> bulk insert. Let me know what you think from there.

I think the argument there assumed that the full range needs to be sorted, as
opposed to just the newly inserted elements, which this patch avoids. However,
the perftests that I did locally only show a benefit over single insert when the
number of inserted items is larger than the number of elements already present
in the container (the benefit isn't as great as the benefit exhibited by single
inserts for smaller number of inserts).

I was hoping to provide an ergonomic API for these types of inserts, but it
seems that we might as well ensure that the caller is aware that the best way of
doing this is single item insertion. Closing this.

[danakj, 2017-05-04 21:41:56]

On Thu, May 4, 2017 at 5:24 PM, <vmpstr@chromium.org> wrote:

> On 2017/05/04 17:59:16, danakj wrote:
> > On 2017/05/04 15:45:21, vmpstr wrote:
> > > ping, danakj do you think this is worth doing?
> >
> > You should read the comments from dyaroshev here:
> > https://codereview.chromium.org/2776793002/ He had some strong opinions
> about
> > bulk insert. Let me know what you think from there.
>
> I think the argument there assumed that the full range needs to be sorted,
> as
> opposed to just the newly inserted elements, which this patch avoids.
> However,
> the perftests that I did locally only show a benefit over single insert
> when the
> number of inserted items is larger than the number of elements already
> present
> in the container (the benefit isn't as great as the benefit exhibited by
> single
> inserts for smaller number of inserts).
>
> I was hoping to provide an ergonomic API for these types of inserts, but it
> seems that we might as well ensure that the caller is aware that the best
> way of
> doing this is single item insertion. Closing this.
>

Hm interesting.

What would you suggest for someone who wants to insert 1000 items, but at 6
different times?


>
> https://codereview.chromium.org/2859593002/
>

-- 
You received this message because you are subscribed to the Google Groups
"Chromium-reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

[vmpstr, 2017-05-04 21:57:39]

On 2017/05/04 21:41:56, danakj wrote:
> On Thu, May 4, 2017 at 5:24 PM, <mailto:vmpstr@chromium.org> wrote:
> 
> > On 2017/05/04 17:59:16, danakj wrote:
> > > On 2017/05/04 15:45:21, vmpstr wrote:
> > > > ping, danakj do you think this is worth doing?
> > >
> > > You should read the comments from dyaroshev here:
> > > https://codereview.chromium.org/2776793002/ He had some strong opinions
> > about
> > > bulk insert. Let me know what you think from there.
> >
> > I think the argument there assumed that the full range needs to be sorted,
> > as
> > opposed to just the newly inserted elements, which this patch avoids.
> > However,
> > the perftests that I did locally only show a benefit over single insert
> > when the
> > number of inserted items is larger than the number of elements already
> > present
> > in the container (the benefit isn't as great as the benefit exhibited by
> > single
> > inserts for smaller number of inserts).
> >
> > I was hoping to provide an ergonomic API for these types of inserts, but it
> > seems that we might as well ensure that the caller is aware that the best
> > way of
> > doing this is single item insertion. Closing this.
> >
> 
> Hm interesting.
> 
> What would you suggest for someone who wants to insert 1000 items, but at 6
> different times?

I think there are heuristics we can do here which branch depending on the size
of the range vs size of the current container.

That aside, one case that I was looking at specifically was appending one flat
set to another flat set, which has a nice property that both ranges are sorted.
If we can add something like sorted_insert, or insert(flat_tree) or some-such,
then it'd certainly be an improvement over single item insert, since it would
only require a merge+unique pass; and perf verifies that it's a pretty
significant win when inserting > 4 items. Unfortunately this seems like a major
departure from STL style containers, despite the fact that some STL algorithms
require sorted ranges. I fear it would only add confusion.

> 
> 
> >
> > https://codereview.chromium.org/2859593002/
> >
> 
> -- 
> You received this message because you are subscribed to the Google Groups
> "Chromium-reviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
email
> to mailto:chromium-reviews+unsubscribe@chromium.org.

[danakj, 2017-05-05 14:59:24]

On Thu, May 4, 2017 at 5:57 PM, <vmpstr@chromium.org> wrote:

> On 2017/05/04 21:41:56, danakj wrote:
>
> > On Thu, May 4, 2017 at 5:24 PM, <mailto:vmpstr@chromium.org> wrote:
> >
> > > On 2017/05/04 17:59:16, danakj wrote:
> > > > On 2017/05/04 15:45:21, vmpstr wrote:
> > > > > ping, danakj do you think this is worth doing?
> > > >
> > > > You should read the comments from dyaroshev here:
> > > > https://codereview.chromium.org/2776793002/ He had some strong
> opinions
> > > about
> > > > bulk insert. Let me know what you think from there.
> > >
> > > I think the argument there assumed that the full range needs to be
> sorted,
> > > as
> > > opposed to just the newly inserted elements, which this patch avoids.
> > > However,
> > > the perftests that I did locally only show a benefit over single insert
> > > when the
> > > number of inserted items is larger than the number of elements already
> > > present
> > > in the container (the benefit isn't as great as the benefit exhibited
> by
> > > single
> > > inserts for smaller number of inserts).
> > >
> > > I was hoping to provide an ergonomic API for these types of inserts,
> but it
> > > seems that we might as well ensure that the caller is aware that the
> best
> > > way of
> > > doing this is single item insertion. Closing this.
> > >
> >
> > Hm interesting.
> >
> > What would you suggest for someone who wants to insert 1000 items, but
> at 6
> > different times?
>
> I think there are heuristics we can do here which branch depending on the
> size
> of the range vs size of the current container.
>
> That aside, one case that I was looking at specifically was appending one
> flat
> set to another flat set, which has a nice property that both ranges are
> sorted.
> If we can add something like sorted_insert, or insert(flat_tree) or
> some-such,
> then it'd certainly be an improvement over single item insert, since it
> would
> only require a merge+unique pass; and perf verifies that it's a pretty
> significant win when inserting > 4 items. Unfortunately this seems like a
> major
> departure from STL style containers, despite the fact that some STL
> algorithms
> require sorted ranges. I fear it would only add confusion.
>

I suppose it diverges from map, but as a counterpoint, vector has an insert
of another vector for instance.


>
> >
> >
> > >
> > > https://codereview.chromium.org/2859593002/
> > >
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Chromium-reviews" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> email
> > to mailto:chromium-reviews+unsubscribe@chromium.org.
>
>
>
> https://codereview.chromium.org/2859593002/
>

-- 
You received this message because you are subscribed to the Google Groups
"Chromium-reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

[brettw, 2017-05-05 21:42:47]

On 2017/05/05 14:59:24, danakj wrote:
> I suppose it diverges from map, but as a counterpoint, vector has an insert
> of another vector for instance.

I wasn't aware of this and I couldn't find it in the docs. Are you sure?

[danakj, 2017-05-05 22:10:27]

On Fri, May 5, 2017 at 5:42 PM, <brettw@chromium.org> wrote:

> On 2017/05/05 14:59:24, danakj wrote:
> > I suppose it diverges from map, but as a counterpoint, vector has an
> insert
> > of another vector for instance.
>
> I wasn't aware of this and I couldn't find it in the docs. Are you sure?
>

Nope, I made it up. I was thinking of insert from iterators and insert from
initializer list. These are algorithmically same as inserting from a vector
though, for that structure. But for flat_set it's not sufficient. It's at
those junctions where I think we should diverge the API when it's useful.
So all that's to say I think inserting another flat_set into a flat_set
seems like it's a good thing to add if you have a use case for it.


>
> https://codereview.chromium.org/2859593002/
>

-- 
You received this message because you are subscribed to the Google Groups
"Chromium-reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

[vmpstr, 2017-05-05 22:30:08]

On 2017/05/05 22:10:27, danakj wrote:
> On Fri, May 5, 2017 at 5:42 PM, <mailto:brettw@chromium.org> wrote:
> 
> > On 2017/05/05 14:59:24, danakj wrote:
> > > I suppose it diverges from map, but as a counterpoint, vector has an
> > insert
> > > of another vector for instance.
> >
> > I wasn't aware of this and I couldn't find it in the docs. Are you sure?
> >
> 
> Nope, I made it up. I was thinking of insert from iterators and insert from
> initializer list. These are algorithmically same as inserting from a vector
> though, for that structure. But for flat_set it's not sufficient. It's at
> those junctions where I think we should diverge the API when it's useful.
> So all that's to say I think inserting another flat_set into a flat_set
> seems like it's a good thing to add if you have a use case for it.
> 

The case I was looking at was switching these sets
https://cs.chromium.org/chromium/src/chrome/browser/ui/unload_controller.h?l=148

to flat set (same for fast_unload_controller). The problem case I ran into is
here:
https://cs.chromium.org/chromium/src/chrome/browser/ui/unload_controller.cc?l...

which inserts one of these sets into another one of the same type. Maybe this
could also be altogether changed, since I'm not sure if the set properties here
are important or whether a vector would do.

> 
> >
> > https://codereview.chromium.org/2859593002/
> >
> 
> -- 
> You received this message because you are subscribed to the Google Groups
> "Chromium-reviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
email
> to mailto:chromium-reviews+unsubscribe@chromium.org.

[danakj, 2017-05-09 23:07:52]

On Fri, May 5, 2017 at 6:30 PM, <vmpstr@chromium.org> wrote:

> On 2017/05/05 22:10:27, danakj wrote:
> > On Fri, May 5, 2017 at 5:42 PM, <mailto:brettw@chromium.org> wrote:
> >
> > > On 2017/05/05 14:59:24, danakj wrote:
> > > > I suppose it diverges from map, but as a counterpoint, vector has an
> > > insert
> > > > of another vector for instance.
> > >
> > > I wasn't aware of this and I couldn't find it in the docs. Are you
> sure?
> > >
> >
> > Nope, I made it up. I was thinking of insert from iterators and insert
> from
> > initializer list. These are algorithmically same as inserting from a
> vector
> > though, for that structure. But for flat_set it's not sufficient. It's at
> > those junctions where I think we should diverge the API when it's useful.
> > So all that's to say I think inserting another flat_set into a flat_set
> > seems like it's a good thing to add if you have a use case for it.
> >
>
> The case I was looking at was switching these sets
> https://cs.chromium.org/chromium/src/chrome/browser/
> ui/unload_controller.h?l=148
>
> to flat set (same for fast_unload_controller). The problem case I ran into
> is
> here:
> https://cs.chromium.org/chromium/src/chrome/browser/
> ui/unload_controller.cc?l=313
>
> which inserts one of these sets into another one of the same type. Maybe
> this
> could also be altogether changed, since I'm not sure if the set properties
> here
> are important or whether a vector would do.
>

Cool, thanks, that does seem like a pretty exemplary use case :)


>
>
> >
> > >
> > > https://codereview.chromium.org/2859593002/
> > >
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Chromium-reviews" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> email
> > to mailto:chromium-reviews+unsubscribe@chromium.org.
>
>
>
> https://codereview.chromium.org/2859593002/
>

-- 
You received this message because you are subscribed to the Google Groups
"Chromium-reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.