Hadoop Common
  1. Hadoop Common
  2. HADOOP-3308

Improve QuickSort by excluding values eq the pivot from the partition

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 0.18.0
    • Component/s: None
    • Labels:
      None
    • Hadoop Flags:
      Reviewed

      Description

      The current implementation of QuickSort naively partitions on either side of the pivot. We can improve this by partitioning on either side of the set of values equal to the pivot. This assumes that comparing keys is expensive compared to swaps and index comparisons (which it certainly is in MapTask, and should be in general).

      1. 3308-0.patch
        5 kB
        Chris Douglas
      2. 3308-1.patch
        5 kB
        Chris Douglas
      3. 3308-2.patch
        6 kB
        Chris Douglas

        Activity

        Chris Douglas created issue -
        Chris Douglas made changes -
        Field Original Value New Value
        Attachment 3308-0.patch [ 12380870 ]
        Chris Douglas made changes -
        Status Open [ 1 ] Patch Available [ 10002 ]
        Assignee Chris Douglas [ chris.douglas ]
        Chris Douglas made changes -
        Attachment 3308-1.patch [ 12380881 ]
        Chris Douglas made changes -
        Status Patch Available [ 10002 ] Open [ 1 ]
        Chris Douglas made changes -
        Status Open [ 1 ] Patch Available [ 10002 ]
        Chris Douglas made changes -
        Attachment 3308-2.patch [ 12380886 ]
        Tsz Wo Nicholas Sze made changes -
        Hadoop Flags [Reviewed]
        Chris Douglas made changes -
        Status Patch Available [ 10002 ] Open [ 1 ]
        Chris Douglas made changes -
        Status Open [ 1 ] Patch Available [ 10002 ]
        Chris Douglas made changes -
        Resolution Fixed [ 1 ]
        Status Patch Available [ 10002 ] Resolved [ 5 ]
        Nigel Daley made changes -
        Status Resolved [ 5 ] Closed [ 6 ]

          People

          • Assignee:
            Chris Douglas
            Reporter:
            Chris Douglas
          • Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development