Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/12947 )
Change subject: generic_iterators: implement three-heap merge algorithm ...................................................................... Patch Set 6: I experimented with the different boost heaps that are available. For each one, I ran TestMerge and TestMergeNonOverlapping from generic_iterators-test with --num_rows=1000, num_lists=1000, and --num_iters=10. I averaged the wall clock times (they were fairly stable) and listed them below. For each heap, the first result is for overlapping input and the second is for non-overlapping. results.binomial 2.737 0.104 results.d_ary_2 1.1864 0.0941 results.d_ary_3 1.2917 0.0935 results.d_ary_4 1.3408 0.0963 results.d_ary_5 1.5982 0.0995 results.fibonacci 2.3818 0.1063 results.pairing 2.4572 0.0927 results.skew 1.0659 0.0881 Based on these results, I switched from using fibonacci heaps to skew heaps. -- To view, visit http://gerrit.cloudera.org:8080/12947 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-Project: kudu Gerrit-Branch: master Gerrit-MessageType: comment Gerrit-Change-Id: I6deab76a103f45c1b5042b104731e46a771a0f5d Gerrit-Change-Number: 12947 Gerrit-PatchSet: 6 Gerrit-Owner: Adar Dembo <[email protected]> Gerrit-Reviewer: Adar Dembo <[email protected]> Gerrit-Reviewer: Grant Henke <[email protected]> Gerrit-Reviewer: Kudu Jenkins (120) Gerrit-Reviewer: Mike Percy <[email protected]> Gerrit-Reviewer: Tidy Bot (241) Gerrit-Reviewer: Todd Lipcon <[email protected]> Gerrit-Comment-Date: Tue, 09 Apr 2019 22:20:42 +0000 Gerrit-HasComments: No
