Sometimes I have strings that (should) contain numbers (like ‘31415’) but I want/need to test them before I use them. If this happens in a loop I could start asking myself questions about performance. And if it is a long loop an a Node.js server the performance may actually matter.

For the purpose of this post I have worked with positives (1,2,3,…), and I have written code that finds the largest valid positive in an array. Lets say there are a few obvious options:

// Parse it and test it
const nv = +nc;
pos = Number.isInteger(nv) && 0 < nv;

// A regular expression
pos = /^[1-9][0-9]*$/.test(nc);

// A custom function
const strIsPositive = (x) => {
   if ( 'string' !== typeof x || '' === x ) return false;
   const min = 48; // 0
   const max = 57; // 9
   let   cc  = x.charCodeAt(0);
   if ( cc <= min || max < cc ) return false;
   for ( let i=1 ; i<x.length ; i++ ) {
     cc = x.charCodeAt(i);
     if ( cc < min || max < cc ) return false;
   }
   return true;
 }
pos = strIsPositive(nc);

Well, I wrote some benchmark code and ran it in Node.js, and there are some quite predictable findings.

It is no huge difference between the alternatives above, but there are differences (1ms for 10000 validations, on a 4th generation i5).

There is no silver bullet, the optimal solution depends on.

If all you want is validation, it is wasteful to convert (+nc). A Regular expression is faster, but you can easily beat a Regular expression with a simple loop.

If most numbers are valid, converting to number (+nc) makes more sense. It is expensive to parse invalid values to NaN.

If you are going to use the number, converting to number (+nc) makes sense (if you convert only once).

The fastest solution, both for valid and invalid numbers, is to never convert to number (but use the custom function above to validate) and find the max using string compare.

if ( strIsPositive(nc) &&
     ( max.length < nc.length ) || ( max.length === nc.length && max < nc )
   )
  max = nc; 

This is obviously not a generally good advice.

Other numeric formats

My above findings are for strings containing positives. I have tested both code that only validates, and code that use the value by comparing it.

You may not have positives but:

• Naturals, including 0, which creates a nastier regular expression but an easier loop.
• Integers, including negative values, which creates even nastier regular expressions.
• Ranged integers, like [-256,255], which probably means you want to parse (+nc) right away.
• Decimal values
• Non standard formats (with , instead of . for decimal point, or with delimiters like spaces to improve readability)
• Hex, scientific formats, whatever

In the end readability is usually more important than performance.

I will present two findings that I find strange in this post:

1. The performance of Node.js (V8?) has clearly gotten consistently worse with newer Node.js versions.
2. The standard library sort (Array.prototype.sort()) is surprisingly slow, often slower than a simple textbook mergesort.

My findings in this article are based on running a simple program mergesort.js on different computers and different node versions.

You may also want to read this article about sorting in Node.js. It applies to V8 version 7.0, which should be used in Node.js V11.

The sorting algorithms

There are three sorting algorithms compared.

1. Array.prototype.sort()
2. mergesort(), a textbook mergesort
3. mergesort_opt(), a mergesort that I put some effort into making faster

Note that mergesort is considered stable and not as fast as quicksort. As far as I understand from the above article, Node.js used to use quicksort (up to V10), and from V11 uses something better called Timsort.

My mergesort implementations (2) (3) are plain standard JavaScript. Nothing fancy whatsoever (I will post benchmarks using Node.js v0.12 below).

The data to be sorted

There are three types of data to be sorted.

1. Numbers (Math.random()), compared with a-b;
2. Strings (random numbers converted to strings), compared with default compare function for sort(), and for my mergesort simple a<b, a>b compares to give -1, 1 or 0
3. Objects, containing two random numbers a=[0-9], b=[0-999999], compared with (a.a-b.a) || (a.b-b.b). In one in 10 the value of b will matter, otherwise looking at the value of a will be enough.

Unless otherwise written the sorted set is 100 000 elements.

On Benchmarks

Well, just a standard benchmark disclaimer: I do my best to measure and report objectively. There may be other platforms, CPUs, configurations, use cases, datatypes, or array sizes that give different results. The code is available for you to run.

I have run all tests several times and reported the best value. If anything, that should benefit the standard library (quick)sort, which can suffer from bad luck.

Comparing algorithms

Lets start with the algorithms. This is Node V10 on different machines.

(ms)     ===== Numbers =====   ===== Strings =====   ==== Objects =====
         sort() merge  m-opt   sort() merge  m-opt   sort() merge  m-opt
NUC i7      82    82     61      110    81     54       95    66     50
NUC i5     113   105    100      191   130     89      149    97     72
NUC Clrn   296   209    190      335   250    196      287   189    157
RPi v3    1886  1463   1205     2218  1711   1096     1802  1370    903
RPi v2     968  1330   1073     1781  1379    904     1218  1154    703

The RPi-v2-sort()-Numbers stand out. Its not a typo. But apart from that I think the pattern is quite clear: regardless of datatype and on different processors the standard sort() simply cannot match a textbook mergesort implemented in JavaScript.

Comparing Node Versions

Lets compare different node versions. This is on a NUC with Intel i5 CPU (4th gen), running 64bit version of Ubuntu.

(ms)     ===== Numbers =====   ===== Strings =====   ==== Objects =====
         sort() merge  m-opt   sort() merge  m-opt   sort() merge  m-opt
v11.13.0    84   107     96      143   117     90      140    97     71
v10.15.3   109   106     99      181   132     89      147    97     71
v8.9.1      85   103     96      160   133     86      122    99     70
v6.12.0     68    76     88      126    92     82       68    83     63
v4.8.6      51    66     89      133    93     83       45    77     62
v0.12.9     58    65     78      114    92     87       55    71     60

Not only is sort() getting slower, also running “any” JavaScript is slower. I have noticed this before. Can someone explain why this makes sense?

Comparing different array sizes

With the same NUC, Node V10, I try a few different array sizes:

(ms)     ===== Numbers =====   ===== Strings =====   ==== Objects =====
         sort() merge  m-opt   sort() merge  m-opt   sort() merge  m-opt
 10 000     10     9     11        8    12      6        4     7      4
 15 000      8    15      7       13    14     11        6    22      7
 25 000     15    35     12       40    27     15       11    25     18
 50 000     35    56     34       66    57     37       51    52     30
100 000    115   107     97      192   138     88      164   101     72
500 000    601   714    658     1015   712    670      698   589    558

Admittedly, the smaller arrays show less difference, but it is also hard to measure small values with precision. So this is from the RPi v3 and smaller arrays:

(ms)     ===== Numbers =====   ===== Strings =====   ==== Objects =====
         sort() merge  m-opt   sort() merge  m-opt   sort() merge  m-opt
  5 000     34    57     30       46    59     33       29    52     26
 10 000     75   129     64      100   130     74       63   104     58
 20 000    162   318    151      401   290    166      142   241    132
 40 000    378   579    337      863   623    391      344   538    316

I think again quite consistently this looks remarkably bad for standard library sort.

Testing throughput (Version 2)

I decided to measure throughput rather than time to sort (mergesort2.js). I thought perhaps the figures above are misleading when it comes to the cost of garbage collecting. So the new question is, how many shorter arrays (n=5000) can be sorted in 10s?

(count)  ===== Numbers =====   ===== Strings =====   ==== Objects =====
         sort() merge  m-opt   sort() merge  m-opt   sort() merge  m-opt
v11.13.0  3192   2538   4744    1996   1473   2167    3791   2566   4822
v10.15.3  4733   2225   4835    1914   1524   2235    4911   2571   4811
RPi v3     282    176    300     144    126    187     309    186    330

What do we make of this? Well the collapse in performance for the new V8 Torque implementation in Node v11 is remarkable. Otherwise I notice that for Objects and Node v10, my optimized algorithm has no advantage.

I think my algorithms are heavier on the garbage collector (than standard library sort()), and this is why the perform relatively worse for 10s in a row.

If it is so, I’d still prefer to pay that price. When my code waits for sort() to finish there is a user waiting for a GUI update, or for an API reply. I rather see a faster sort, and when the update/reply is complete there is usually plenty of idle time when the garbage collector can run.

Optimizing Mergesort?

I had some ideas for optimizing mergesort that I tried out.

Special handling of short arrays: clearly if you want to sort 2 elements, the entire mergesort function is heavier than a simple function that sorts two elements. The article about V8 sort indicated that they use insertion sort for arrays up to length 10 (I find this very strange). So I implemented special functions for 2-3 elements. This gave nothing. Same performance as calling the entire mergesort.

Less stress on the garbage collector: since my mergesort creates memory nodes that are discarded when sorting is complete, I thought I could keep those nodes for the next sort, to ease the load on the garbage collector. Very bad idea, performance dropped significantly.

Performance of cmp-function vs sort

The relevant sort functions are all K (n log n) with different K. It is the K that I am measuring and discussing here. The differences are, after all, quite marginal. There is clearly another constant cost: the cost of the compare function. That seems to matter more than anything else. And in all cases above “string” is just a single string of 10 characters. If you have a more expensive compare function, the significance of sort() will be even less.

Nevertheless, V8 is a single threaded environment and ultimately cycles wasted in sort() will result in overall worse performance. Milliseconds count.

Conclusions

Array.prototype.sort() is a critical component of the standard library. In many applications sorting may be the most expensive thing that takes place. I find it strange that it does not perform better than a simple mergesort implementation. I do not suggest you use my code, or start looking for better sort() implementations out there right away. But I think this is something for JavaScript programmers to keep in mind. However, the compare function probably matters more in most cases.

I find it strange that Node v11, with Timsort and V8 Torque is not more of an improvement (admittedly, I didnt test that one very much).

And finally I find it strange that Node.js performance seems to deteriorate with every major release.

Am I doing anything seriously wrong?

JavaScript has two very powerful and flexible build in data structures: [] and {}. You can program rather advanced JavaScript for years without needing anything else.

Nevertheless I had a conversation about possible advantages of using a linked list (instead of an array). Linked lists are not very popular, Stroustrup himself has suggested they should be avoided. But what if you mostly do push(), pop(), shift() and unshift() and never access an item by its index? Higher order functions as map(), reduce(), filter() and sort(), as well as iterators should be just fine.

I decided to implement a Double Linked List in JavaScript making it (mostly) compatible with Array and do some tests on it. The code both of the DoubleLinkedList itself, and the unit tests/benchmarks are available.

• double-linked-list.js
• double-linked-list-tests.js

Disclaimer

This is a purely theoretical, academical and nerdy experiment. The DoubleLinkedList offers no advantages over the built in Array, except for possible performance advantages in edge cases. The disadvantages compared to Array are:

• Lower performance in some cases
• Less features / limited API
• Less tested and proven
• An extra dependency, possible longer application loading time

So, my official recommendation is that you read this post and perhaps look at the code for learning purposes. But I really doubt you will use my code in production (although you are welcome to).

Benchmarks

Benchmarks are tricky. In this case there are three kinds of benchmarks:

1. Benchmarks using array[i] to get the item at an index. This is horrible for the linked list. I wrote no such benchmarks.
2. Benchmarks testing map(), reduce(), filter(), that I wrote but that show consistently no relevant and interesting differences between built in Array and my DoubleLinkedList (my code is essentially equally fast as the standard library array code, which on one hand is impressive, and on the other hand is reason not to use it).
3. Benchmarks where my DoubleLinkedList does fine, mostly that heavily depends on push(), pop(), shift() and unshift().

The only thing I present below is (3). I have nothing for (1), and (2) shows nothing interesting.

The machines are in order an Hades Canyon i7-NUC, an old i5-NUC, a newer Celeron-NUC, an Acer Chromebook R13 (with an ARMv8 CPU), A Raspberry Pi v3, and a Raspberry Pi V2. The Chromebook runs ChromeOS, the i7 runs Windows, the rest run Linux.

My benchmarks use Math.random() to create test data. That was not very smart of me because the variation between test runs is significant. The below numbers (milliseconds) are the median value of running each test 41 times. You can see for yourself that the values are quite consistent.

The tested algorithms

The push(), pop(), shift(), unshift() tests use the array/list as a queue and push 250k “messages” throught it, keeping the queue roughly 10k messages.

The mergesort() test is a mergesort built on top of the datastructures using push()/shift().

The sort() test is the standard Array.sort(), versus a mergesort implementation for DoubleLinkedList (it has less overhead than mergesort(), since it does not create new objects for every push()).

Benchmark result

                    Node8   ============== Node 10 =====================
(ms)                NUCi7   NUCi7   NUCi5   NUC-C    R13   RPiV3  RPiV2
unshift/pop 250k  
  Array               679     649    1420    1890   5216   11121   8582
  D.L.L.                8      13      10      20     40     128    165
push/shift 250k
  Array                37      31      31      49    143     388    317
  D.L.L.               10      12      10      19     44     115    179
mergesort 50k
  Array               247     190     300     466   1122    3509   3509
  D.L.L.               81      88     121     244    526    1195   1054
sort 50k
  Array                53      55      59     143    416    1093    916
  D.L.L.               35      32      42      84    209     543    463

What do we make of this?

• For array, push/shift is clearly faster than unshift/pop!
• It is possible to implement a faster sort() than Array.sort() of the standard library. However, this may have little to do with my linked list (I may get an even better result if I base my implementation on Array).
• I have seen this before with other Node.js code but not published it: the RPiV2 (ARMv7 @900MHz) is faster than the RPiV3 (ARMv8 @1200Mhz).
• I would have expected my 8th generation i7 NUC (NUC8i7HVK) to outperform my older 4th generation i5 NUC (D54250WYK), but not so much difference.

More performance findings

One thing I thought could give good performance was a case like this:

x2 = x1.map(...).filter(...).reduce(...)

where every function creates a new Array just to be destroyed very soon. I implemented mapMutate and filterMutate for my DoubleLinkedList, that reuse existing List-nodes. However, this gave very little. The cost of the temporary Arrays above seems to be practically insignificant.

However for my Double linked list:

dll_1 = DoubleLinkedList.from( some 10000 elements )
dll_1.sort()
dll_2 = DoubleLinkedList.from( some 10000 elements )

Now
dll_1.map(...).filter(...).reduce(...)    // slower
dll_2.map(...).filter(...).reduce(...)    // faster

So it seems I thought reusing the list-nodes would be a cost saver, but it turns out to produce cache-misses instead

Using the Library

If you feel like using the code you are most welcome. The tests run with Node.js and first runs unit tests (quickly) and then benchmarks (slower). As I wrote earlier, there are some Math.random() in the tests, and on rare occations statistically unlikely events occur, making the tests fail (I will not make this mistake again).

The code itself is just for Node.js. There are no dependencies and it will require minimal work to adapt it to any browser environment of your choice.

The code starts with a long comment specifying what is implemented. Basically, you use it just as Array, with the exceptions/limitations listed. There are many limitations, but most reasonable uses should be fairly well covered.

Conclusion

It seems to make no sense to replace Array with a linked list in JavaScript (Stroustrup was right). If you are using Array as a queue be aware that push/shift is much faster than unshift/pop. It would surprise me much if push/pop is not much faster than unshift/shift for a stack.

Nevertheless, if you have a (large) queue/list/stack and all you do is push, pop, shift, unshift, map, filter, reduce and sort go ahead.

There is also a concatMutate in my DoubleLinkedList. That one is very cheap, and if you for some reason do array.concat(array1, array2, array3) very often perhaps a linked list is your choice.

It should come as no surprise, but I was suprised that sort(), mergesort in my case, was so easy to implement on a linked list.

On RPiV2 vs RPiV3

I have on several occations before written about that the 900MHz ARMv7 of RPiV2 completely outperformes the 700MHz ARMv6 of RPiV1. It is about 15 times faster, and not completely clear why the difference is so big (it is that big for JavaScript, not for C typical code).

The RPiV3 is not only 300MHz faster than the RPiV2, it is also a 64-bit ARMv8 cpu compared to the 32-bit ARMv7 cpu of RPiV2. But V3 delivers worse performance than V2.

One reason could be that the RPi does not have that much RAM, and not that fast RAM either, and that the price of 64-bit is simply not worth it. For now, I have no other idea.

References

An article about sorting in V8: https://v8.dev/blog/array-sort. Very interesting read. But I tried Node version 11 that comes with V8 version 7, and the difference was… marginal at best.

The workhorse of many (JavaScript) programs is sort(). When you want to sort objects (or numbers, actually) you need to supply a compare-function. Those are nice functions because they are very testable and reusable, but sorting is also a bit expensive (perhaps the most expensive thing your program does) so you want them fast.

For the rest of this article I will assume we are sorting som Order objects based status, date and time (all strings).

The naive way to write this is:

function compareOrders1(a,b) {
  if ( a.status < b.status ) return -1;
  if ( a.status > b.status ) return  1;
  if ( a.date   < b.date   ) return -1;
  if ( a.date   > b.date   ) return  1;
  if ( a.time   < b.time   ) return -1;
  if ( a.time   > b.time   ) return  1;
  return 0;
}

There are somethings about this that is just not appealing: too verbose, risk of a typo, and not too easy to read.

Another option follows:

function cmpStrings(a,b) {
  if ( a < b ) return -1;
  if ( a > b ) return  1;
  return 0;
}

function compareOrders2(a,b) {
  return cmpStrings(a.status,b.status)
      || cmpStrings(a.date  ,b.date  )
      || cmpStrings(a.time  ,b.time  );
}

Note that the first function (cmpStrings) is highly reusable, so this is shorter code. However, there is still som repetition, so I tried:

function cmpProps(a,b,p) {
  return cmpStrings(a[p], b[p]);
}

function compareOrders3(a,b) {
  return cmpProps(a,b,'status')
      || cmpProps(a,b,'date')
      || cmpProps(a,b,'time');
}

There is something nice about not repeating status, date and time, but there is something not so appealing about quoting them as strings. If you want to go more functional you can do:

function compareOrders4(a,b) {
  function c(p) {
    return cmpStrings(a[p],b[p]);
  }
  return c('status') || c('date') || c('time');
}

To my taste, that is a bit too functional and obscure. Finally, since it comes to mind and some people may suggest it, you can concatenate strings, like:

function compareOrders5(a,b) {
  return cmpStrings(
    a.status + a.date + a.time,
    b.status + b.date + b.time
  );
}

Note that in case fields “overlap” and/or have different length, this could give unexpected results.

Benchmarks

I tried the five different compare-functions on two different machines and got this kind of results (i5 N=100000, ARM N=25000), with slightly different parameters.

In these tests I used few unique values of status and date to often hit the entire compare function.

(ms)   i5    i5    ARM
#1    293   354    507
#2    314   351    594
#3    447   506   1240
#4    509   541   1448
#5    866   958   2492

This is quite easy to understand. #2 does exactly what #1 does and the function overhead is eliminated by the JIT. #3 is trickier for the JIT since a string is used to read a property. That is true also for #4, which also requires a function to be generated. #5 puts two strings on the stack needlessly when often only the first two strings are needed to compare anyway.

Conclusion & Recommendation

My conclusion is that #3 may be the best choice, despite it is slightly slower. I find #2 clearly preferable to #1, and I think #4 and #5 should be avoided.