Почему сортировка 32-разрядных чисел с использованием JavaScript намного быстрее, чем сортировка 33-разрядных чисел? - PullRequest
Новая
       5

Почему сортировка 32-разрядных чисел с использованием JavaScript намного быстрее, чем сортировка 33-разрядных чисел?

1 голос
/ 24 марта 2020

Следующий код просто создает массив и сортирует его. Очень странно, что на моем Macbook Pro 2013 года для сортировки 30-битных чисел потребовалось 5,8 секунды: 

n = 10000000;
numMax = 1000000000;

console.log(`numMax is how many bits: ${Math.ceil(Math.log(numMax) / Math.log(2))}`)

console.log("\n## Now creating array");

let start = Date.now();
let arr = new Array(n);

for (let i = 0; i < arr.length; ++i) 
    arr[i] = Math.floor(Math.random() * numMax);

console.log(`took ${(Date.now() - start)/ 1000} seconds to create the array`);


console.log("\n## Now sorting it");
start = Date.now();

arr.sort((a, b) => a - b);

console.log(`took ${(Date.now() - start)/ 1000} seconds to sort`);

Но допустим, мы сделали это 34-битными числами. Теперь для запуска требуется 12,7 секунды: 

n = 10000000;
numMax = 10000000000;

console.log(`numMax is how many bits: ${Math.ceil(Math.log(numMax) / Math.log(2))}`)

console.log("\n## Now creating array");

let start = Date.now();
let arr = new Array(n);

for (let i = 0; i < arr.length; ++i) 
    arr[i] = Math.floor(Math.random() * numMax);

console.log(`took ${(Date.now() - start)/ 1000} seconds to create the array`);


console.log("\n## Now sorting it");
start = Date.now();

arr.sort((a, b) => a - b);

console.log(`took ${(Date.now() - start)/ 1000} seconds to sort`);

Вкл. NodeJS (обновление: я использую v12.14.0), разница еще больше: 5,05 секунды против 28,9 секунды. Почему разница такая большая? Если это связано с тем, что Chrome или NodeJS могут оптимизировать его с помощью 32-разрядных целых чисел по сравнению с 64-разрядными целыми числами или числами IEEE 754, потребуется ли для выполнения сравнения во время сортировки ровно один тактовый цикл ( и перемещение данных во время «фазы разделения» быстрой сортировки)? Почему это займет более 2 или даже 5 раз? Имеет ли это также какое-то отношение к подгонке всех данных во внутреннем кеше процессора и может ли внутренний кеш поддерживать 32-разрядные, но не номера IEEE 754?

1 Ответ

9 голосов
/ 24 марта 2020

V8 разработчик здесь. Вкратце: именно поэтому V8 использует «Smis» (маленькие целые числа) для внутренних целей, когда это возможно.

В JavaScript любое значение обычно может быть чем угодно, поэтому движки обычно представляют значения в некотором формате, в котором хранится информация о типе. наряду с самой ценностью. Это включает в себя цифры; поэтому число в куче - это объект с двумя полями: дескриптор типа и фактическое значение числа, которое является 64-битным двойным значением IEEE-754 на JavaScript spe c. Поскольку small-i sh, целочисленные числа особенно распространены, V8 использует специальный прием для более эффективного их кодирования: они вообще не сохраняются как объекты в куче, вместо этого значение напрямую кодируется в " pointer ", и один из битов указателя используется для обозначения его как так называемого Smi. Во всех текущих версиях Chrome V8 использует 32-битные указатели кучи, что оставляет 31 бит для полезной нагрузки Smi. Поскольку массивы чисел также довольно распространены, хранение дескриптора типа для каждого элемента довольно расточительно; вместо этого V8 имеет двойные массивы, где сам массив запоминает тот факт (только один раз!), что все его элементы являются двойными; затем эти элементы могут быть сохранены непосредственно в массиве.

Таким образом, в 30-битной версии вашего кода резервное хранилище массива представляет собой массив, заполненный Smis, и вызов функции сравнения может передать два из них напрямую. , Эта функция, в свою очередь, может быстро Smi-проверить и вытащить значения для выполнения вычитания.

В 34-разрядной версии резервное хранилище массива удваивается. Каждый раз, когда требуется вызвать компаратор, два необработанных двойных числа считываются из массива, помечаются как «числа кучи», чтобы использоваться в качестве параметров для вызова функции, а функция компаратора должна прочитать значение из кучи перед тем, как быть в состоянии вычесть их. Я на самом деле удивлен, что это примерно вдвое медленнее: -)

Чтобы немного поиграть с деталями производительности этого тестового примера, вы можете заставить массив хранить числа кучи вместо распакованных двойников. Несмотря на то, что он потребляет больше оперативной памяти и снижает производительность во многих случаях, в данном конкретном случае он фактически экономит около 10% времени, так как во время выполнения выделяется меньше недолговечного мусора. Если дополнительно принудительно вернуть результат сравнения как Smi: 

arr.sort((a, b) => a > b ? 1 : a < b ? -1 : 0);

, это экономит еще 10%.

Вкл. NodeJS, разница будет еще больше: 5.05 секунд против 28,9 секунд.

С Узлом 13.11 я не могу воспроизвести это; Я получаю почти такие же числа, как и с Chrome 81.

Chrome или NodeJS, способными оптимизировать его с помощью 32-разрядных целых чисел по сравнению с 64-разрядными целыми числами, или IEEE 754 Numbers

Возможность использования 32-разрядных целочисленных инструкций ЦП является побочным эффектом использования представления Smi, но это не является (основной) причиной разницы в производительности. Внутреннее использование 64-битных целых чисел было бы нарушением JavaScript spe c (если только механизм не был очень осторожен, чтобы обнаруживать и избегать слишком точных ).

потребовалось бы ровно один тактовый цикл для сравнения

Оценить тактовые циклы на современных процессорах очень сложно, и почти ничто не так просто, как "ровно один тактовый цикл". С одной стороны, процессоры могут выполнять (части) более одной инструкции за цикл, с другой стороны, они имеют конвейеры, что означает, что завершение выполнения только одной инструкции занимает много циклов. В частности, частое ветвление (т. Е. «Принятие решений» внутри ЦП), как обычно приходится делать алгоритмам сортировки, имеет тенденцию страдать от задержек, связанных с конвейером.

«фаза разделения» быстрой сортировки

V8 больше не использует Quicksort. Тем не менее, конечно, все алгоритмы сортировки должны перемещать данные.

Имеет ли это отношение к подгонке всех данных во внутреннем кеше процессора и может ли внутренний кеш поддерживать 32-разрядные, но не номера IEEE 754?

Кеш ЦП не поддерживает заботиться о типе данных. Размер данных (64-разрядные двойные числа в два раза больше, чем 32-разрядные целые числа) могут вызвать различия в производительности, связанные с кэшированием.

V8 способен оптимизировать тип хранилища цифр c если оптимизатор может сделать вывод, что все значения в массиве будут соответствовать этому размеру

Почти; никаких отчислений не требуется: массив оптимистично начинается с резервного хранилища Smi и обобщает его при необходимости, например, при сохранении первого двойного хранилища, хранилище переключается на двойной массив.

You вероятно, наблюдается эффект "своевременной компиляции".

Не совсем. Конечно, все современные движки JIT-компилируют ваш код, но это верно для всего кода и здесь не объясняет разницу.

...