Typed array sort() does not work with negative numbers?

Hi,

I need fast array sorting to determine various quantiles from arrays of accelerometer data. I'm using bangle.js and scaling the values to an Int16Array because it seems to sort() twice as fast than a Float32Array, but I get odd results:

var arr16 = new Int16Array([2,-1,0,-2,1])
=new Int16Array([2, -1, 0, -2, 1])
arr16.sort()
=new Int16Array([-1, -2, 0, 1, 2])

Clearly it should be [-2, -1, 0, 1, 2].

arr16.sort((a,b)=>{return a-b}) gets the order correct, but significantly slower than using sort(). An Int16Array of 250 elements sorts at approximately 0.4s with sort() but takes twice as long with the comparison function.

Or is there some even faster way to sort an array?

• Jussi
  

Yay JavaScript!

MDN says (for Array.sort): The default sort order is ascending, built upon converting the elements into strings, then comparing

So amazingly [2,-1,0,-2,1].sort() is meant to be broken!

I'd stupidly thought that Int16Array.sort would behave the same as Array.sort but it seems not...

I have just fixed this, so if you try a 'cutting edge' build then it should work fine. It should even be a little faster!

Otherwise if you want to go even faster the best way would probably be to use a quicksort function in Inline C on the raw data in the Int16Array, but that is probably overkill :)

best way would probably be to use a quicksort function in Inline C on the raw data in the Int16Array

How would you iterate over array in inline C? Actually I'd love to pass typed array/arraybuffer or string to inline C and iterate over it to avoid flat strings. I know there is some stuff exported for compiled javascript but didn't know how to use it properly. I there any example? Tried to decipher some output of compiled javascript but it was too hard.

This should help? http://www.espruino.com/InlineC#direct-a­ccess

That only uses Uint8Array but it's as easy as swapping to Int16Array and then using short* in C

That's what I use already but it needs flat string and direct memory pointer. What I was thinking was directly passing JsVar of type string or typed array and iterating over it inside inline c even if it not flat string. Not super important but would solve cases with fragmented memory when E.toString does not work.

Like the sort case above, some smaller arrays are not allocated as flat buffers so to sort every array it needs some extra code like this or this

Thanks a lot, that was fast! With the cutting edge build a Float32Array sorts correctly about six times faster than with a comparison function. And just as fast as an Int16Array, so I can use full accelerometer precision.

I'd completely forgotten about the inline C option, I'll try that next if I still need more speed.

• Jussi
  

It'd be possible to extend the compiler service to include JsvIterator which would make iteration over JsVars a lot easier... However in this case for sorting it's not such a huge help as it's a nightmare having to sort via iterators.

Well, yes, accesing array element directly by integer index would be needed here too.

Not sure how fast it could be when compared to direct memory access and how much stuff needs to be exported to make it usable, when checking eg. source of E.crc32 it looks relatively easy. But when checking E.mapInPlace it can be seen there are quite a lot of methods for various types. Or in jswrap_graphics.c I see lot of usage of string iterator, also plenty of methods there.

But you mentioned JsvIterator and looks like there is generic implementation wrapping those various types here src/jsvariterator.c#L649 so maybe it could be easy after all?