В Rust при сортировке на месте перемещение элементов по вектору станет дорогим?
Я стараюсь использовать Vec::sort_unstable_by_key периодически. Насколько я понимаю, это сортировка на месте; Таким образом, он перемещает элементы внутри вектора.
Я думаю:
Если размер элемента большой, станет ли он дорогим? В этом случае поможет ли упаковка больших данных в указатели типа Rc, а затем сохранение указателей в векторе?
Box! Да, определенно лучше, чем Rc. К сожалению, в моем случае «ключевые функции» для сортировки меняются. Я считаю, что BTreeSet с этим не работает.
Ответы 1
Копирование памяти занимает, по очень грубым оценкам, около 0,04 наносекунды на байт. Источник.
Полный пропуск кэша в ОЗУ занимает около 65 наносекунд. Источник.
Обе эти оценки являются очень приблизительными, но они должны дать вам представление о разнице в порядке величин.
Если вы используете косвенность через Box или Rc, обмен станет очень быстрым, но на самом деле проверка содержимого для его сравнения потребует выборки удаленной области из памяти, которая с большей вероятностью пропустит кеш. Также вам нужно проверять данные гораздо чаще, чем менять местами объекты для сортировки массива.
Таким образом, данные должны быть очень большими, прежде чем использование Box или Rc станет оправданным. Обычно я начинаю рассматривать возможность использования косвенности, если размер объекта превышает несколько килобайт. Оптимизация очень сложна, и единственный способ узнать, что быстрее для вашего конкретного случая использования, — это измерить.
Вместо Box вы можете использовать индексы для Vec, это будет одновременно кэшироваться и быстро сортироваться.
Вы имеете в виду, что использование другого Vec удерживает индексы оригинала Vec для сортировки; Затем отсортируйте вектор индексов на основе элементов, хранящихся в исходном векторе, на который указывают индексы? Но будет ли проверка значения в исходном векторе по индексам быстрее, чем Box?
@ChayimFriedman Вы также можете использовать Vec<&T> для аналогичного эффекта. Теоретически это увеличит скорость, поскольку объекты будут храниться близко друг к другу, что увеличит вероятность попадания в кэш за счет выделения целого нового вектора. Вам нужно будет измерить, чтобы увидеть, стоит ли это того.
А если вы идете по пути индексов и векторов, обратите внимание на sort_by_cached_key, который сделает это за вас. (Но для этого также требуется ключ сортировки, и он также будет храниться во временном векторе.)
@yushizhao Да, так и будет, потому что элементы будут близки и выбраны вместе по памяти.
@mousetail Вы ссылаетесь на источники своих чисел, но они вообще не подтверждают ваши цифры? Промах кэша по ОЗУ: 65 нс. memcopy: 17 ГБ/с → 0,06 нс/Б. Кроме того, цифры не очень актуальны, нет автоматического значения Box → полный промах в кэше или Vec → линейный доступ, нет промахов в кэше. Наконец: в зависимости от размера объекта и шаблонов доступа подход целочисленного индекса-Vec может вообще не дать больших преимуществ по сравнению с Box с точки зрения локальности кэша.
@Caesar Numbers Конечно, Box не гарантирует промаха в кеше, и непрерывное хранилище не гарантирует попадания в кеш. Я никогда не утверждал, что так будет. Это просто более вероятно.
В этом случае вам понадобится Box, а не Rc. И да, это может стать дорогостоящим, но вы не можете предсказать, будет ли это дороже, чем косвенность, введенная блоком, вам нужно будет это измерить. Кроме того, если вы периодически что-то сортируете, другим вариантом может быть использование
BTreeSet.