Производительность thrust :: redu_by_key с несколькими ключевыми повторениями

Question

Я должен выполнить сокращение массивов с помощью множества различных ключей, которые повторяются только время от времени:

keys =  {1,2,3,3,4,5,6,7,7, 8, 9, 9,10,11,...}
array = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,...}

// after reduction
result = {1,2,7,5,6,7,17,10,23,13,14}

Использование thrust::reduce_by_key (или любого другого метода сегментного сокращения) - не самый быстрый вариант здесьтак как большинство операций на самом деле являются просто копиями из одного массива в другой.

Что может быть лучше для решения этой проблемы?

Answer 1

На самом деле reduce_by_key является подходящим алгоритмом для использования здесь. Просто текущая реализация в Thrust не такая быстрая, как могла бы быть. Чтобы уточнить, нет ничего, что могло бы помешать выполнению reduce_by_key со скоростью memcpy, и я считаю, что другие реализации уже достигли этой скорости. Наш предварительный план для Thrust v1.7 предусматривает повышение производительности reduce_by_key и других алгоритмов сканирования с использованием кодов в связанном проекте back40computing .

Обратите внимание, что когда сегменты имеют (1) длинную или (2) одинаковую длину, то это можно сделать лучше, чем reduce_by_key. Например, в какой-то момент более экономично использовать дескриптор сегмента на основе смещения, чем ключи или заголовочные флаги. Однако, когда сегменты короткие (как в вашем случае) или имеют переменную длину, оптимальная реализация reduce_by_key действительно лучший инструмент для работы.