Fast sorting and hot functions

Back in 2016, I was tasked to fix an app which started to falter under the weight of a growing amount of data. Profiling confirmed my hypothesis: sorting was taking too much juice.

The domain of sorting algorithms has been refined to the point of elegance, by many smart people. Most standard libraries provide a highly efficient sorting algorithm out-of-the-box. Developers only implement the logic which determines the correct order of the elements.

This is great design. The average developer is liberated from the task of implementing a sorting algorithm (after contemplating the performance implications of each one), yet can come up with any logic for the order they see fit. It's straightforward and flexible.

In JavaScript, this logic is provided in the form of a compare function. The sorting engine takes two elements at a time and calls this compare function to find out in what order those two should appear, and keeps doing that until it has deduced the definitive order of the complete set.

The drawback

As the compare function is called every time two elements are compared, it is called more frequently than you might initially expect. The Timsort implementation in V8 calls the compare function over 8000 times for 1000 (randomly-ordered) elements. This amount grows loglinearly.

In the app I was troubleshooting, items were sorted by relevance. The compare function in turn called calculateRelevance ‒ for both items ‒ to determine which should go first. This results in 100 000 relevance calculations for only ±4600 items. That's a hot function!

There are two ways to optimise hot functions: make them computationally cheaper, or cool them down. This particular function can be cooled down.

Doing the map-sort

Ideally, the app would only calculate the relevance of each item once. This can be accomplished by splitting the process into two parts: map and sort.

1. The map operation calculates the relevance.
2. The sort operation sorts based on the previously-calculated relevance.

This tweak did the job for me. Ticket closed.

The map-sort approach has proven useful over the years. We decided to mold it into an open source JavaScript library which you can use right now.

Install mapsort with npm and start doing the map-sort:

import mapSort from 'mapsort';

const sortedArray = mapSort(
	array,
	element => {
		// Return the version of "element" which is ideal for
		// sorting. This version is passed to the compare
		// function below.
	},
	(a, b) => {
		// (Optional.) Return a negative number if a comes
		// before b; a positive number if b comes before a; or
		// 0 if they are equal.
	}
);

If you encounter a bug or find the documentation lacking, please let us know. And may your projects perform smooth as butter!