Chapter 9 Impact
In this section we give a perspective on the impact of the greeNsort® innovations on computational Thinking, Research, Teaching, Libraries, APIs, IDEs, Languages, Compilers and Hardware – to the degree that we already can imagine them today.
9.1 Thinking
I expect that the surprisingly successful development of the greeNsort® methods and algorithms with very few man years investment could somewhat change today’s computational thinking. Liu et al. (2021) have already questioned the current scope as too narrow, I agree, but I think that their approach which adds historical-thinking, data-centric-thinking and architectural thinking still jumps too short. I plan a book chapter that will take a look at recursive-thinking, symmetric-thinking, aesthetical-thinking, ethical-thinking and experimental-thinking and their role in problem-solving for a sustainable-society.
9.2 Research
I expect short-term, mid-term and long-term impact on research:
- short-term: research on existing greeNsort® algorithms (like the publications following of the publication of Dual-Pivot-Quicksort of @Yaroslavskiy (2009), namely Wild (2012), Wild and Nebel (2012), Wild et al. (2013), Wild, Nebel, and Neininger (2015), Aumüller and Dietzfelbinger (2015), Martínez, Nebel, and Wild (2015), Aumüller, Dietzfelbinger, and Klaue (2016), Nebel, Wild, and Martínez (2016), Wild, Nebel, and Mahmoud (2016), Wild (2016), Wild (2017), Wild (2018a), Wild (2018b), Martínez, Nebel, and Wild (2019))
- mid-term: research applying greeNsort® methods and principles to further algorithmic problems
- long-term: research on programming languages, compilers and CPUs that support greeNsort® methods, particularly Code-mirroring
For example, the B-level innovation – (D)istinct (I)dentification for (E)arly (T)ermination (DIET) and B-level innovation – (F)ast (L)oops (I)n (P)artitioning (FLIP) methods have first been proven useful for solving Quicksort-Dilemma in unstable binary sorting, and then gave way to Ducksort. The section Partial Z:cksort has shown further implications for various closely related partial sorting algorithms, and section Incremental sorting has shown further implications for not so closely related priority queues. So far unstable sorting. Then DIET and FLIP could also be applied to stable binary Partition&Pool sorting, and I suspect it could play a role in k-ary Partition&Pool sorting, at least help to make (I)n-place (P)arallel (S)uper (S)calar (S)ample(So)rt (IPS4o) stable. From a more abstract perspective, the broadest implication of the symmetric thinking and recursive thinking behind DIET and FLIP is that they open the door to a new, unexplored part of an enlarged solution space for many algorithmic problems. In the statistical programming languages S and R there is the concept of “computing on the language”; this means using code to create code which is then executed; this increases the expressiveness of these interpreted languages but comes as a performance penalty. The FLIP method is an example of computing on the recursion which also increases expressiveness, but without such performance penalties. Clearly, if for each recursive recall we have to choose between two mirrored versions of code, this increases expressiveness by factor 2. In other words: computing symmetry on the recursion increases the solution space for algorithmic problems by at least factor 2. If we consider, that we actually do not mirror all code but selected code sections, the number of possible variations is higher than 2 (of which many are not useful, but some might). Of course, since all recursive algorithms can be coded without recursion, all of this enlarged solution space can theoretically be reached without computing symmetry on the recursion, but in practice, algorithms need to be written by humans who understand what they do, and hence recursion and symmetry are helpful mental tools for understanding problems and designing algorithms. Hence the concept of computing symmetry on the recursion is a powerful mental instrument that combines recursive thinking, symmetric thinking and spatial thinking. Code mirroring is at the junction between verbal and visual cognitive abilities, and that plays a role in problem solving and innovating. In summary, computing symmetry on the recursion is promising
- because of its potential to simplify (and visualize) complex algorithmic tasks
- because it is widely unexplored terrain
- because the inherent redundancy provides further optimization opportunities, see [Languages]
Note that this outlook has not even touched on the major share of the greeNsort® innovations: Split&Merge sorting. It also has not touched on index-trees. The following quote shows a common belief that symmetric tree-traversal is not interesting:
Binary tree is a tree structure, traversal is to make all nodes in the tree be visited only once, that is, arranged into a linear queue according to certain rules. A binary (sub) tree is a recursively defined structure, consisting of three parts: the root node (N), the left subtree (L), and the right subtree (R). Classify the traversal of the binary tree according to the access order of these three parts. There are 6 traversal schemes in total: NLR, LNR, LRN, NRL, RNL and LNR. Studying the traversal of binary trees is to study these 6 specific traversal schemes. Obviously, according to simple symmetry, the traversal of the left and right subtrees can be interchanged, that is, NLR and NRL, LNR and RNL, LRN and RLN Therefore, it is only necessary to study the three types of NLR, LNR and LRN, which are called “pre-order traversal”, “medium-order traversal” and “post-order traversal”.
— TitanWolf - Binary tree traversal
Assuming upfront that mirrored versions of tree-operations can be ignored looks again like unexplored opportunities of a larger solution space.
9.3 Teaching
I expect short-term, mid-term and long-term impact on teaching:
- short-term: teaching existing greeNsort® algorithms, methods and principles. It is obvious, that textbooks on algorithms require updating their sections on unstable sorting, partial sorting and selection and priority queues. The same is true for sections on stable sorting and incremental sorting. Beyond that, textbooks need to update theirs sections on recursion and should teach the greeNsort® methods (such as code-mirroring and computing-on-the-recursion) and principles (such as measuring sustainability and designing for simplicity).
- mid-term: teaching the algorithms that result from research using greeNsort® methods and principles, see above
- long-term: teaching the results of research on programming languages, compilers and CPUs that support greeNsort® methods, see above and below
9.4 Libraries
The first motivation for greeNsort® was to provide more efficient sorting libraries in order to reduce CO2-emissions. Because of the bigger savings potential of stable sorting the focus of greeNsort® is on alternatives to Mergesort, that save both, electricity and memory. Nonetheless, unstable Quicksort plays an important role in IT and most programming languages have an API for unstable in-place sorting, often using implementations inferior to Pdqsort, Z:cksort or Ducksort. Z:cksorts allow simple and efficient implementation which is superior to both Quicksort2 and Quicksort3, notwithstanding further tuning. For example the C sort routine implements 3-way-Quicksort. Z:cksort can replace it with the benefit of faster sorting untied data and still early terminating in tied data. The simplicity of Z:cksort facilitates verification of correctness of implementations.
Much more impact on sorting libraries is to be expected from the greeNsort® Split&Merge algorithms with their superior trade-off between memory and speed.
9.5 APIs
Each Z:cksort uses two binary comparison operators: EQ in the DIET loop and then GT (or LT) and LE (or GE). All of them can be derived from the {-1|0|+1} output of the ternary cmd-function which the C sort API takes as a parameter. However, using cmp is not efficient, because internally it always requires two comparisons, whatever the usage of its output is. Hence, further efficiency gains should be possible by creating a new API taking three binary comparison operators, or at least two of them. For those to whom this sounds overkill: C++ has introduced syntax for exactly this. I plan a book chapter on optimal design for sorting APIs.
9.6 IDEs
If symmetric thinking indeed gains importance in algorithm design, programmers will push for IDE support for mirroring code, for example ‘copy’ and ‘paste mirrored’. However, that does not remove the burden to maintain the mirrored code, furthermore not all language element allow for mirroring, therefore more fundamental support for symmetry will be needed in Languages, Compilers and Hardware.
9.7 Languages
The mirroring of code in the FLIP-method comes with programming effort. Mirroring a piece of code is less work and less error-prone compared to writing new code, but still writing and maintaining it is work. However, it is work that can be automated by an interpreter, by a pre-processor or by a compiler. In other words: it is to be expected, that the FLIP method will have impact on future design of meta-programming or programming languages in order to facilitate programmer effort and minimize programming errors. To demonstrate this, we give an implementation of Zacksort in R25. R is an advancement of the S language. It is related to scheme, a LISP dialect, and as such treats code as data and allows “computing on the language”, in other words: meta-programming is built into the language. Note that this is just a demonstration of feasibility, since R as an interpreted language it too slow to be a serious implementation language for sorting algorithms. Having said this, let’s do it. First we need the usual comparison functions:
EQ <- function(a,b)a==b
LE <- function(a,b)a<=b
GT <- function(a,b)a>b
LT <- function(a,b)a<b
GE <- function(a,b)a>=bThe SELF-function returns the code (parse tree) of the current function, and the KEEP-function protects code from being mirrored (and executes the code):
SELF <- function(){
sys.function(sys.parent())
}KEEP <- function(exp){
eval.parent(substitute(exp))
}The following FLIP-function returns a mirrored function of f (assuming f conforms with certain rules encoded in FLIP):
FLIP <- function (f)
{
flip <- function(e) {
if (is.call(e)) {
if (is.symbol(e[[1]])) {
if (e[[1]] != as.symbol("KEEP")) {
for (i in seq_along(e)) {
e[[i]] <- flip(e[[i]])
}
}
e
}
else {
e
}
}
else if (is.symbol(e)) {
s <- as.character(e)
if (length(grep("_tieleft$",s))==1){
fs <- sub("_tieleft","_tieright",s)
}else if (length(grep("_tieright$",s))==1){
fs <- sub("_tieright","_tieleft",s)
}else{
fs <- switch(s
, l = "r" , r = "l"
, i = "j" , j = "i"
, f = "g" , g = "f"
, `+` = "-" , `-` = "+"
, `<` = ">" , `>` = "<"
, `<=` = ">=", `>=` = "<="
, LT = "GT" , GT = "LT"
, LE = "GE" , GE = "LE"
, s
)
}
as.symbol(fs)
}
else {
e
}
}
g <- f
body(g) <- flip(body(g))
return(g)
}Here is a version of Zocksort simply calling itself via SELF() instead of the R-typical Recall-function:
zocksort <- function(x, l=1, r=length(x))
{
if (l >= r)
return
j <- sample(r-l+1, 1)
v <- x[j]
x[c(l,j)] <- x[c(j,l)] # SWAP pivot
# DIET LOOP
i <- l
while (EQ(x[i <- i+1], v))
if (i >= r)
return(x) # early termination
# MAIN LOOP
i<-i-1; j<-r+1
repeat{
while ({j <- j-1; GT(x[j], v)}) # sentinel stop
{NULL}
while ({i <- i+1; LE(x[i], v)})
if (i >= j) # explicit stop
break
if (i >= j)
break
x[c(i,j)] <- x[c(j,i)] # SWAP
}
x[c(l,j)] <- x[c(j,l)] # SWAP pivot back
m <- j
h <- SELF() # h(...) replaces Recall(...)
n <- m - l; if (n>1) x[l:(m-1)] <- h(x[l:(m-1)], 1, n)
n <- r - m; if (n>1) x[(m+1):r] <- h(x[(m+1):r], 1, n)
return(x)
}This is Zacksort calling a flipped version of itself:
zacksort <- function(x, l=1, r=length(x))
{
KEEP(
if (l >= r)
return
)
j <- KEEP(sample(r-l+1, 1))
v <- x[j]
x[c(l,j)] <- x[c(j,l)] # SWAP pivot
# DIET LOOP
i <- l
while (EQ(x[i <- i+1], v))
if (i >= r)
return(x) # early termination
# MAIN LOOP
i<-i-1; j<-r+1
repeat{
while ({j <- j-1; GT(x[j], v)}) # sentinel stop
{NULL}
while ({i <- i+1; LE(x[i], v)})
if (i >= j) # explicit stop
break
if (i >= j)
break
x[c(i,j)] <- x[c(j,i)] # SWAP
}
x[c(l,j)] <- x[c(j,l)] # SWAP pivot back
m <- j
h <- FLIP(SELF())
KEEP({
n <- m - l; if (n>1) x[l:(m-1)] <- h(x[l:(m-1)], 1, n)
n <- r - m; if (n>1) x[(m+1):r] <- h(x[(m+1):r], 1, n)
})
return(x)
}This is the flipped Zacksort:
> FLIP(zacksort)
function (x, l = 1, r = length(x))
{
KEEP(if (l >= r)
return)
i <- KEEP(sample(r - l + 1, 1))
v <- x[i]
x[c(r, i)] <- x[c(i, r)]
j <- r
while (EQ(x[j <- j - 1], v)) if (j <= l)
return(x)
j <- j + 1
i <- l - 1
repeat {
while ({
i <- i + 1
LT(x[i], v)
}) {
}
while ({
j <- j - 1
GE(x[j], v)
}) if (j <= i)
break
if (j <= i)
break
x[c(j, i)] <- x[c(i, j)]
}
x[c(r, i)] <- x[c(i, r)]
m <- i
h <- FLIP(SELF())
KEEP({
n <- m - l
if (n > 1)
x[l:(m - 1)] <- h(x[l:(m - 1)], 1, n)
n <- r - m
if (n > 1)
x[(m + 1):r] <- h(x[(m + 1):r], 1, n)
})
return(x)
}For comparison the double-flipped Zacksort (standardized without code comments):
> FLIP(FLIP(zacksort))
function (x, l = 1, r = length(x))
{
KEEP(if (l >= r)
return)
j <- KEEP(sample(r - l + 1, 1))
v <- x[j]
x[c(l, j)] <- x[c(j, l)]
i <- l
while (EQ(x[i <- i + 1], v)) if (i >= r)
return(x)
i <- i - 1
j <- r + 1
repeat {
while ({
j <- j - 1
GT(x[j], v)
}) {
}
while ({
i <- i + 1
LE(x[i], v)
}) if (i >= j)
break
if (i >= j)
break
x[c(i, j)] <- x[c(j, i)]
}
x[c(l, j)] <- x[c(j, l)]
m <- j
h <- FLIP(SELF())
KEEP({
n <- m - l
if (n > 1)
x[l:(m - 1)] <- h(x[l:(m - 1)], 1, n)
n <- r - m
if (n > 1)
x[(m + 1):r] <- h(x[(m + 1):r], 1, n)
})
return(x)
}and finally Zucksort which calls itself on the non-critical branch but its flipped-self on the critical branch:
zucksort <- function(x, l=1, r=length(x))
{
KEEP(
if (l >= r)
return
)
j <- KEEP(sample(r-l+1, 1))
v <- x[j]
x[c(l,j)] <- x[c(j,l)] # SWAP pivot
# DIET LOOP
i <- l
while (EQ(x[i <- i+1], v))
if (i >= r)
return(x) # early termination
# MAIN LOOP
i<-i-1; j<-r+1
repeat{
while ({j <- j-1; GT(x[j], v)}) # sentinel stop
{NULL}
while ({i <- i+1; LE(x[i], v)})
if (i >= j) # explicit stop
break
if (i >= j) break
x[c(i,j)] <- x[c(j,i)] # SWAP
}
x[c(l,j)] <- x[c(j,l)] # SWAP pivot back
m <- j
g <- SELF()
f <- FLIP(g)
KEEP({
n <- m - l; if (n>1) x[l:(m-1)] <- f(x[l:(m-1)], 1, n)
n <- r - m; if (n>1) x[(m+1):r] <- g(x[(m+1):r], 1, n)
})
return(x)
}We can formally verify the code-symmetry as true:
> # standardize Zacksort and Zucksort
> zacksort <- FLIP(FLIP(zacksort))
> zucksort <- FLIP(FLIP(zucksort))
> # single flip modifies the functions
> all.equal(FLIP(zacksort), zacksort)
[1] "target, current do not match when deparsed"
> all.equal(FLIP(zucksort), zucksort)
[1] "target, current do not match when deparsed"
> # double flip is idempotent
> all.equal(FLIP(FLIP(zacksort)), zacksort)
[1] TRUE
> all.equal(FLIP(FLIP(zucksort)), zucksort)
[1] TRUEThis section has shown that algorithms using the FLIP-method can be written without mirror-duplicating code-redundancy, in suitable languages.
9.8 Compilers
The above interpreted FLIP operation at runtime in each call of the R-zacksort is very inefficient. It is better to only do this only once at compile time. The seemingly least invasive thing to do is using meta-programming – for example the C-preprocessor – for creating mirrored versions of code, which then is compiled along the standard path, without any particular support for symmetry in the language, the compiler or the hardware. However, there might be reasons to consider symmetry in the language itself. For example many languages provide ‘iterators’; these usually have a standard iteration direction and might not support efficient iteration in the reverse direction. C++, C# and Java have bi-directional iterators, Python and Rust have not, Mapcar in Lisp is unidirectional.
9.9 Hardware
Supporting symmetry in compilers but not in hardware still comes at a price: binary code duplication uses space in the instruction cache. If symmetric programming finds widespread use, then hardware support for symmetry – for example a FLIP instruction – might provide benefits. Co-design of language, compilers and hardware for symmetric programming is an interesting topic for future research.
9.10 Impact conclusion
Without knowing what will happen, I see good reasons to believe that – beyond saving time, energy and hardware – the greeNsort® innovations can have substantial impact on computational Thinking, Research, Teaching, Libraries, APIs, IDEs, Languages, Compilers and – hopefully – Hardware.