Motivation: why we need greeNsort®

Problem: global warming

The ICT sector emits 4% of global greenhouse gas (GHG) and is quickly growing ― Lean ICT Report 2019¹

4% GHG correspond to 341 large-scale power stations at the size of 12TWh/year².

The energy demands and carbon output of computing and the entire ICT sector must be dramatically moderated if climate change is to be slowed in time to avoid catastrophic environmental damage. The scale of the challenge is great and growing fast. ― ACM Technology Policy Council 2021³

A huge fraction of ICT energy costs is caused by inefficient software.

Complication: performance of software is hard to fix

Because algorithm design requires human ingenuity, however, it is hard to anticipate advances ― Leiserson et. al⁴

software development since 1960 focused on minimizing HR costs
packaged software producers do not pay the hardware and energy bill
accelerated code bloat forces companies and consumers to replace hardware early before footprint amortization

There is little awareness of the material cost of IT⁵. Yes there is Green IT (more efficient CPUs) but also huge Rebound Effects (more use of IT for e.g. big data, more network costs between devices and clouds, Bitcoin’s energy⁶ and e-waste⁷ craziness and that of other crypto-currencies⁸). Particularly the energy cost of software is widely ignored and digitalization is rather seen as a vehicle to promote sustainability. Yes there are Principles of Sustainable Software Engineering, some teaching on them, some blogging, some articles, a difficult to find TED Talk on Green Coding and an academic book on Green in Software Engineering, however, not much, of this arrives in practice, and nothing improves existing legacy software. Green coding is hard work and scales badly: removing the technical dept of the last 60 years would cost millions of man-years⁹.

One solution: improve sorting libraries

in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed — Report to the President and Congress¹⁰

Part of the technical dept in software can be removed with little effort¹¹, because it is encapsulated in libraries:

about half¹² of the ICT cost is related to CPU-work (168 Nuclear Power Stations)
sorting is responsible for 25% of CPU-Work according to IBM¹³ (42 Nuclear Power Stations)
sorting is one of the most fundamental operations in computers and the basis for many other algorithms
sorting is one of the most expensive operations in computers
doubling data size more than doubles sorting costs (\(\mathcal{O}(N\log{N})\))
slow sorting limits user experience and hence drives early replacement of good enough hardware before amortization
is has been shown experimentally that clever choice of sorting algorithms can reduce energy consumption¹⁴
much of sorting uses algorithms from few central libraries, improving those has huge impact
finally enjoy a nice visualization of big differences in sorting algorithms

I’m sort of mildly pessimistic. We’ve been talking about this for some time. The summer UN panel report basically said, “You know what? We started 20 or more years too late.” You take a look around you—we had extreme climate events at higher frequency, greater severity, and globally in terms of scope: floods in China, floods in Turkey, you name it. Pick drought, pick fires, floods in Germany. They didn’t say, “I told you so.” But they basically said, “So the time to prevent that kind of thing has passed.” And so what you see around you now is the new climate normal for the next 20 years. Period. — That window has closed. Nevertheless, if we do nothing, then the second half of the century is going to be pretty unpleasant, to put it mildly. — Michael Spence¹⁵

Lean ICT Report March 2019, see also The real climate and transformative impact of ICT: A critique of estimates, trends, and regulations. Freitag, Berners-Lee, Widdicks, Knowles, Blair & Friday (2021) Patterns Volume 2, Issue 9 ↩︎
12TWh/year is the average size of a nuclear power station↩︎
TechBriefs | COMPUTING AND CLIMATE CHANGE ↩︎
There’s plenty of room at the Top. What will drive computer performance after Moore’s law?↩︎
The ‘Invisible’ Materiality of Information Technology, COMMUNICATIONS OF THE ACM, 06/2020 ↩︎
Cambridge Bitcoin Electricity Consumption Index (CBECI)↩︎
“E-waste represents a growing threat to our environment, from toxic chemicals and heavy metals leaching into soils, to air and water pollutions caused by improper recycling. Here we present a methodology to estimate Bitcoin’s e-waste and find that it adds up to 30.7 metric kilotons annually, per May 2021. This number is comparable to the amount of small IT and telecommunication equipment waste produced by a country like the Netherlands. At peak Bitcoin price levels seen early in 2021, the annual amount of e-waste may grow beyond 64.4 metric kilotons in the midterm, which highlights the dynamic trend if the Bitcoin price rises further. Moreover, the demand for mining hardware already today disrupts the global semiconductor supply chain.”, Bitcoin’s growing e-waste problem, de Vries & Stoll (2021)↩︎
Ethereum Energy Consumption Index ↩︎
See for example The Most Expensive One-byte Mistake↩︎
Designing a Digital Future: Federally Funded Research and Development in Networking and Information Technology, recently verified: “Overall, we find that algorithmic progress for the median algorithm family increased substantially but by less than Moore’s law for moderate-sized problems and by more than Moore’s law for big data problems” — How Fast Do Algorithms Improve? Sherry & Thompson (2021)↩︎
More work of many parties is required to follow for example these 10 Best Practices for Green IT System or this List of Quick Wins to make your software application more efficient ↩︎
The other half of ICT costs is related to network communication and external devices such as screens↩︎
“Computer manufacturers of the 1960’s estimated that more than 25 percent of the running time of their computers was spent on sorting, when all their customers were taken into account. In fact, there were many installations in which the task of sorting was responsible for more than half of the computing time. From these statistics we may conclude that either there are many important applications of sorting, or many people sort when they shouldn’t, or inefficient sorting algorithms have been in common use.” — Donald Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching↩︎
“Developers made much effort to optimize hardware in order to reduce their energy consumption. However, we show in this paper that one also has to consider energy awareness in terms of software. In this study we focus on sorting algorithms, which are not only used directly by the user of a device but also very often implicitly by other algorithms. Our experiments show, that different sorting algorithms have different energy consumptions”, Bunse et. al. 2009, Exploring the Energy Consumption of Data Sorting Algorithms in Embedded and Mobile Environments ↩︎
Michael Spence (The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2001) in “Forward Thinking on economies beyond COVID-19 with Michael Spence” interviewed by McKinsey Global Institute, October 6th 2021 ↩︎