Почему моя быстрая сортировка, экспортируемая в веб-сборке, медленнее, чем реализация чистого javascript? - PullRequest
Новая
       9

Почему моя быстрая сортировка, экспортируемая в веб-сборке, медленнее, чем реализация чистого javascript?

0 голосов
/ 28 ноября 2018

Я реализовал очень наивную быструю сортировку в чистом Javascript и в C, позже экспортируемую как модуль WebAssembly.

Я сортирую 2 одинаковых массива из 10 6 целых чисел вдиапазон [0; 1000].Чистая реализация javascript занимает в среднем 780 мс, а на основе WebAssembly - 935 мс (1020 мс, если не установлены флаги оптимизации).

Почему чистая реализация javascript является самой быстрой?

Ниже 2 реализаций ввопрос:

JS: 

function swap(array, swapy1, swapy2) {
  let tmp = array[swapy1];
  array[swapy1] = array[swapy2];
  array[swapy2] = tmp;
}


function partition(array, lo, hi) {
  const pivot = array[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (array[j] < pivot) {
      if (i !== j) {
        i++;
        swap(array, i, j)
      }
    }
  }
  i++;
  swap(array, i, hi);
  return i;
}

export default function sort(array, lo, hi) {
  if (lo < hi) {
    const p = partition(array, lo, hi);
    sort(array, lo, p - 1);
    sort(array, p + 1, hi);
  }
}

C: 

void swap(int *array, int swapy1, int swapy2) {
    int tmp = array[swapy1];
    array[swapy1] = array[swapy2];
    array[swapy2] = tmp;
  }


  int partition(int *array, int lo, int hi) {
    int pivot = array[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
      if (array[j] < pivot) {
        if (i != j) {
          i++;
          swap(array, i, j);
        }
      }
    }
    i++;
    swap(array, i, hi);
    return i;
  }

  void sort(int *array, int lo, int hi) {
    if (lo < hi) {
      int p = partition(array, lo, hi);
      sort(array, lo, p - 1);
      sort(array, p + 1, hi);
    }
  }

  void quicksort(int *array, int lo, int hi, char *exp) {
   struct timeval t1, t2;
   double elapsedTime;

    gettimeofday(&t1, NULL);
    sort(array, lo, hi);
    gettimeofday(&t2, NULL);

    // compute and print the elapsed time in millisec
    elapsedTime = (t2.tv_sec - t1.tv_sec) * 1000.0;      // sec to ms
    elapsedTime += (t2.tv_usec - t1.tv_usec) / 1000.0;   // us to ms

    printf(" - 10%s entries sorted in %.0f ms\n", exp, elapsedTime);
  }

Код абонента (через объект модуля emscripten): 

WasmModule().then(wasm => {
    console.log("Monothreaded Lomuto Quicksort, WebAssembly");
    function callWasm(array, exponant) {
      let heapBuf = wasm._malloc(array.length * Uint32Array.BYTES_PER_ELEMENT);
      wasm.HEAP32.set(array, heapBuf / 4);
      wasm.ccall('quicksort', null, ['number', 'number', 'number', 'string'], [heapBuf, 0, array.length - 1, exponant]);
      wasm._free(heapBuf);
    }
    millionIntCopy = millionInt.slice();
    tenMillionIntCopy = tenMillionIntCopy.slice();
    callWasm(millionIntCopy, "\u2076");
    // callWasm(tenMillionIntCopy, "\u2077"); // stack overflow
    // callWasm(hundredMillionInt, "\u2078"); stackoverflow
  })

Полный проектможно найти здесь

...