[
https://issues.apache.org/jira/browse/TAJO-2109?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15223216#comment-15223216
]
ASF GitHub Bot commented on TAJO-2109:
--------------------------------------
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
----
> Implement Radix sort
> --------------------
>
> Key: TAJO-2109
> URL: https://issues.apache.org/jira/browse/TAJO-2109
> Project: Tajo
> Issue Type: New Feature
> Components: Sort algorithm
> Reporter: Jihoon Son
> Assignee: Jihoon Son
> Fix For: 0.12.0
>
>
> Radix sort is known for very fast sort algorithm when the length of the sort
> key is not long. We can benefit from Radix sort if it is used when it is
> faster than Tim sort.
> In this issue, I will implement Radix sort for Tajo, and conduct some
> benchmark tests to compare its performance with Tim sort.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
