handle empty strings at array.sort(?) callback in chrome is very slow

Question

in js i have to sort a lot of array elements(100k-1kk). İn production its possible to have many blank ('') strings.

in my sort function i handle empty values - so that this values always come last .its ok.. until i have many null or undefined or blank('') values in data

if data have many nulls for example or blank strings performance is veeery slow.

And the main thing is that this fragment very slow at Chrome (at least last version for now 49.0.2623.110 m)

firefox(45.0.1) works very well (even with standart case without empty data my test x10 faster ??) just test.with chrome and firefox

P.S. i know jsperf is more preferable for that.anyway

https://jsfiddle.net/3h0gtLu2/18/

data = []

var i = 0;

while (i++ <1000){

    data.push('' + i)
}

while (i++ < 20000){

    data.push(''+i  )

}

var start = window.performance.now()
data.sort(function(a,b){

   if (a == null || a == undefined)
                        return 1;
   else if ( b == null || b == undefined)
                        return -1;
   return  (parseInt(a) - parseInt(b));
})

$('#time0').html($('#time0').html() + (window.performance.now() - start))


data = []

var i = 0;

while (i++ <1000){

    data.push('' + i)
}

while (i++ < 20000){

    data.push(null  )

}

var start = window.performance.now()
data.sort(function(a,b){

   if (a == '' || a === null || a == undefined)
                        return 1;
   else if ( a == '' || b === null || b == undefined)
                        return -1;
   return  (parseInt(a) - parseInt(b));
})


$('#time1').html($('#time1').html() + (window.performance.now() - start))


data = []

var i = 0;

while (i++ <1000){

    data.push('' + i)
}

while (i++ < 20000){

    data.push(''  )

}

var start = window.performance.now()
data.sort(function(a,b){

   if ( a == null || a == undefined)
                        return 1;
   else if ( b == null || b == undefined)
                        return -1;
   return  (parseInt(a) - parseInt(b));
})

$('#time2').html($('#time2').html() +( window.performance.now() - start))

data = []

var i = 0;

while (i++ <1000){

  data.push('' + i)
}

while (i++ < 20000){

  data.push(''  )

}

var start = window.performance.now()
data.sort(function(a,b){

   if (a == '' || a == null || a == undefined)
                        return 1;
   else if (b == '' || b == null || b == undefined)
                        return -1;
   return  (parseInt(a) - parseInt(b));
})
$('#time3').html($('#time3').html() +( window.performance.now() - start))

Answer 1

In order to ensure that your comparator will always return a logical answer for every pair of values, you'll have to add the case for when both values are empty:

data.sort(function(a,b){  
   var anull = (a == '' || a == null), bnull = (b == '' || b == null);
   if (anull && bnull)
     return 0;
   if (anull)
     return 1;
   if (bnull)
     return -1;
   return  (parseInt(a) - parseInt(b));
})

Note that you don't need an explicit compare to both null and undefined; comparing == null is exactly the same as comparing === null and === undefined.

My making sure you tell the sort algorithm that when both values are empty they can be left alone (by returning 0), you avoid it thrashing back and forth in some weird cases.

Another thing that might speed things up would be to make a single pass through the array to convert all the empty entries to some single value (maybe null; doesn't matter) and all the non-empty entries to actual numbers. That way your sort won't be paying the price of converting the strings to numbers over and over again (that is, all the calls to parseInt()). If you want the array to be strings, you can always convert it back in a subsequent single pass.