[kudu-CR] generic iterators: switch MergeIterator to intrusive list of states

2019-04-09 Thread Adar Dembo (Code Review) 
Adar Dembo has submitted this change and it was merged. ( 
http://gerrit.cloudera.org:8080/12944 )

Change subject: generic_iterators: switch MergeIterator to intrusive list of 
states
..

generic_iterators: switch MergeIterator to intrusive list of states

I originally wanted this for dominance because, in that world, a state is
either linked to the main list or to another state's dominated list. We're
going to go in a different direction, but an intrusive list still makes
sense because:
1. We don't need random access into states_, and
2. An intrusive list will yield O(1) erase without increasing the total
   number of allocations.

I also changed the MergeIterator tests to use int64_t instead of uint32_t
for values, as the latter reliably overflowed the non-overlapped input test
when num_lists >= 30.

Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Reviewed-on: http://gerrit.cloudera.org:8080/12944
Reviewed-by: Mike Percy 
Tested-by: Kudu Jenkins
---
M src/kudu/common/generic_iterators-test.cc
M src/kudu/common/generic_iterators.cc
2 files changed, 89 insertions(+), 67 deletions(-)

Approvals:
  Mike Percy: Looks good to me, approved
  Kudu Jenkins: Verified

--
To view, visit http://gerrit.cloudera.org:8080/12944
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Gerrit-Change-Number: 12944
Gerrit-PatchSet: 5
Gerrit-Owner: Adar Dembo 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy 
Gerrit-Reviewer: Todd Lipcon

[kudu-CR] generic iterators: switch MergeIterator to intrusive list of states

2019-04-09 Thread Mike Percy (Code Review) 
Mike Percy has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/12944 )

Change subject: generic_iterators: switch MergeIterator to intrusive list of 
states
..


Patch Set 4: Code-Review+2


--
To view, visit http://gerrit.cloudera.org:8080/12944
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Gerrit-Change-Number: 12944
Gerrit-PatchSet: 4
Gerrit-Owner: Adar Dembo 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy 
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Wed, 10 Apr 2019 00:24:32 +
Gerrit-HasComments: No

[kudu-CR] generic iterators: switch MergeIterator to intrusive list of states

2019-04-09 Thread Adar Dembo (Code Review) 
Adar Dembo has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/12944 )

Change subject: generic_iterators: switch MergeIterator to intrusive list of 
states
..


Patch Set 3:

> Patch Set 3:
>
> 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.

And of course this has nothing to do with this patch. Whoops.


--
To view, visit http://gerrit.cloudera.org:8080/12944
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Gerrit-Change-Number: 12944
Gerrit-PatchSet: 3
Gerrit-Owner: Adar Dembo 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy 
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Tue, 09 Apr 2019 22:20:27 +
Gerrit-HasComments: No

[kudu-CR] generic iterators: switch MergeIterator to intrusive list of states

2019-04-09 Thread Adar Dembo (Code Review) 
Adar Dembo has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/12944 )

Change subject: generic_iterators: switch MergeIterator to intrusive list of 
states
..


Patch Set 3:

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/12944
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Gerrit-Change-Number: 12944
Gerrit-PatchSet: 3
Gerrit-Owner: Adar Dembo 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy 
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Tue, 09 Apr 2019 22:19:46 +
Gerrit-HasComments: No

[kudu-CR] generic iterators: switch MergeIterator to intrusive list of states

2019-04-09 Thread Adar Dembo (Code Review) 
Adar Dembo has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/12944 )

Change subject: generic_iterators: switch MergeIterator to intrusive list of 
states
..


Patch Set 1:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/12944/1/src/kudu/common/generic_iterators.cc
File src/kudu/common/generic_iterators.cc:

http://gerrit.cloudera.org:8080/#/c/12944/1/src/kudu/common/generic_iterators.cc@106
PS1, Line 106: MergeIterStateList
> nit: maybe just call this 'List' so it's not redundantrly MergerIterState::
Done



--
To view, visit http://gerrit.cloudera.org:8080/12944
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Gerrit-Change-Number: 12944
Gerrit-PatchSet: 1
Gerrit-Owner: Adar Dembo 
Gerrit-Reviewer: Adar Dembo 
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy 
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Tue, 09 Apr 2019 20:45:05 +
Gerrit-HasComments: Yes

[kudu-CR] generic iterators: switch MergeIterator to intrusive list of states

2019-04-09 Thread Adar Dembo (Code Review) 
Hello Mike Percy, Kudu Jenkins, Todd Lipcon,

I'd like you to reexamine a change. Please visit

http://gerrit.cloudera.org:8080/12944

to look at the new patch set (#2).

Change subject: generic_iterators: switch MergeIterator to intrusive list of 
states
..

generic_iterators: switch MergeIterator to intrusive list of states

I originally wanted this for dominance because, in that world, a state is
either linked to the main list or to another state's dominated list. We're
going to go in a different direction, but an intrusive list still makes
sense because:
1. We don't need random access into states_, and
2. An intrusive list will yield O(1) erase without increasing the total
   number of allocations.

I also changed the MergeIterator tests to use int64_t instead of uint32_t
for values, as the latter reliably overflowed the non-overlapped input test
when num_lists >= 30.

Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
---
M src/kudu/common/generic_iterators-test.cc
M src/kudu/common/generic_iterators.cc
2 files changed, 89 insertions(+), 67 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/44/12944/2
--
To view, visit http://gerrit.cloudera.org:8080/12944
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Gerrit-Change-Number: 12944
Gerrit-PatchSet: 2
Gerrit-Owner: Adar Dembo 
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy 
Gerrit-Reviewer: Todd Lipcon

[kudu-CR] generic iterators: switch MergeIterator to intrusive list of states

2019-04-09 Thread Todd Lipcon (Code Review) 
Todd Lipcon has posted comments on this change. ( 
http://gerrit.cloudera.org:8080/12944 )

Change subject: generic_iterators: switch MergeIterator to intrusive list of 
states
..


Patch Set 1:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/12944/1/src/kudu/common/generic_iterators.cc
File src/kudu/common/generic_iterators.cc:

http://gerrit.cloudera.org:8080/#/c/12944/1/src/kudu/common/generic_iterators.cc@106
PS1, Line 106: MergeIterStateList
nit: maybe just call this 'List' so it's not redundantrly 
MergerIterState::MergeIterStateList?



--
To view, visit http://gerrit.cloudera.org:8080/12944
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Gerrit-Change-Number: 12944
Gerrit-PatchSet: 1
Gerrit-Owner: Adar Dembo 
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy 
Gerrit-Reviewer: Todd Lipcon 
Gerrit-Comment-Date: Tue, 09 Apr 2019 17:38:13 +
Gerrit-HasComments: Yes

[kudu-CR] generic iterators: switch MergeIterator to intrusive list of states

2019-04-05 Thread Adar Dembo (Code Review) 
Hello Mike Percy, Todd Lipcon,

I'd like you to do a code review. Please visit

http://gerrit.cloudera.org:8080/12944

to review the following change.


Change subject: generic_iterators: switch MergeIterator to intrusive list of 
states
..

generic_iterators: switch MergeIterator to intrusive list of states

I originally wanted this for dominance because, in that world, a state is
either linked to the main list or to another state's dominated list. We're
going to go in a different direction, but an intrusive list still makes
sense because:
1. We don't need random access into states_, and
2. An intrusive list will yield O(1) erase without increasing the total
   number of allocations.

I also changed the MergeIterator tests to use int64_t instead of uint32_t
for values, as the latter reliably overflowed the non-overlapped input test
when num_lists >= 30.

Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
---
M src/kudu/common/generic_iterators-test.cc
M src/kudu/common/generic_iterators.cc
2 files changed, 91 insertions(+), 67 deletions(-)



  git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/44/12944/1
--
To view, visit http://gerrit.cloudera.org:8080/12944
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: I1a165858e37c3e0a6ef85e46e20078c264fa8a65
Gerrit-Change-Number: 12944
Gerrit-PatchSet: 1
Gerrit-Owner: Adar Dembo 
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Mike Percy 
Gerrit-Reviewer: Todd Lipcon