Array size limited

[louisvangeldrop]

If I increase the var SORTELEMENTS to 7729 then the following code will fail if compiled to a native quicksort.exe

`"use strict";
/* This file is modified base on:

• https://browserbench.org/JetStream/wasm/quicksort.c
  */
  var SORTELEMENTS = 7728;
  var maximum = 0;
  var minimum = 65536;

function initArr(sortList) {
var seed = 74755;
for (var i = 1; i <= SORTELEMENTS; i++) {
sortList[i] = Math.random(seed);
if (sortList[i] > maximum) {
maximum = sortList[i];
}
else if (sortList[i] < minimum) {
minimum = sortList[i];
}
}
}
function quickSort(a, l, r) {
var i = l, j = r;
var w;
var idx = Math.floor((l + r) / 2);
var x = a[idx];
do {
while (a[i] < x)
i++;
while (x < a[j])
j--;
if (i <= j) {
w = a[i];
a[i] = a[j];
a[j] = w;
i++;
j--;
}
} while (i <= j);
if (l < j)
quickSort(a, l, j);
if (i < r)
quickSort(a, i, r);
}
var print = console.log;
function main() {
var sortList = new Array(SORTELEMENTS + 1);
var t1 = performance.now();
initArr(sortList);
quickSort(sortList, 1, SORTELEMENTS);
if (sortList[1] != minimum || sortList[SORTELEMENTS] != maximum) {
// print('Validate result error in quicksort');
}
print(performance.now() - t1);
}

main()
`

[Rob23oba]

I'm pretty sure array limitations are a known problem - arrays are not reallocated and therefore have a maximum capacity which is defined by the allocated size (64kb). With 4 bytes of length and 9 bytes per element you can get up to 7281 (= (65536 - 2) / 9) elements. Anything beyond that is basically undefined behaviour. In your case, you were lucky to get a bit more space but that probably overwrote something else and caused problems at some point. Thanks for reporting though.

[louisvangeldrop]

Thx for the explanation. I have done some more performance tests. I have changed the main function with "quicksort" loop.

`function main(n) {
var t1 = performance.now();
// n = 100
var sortList = new Array(SORTELEMENTS + 1);

for (var i = 0; i < n; i++) {
    sortList = new Array(SORTELEMENTS + 1);
    initArr(sortList);
    quickSort(sortList, 1, SORTELEMENTS);
    if (sortList[1] != minimum || sortList[SORTELEMENTS] != maximum) {
        // print('Validate result error in quicksort');
    }
}
print(i)
print(performance.now() - t1);

}`

If n=10, it takes 14 msec. However if n=1000 it takes 32333 msec.
I have commented out the second array initialisation "sortList = new Array(SORTELEMENTS + 1);"
If n=1000 the measured time is reduced to 608 msec.

[Rob23oba]

Yeah, the basic problem is that everytime a new array is allocated, the memory is grown by 1 wasm page (64kb). Some implementations of memory growth copy all memory over, meaning that an array allocation is basically O(size of current memory). This causes the loop to slow down gradually, resulting in ~O(n²) total.

[louisvangeldrop]

BTW The last value is the same result as running with Nodejs. A remarkable good result.

[louisvangeldrop]

What is the reason that the generated native code is so much faster than the wasm-code?

[Rob23oba]

The native implementation uses realloc for allocations, realloc probably has some optimizations to prevent copying. In contrast, memory.grow might be implemented to literally copy everything, which would obviously cause a bigger problem. Normally, this is not a problem though, since the Wasm is expected to handle memory efficiently anyways. I'm not sure but the most recent changes in Porffor might improve the results slightly due to allocating in chunks.