[
https://issues.apache.org/jira/browse/MAPREDUCE-2841?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13169965#comment-13169965
]
Binglin Chang commented on MAPREDUCE-2841:
------------------------------------------
bq. Dual-pivot quicksort causes the exact same number of comparisons as
ordinary quicksort. However, it should have fewer swaps (0.80 times as many).
Unfortunately, the main overhead of current sort in Hadoop comes from
comparison, the swaps just swap two integer index, I thinks that's why
Dual-pivot quicksort don't show any improvements. As Todd's results in
MAPREDUCE-3235 and I experienced in this issue, the main overhead for the
current Hadoop sort implementation is cache miss, nearly all comparison
operations cause 2 random memory access in a huge memory area(typically X00MB).
So it's not language differentes, just implementation differentes, to get
better performance, we can:
Add index in MAPREDUCE-3235, or use partition bucket based sort.
I port DualPivotQuickSort java code to C++ and tested it on my intel i5
macbookpro, with terasort 10bytes key type and word key type in
RandomTextWriter.
TeraSort input data 50MB 500000 key/value pair
11/12/15 12:18:16 INFO qsort time: 0.23108s
11/12/15 12:18:16 INFO std::sort time: 0.18266s
11/12/15 12:18:17 INFO DualPivotQuicksort time: 0.17167s
About 6% faster, I think sorting an array of ints can get much better results,
cause compare two inplace ints is much faster than campare two indexed binary
string.
Some updates about my work, I almost finished whole native mapTask, and part of
native reduce task.
As for native MapTask with C++ RecordReader, Mapper, Partitioner,
MapOutputCollector, a native MapTask now can process 250MB(47MB compressed)
terasort input data in just 1.6s, comparing this with the earlier test
results(14s for java, 7s for java with NativeMapOutputCollector), it is a huge
speed up, and it can be further optimized.
> Task level native optimization
> ------------------------------
>
> Key: MAPREDUCE-2841
> URL: https://issues.apache.org/jira/browse/MAPREDUCE-2841
> Project: Hadoop Map/Reduce
> Issue Type: Improvement
> Components: task
> Environment: x86-64 Linux
> Reporter: Binglin Chang
> Assignee: Binglin Chang
> Attachments: MAPREDUCE-2841.v1.patch, MAPREDUCE-2841.v2.patch,
> dualpivot-0.patch, dualpivotv20-0.patch
>
>
> I'm recently working on native optimization for MapTask based on JNI.
> The basic idea is that, add a NativeMapOutputCollector to handle k/v pairs
> emitted by mapper, therefore sort, spill, IFile serialization can all be done
> in native code, preliminary test(on Xeon E5410, jdk6u24) showed promising
> results:
> 1. Sort is about 3x-10x as fast as java(only binary string compare is
> supported)
> 2. IFile serialization speed is about 3x of java, about 500MB/s, if hardware
> CRC32C is used, things can get much faster(1G/s).
> 3. Merge code is not completed yet, so the test use enough io.sort.mb to
> prevent mid-spill
> This leads to a total speed up of 2x~3x for the whole MapTask, if
> IdentityMapper(mapper does nothing) is used.
> There are limitations of course, currently only Text and BytesWritable is
> supported, and I have not think through many things right now, such as how to
> support map side combine. I had some discussion with somebody familiar with
> hive, it seems that these limitations won't be much problem for Hive to
> benefit from those optimizations, at least. Advices or discussions about
> improving compatibility are most welcome:)
> Currently NativeMapOutputCollector has a static method called canEnable(),
> which checks if key/value type, comparator type, combiner are all compatible,
> then MapTask can choose to enable NativeMapOutputCollector.
> This is only a preliminary test, more work need to be done. I expect better
> final results, and I believe similar optimization can be adopt to reduce task
> and shuffle too.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
