А так же о всякой фигне
На всяких курсах по программированию и на собеседованиях есть стандартная задача: есть 2 переменных a и b, нужно поменять местами их значения, подразумевается, что мы должны выпендриться и вместо использования буфера заюзать XOR или математику:
let a = 10; let b = 20; let c; // 1 способ, с использованием буфера c = a; a = b; b = c; // 2 способ, сложение/вычитание a = b + a; b = a - b; a = a - b; // 3 способ - XOR a = a ^ b; b = b ^ a; a = b ^ a;
Стандартное пояснение к этому всему - это то, что математика тащит за собой неиллюзорную проблему переполнения значений. XOR - всем хорош, кроме того, что работает исключительно с байтовыми данными и не способен работать, например, с объектами, впрочем как и математика.
Но меня интересует не это, а то, на сколько быстро/медленно эти способы работают. Давайте напишим тестик:
let a = 10; let b = 20; let c; // test - 1 let start = new Date(); for(let ii=0; ii< 10000; ii++) for(let i=0; i<1000000; i++) { a = a ^ b; b = b ^ a; a = b ^ a; } let stop = new Date(); let timeDiff = stop - start; console.log('XOR', start, stop, timeDiff); // test - 2 start = new Date(); for(let ii=0; ii< 10000; ii++) for(let i=0; i<1000000; i++) { let cc = a; a = b; b = cc; } stop = new Date(); timeDiff = stop - start; console.log('Buffer with local var', start, stop, timeDiff); // test - 2-2 start = new Date(); for(let ii=0; ii< 10000; ii++) for(let i=0; i<1000000; i++) { c = a; a = b; b = c; } stop = new Date(); timeDiff = stop - start; console.log('Buffer with global var', start, stop, timeDiff); // test - 3 start = new Date(); for(let ii=0; ii< 10000; ii++) for(let i=0; i<1000000; i++) { a = b + a; b = a - b; a = a - b; } stop = new Date(); timeDiff = stop - start; console.log('Math', start, stop, timeDiff);
Запускаем и смотрим:
И вот у нас уже есть пруфы, что обмен через буфер самый быстрый, даже если будем каждый раз создавать временную переменную. Следом идёт XOR, и потом математика, т.к. в теории, математические операции работаю медленнее, чем побитовые.
А теперь давайте всё это протестируем ещё и на С. Начнём с буфера:
// swaptest_buf.c #include <stdio.h> #include <sys/time.h> long getMicrotime() { struct timeval currentTime; gettimeofday(¤tTime, NULL); return currentTime.tv_sec * (int)1e6 + currentTime.tv_usec; } int main() { int a = 1; int b = 9; int c = 0; long startTime = getMicrotime(); // test 1 for(int ii=0; ii<10000; ii++) { for(int i=0; i<1000000; i++) { c = a; a = b; b = c; } } long stopTime = getMicrotime(); long timeDiff = stopTime - startTime; printf("a= %d, b= %d ", a, b); printf("startTime= %ld, stopTime= %ld, timeDiff= %ld ", startTime, stopTime, (timeDiff/1000)); return 0; }
Компилим и запускаем:
Результат как-то не впечатлил, в 4 раза медленнее, чем то же самое но на JS. Давайте ка обмажемся оптимизацией:
2.7 секунды против ~6 на JS. На самом деле это означает, что JS офигенно быстро работает, всего-то в 2 раза медленне, чем C с максимально оптимизацией.
Но давайте продолжим, C и XOR:
// swaptest_xor.c #include <stdio.h> #include <sys/time.h> long getMicrotime() { struct timeval currentTime; gettimeofday(¤tTime, NULL); return currentTime.tv_sec * (int)1e6 + currentTime.tv_usec; } int main() { int a = 1; int b = 9; long startTime = getMicrotime(); // test 1 for(int ii=0; ii<10000; ii++) { for(int i=0; i<1000000; i++) { a = a ^ b; b = b ^ a; a = b ^ a; } } long stopTime = getMicrotime(); long timeDiff = stopTime - startTime; printf("a= %d, b= %d ", a, b); printf("startTime= %ld, stopTime= %ld, timeDiff= %ld ", startTime, stopTime, (timeDiff/1000)); return 0; }
Немного поигравшись с оптимизацией, добиваемся ровно того же результата, что и с буфером. Различие укладывается в погрешность измерения.
Ну и C и математика:
#include <stdio.h> #include <sys/time.h> long getMicrotime() { struct timeval currentTime; gettimeofday(¤tTime, NULL); return currentTime.tv_sec * (int)1e6 + currentTime.tv_usec; } int main() { int a = 1; int b = 9; long startTime = getMicrotime(); // test 1 for(int ii=0; ii<10000; ii++) { for(int i=0; i<1000000; i++) { a = b + a; b = a - b; a = a - b; } } long stopTime = getMicrotime(); long timeDiff = stopTime - startTime; printf("a= %d, b= %d ", a, b); printf("startTime= %ld, stopTime= %ld, timeDiff= %ld ", startTime, stopTime, (timeDiff/1000)); return 0; }
Результат аналогичный.
На низком уровне, для современных процессоров без разницы что выполнять: MOV/PXOR/FISUB/FIADD, разница в пределах погрешности.
А вот на высоком уровне, как минимум в JS, математика и побитовые операции несут больше издержек, чем простой обмен значениями через буфер.
Частенько джбаскриптеры любят называть крестовиков байтоёбами. Типа трахаются они со своими memalloc, байтовыми операция, а нам оно и нахуй не нужно, у нас всё супер высокоуровневенько.
Собрались как-то 2 айтишника, и от нечего делать разобрали ямаху