Julia vs R vs Python: производительность сортировки строк + незавершенное путешествие к оптимизации производительности Джулии

Автор оригинала: ZJ.

Сортировка строк теперь быстрее в Julia

намного более быстрый новый алгоритм сортировки строк radix sort был опубликован в рамках Sorting Lab.jl . Он может сортировать строки в 3 раза быстрее! Это особенно эффективно для строк фиксированной длины.

Пример использования

# run once to install SortingLab
# Pkg.add("SortingLab") 

using SortingLab
# generate a random id vector with 1 million unique IDs
idstrvec = rand("id".*dec.(1:1_000_000,10), 100_000_000)

# sort the string vector 
idstrvec_radixsorted = radixsort(idstrvec)
issorted(idstrvec_radixsorted) #true

# sort the original vector in-place
radixsort!(idstrvec)
issorted(idstrvec) #true

Бенчмарки против R против Python

Производительность сортировки строк-это тонкая тема. Похоже, что Джулия самая быстрая (как показано на фото с обложки). Однако история может измениться, если мы рассмотрим еще пару синтетических примеров.

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

R является самым быстрым, если есть много значений дубликатов (или, другими словами, если отношение уникальных строк к строкам невелико, например, 1:100) и если есть большое количество элементов; Джулия иногда может превзойти R, даже если есть много дубликатов, если количество элементов для сортировки невелико (например, 10 миллионов); это показано в приведенных ниже тестах.

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

Код бенчмаркинга

Приведенный ниже код для Julia, R и Python-это здесь . Код R и Python был адаптирован со страницы data.table group-by benchmarks ).

Производительность сортировки по строковому вектору длиной 10 миллионов

Путешествие к более быстрой сортировке строк в Джулии

Если вас интересует путь, ведущий к реализации сортировки по основанию строк, читайте дальше. Вы можете найти эти моменты интересными

• Как загрузить базовые байты из строк?
• Некоторые указания об арифметике указателей в Джулии

Мотивация и предыдущее состояние сортировки строк в Julia

Возможность быстрой сортировки строк является ключевым элементом современных манипуляций с данными. Хотя часто признается, что, когда мы сортируем вектор строк, на самом деле мы хотим сгруппировать их; но все же полезно иметь возможность быстро сортировать строки.

Однако первоначальное исследование показало, что сортировка строк в Julia происходит медленно по сравнению с R при сортировке строк с большим количеством повторяющихся значений. Это, вероятно, сравнение Джулии с икрой, но с точки зрения пользователя, проще говоря, им, вероятно, все равно. Падение производительности в 3 раза – это не фантастическая история для Джулии. Это должно быть быстро, верно? Кроме того, Python также работает медленно (см. Тесты выше), и, надеюсь, pandas 2 может помочь решить эту проблему .

К более быстрой сортировке строк

Имея это в виду, я хотел выяснить, может ли Джулия также быстро выполнять сортировку строк; по крайней мере, приблизиться к производительности R в сортировке строк. После некоторых исследований я обнаружил, что R использует сортировку по радиусу для сортировки строк, поэтому естественной отправной точкой является реализация сортировки по радиусу строки Julia.

Большинство моих исследований указывают на какой-то вариант сортировки радикалов наиболее значимых цифр (MSD) для строк, см. 1 и 2 . Кроме того, существует сортировка по радиусу LSD для некоторых типов битов (но не строк), уже реализованных в SortingAlgorithms.jl . Поэтому я реализовал алгоритмы сортировки по радиусу как для MSD, так и для LSD-разновидностей.

О сортировке по радиусу

Я нашел эти конспекты лекций хорошим введением в сортировку строк по основанию. Несмотря на то, что исходный код написан на языке Си, его можно легко перевести построчно на язык Джулии.

Ниже приведены несколько проблем, с которыми я столкнулся при разработке алгоритмов сортировки строк radix.

Проблема 1: доступ к базовым байтам

Для выполнения сортировки по основанию необходим доступ к базовым байтам. Одним из способов загрузки байта n – го символа в строку является использование единицы кода(s, n) , например

charAt(s::String, n) = @inbounds codeunit(string, n)

Я рассчитал время выше, и, по моим расчетам, это будет слишком медленно, чтобы соответствовать производительности R.

После долгих экспериментов я обнаружил, что загрузка 8 байтов за раз почти так же быстра, как загрузка всего 1 байта, так что это стало моим предпочтительным подходом. Например, см. Ниже

# `pointer` returns a pointer to `UInt8` (i.e. a byte) that points to the first byte of a string
# `Ptr{UInt64}` converts the pointer to a pointer of `UInt64` and so `unsafe_load`
# will load exactly 8 bytes (64 bits) starting from the location pointed at by the pointer
load_8bytes(s) = s |> pointer |> Ptr{UInt64} |> unsafe_load

В этом подходе также есть две подзадачи: Подзадача 1: строка короче 8 байт Нужно быть осторожным в том, как обращаться с более коротким случаем. Один из подходов состоит в том, чтобы в любом случае загрузить 8 байт и установить ненужные биты в 0; этот подход может привести к попытке доступа к памяти, недоступной для программы, и вызвать сбой. Это было указано мне во время процесса проверки кода. Судя по моему тестированию, загрузка 8 байт для строк более короткой длины в большинстве случаев хороша, но мы все равно должны быть осторожны, чтобы не разбить программу. В настоящее время для его решения необходимо проверить, меньше ли длина 8 байт, а затем использовать более медленный загрузчик.

Есть больше возможностей для оптимизации. Например, в большинстве случаев только небольшая часть строк хранится в местах, где загрузка 8 байт вызовет проблему. Чтобы лучше понять это, нам нужно некоторое понимание того, как организована память; ниже приведено мое обобщенное понимание

• данные загружаются в память страницами определенного размера (на большинстве 64-битных машин размер будет не менее 4 кб)
• при загрузке байтов вы можете загружать из любого места на одной странице, но загрузка через границы страницы может привести к сбою программы
• поэтому только те строки, которые находятся на расстоянии 8 байт или меньше от границы страницы, вызовут проблему
• как указал член дискурса Джулии @stevengj, можно проверить, находится ли строка s вблизи границы, используя (UInt(указатель(ы)) & 0xfff) > 0xff8

Если вы хотите узнать больше о компьютерной памяти, я рекомендую brilliant.org курс компьютерной памяти .

Наконец, стоит помнить, что самая медленная часть алгоритма сортировки заключается не в загрузке байтов, а в самой сортировке.

Подзадача 2: строка длиннее 8 байт Если строка длиннее 8 байт, я могу сортировать вектор строки итеративно по 8 байт за раз. Существуют хорошо известные методы для выполнения как в вариантах MSD, так и в вариантах LSD типа radix, которые я не буду здесь повторять.

Проблема 2: Перестановка строк при сортировке радикса

Как только я загрузил базовые байты в вектор байтов, я могу отсортировать вектор байтов с помощью сортировки по радиусу, что довольно быстро. Однако мне также нужно одновременно переставить исходный вектор-строку. Для этого я закодировал sorttwo!(bytesvec, stringvec) функция, которая сортирует байт-вектор bytesvec и переставляет строковый вектор таким же образом bytesvec переставляется в процессе сортировки. Сортировка два! функция-это простая адаптация существующей функции сортировки по радиусу в Алгоритмах сортировки.jl .

Другое применение сортировка два! находится в реализации более быстрого sortperm для строк. Для пользователей R sortperm является эквивалентом R order .

Реализация алгоритмов MSD и LSD

Я реализовал вариант MSD и вариант LSD. Из моих исследований часто следует, что алгоритмы MSD лучше работают для строк переменной длины, а алгоритмы LSD лучше всего работают для алгоритмов фиксированной длины.

Некоторые даже утверждают, что ЛСД не работает с вектором строк переменной длины. Я думаю, что это не так, поскольку вы можете представить пустой байт с 0 (хотя технически это null ). Например, если я загружаю строку “abc” с помощью 8-байтового загрузчика, она становится в шестнадцатеричной форме, 0x6162630000000000 где 61 , 62 и 63 являются шестнадцатеричным представлением кодов ASCII “a”, “b” и “c”. Затем я могу отсортировать это с помощью сортировки по радиусу вместе с другими строками. Однако является ли это наиболее эффективным-это реальный вопрос, на который у меня нет ответа.

Моя реализация сортировки MSD radix основана на 3-полосной быстрой сортировке radix, которая хорошо известна и документирована в 1 и 2 уже.

Судя по моему бенчмаркингу, моя реализация MSD не так эффективна, как алгоритм LSD, даже для строк переменной длины. Это кажется странным, поскольку большинство моих исследований указывают на то, что MSD более эффективен, чем ЛСД. Это может быть признаком того, что моя реализация сортировки MSD radix является неоптимальной.

На самом деле, почему R так быстро? Открытие окон для других подходов

Ряд людей указали, что R использует форму интернирования строк для хранения своих строк. Мое понимание того, как это работает, выглядит следующим образом: например, рассмотрим a("abcdefghi", "abcdefghi") – это вектор из двух строк, содержащих одно и то же содержимое, поэтому a[1] и a[2] просто укажите на одно место для хранения “abcdefghi” вместо хранения двух копий одной и той же строки.

Ниже приводится выдержка из R’s ?сортировка документация

Реализация [radix sort] на порядки быстрее, чем сортировка оболочки для символьных векторов, отчасти благодаря умному использованию внутренней таблицы CHARSXP.

что приводит меня к поиску документации по CHARSXP , в которой говорится

Существует глобальный кэш для CHARSXPs, созданный mkChar — кэш гарантирует, что большинство CHARSXPs с одинаковым содержимым совместно используют хранилище.

Если одна и та же строка хранится только один раз, это может привести к повышению эффективности использования пространства. Кроме того, что еще более важно, можно использовать это (печень) для создания более эффективных алгоритмов.

Кроме того, это может упростить групповые операции. Если пользователь знает, что все строки с одинаковым содержимым имеют один и тот же указатель, то мы можем просто сгруппировать по указателю, который имеет фиксированный размер и является числовым и, следовательно, быстрее сортировать и группировать.

Однако по умолчанию у Джулии нет интернированных строк (хотя есть пакет InternedStrings.jl ), и поэтому эти типы оптимизации недоступны, и поэтому Джулии может быть трудно соответствовать производительности сортировки строк R во всех случаях. Но это открывает альтернативный взгляд на вещи: R займет больше времени, чтобы загрузить эти строки, поскольку им также необходимо загрузить их в глобальный кэш. Это более длительное время загрузки привело к более высокой скорости сортировки. Поэтому в Julia может быть возможно создать структуру данных, которая имитирует поведение R и приводит к более эффективной сортировке. Поэтому в настоящее время сравнение скорости сортировки R с Джулией не является полной историей, хотя на первый взгляд R выглядит быстрее, и с точки зрения пользователей (после загрузки данных) R по-прежнему является королем скорости.

Будущие работы

Очевидный способ ускорить процесс-использовать параллельные методы, эта статья “Инженерная параллельная сортировка строк для многоядерных систем” является лучшим результатом Google для “параллельной сортировки строк”. Его результаты показывают, что “многоключевая быстрая сортировка” (многовариантный вариант сортировки MSD radix (quick), которую я перенес) является самым быстрым алгоритмом последовательной сортировки, который они нашли реализованным в C/C++. Это стоит исследовать. Они также указали на свой параллельный вариант, называемый Супер Скалярная сортировка выборки строк ( S 5 S^5 S 5 ), что является эффективным для многоядерных систем.

Как уже обсуждалось, моя реализация сортировки MSD string radix может быть неоптимальной. Эта статья указывает на реализации Rantala на C/C++ сортировки string radix как высокое качество, так что это может быть хорошим эталоном для сравнения.

Я экспериментировал с преобразованием строк в интернированные строки с помощью пакета Interned Strings.jl и обнаружил, что производительность слишком низкая. Для процесса преобразования возможна оптимизация, поэтому мы проверим, как только эти оптимизации будут выполнены, чтобы увидеть, сможем ли мы использовать внутренние строки для создания еще более быстрых сортировок строк.