GitHub user jihoonson opened a pull request:
https://github.com/apache/tajo/pull/992
TAJO-2109: Implement Radix sort
Here are some benchmark results using JMH.
```
# of tuples = 10,000, sort by 2 columns
Benchmark Mode Cnt Score Error Units
BenchmarkSort.msdRadixSort thrpt 22.890 ops/s
BenchmarkSort.timSort thrpt 26.824 ops/s
BenchmarkSort.msdRadixSort avgt 0.044 s/op
BenchmarkSort.timSort avgt 0.038 s/op
BenchmarkSort.msdRadixSort sample 24 0.043 ± 0.004 s/op
BenchmarkSort.timSort sample 26 0.039 ± 0.003 s/op
BenchmarkSort.msdRadixSort ss 0.078 s/op
BenchmarkSort.timSort ss 0.063 s/op
# of tuples = 100,000, sort by 2 columns
Benchmark Mode Cnt Score Error Units
BenchmarkSort.msdRadixSort thrpt 6.757 ops/s
BenchmarkSort.timSort thrpt 7.211 ops/s
BenchmarkSort.msdRadixSort avgt 0.145 s/op
BenchmarkSort.timSort avgt 0.136 s/op
BenchmarkSort.msdRadixSort sample 7 0.147 ± 0.011 s/op
BenchmarkSort.timSort sample 8 0.136 ± 0.016 s/op
BenchmarkSort.msdRadixSort ss 0.238 s/op
BenchmarkSort.timSort ss 0.158 s/op
# of tuples = 1,000,000, sort by 2 columns
Benchmark Mode Cnt Score Error Units
BenchmarkSort.msdRadixSort thrpt 1.139 ops/s
BenchmarkSort.timSort thrpt 0.604 ops/s
BenchmarkSort.msdRadixSort avgt 0.895 s/op
BenchmarkSort.timSort avgt 1.669 s/op
BenchmarkSort.msdRadixSort sample 2 0.845 s/op
BenchmarkSort.timSort sample 1.560 s/op
BenchmarkSort.msdRadixSort ss 0.899 s/op
BenchmarkSort.timSort ss 1.556 s/op
```
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/jihoonson/tajo-2 sort
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/tajo/pull/992.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #992
----
commit 0968c4a48763ea837b54d619f8956c647a4a977f
Author: Jihoon Son <[email protected]>
Date: 2016-03-23T00:08:58Z
testing
commit 9152ace2261b2d05a539cb8eef697de19f80230f
Author: Jihoon Son <[email protected]>
Date: 2016-03-23T02:03:33Z
Merge branch 'sort' of https://github.com/jihoonson/tajo-2 into sort
commit b5f3114082db156f8c515675aa82880893c34872
Author: Jihoon Son <[email protected]>
Date: 2016-03-23T06:55:20Z
Testing
commit 81216cb591983f3c9e55bc7af6e7f43fea16d019
Author: Jihoon Son <[email protected]>
Date: 2016-03-23T08:01:31Z
testing
commit 0154cdd3946a621d4d47b388d16d1b836a4d2917
Author: Jihoon Son <[email protected]>
Date: 2016-03-24T04:39:07Z
testing
commit 1fe5d710b4cf3f967d6677524b4754df9b9216f4
Author: Jihoon Son <[email protected]>
Date: 2016-03-25T06:36:06Z
Testing
commit 2f92363461943f47136f2b2a327c83be7c0134a1
Author: Jihoon Son <[email protected]>
Date: 2016-03-26T00:35:11Z
Add in-place MSD radix sort
commit 566e621a34aad1a5a352ec028ac7e7578854d662
Author: Jihoon Son <[email protected]>
Date: 2016-03-26T05:53:28Z
Testing
commit a16c856f285150d352053e853b4a048ab315884c
Author: Jihoon Son <[email protected]>
Date: 2016-03-26T07:59:29Z
Add contended
commit 31699e55475bfe2e240c49bd813b72f1ffe9230e
Author: Jihoon Son <[email protected]>
Date: 2016-03-27T06:31:12Z
Key cache
commit 74b6882d0be8e6bb2e446bdf93de3a7232daa818
Author: Jihoon Son <[email protected]>
Date: 2016-03-27T14:44:25Z
Testing
commit 9850623eb8d50f5904ef48ed8b8f4010fc8f8f67
Author: Jihoon Son <[email protected]>
Date: 2016-03-28T12:04:57Z
Fix bug
commit 4859b8f0bc39d8f07fd4995576db5f677bf4f97a
Author: Jihoon Son <[email protected]>
Date: 2016-03-29T05:41:54Z
Testing
commit a90347336604c75ff6087eafa2bafdb6feedb3e8
Author: Jihoon Son <[email protected]>
Date: 2016-03-31T12:53:18Z
Reducing cache miss in swapping
commit f38b30415abb7524aeed2bcaf208a883558987e3
Author: Jihoon Son <[email protected]>
Date: 2016-04-01T14:13:03Z
Testing
commit 1cf6c02c0c22c70805c9c68c6bb9b363c3991e68
Author: Jihoon Son <[email protected]>
Date: 2016-04-01T14:29:38Z
Start impl
commit 6a1675dd917c82ab9c39cb5a90ae10c2bb5ee2ac
Author: Jihoon Son <[email protected]>
Date: 2016-04-02T09:02:14Z
Multi column sort
commit 2bf841cbc8d375304ff6da4539c1cbc7951ad1e0
Author: Jihoon Son <[email protected]>
Date: 2016-04-02T10:43:33Z
Add LSD RADIx
commit a337f38a6abd83e9cf2b36bc227333cb0400fbef
Author: Jihoon Son <[email protected]>
Date: 2016-04-03T04:49:03Z
Use tim sort when run is short
commit 2d7128f75d219577d10a1d386fab38e57ba2c6ad
Author: Jihoon Son <[email protected]>
Date: 2016-04-03T06:41:08Z
Support null first and desc
commit b4aedcb09bd722c4723116d865fbf92860b82a8c
Author: Jihoon Son <[email protected]>
Date: 2016-04-03T09:02:52Z
Sign considered radix sort
commit f2ced4ea702c706f6aa8e28662ffae4cbd4bc0c8
Author: Jihoon Son <[email protected]>
Date: 2016-04-03T10:47:34Z
Add descriptions
commit 7eab3d6cec035652fdd7b1eb81227a10efcab97d
Author: Jihoon Son <[email protected]>
Date: 2016-04-03T10:51:53Z
Add some more descriptions.
commit f2f6a466a275b0e64377352e655f64964106085b
Author: Jihoon Son <[email protected]>
Date: 2016-04-03T11:13:26Z
Fix test failures and cleanup codes.
commit 35c22f9f9e30487aa7d2fd399aabdeff45ecd2b4
Author: Jihoon Son <[email protected]>
Date: 2016-04-03T11:15:56Z
Merge branch 'master' of https://git-wip-us.apache.org/repos/asf/tajo into
sort
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at [email protected] or file a JIRA ticket
with INFRA.
---
