Тяга: sort_by_key медленный из-за выделения памяти

Question

Я делаю sort_by_key с массивами ключ-значение размером 80 миллионов. Устройство GTX 560 Ti с 2 ГБ видеопамяти. Когда доступная (свободная) память перед sort_by_key 1200MBзаканчивает сортировку в 200ms, Но когда доступная память падает до 600MB, sort_by_key для тех же массивов ключ-значение занимает 1.5-3s!

Я запустил программу под Compute Visual Profiler. Я обнаружил, что метка времени GPU скачет на 1,5-3 с между последним ядром sort_by_keyи первый вызов ядра внутри sort_by_key (который являетсяRakingReduction).

Я подозреваю, что происходит выделение памяти внутри sort_by_keyдо того, как он вызовет свое первое внутреннее ядро. Память о том, что sort_by_keyпотребности доступны (даже если доступная память 600MB) так какsort_by_key работает, хотя и медленнее. Я вижу, что компьютер зависает на 1 с, когда это происходит. Я также вижу всплеск на графикефизической памяти ЦП, если я оставлю Process Explorer открытым.

Есть ли что-нибудь, что я могу сделать, чтобы сделать это sort_by_key работать так же быстро, когда доступная память меньше? Кроме того, что происходит между устройством и хостом, что вызывает скачок памяти и временное зависание?

Answer 1

thrust::sort_by_key действительно выделяет временное пространство O(N) - сортировка по основанию не является сортировкой на месте, когда она больше, чем это может сделать один мультипроцессор. Поэтому вам нужно как минимум 80M * 2 * sizeof(int) = 640MB для входных данных, плюс место для временных файлов, которое должно быть не менее 320MB для этого вида. Я точно не знаю, почему сортировка не происходит просто так, когда у вас недостаточно памяти - возможно, 600 МБ - это низкая оценка, или, возможно, упор на выполнение ЦП (я сомневаюсь, что это так).

Другая идея о снижении производительности состоит в том, что, когда вам требуется почти вся доступная память, в доступной памяти может быть небольшая фрагментация, с которой приходится сталкиваться драйверу / среде выполнения для выделения таких больших массивов, что приводит к дополнительным накладным расходам.

Кстати, как вы измеряете доступную память?