Uploaded image for project: 'Hadoop Map/Reduce'
  1. Hadoop Map/Reduce
  2. MAPREDUCE-3235

Improve CPU cache behavior in map side sort



    • Improvement
    • Status: Open
    • Major
    • Resolution: Unresolved
    • 0.23.0
    • None
    • performance, task
    • None


      When running oprofile on a terasort workload, I noticed that a large amount of CPU usage was going to MapTask$MapOutputBuffer.compare. Upon disassembling this and looking at cycle counters, most of the cycles were going to memory loads dereferencing into the array of key-value data – implying expensive cache misses. This can be avoided as follows:

      • rather than simply swapping indexes into the kv array, swap the entire meta entries in the meta array. Swapping 16 bytes is only negligibly slower than swapping 4 bytes. This requires adding the value-length into the meta array, since we used to rely on the previous-in-the-array meta entry to determine this. So we replace INDEX with VALUELEN and avoid one layer of indirection.
      • introduce an interface which allows key types to provide a 4-byte comparison proxy. For string keys, this can simply be the first 4 bytes of the string. The idea is that, if stringCompare(key1.proxy(), key2.proxy()) != 0, then compare(key1, key2) should have the same result. If the proxies are equal, the normal comparison method is used. We then include the 4-byte proxy as part of the metadata entry, so that for many cases the indirection into the data buffer can be avoided.

      On a terasort benchmark, these optimizations plus an optimization to WritableComparator.compareBytes dropped the aggregate mapside CPU millis by 40%, and the compare() routine mostly dropped off the oprofile results.


        1. hashed-sort-MAPREDUCE-3235.patch
          10 kB
          Gopal Vijayaraghavan
        2. map_sort_perf.diff
          8 kB
          Hal Mo
        3. mr-3235-poc.txt
          12 kB
          Todd Lipcon

        Issue Links



              tlipcon Todd Lipcon
              tlipcon Todd Lipcon
              0 Vote for this issue
              38 Start watching this issue