1341264 - array operation is too slow for big arrays

Status: RESOLVED INCOMPLETE

(Core :: JavaScript Engine, defect, P3)

Description

[peter]

What did you do?
================
I trying js insertion-sort code. I need compare last items with some items before, get position, insert item into middle array. But faster is loop code then arr.splice.
Code:
//-- splice faster in IE
//	tmp_value = arr[1][tmp];
//	arr[1].splice(tmp, 1);	//splice is slow in FF
//	arr[1].splice(mid, 0, tmp_value);
//-- loop faster in FF
	tmp_value = arr[1][tmp];
	j = tmp;
        while (j>mid)
	   {
            arr[1][j--] = arr[1][j];
           }
        arr[1][mid] = tmp_value;


What happened?
==============
Splice is slower than loop.

What should have happened?
==========================
Both is too slow for big arrays. Why?

Is there anything else we should know?
======================================
Tip: You can big array cut to 10 smaller dynamic array. Add remove item can do faster. You can control this with one object with length of all subarrays.

You can see problem on full test time of sorting:
http://mlich.zam.slu.cz/js-sort/x/sorting3.htm
1. [+] Efectivity test 
2 Start ef. test

Comment 1

[peter]

test2
arr[m] = [8,2,5,7,9,6,4,1,3,0];
i = 4;
j = 7;

// 1 - slow
tmp = arr[m][j];
arr[m].splice(j, 1);
arr[m].splice(i, 0, tmp);

// 2 - slow
tmp = arr[m][j];
arr[m] = arr[m].slice(0, i).concat(tmp).concat(arr[m].slice(i,j)).concat(arr[m].slice(j+1));

// 3 - slow
tmp = arr[m][j];
arr[m].splice(j, 1);
arr[m] = arr[m].slice(0, i).concat(tmp).concat(arr[m].slice(i));

// 4 - fast
tmp = arr[m][j];
ii = j;
while (ii>i)
	{
	arr[m][ii] = arr[m][--ii];
cycles++;
	}
arr[m][i] = tmp;

// 5 - but i need some faster
// for sorting algorithm or i must use double array, then very fast
- remove from position A
- add to position B
- large array, 1.000.000, 18.716.356 repeats
(splite-slice-concat / only 1.000 / 8.680 = 226 ms
slice-concat / only 1.000 / 8.715 = 307 ms
splice / only 5.000 / 56.899    = 293 ms
loop / only 10.000 / 123.726 =  72ms
loop double array / 1.000.000 / 18.716.356 = 258 ms)
This is very tragedy statistics, if loop is 500-1000x faster then native functions

Comment 2

[Tooru Fujisawa [:arai]]

> You can see problem on full test time of sorting:
> http://mlich.zam.slu.cz/js-sort/x/sorting3.htm
> 1. [+] Efectivity test 
> 2 Start ef. test

it doesn't work.

> ReferenceError: TimSort is not defined  sorting3.htm:3772:1

http://mlich.zam.slu.cz/js-sort/x/timsort.js is 404.

Comment 3

[Tooru Fujisawa [:arai]]

for now, changing summary to something more specific, but I'm not sure if it describes well.

anyway, can you attach a testcase file to bugzilla?

Comment 4

[peter]

Mistake. Added file there. Sorry, i not test it. Or, you must edit code and disable timsort.

Comment 5

[peter]

XsortInsertMiddle_1a - is insertion sort with shifting in array
XsortListMerge_1a  - test (can not work good), sortListMerge_2a rewrited do one array with shifting
sortListMerge_2a - use two arrays for sort

Comment 6

[Tooru Fujisawa [:arai]]

I get this in "Stats"
how to read those numbers?

> suma time max = 70
> id alg name                  ef   1000  2000  3000   5000 10000  20000 30000 50000 100000 200000 300000 
>  0 sortJsNative              148  2.68  2.56   0.8   0.67  1.38   3.13  5.15  8.44  17.79  43.62 
>  1 sortListMerge_2a          166  1.68  2.12  0.32    0.6  1.26   2.92   4.5  7.72  18.44  37.03 
>  2 sortListMerge_3a          136  2.07  1.29  0.56   0.81  1.62   3.73  5.63  9.97  21.36  46.64 
>  3 sortListMerge2_3a         151  1.71  4.19  0.36   0.52  1.05   2.42  3.71  6.46  13.77  30.92  79.76 
>  4 sortListMerge3_3a         200  1.94   4.6  0.35   0.53  1.02   2.67  3.57  6.21  14.53  30.63  43.02 
>  5 sortSwapListMerge_2a_4xn  7    5.48  2.53  5.27  14.46 58.31 
>  6 sortSwapListMerge_2a_nx4  142  1.11   1.6  1.42   0.75  1.78   3.61  5.46 11.06  20.29   42.9 
>  9 sortTimsort               144  5.55  2.94  1.86   1.64  1.58   3.93  4.99  9.07  17.28  39.92 
> 10 sortCounting_UniqueValues 29   10.8  9.66 10.52   7.74  11.1  11.43 13.31 
> 11 sortCountingPigeonhole    27  11.99  8.17  7.69   8.64 10.74  13.34 18.15 
> 12 sortCountingRadix3LSD     36   2.69  2.19  1.55   2.73  6.44  18.06 25.19 42.93 
> 14 sortCountingRadixLSD      14   2.14  1.92  1.47   3.56 16.23  63.01 
> 15 sortCountingRadixLSB      2    9.84 18.21  35.6 102.14 
> 16 sortBubble                3    3.65 10.38 20.75  63.25 
> 17 sortBubbleDbl             3    3.81 11.39 28.72   79.4 
> 18 sortSelect                5    1.84   4.5  9.34   21.9 83.36 
> 19 sortSelect_2aDbl          3    3.82 11.22 24.28  66.42 
> 20 sortInsert_1a             7    1.55     3  6.24  14.97 64.67 
> 21 sortInsert_2a             8    1.69  3.22  5.44  13.97 57.05 
> 22 sortSwap                  4    3.21  9.12 22.61  55.97 
> 25 sortQuick2_2a             226  1.49   1.5  0.25   0.46  0.96   2.19  3.44  6.16  12.72  26.89  40.72 
> 28 XsortListMerge_1a         5    2.76  3.09  4.26  11.73 45.82 186.99 
> 31 sortSort4ListMerge_nx4_2a 147  1.57  0.62  0.76    0.7   1.5      4  5.12     9  19.13  44.14 
> 43 XsortInsertMiddle_1a      12    1.8  1.85  1.82   4.83 18.37  77.06

Comment 7

[peter]

This number is only test from my program. Limit to stop testing is 70. If suma time is bigger 70, than script continue with next algoritm. Begin sort with 1.000, end on 1.000.000
Algorithm sortInsert_1a, XsortInsertMiddle_1a, XsortListMerge_1a use shifting array. Time stop on 10.000 nember. Algoritmus sortListMerge_2a use two arrays (same as XsortListMerge_1a), stop at 200.000 numbers.

Shift / move in array is slowly. Example:
1 2 3 4 5 6 7, need move 5 after 2
1 2 3 4 6 7 - 5 delete
1 2 5 3 4 6 7 - 5 insert
Its very slow, if you this do for large array, 10.000 and more numbers.

But, i not have idea, how do it faster. only, if array is cutted to smaller subarrays.
123 | 456 | 7
123 | 46 | 7 - delete 5, change is only in array1
1253 | 46 | 7 - insert 5, change is only in array0
if length of array > double, create new subarray
125389 | 46 | 7
125 | 389 | 46 | 7
Some object must have control of subarrays id

Or, if you can help me, how can i do this algorithm faster?

---
1. my insert sort: insert one number into sorted array
7568
start = 7, tmp = 5, 5<7
next = 57, tmp = 6, 5<6, 6<7
next = 567, tmp = 8, 5<7, 6<7, 7<8
5678

2. insert into middle sort: insert one number into middle of sorted array
7568
start = 7, tmp = 5, 5<7
next = 57, tmp = 6, 6<7, 5<6
next = 567, tmp = 8, 6<8, 7<8 (compare middle, there is 6, then middle of array under 6)
5678

3. merge list, is some as insert sort. Insert sorted array into sorted array. Its 2 ways, detect sorted array, asc, desc, merge (sortListMerge_3a). But better is, if you select as sorted array length = 1
7568
7 5 6 8 - 7 sorted, 5, sorted, 6, sorted, 8 sorted, merge all 1:1 to 2
57 68 - merge all 2:2 to 4
5678
But, if array sorted ASC, DESC, faster is way sortListMerge_3a.

Comment 8

[peter]

I dont know, why pslice is slower than loop. And, why is pslice faster in IE :) I use in my sorting algoritm for now loop.

Comment 9

[Tooru Fujisawa [:arai]]

is it possible to provide simpler testcase for single algorithm with single input, that you think it's slow?

or, can you tell me which function I should look into?

Comment 10

[peter]

All is in comment1, but, i can do test page.
http://mlich.zam.slu.cz/x/test-arr-shift.htm

On this notebook write (FF 51.01):
times = , 5.055, test4, 104.32, test1, 42.17, test2, 2452.339, test3, 3091.145, 4.579 (init + tests)
bool = , 1, 1, 1, 1

Understand:
//n = 10.000, num value = 0 - 65.535 random
test4, 104.32, // splice
test1, 42.17, // loop
test2, 2452.339, 
test3, 3091.145, 

//n = 1.000, num value = 0 - 65.535 random
test4, 3.769, // splice
test1, 16.91, // loop
test2, 46.215, 
test3, 45.11

Comment 11

[Tooru Fujisawa [:arai]]

Can you please tell me the score both for Firefox and IE on your environment?
are you comparing the raw score between Firefox and IE, or the relation between splice and loop for each browser?


the difference of the score between the splice one and loop one is because the splice one moves the array elements twice,
while the most part don't have to be moved at all.

  for(i_end=arr[m].length-1,i=0;i<i_end;i++)
    {
    pos = arr[0][i];
    tmp = arr[m][pos];
    arr[m].splice(pos, 1);    // here
    arr[m].splice(i, 0, tmp); // and here
    }

so, simply the code is doing more than twice amount of operations than loop,
and 104.32 vs 42.17 in result score sounds reasonable.


you can move the array elements by Array.prototype.copyWithin, that's added in ES6 (unfortunately IE doesn't support tho)
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/copyWithin

modified code:

  for(i_end=arr[m].length-1,i=0;i<i_end;i++)
    {
    pos = arr[0][i];
    tmp = arr[m][pos];
    arr[m].copyWithin(i + 1, i, pos);
    arr[m][i] = tmp;
    }

the result:
  times = , 4.385, test4, 23.13, test1, 40.514, test2, 2356.42, test3, 3005.09, 4.525 (init + tests)
  bool = , 1, 1, 1, 1

now copyWithin takes 1/2 time than loop.


slice+concat ones just creates many new arrays, that will surely take long time.


then, can you please provide the detail about the "big arrays" case?
how is it "slow" compared to theory?

Comment 12

[peter]

No. I report, if you do something, its your problem. If i can trust google, test google :)

arr_max = 10000; // numbers in array | localhost C:\..., but in IE use new Date, not performance time

1.000 FF51: test4, 4.259, test1, 6.31, test2, 51.585, test3, 80.435
1.000 IE9: test4, 1, test1, 18, test2, 18, test3, 23

5.000 FF51: test4, 48.715, test1, 20.43, test2, 1459.395, test3, 1938.465
5.000 IE9: test4, 16, test1, 446, test2, 553, test3, 735 

10.000 FF51: test4, 182.289, test1, 57.085 
10.000 IE9: test4, 57, test1, 1729, test2, 1939, test3, 2621

50.000 IE9: test4, 4420.145, test1, 1296.56 
50.000 IE9: test4, 1439, test1, 10790 

100.000 FF51: time script limit, button alert
100.000 IE9: test4, 5110, test1, 43625

Comment 13

[Tooru Fujisawa [:arai]]

what is the number at the beginning of each line?  (like 1.000, 5.000)

Comment 14

[peter]

How can i write arr.copyWithin(target, start, end) for my problem? Copy do copy, but, i need shuffle. Example:
0123456789
x = 1 //i
y = 5 //pos; y>x (y>=x)
arr[y] = 5 // get from position 5, shift array
012346789
0|12346789 // put on position 1
0512346789 // output
0123456789 // input
I think, copy not usable here. But thanks, not know.

"what is the number at the beginning of each line?  (like 1.000, 5.000)"
In not write :)
I use my program and change value arr_max = 10000; - number of numbers.
This is table, all 4 test for FF and for IE.
Bug... "50.000 IE9:" first is always FF.
For 50.000 is 4x slower. I use 2x splice, but slow is 4x!
For 1.000 is faster splice than loop.
You not have right about 2x slower. Splice can be faster. Something block his speed for large arrays.

Comment 15

[Tooru Fujisawa [:arai]]

(In reply to peter from comment #14)
> How can i write arr.copyWithin(target, start, end) for my problem? Copy do
> copy, but, i need shuffle. Example:

> 0512346789 // output
> 0123456789 // input

the operation done here is shifting the "1234" chunk

0123456789
 ====
  |
  +-+
    |
    v
0112346789
  ====

and put "5" before it.

 |
 v
0512346789
  ====

so, in first step, you can use copyWithin, to move elements, while keeping elements after them stay there.

Comment 16

[peter]

	pos = arr[0][i];
	tmp = arr[m][pos];
	arr[m].copyWithin(pos, pos+1);
	arr[m].copyWithin(i+1, i);
	arr[m][i] = tmp;

10.000 FF51: test4, 182.289, test1, 57.085 
10.000 IE9: test4, 57, test1, 1729, test2, 1939, test3, 2621
---
10.000 FF51: test4, 181.399, test1, 61.274, [[[ test5, 132.835 ]]]

50.000 FF51: test4, 4420.145, test1, 1296.56 
50.000 IE9: test4, 1439, test1, 10790
---
50.000 FF51: test4, 4426.61, test1, 1313.635, [[[ test5, 3163.319 ]]]

Yes, copyWithin is faster than splice, but loop still fastest (for large arrays) :)

Comment 17

[Tooru Fujisawa [:arai]]

(In reply to peter from comment #16)
> 	pos = arr[0][i];
> 	tmp = arr[m][pos];
> 	arr[m].copyWithin(pos, pos+1);
> 	arr[m].copyWithin(i+1, i);
> 	arr[m][i] = tmp;

you're moving unnecessary parts, and comparing that against loop isn't fair.

you need to move only the block between i and pos.

    pos = arr[0][i];
    tmp = arr[m][pos];
    arr[m].copyWithin(i + 1, i, pos);
    arr[m][i] = tmp;