Sorting algorithms should be simple, robust and sustainable.


Simplicity

Simplicity is prerequisite for reliability ― Edsger W. Dijkstra

Sorting algorithms must be simple for reliable industrial grade use. Complexity hinders widespread use and carries risks. Examples of this are the following:


Robustness, Adaptivity and Resilience

It is time to develop the discipline of resilient algorithms ― Moshe Y. Vardi2

Sorting algorithms must function robustly under divers conditions. Simple algorithms also tend to be more robust. Tuning for specific conditions not only makes algorithms more complex, the success of some tuning techniques also strongly depends on CPU and compiler version, notoriously for tuning against branch-misprediction. greeNsort® algorithms require less tuning than other algorithms. Even without tuning greeNsort® algorithms are very adaptive to many diverse data inputs, and some algorithms even reduce branch-misprediction. Still, greeNsort® algorithms may be tuned for specific preferences. The covid-19 pandemie increased appreciation for short local supply chains: greeNsort® algorithms prefer local memory access over distant memory access, where possible. Finally, greeNsort® algorithms allow the resilient execution under difficult conditions: some are designed for economic execution with negligible buffer memory, others allow to cope with temporary shortage of memory when calling them.


Sustainability

What can software professionals do? Software can be designed and tuned for efficiency and memory size, enabling client devices to remain viable for over eight years. Software upgrades should have as a design goal to avoid driving client hardware obsolescence. ― Andrew A. Chien3

The footprint of software is composed of fixed investment cost (hardware production) and variable runtime cost (energy consumption). However, academic research has almost exclusively compared sorting algorithms with regard to variable cost (typically measuring runtime or counts of certain operations such as moves and comparisons). Ignoring the fixed costs has two major drawbacks:

We introduce the sorting footprint4 for measuring and comparing algorithms: greeNsort® algorithms achieve better runtime with less hardware.


greeNsort® algorithms are simple, robust and sustainable

The most sustainable way is to not make things. The second most sustainable way is to make something very useful, to solve a problem that hasn’t been solved. ― Thomas Sigsgaard

greeNsort® algorithms are …


There’s a way to do it better. Find it. ― Thomas Edison



  1. Peter Lammich 2020 Efficient Verified Implementation of Introsort and Pdqsort↩︎

  2. Efficiency vs. Resilience: What COVID-19 Teaches Computing, COMMUNICATIONS OF THE ACM, 05/2020↩︎

  3. What Do DDT and Computing Have in Common?, COMMUNICATIONS OF THE ACM, 06/2020↩︎

  4. The footprint measure integrates fixed and variable costs by integrating resources such as CPU and RAM over runtime and the footprint measure allows to compare algorithms with different memory requirements. For single-threaded sorting the footprint is just \(\int_{t=0}^{runtime} memory_t \; dt\), for algorithms using constant memory this simplifies to \(runtime \cdot memory\)↩︎

 

greeNsort logo


Copyright © 2020 Dr. Jens Oehlschlägel - All rights reserved - Terms - Privacy - Impressum