JEP 103: Parallel Array SortingJEP 103: Parallel Array SortingAuthorsDavid Holmes, Chris HegartyOwnerChris HegartyTypeFeatureScopeSEStatusClosed / DeliveredRelease8Componentcore-libsDiscussioncore dash libs dash dev at openjdk dot java dot netEffortXSDurationXSDependsJEP 155: Concurrency UpdatesEndorsed byBrian GoetzCreated2011/09/26 20:00Updated2017/08/13 17:12Issue8046093Summary
Add additional utility methods to java.util.Arrays that use the JSR 166
Fork/Join parallelism common pool to provide sorting of arrays in parallel.
Non-Goals
There are many algorithms for parallel array sorting with different trade-offs
for time and space. The goal here is to provide a generally useful utility
operation, not to provide a framework of different algorithms from which the
programmer can select.
Success Metrics
A minimum speedup of at least 1.3 over sequential sort on a two core system,
for a suitably sized data set.
Motivation
Java 7 added the Fork/Join framework for lightweight data parallelism, but
users must presently implement their own algorithms for simple/common
tasks. This proposal addresses one common task by providing parallel sorting of
arrays. By converting to/from arrays this can also be used to sort arbitrary
collections (for those that have a defined traversal order).
Description
Current sorting implementations provided by the Java Collections Framework
(Collections.sort and Arrays.sort) all perform the sorting operation
sequentially in the calling thread. This enhancement will offer the same set of
sorting operations currently provided by the Arrays class, but with a parallel
implementation that utilizes the Fork/Join framework. These new API's are still
synchronous with regard to the calling thread as it will not proceed past the
sorting operation until the parallel sort is complete.
The actual sorting API this proposal adds will leverage the ForkJoinPool
commonPool (default Fork/Join pool being defined by JEP 155).
public class Arrays {

  ...
  public static void parallelSort(byte[] a) { ... }
  public static void parallelSort(byte[] a, int fromIndex, int toIndex)
  public static void parallelSort(short[] a) { ... }
  public static void parallelSort(short[] a, int fromIndex, int toIndex)
    {...}

  ...

}
Sort methods are defined for all primitive array types except boolean, plus
Comparable object types, plus arbitrary Object types using a supplied
Comparator. The sorting algorithm is that used in Doug Lea's ParallelArray
implementation and requires a working space the same size as the array to be
sorted (this is the whole array, not just the portion to be sorted).
Open issues:


Will some users require the ability to specify which pool to use?


Will users want a choice of algorithms to allow space/time trade-offs?


Alternatives
No general alternatives have been considered. The parallel sorting
implementation comes from Doug Lea's ParallelArray framework. Some variations
in the API's, particularly in regard to which pool to use, have been
considered, but are presently deemed more complex than needed.
Testing


Includes unit tests adapted from the existing tests for Arrays.sort


Simple benchmarking tests showing speedup over serial sort also included.


Requires larger (8+ core) system for performance regression testing.


Risks and Assumptions
It is assumed that the choice of the Fork/Join system-wide common pool, and the
tying of this API to that pool will not be contentious (or at least not to the
point where it prevents the progress of this proposal). The ability to expand
the API to allow further control over the pool could be added at a later stage.
It is also assumed that the simple algorithm choice will be sufficient for the
general use case.
Impact


Compatibility: Forward compatible only


Security: Offers additional DoS attacks base upon shared resource (system
fork/join pool)


Documentation: Javadoc only


Internationalization: Unchanged from existing serial sorting.


InstallingContributingSponsoringDevelopers' GuideVulnerabilitiesJDK GA/EA BuildsMailing listsWiki
                      · IRCBylaws · CensusLegalWorkshopJEP ProcessSource codeMercurialGitHubToolsGitjtreg harnessGroups(overview)AdoptionBuildClient LibrariesCompatibility & Specification ReviewCompilerConformanceCore LibrariesGoverning BoardHotSpotIDE Tooling & SupportInternationalizationJMXMembersNetworkingPortersQualitySecurityServiceabilityVulnerabilityWebProjects(overview,
      archive)AmberBabylonCRaCCaciocavalloClosuresCode ToolsCoinCommon VM InterfaceCompiler GrammarDetroitDevelopers' GuideDevice I/ODukeGalahadGraalIcedTeaJDK 7JDK 8JDK 8 UpdatesJDK 9JDK
      (…,
       21,
       22,
       23)JDK UpdatesJavaDoc.NextJigsawKonaKullaLambdaLanaiLeydenLilliputLocale EnhancementLoomMemory Model UpdateMetropolisMission ControlMulti-Language VMNashornNew I/OOpenJFXPanamaPenrosePort: AArch32Port: AArch64Port: BSDPort: HaikuPort: Mac OS XPort: MIPSPort: MobilePort: PowerPC/AIXPort: RISC-VPort: s390xPortolaSCTPShenandoahSkaraSumatraTiered AttributionTsanType AnnotationsValhallaVeronaVisualVMWakefieldZeroZGC

        © 2024 Oracle Corporation and/or its affiliates
        Terms of Use
        ·
        
            License: GPLv2
        · Privacy
        · Trademarks
