Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(208)

Issues Search
    My Issues | Starred     Open | Closed | All

Issue 2862813002: Insertion by one sometimes gives drammatically better results than (Closed)

Created:
3 years, 7 months ago by dyaroshev
Modified:
3 years, 7 months ago
Reviewers:
CC:
chromium-reviews, jdonnelly+watch_chromium.org, danakj+watch_chromium.org, vmpstr+watch_chromium.org
Target Ref:
refs/heads/master
Project:
chromium
Visibility:
Public.

Description

Insertion by one sometimes gives dramatically better results than insert + sort + merge. I used components_perftests/HQPPerfTestOnePopularURL.Backspacing for my measurements. As you can see, sometimes inserting range by one can be up to 20 times faster. This big of a difference seems unacceptable even for the worst case. This is why I think we need better algorithm for bulk insert. Measurement results: Buffered <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< [ RUN ] HQPPerfTestOnePopularURL.Backspacing 54-50= [12,4,4,4,4,] ms 49-45= [4,5,5,16,35,] ms 44-40= [35,34,32,32,36,] ms 39-35= [31,33,32,35,31,] ms 34-30= [35,36,32,32,37,] ms 29-25= [28,32,30,28,28,] ms 24-20= [28,30,32,33,30,] ms 19-15= [29,33,31,37,30,] ms 14-10= [29,40,26,25,25,] ms 9-5= [27,34,23,22,23,] ms 4-0= [23,24,25,30,1,] ms By one <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< [ RUN ] HQPPerfTestOnePopularURL.Backspacing 54-50= [12,5,4,4,4,] ms 49-45= [4,5,5,17,43,] ms 44-40= [39,34,38,34,36,] ms 39-35= [39,34,36,34,33,] ms 34-30= [32,35,34,33,34,] ms 29-25= [30,34,29,31,33,] ms 24-20= [31,32,30,30,34,] ms 19-15= [30,36,32,32,30,] ms 14-10= [34,46,29,27,27,] ms 9-5= [29,37,25,24,26,] ms 4-0= [24,26,25,34,1,] ms Insert merge <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< [ RUN ] HQPPerfTestOnePopularURL.Backspacing 54-50= [12,4,4,4,4,] ms 49-45= [4,5,5,37,34,] ms 44-40= [38,34,33,32,33,] ms 39-35= [33,34,32,32,34,] ms 34-30= [32,35,32,56,834,] ms 29-25= [33,33,31,34,29,] ms 24-20= [29,32,30,29,29,] ms 19-15= [30,33,31,30,32,] ms 14-10= [49,812,31,26,28,] ms 9-5= [54,803,24,25,26,] ms 4-0= [24,28,51,839,1,] ms BUG=682249

Patch Set 1 #

Unified diffs Side-by-side diffs Delta from patch set Stats (+55 lines, -0 lines) Patch
M base/containers/flat_tree.h View 1 chunk +18 lines, -0 lines 0 comments Download
M components/omnibox/browser/url_index_private_data.cc View 2 chunks +37 lines, -0 lines 0 comments Download

Messages

Total messages: 3 (3 generated)
dyaroshev
Description was changed from ========== Insertion by one sometimes gives drammatically better results than insert ...
3 years, 7 months ago (2017-05-04 09:56:48 UTC) #1
dyaroshev
Description was changed from ========== Insertion by one sometimes gives dramatically better results than insert ...
3 years, 7 months ago (2017-05-04 09:57:10 UTC) #2
dyaroshev
3 years, 7 months ago (2017-05-04 09:57:27 UTC) #3 
Description was changed from

==========
Insertion by one sometimes gives dramatically better results than
insert + sort + merge.

I used components_perftests/HQPPerfTestOnePopularURL.Backspacing for my
measurements. As you can see, sometimes inserting range by one can be up to 20 
times faster. This big of a difference seems unacceptable even for the worst
case.
This is why I think we need better algorithm for bulk insert.

Measurement results:

Buffered <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[ RUN      ] HQPPerfTestOnePopularURL.Backspacing
54-50= [12,4,4,4,4,] ms
49-45= [4,5,5,16,35,] ms
44-40= [35,34,32,32,36,] ms
39-35= [31,33,32,35,31,] ms
34-30= [35,36,32,32,37,] ms
29-25= [28,32,30,28,28,] ms
24-20= [28,30,32,33,30,] ms
19-15= [29,33,31,37,30,] ms
14-10= [29,40,26,25,25,] ms
9-5= [27,34,23,22,23,] ms
4-0= [23,24,25,30,1,] ms

By one <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[ RUN      ] HQPPerfTestOnePopularURL.Backspacing
54-50= [12,5,4,4,4,] ms
49-45= [4,5,5,17,43,] ms
44-40= [39,34,38,34,36,] ms
39-35= [39,34,36,34,33,] ms
34-30= [32,35,34,33,34,] ms
29-25= [30,34,29,31,33,] ms
24-20= [31,32,30,30,34,] ms
19-15= [30,36,32,32,30,] ms
14-10= [34,46,29,27,27,] ms
9-5= [29,37,25,24,26,] ms
4-0= [24,26,25,34,1,] ms

Insert merge <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[ RUN      ] HQPPerfTestOnePopularURL.Backspacing
54-50= [12,4,4,4,4,] ms
49-45= [4,5,5,37,34,] ms
44-40= [38,34,33,32,33,] ms
39-35= [33,34,32,32,34,] ms
34-30= [32,35,32,56,834,] ms
29-25= [33,33,31,34,29,] ms
24-20= [29,32,30,29,29,] ms
19-15= [30,33,31,30,32,] ms
14-10= [49,812,31,26,28,] ms
9-5= [54,803,24,25,26,] ms
4-0= [24,28,51,839,1,] ms

BUG=682249
==========

to

==========
Insertion by one sometimes gives dramatically better results than
insert + sort + merge.

I used components_perftests/HQPPerfTestOnePopularURL.Backspacing for my 
measurements. As you can see, sometimes inserting range by one can be up to 20 
times faster. This big of a difference seems unacceptable even for the worst
case.
This is why I think we need better algorithm for bulk insert.

Measurement results:

Buffered <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[ RUN      ] HQPPerfTestOnePopularURL.Backspacing
54-50= [12,4,4,4,4,] ms
49-45= [4,5,5,16,35,] ms
44-40= [35,34,32,32,36,] ms
39-35= [31,33,32,35,31,] ms
34-30= [35,36,32,32,37,] ms
29-25= [28,32,30,28,28,] ms
24-20= [28,30,32,33,30,] ms
19-15= [29,33,31,37,30,] ms
14-10= [29,40,26,25,25,] ms
9-5= [27,34,23,22,23,] ms
4-0= [23,24,25,30,1,] ms

By one <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[ RUN      ] HQPPerfTestOnePopularURL.Backspacing
54-50= [12,5,4,4,4,] ms
49-45= [4,5,5,17,43,] ms
44-40= [39,34,38,34,36,] ms
39-35= [39,34,36,34,33,] ms
34-30= [32,35,34,33,34,] ms
29-25= [30,34,29,31,33,] ms
24-20= [31,32,30,30,34,] ms
19-15= [30,36,32,32,30,] ms
14-10= [34,46,29,27,27,] ms
9-5= [29,37,25,24,26,] ms
4-0= [24,26,25,34,1,] ms

Insert merge <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[ RUN      ] HQPPerfTestOnePopularURL.Backspacing
54-50= [12,4,4,4,4,] ms
49-45= [4,5,5,37,34,] ms
44-40= [38,34,33,32,33,] ms
39-35= [33,34,32,32,34,] ms
34-30= [32,35,32,56,834,] ms
29-25= [33,33,31,34,29,] ms
24-20= [29,32,30,29,29,] ms
19-15= [30,33,31,30,32,] ms
14-10= [49,812,31,26,28,] ms
9-5= [54,803,24,25,26,] ms
4-0= [24,28,51,839,1,] ms

BUG=682249
==========

Powered by Google App Engine
This is Rietveld 408576698