[Перевод] Меняем std::sort для Google
Мы меняемstd::sort в библиотеке libcxx проекта LLVM. В этой статье мы подробно расскажем о том, как мы пришли к этому решению и какими будут возможные последствия, о багах, с которыми вы можете столкнуться в примерах из open source. Мы покажем несколько бенчмарков, объясним, почему вообще это сделали и чего это нам стоило, на примерах закона Хайрама и обучения с подкреплением. Все изменения выложены в open source, поэтому я свободно могу о них рассказывать.
Эта статья разделена на три части. Первая — это подробная история недавнего прошлого сортировки в стандартных библиотеках C++. Вторая расскажет об усилиях, необходимых для перехода от одного алгоритма сортировки к другому с различными багами. В третьей мы объясним выбранную нами реализацию и все внесённые нами оптимизации.
Алгоритмы сортировки активно исследовались ещё с самого зарождения computer science1. В частности, люди пытались оптимизировать среднее количество сравнений в наихудшем случае и в определённых случаях, например, при частично отсортированных данных. Существует даже алгоритм сортировки, основанный на машинном обучении2 — он пытается прогнозировать позицию, где должны находиться элементы, и его бенчмарки весьма впечатляют! Очевидно одно — алгоритмы сортировки эволюционируют даже сейчас, улучшая постоянные коэффициенты и снижая количество сравнений.
Во всех языках программирования есть вызовы сортировки, и выбор используемого алгоритма зависит от библиотеки. О различиях в языках мы поговорим позже. Споры о том, какая сортировка лучше, не прекращаются на Hackernews3, в статьях4 и репозиториях5.
Дональд Кнут сказал:
Было бы здорово, если бы только один-два способа сортировки доминировали над остальными, вне зависимости от сферы применения и используемого компьютера. Однако, на самом деле каждый способ имеет собственные любопытные достоинства. […] Поэтому мы должны помнить практически все алгоритмы, потому что в некоторых случаях они оказываются наилучшими. — Дональд Кнут, «Искусство программирования», том 3
История C++
std::sort появилась в C++ с момента изобретения Александром Степановым9 так называемой «STL», а в стандарте C++ того времени была интересная инновация под названием «сложность». В то время сложность была установлена на At the time the complexity равной $inline$O (n \log n)$inline$ сравнений в среднем. Из курсов Computer Science мы знаем, что quicksort имеет $inline$O (n \log n)$inline$ сравнений в среднем, правильно? Этот алгоритм впервые появился в оригинальной STL.
Как была реализована первая std::sort?
В ней использовался простой quicksort с медианой 3 (медиана от (первого, среднего, последнег) элементов). Если рекурсия затрагивает менее 16 элементов, она прекращается и в конце использует сортировку вставками, поскольку считается, что она быстрее для небольших массивов.
Вы видите последний этап, на котором она пытается «сгладить» неточные блоки размера 16.
Небольшая проблема quicksort
Да, действительно правда, что quicksort в среднем имеет сложность $inline$O (n \log n)$inline$, однако C++ STL может принимать третий параметр, называемый функцией comp:
Это даёт нам возможность самомодифицирования массива, или, иными словами, принятия решений в процессе вызова функции comp и внедряет наихудшую временную сложность для любых данных. Ниже мы объясним данный код:
int quadratic(int size) {
int num_solid = 0;
// gas означает "бесконечность"
int gas = size + 1;
int comparison_count = 0;
std::vector indices(size);
std::vector values(size);
// индексы - это 0, 1, …, size
// все значения бесконечны
for (int i = 0; i < size; ++i) {
indices[i] = i;
values[i] = gas;
}
// Принудительно обеспечиваем равномерное распределение входящих данных!
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(indices.begin(), indices.end(), g);
sort(indices.begin(), indices.end(), [&](int x, int y) {
comparison_count += 1;
// Если оба бесконечны, задать левое.
// В противном случае gas всегда больше
if (values[x] == gas && values[y] == gas) {
values[x] = num_solid++;
return true;
} else if (values[x] == gas) {
return false;
} else if (values[y] == gas) {
return true;
} else {
return values[x] < values[y];
}
});
return comparison_count;
}
Если мы рассмотрим любой алгоритм быстрой сортировки со следующей семантикой:
- Находим некий опорный $inline$X$inline$ среди $inline$C$inline$ (константа).
- Разделяем по опорному элементу, выполняем рекурсию с обоих сторон.
то значение «gas» обозначает неизвестное, бесконечность; значение левого элемента присваивается только при сравнении двух неизвестных элементов, и если один из элементов gas, то он всегда больше.
На первом шаге выберем какой-то опорный элемент из не более чем $inline$C$inline$ элементов. При разделении все остальные $inline$n — C$inline$ элементов будут справа от опорного.
На шаге $inline$i$inline$ мы знаем, что отношение не более чем $inline$C\cdot i$inline$ элементов и все $inline$n-C\cdot i$inline$ элементов по-прежнему будут находится справа. Возьмём $inline$i$inline$ равным $inline$n/2C$inline$, и уже получим квадратичное поведение.
Если мы запустим этот код с оригинальной STL10, то точно получим квадратичное количество сравнений.
int main(int argc, char** argv) {
std::cout << "N: comparisons\n";
for (int i = 100; i <= 6400; i *= 2) {
std::cout << i << ": " << quadratic(i) << "\n";
}
return 0;
}
/*
N: сравнения
100: 2773
200: 10623
400: 41323
800: 162723
1600: 645523
3200: 2571123
6400: 10262323
*/
Какую бы рандомизацию мы не вносили, даже quicksort-реализация std::sort в среднем квадратична (с учётом произвольного компаратора) и реализация, строго говоря, не будет соответствовать требованиям.
Показанный выше пример не пытается ничего доказать и является довольно искусственным, хоть и существуют некоторые проблемы с формулировками в стандарте относительно «среднего» случая.
Отход от квадратичного поведения
Тестирование наихудшего случая Quicksort впервые было проведено Дугласом Макилроем11 в 1998 году, оно называлось «Antiquicksort». В конечном итоге оно повлияло на то, чтобы перейти к сложности std::sort $inline$O (n \log n)$inline$ для наихудшего случая, а не среднего, и это изменение было внесено в стандарт C++11. Это решение частично было вызвано тем, что существует множество эффективных сортировок со сложностью наихудшего случая $inline$O (n \log n)$inline$.
Однако на этом история не закончилась.
Соответствуют ли требованиям современные стандартные библиотеки C++?
В стандарте C++ есть не так много мест с формулировкой «в среднем». Ещё одним примером этого является вызов std::nth_element.
Что такое std::nth_element?
Вы можете догадаться, что функция находит n-ный элемент в интервале. Если конкретнее, то std::nth_element(first, nth, last, comp) — это алгоритм частичной сортировки, изменяющий порядок элементов в интервале следующим образом:
- Элемент, на который указывает
nth, меняется на тот элемент, который находится в этой позиции, если[first, last)отсортированы. - Все элементы до этого нового элемента
nthменьше или равны элементам после нового элементаnth.
Вы видите, что в сложности по-прежнему указывается «в среднем».
Это решение используется из-за применяемого алгоритма 12. Однако этот алгоритм восприимчив к одинаковым трюкам в реализациях и GNU, и LLVM.
В версии LLVM/clang он очевидно деградирует до квадратичного поведения, в версии GNU $inline$2 \cdot n \cdot \log_2 n$inline$ при $inline$n = 1600,3200,6400$inline$ приблизительно равен $inline$34060, 74520, 161841$inline$, что очень близко к указанным числам. Если внимательно прочитать реализацию13, то можно увидеть, что fallback-алгоритм использует выбор кучи, создавая кучу и извлекая из неё элементы. А известно, что извлечение из кучи является логарифмическим.
Однако для нахождения элемента nth существует не так много линейных алгоритмов наихудшего случая, один из них — это алгоритм median of medians16, имеющий очень плохую константу. Нам потребовалось около двадцати лет, чтобы найти что-нибудь действительно подходящее, и это удалось Андрею Александреску14. В моём посте об алгоритмах выбора эта тема изложена достаточно подробно (и есть реализация, созданная самим Андреем!). Мы выявили большое ускорение на реальных данных для реальных SQL-запросов типа SELECT * from table ORDER BY x LIMIT N.
Miniselect: Practical and Generic Selection Algorithms
Что случилось с std::sort?
В ней начали использовать интроспективную сортировку, или introsort, поверх слишком многих уровней quicksort, если конкретнее, то $inline$2 \log_2 n$inline$, и откатываться к пирамидальной сортировке (heap sort). Даже в Википедии есть хорошие ссылки15 о реализациях introsort.
Вот наихудший случай сортировки introsort для реализации GNU:
История LLVM
Когда LLVM попытался собрать версию STL для C++0x, Ховард Хиннант создал презентацию6 о том, как проходит реализация. В то время мы нашли очень интересные бенчмарки и всё больше бенчмарков сортировок на разных паттернах данных.
Слайд Ховарда Хиннанта о сортировке, 2010 год
Это заставило нас задуматься о том, что делает сортировку успешной и эффективной. Очевидно, что не все данные случайны и в продакшене возникают некоторые паттерны, насколько важно их балансировать и распознавать?
Например, даже в Google, поскольку мы используем много protobuf, встречаются частые вызовы std::sort, исходящие от библиотеки7, сортирующей все метки представленных в сообщении полей:
struct FieldNumberSorter {
bool operator()(const FieldDescriptor* left,
const FieldDescriptor* right) const {
// Сортируем по порядку меток.
return left->number() < right->number();
}
};
void Reflection::ListFieldsMayFailOnStripped(
const Message& message, bool should_fail,
std::vector* output) const {
// Обходим все поля по порядку их объявления.
for (int i = 0; i <= last_non_weak_field_index; i++) {
const FieldDescriptor* field = descriptor_->field(i);
if (FieldSize(message, field) > 0) {
output->push_back(field);
}
}
// Сортируем по их номеру метки
std::sort(output->begin(), output->end(), FieldNumberSorter());
} message GoogleMessage2 {
// тип имя метка
// vvvvvv vvvvvv vvv
optional string field1 = 1;
optional int64 field3 = 3;
optional int64 field4 = 4;
optional int64 field30 = 30;
optional bool field75 = 75 [default = false];
// Немного не по порядку, 1, 3, 4, 30, 75, 6, 2
optional string field6 = 6;
optional bytes field2 = 2;
// …
}
Это первое важное наблюдение: нам нужно распознавать «почти отсортированные» паттерны, когда они встречаются. Очевидными случаями являются возрастание/убывание, небольшие примеси их, а также множественные последовательные серии увеличивающихся или уменьшающихся значений. TL; DR; нам не удалось достичь в этом особо хороших результатов, однако большинство современных алгоритмов может распознавать самые очевидные случаи.
Теория: presortedness
Показатель Presortedness впервые был формально описан в 8:
Условие 1 — это нормализатор, условие 2 указывает, что нас должны интересовать только сравнения, а не элементы, условие 3 показывает, что если мы можем отсортировать надпоследовательность, то мы сможем и отсортировать подпоследвательность за меньшее количество сравнений, условие 4 — верхний предел для сортируемых частей: вы должны иметь возможность отсортировать $inline$XY$inline$, если можете отсортировать $inline$Y$inline$, условие 5 — более обобщённый верхний предел — вы должны иметь возможность найти позицию $inline$a$inline$ за линейное количество сравнений.
Существует множество оценок presortedness, например
- m01: 1 — если не отсортировано, 0 — если отсортировано. Довольно глупая оценка.
- Block: количество элементов в последовательности, за которыми не следует тот же элемент в отсортированной последовательности.
- Mono: минимальное количество элементов, которое нужно удалить из X, чтобы получить отсортированную подпоследовательность, что соответствует |X| минус размер наибольшей неуменьшающейся подпоследовательности X.
- Dis: максимальное расстояние, определяемое инверсией.
- Runs: количество неуменьшающихся изменений в X минус один.
- И т. д.
Некоторые оценки presortedness лучше других, то есть если существует алгоритм, оптимальный для определённой оценки (под оптимальностью понимается, что количество сравнений $inline$T (X)$inline$ для всех входящих $inline$X$inline$ ведёт себя логарифмически для количества входящих данных не больше значения оценки: $inline$T (X) \leq C\max (X, \log|\mathrm{below}(X, M)|)$inline$), то он также оптимален для другой. И здесь теория начинает сильно расходиться с реальностью. В теории найдена хорошая «общая» оценка presortedness, однако она очень сложна и мы не будем её рассматривать в этой статье.
NeatSort — A practical adaptive algorithm
К сожалению, среди всех приведённых выше оценок только Mono, Dis и Runs выполянются за линейное временя (другие за $inline$\Omega (n \log n)$inline$ и остаётся под вопросом, имеют ли они меньшую сложность). Если вы хотите вычислить некоторые из этих оценок, то нужно много сэмплов или добавить дополнительное $inline$\Omega (n \log n)$inline$ в саму сортировку, что плохо для производительности. Мы бы могли поработать в этой области, но в целом пока мы пробовали только микробенчмарки плюс множество нагрузок из реального мира.
Что ж, наверно, вам надоела теория и вы готовы к чему-то более практичному.
Продолжение истории LLVM
Так как библиотека LLVM libcxx была разработана до C++11, первая версия тоже основывалась на quicksort. В чём заключалось отличие от сортировки GNU?
Реализация libcxx обрабатывала несколько конкретных случаев особым образом. Коллекции длиной 5 или меньше сортировались при помощи специальных самописных сортировок на основе сравнений.
sort4.cpp:
template
unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4,
_Compare __c) {
unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
if (__c(*__x4, *__x3)) {
swap(*__x3, *__x4);
++__r;
if (__c(*__x3, *__x2)) {
swap(*__x2, *__x3);
++__r;
if (__c(*__x2, *__x1)) {
swap(*__x1, *__x2);
++__r;
}
}
}
return __r;
} sort5.cpp:
template
unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
_ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) {
unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
if (__c(*__x5, *__x4)) {
swap(*__x4, *__x5);
++__r;
if (__c(*__x4, *__x3)) {
swap(*__x3, *__x4);
++__r;
if (__c(*__x3, *__x2)) {
swap(*__x2, *__x3);
++__r;
if (__c(*__x2, *__x1)) {
swap(*__x1, *__x2);
++__r;
}
}
}
}
return __r;
}
При некоторых типах данных коллекции длиной до 30 сортировались вставками. Тривиальные типы достаточно легко менять местами и ассемблерный код для них вполне подходит.
Есть специальный случай обработки коллекций, большинство элементов которых равно, и для коллекций, которые почти отсортированы. Алгоритм пытается использовать сортировку вставками до предела в 8 перестановок: если во время внешнего цикла мы встречаем больше 8 парных элементов, где $inline$x_i > x_{i + 1}$inline$, то переходим к рекурсии, в противном случае выполняем сортировку и не используем её. Это отлично подходит для почти отсортированных паттернов.
const unsigned __limit = 8;
unsigned __count = 0;
for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
if (__comp(*__i, *__j)) {
value_type __t(_VSTD::move(*__i));
_RandomAccessIterator __k = __j;
__j = __i;
do {
*__j = _VSTD::move(*__k);
__j = __k;
} while (__j != __first && __comp(__t, *–__k));
*__j = _VSTD::move(__t);
if (++__count == __limit)
return ++__i == __last;
}
__j = __i;
}
Сортировка libcxx LLVM при случайных данных
Однако, если посмотреть на входящие данные с возрастанием, то мы видим, что libstdcxx выполняет множество необязательной работы по сравнению с сортировкой libcxx, что на практике важно. Во-первых, она выполняется в 4,5 раза быстрее!
libcxx для возрастающих данных
libstdcxx для возрастающих данных
Последнее отличие заключается в том, что медиана, равная 5, выбирается, когда количество элементов в quicksort partition больше 1000. Больше никаких отличий; для меня самое большое влияние этой сортировки заключается в том, что она пытается распознавать стандартные паттерны, что затратно, но во многих реальных ситуациях даёт множество преимуществ.
Когда мы в Google сменили libstdcxx на libcxx, то заметили существенные улучшения (на десятки процентов) во времени, потраченном на std::sort. С тех пор алгоритм не менялся, но данные, которые он обрабатывал, увеличивались.
Проблема квадратичности
Так как libcxx LLVM разрабатывалась для C++03, первая реализация была нацелена на средний случай, о котором мы говорили выше. К этой проблеме обращались несколько раз, в 2014, 2017 и 2018 годах17, 18.
В конечном итоге мне удалось реализовать такое же улучшение, которое в библиотеке GNU добавили с помощью introsort. Мы добавили в алгоритм дополнительный параметр, определяющий максимальную глубину рекурсии, на которую может уйти алгоритм, после которой оставшаяся последовательность пути сортируется при помощи heapsort. Количество допустимых разделений задаётся равным $inline$2n \log_2 n$inline$. Так как временная сложность наихудшего случая heapsort равна $inline$O (n \log n)$inline$, модифицированный алгоритм тоже имеет временную сложность наихудшего случая $inline$O (n \log n)$inline$. Коммит этого изменения19 был внесён в основную ветку LLVM и выпущен в LLVM 14.
void
__introsort(_RandomAccessIterator __first, _RandomAccessIterator __last,
difference_type __depth) {
// …
while (true) {
if (__depth == 0) {
// Откат к heapsort, как предложено в Introsort.
_VSTD::__partial_sort<_Compare>(__first, __last, __last);
return;
}
–__depth;
// …
}
template
inline _Number __log2i(_Number __n) {
_Number __log2 = 0;
while (__n > 1) {
__log2++;
__n >>= 1;
}
return __log2;
}
void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
difference_type __depth_limit = 2 * __log2i(__last – __first);
_VSTD::__introsort(__first, __last, __depth_limit);
} Сколько случаев из реального мира попало в heapsort?
Также нам было интересно, какая часть производительности ушла на глубокие уровни quicksort, и мы убедились, что один из нескольких тысяч всех вызовов std::sort откатывается к heapsort.
Это было довольно необычное открытие. Оно не показало никаких статистически значимых улучшений, т. е. не было найдено никаких очевидных или существенных квадратических улучшений. На самом деле Quicksort вполне хорошо работает с реальными данными, однако этот алгоритм может подвергаться эксплойтам.
Поначалу кажется, что легко просто поменять реализацию и выиграть в ресурсах: сортировка имеет порядок и, например, если вы сортируете integer, то API не волнует ваша реализация; ему достаточно, чтобы интервал был упорядочен правильно.
Однако C++ API может получать функции сравнения, которые для простоты могут быть лямбда-функциями. Мы называем их «компараторами». Они могут различными способами нарушать наши допущения о детерминированности сортировки. Иногда я называю эту проблему «ничья может решаться по-разному».
std::vector> first_elements_equal{{1, 1}, {1, 2}};
std::sort(first_elements_equal.begin(),
first_elements_equal.end(),
[](const auto& lhs, const auto& rhs) {
// Сравнение только с частью отсортированных данных.
return lhs.first < rhs.first;
});
// Сериализируем или делаем допущения обо всех данных.
// Ошибка, может быть или 1, или 2.
assert(first_elements_equal[0].second == 1);
В более серьёзных примерах могут использоваться SQL-запросы такого типа: Результат PostgreSQL
create table example (id_1 integer, id_2 integer);
— Insert lots of equal id_1
insert into example (id_1, id_2) values (1, 1);
insert into example (id_1, id_2) values (0, 3);
insert into example (id_1, id_2) values (0, 2);
insert into example (id_1, id_2) values (0, 3);
insert into example (id_1, id_2) values (0, 2);
insert into example (id_1, id_2) values (0, 3);
insert into example (id_1, id_2) values (1, 3);
— Order only by the first element, second
— is undefined for equal first elements.
select * from example order by id_1;
Результат MySQL
И мы знаем, что пользователию любят писать золотые тесты для подобных запросов. Однако несмотря на то, что никто не гарантирует порядок равных элементов, пользователи зависят от такого поведения, поскольку он может быть закопан в коде, о котором они никогда не слышали. Это классический пример закона Хайрама.
При достаточном количестве пользователей API, не важно, что вы обещаете в контракте: все наблюдаемые поведения вашей системы будут зависеть от кого-то. — Хайрам Райт
Если различия слишком велики, золотые тесты могут сбивать с толку: мы что-то ломаем или тест слишком хрупкий, чтобы показывать что-то полезное? Золотые тесты непохожи на типичные юнит-тесты, поскольку они не принуждают ни к какому поведению. Они просто дают нам знать, что результат работы сервиса изменился. Нет никакого контракта о значении этих изменений; пользователь сам должен решать, что он хочет делать с этой информацией.
Когда мы попытались найти все такие случаи, то поняли, что из-за этого миграцию почти невозможно автоматизировать — откуда мы знаем, что именно эти изменения нужны нашим пользователям? В конечном итоге мы получили довольно суровый урок о том, что даже незначительные изменения в способе использования примитивов приводят к проблемам с золотыми тестами. Лучше использовать вместо золотых тестов юнит-тесты или уделять больше внимания детерминированности написанного кода.
Как найти все зависимости равных элементов?
Поскольку равные элементы в основном неразличимы при функциях сравнения (мы нашли только горстку примеров компараторов, вносящих изменения в массив в процессе), достаточно рандомизировать интервал перед самим вызовом std::sort. Вы можете самостоятельно вычислить вероятности и доказать, что этого достаточно.
Мы решили реализовать такую функциональность в LLVM в режиме отладки20 для вызовов std::sort, std::nth_element, std::partial_sort.
// _LIBCPP_DEBUG_RANDOMIZE_RANGE - это std::shuffle
template
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp) {
// Рандомизируем интервал.
_LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
// Вызываем внутреннюю сортировку.
_VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first),
_VSTD::__unwrap_iter(__last), _Comp_ref(__comp));
}
template
void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last, _Compare __comp) {
// Рандомизируем интервал.
_LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
// Вызываем внутреннюю nth_element.
_VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
// Обе части разделения не имеют требований к упорядочиванию.
_LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth);
if (__nth != __last) {
_LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last);
}
}
template
void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle,
_RandomAccessIterator __last, _Compare __comp) {
// Рандомизируем интервал.
_LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
_VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
// Замыкающая часть не имеет требований к упорядочиванию.
_LIBCPP_DEBUG_RANDOMIZE_RANGE(__middle, __last);
} Техники получения порождающих значений
Для использовали для получения порождающих значений генератора случайных чисел технику ASLR (address space layout randomization)21, при которой статические переменные будут находиться по случайным адресам при запуске программы и мы можем использовать его в качестве seed. Это обеспечивает ту же гарантию стабильности при прогоне программы, но не при разных прогонах, например тесты могут оказаться слоистыми и может показаться, что они сломались. Для платформ, не поддерживающих ASLR, seed при сборке делается фиксированным. Использование других техник от заголовка
static uint_fast64_t __seed() {
// адрес статической переменной может быть рандомизирован, если сборка выполняется с ASLR.
static char __x;
return reinterpret_cast(&__x);
}
Такая рандомизация была включена в режиме отладочной сборки, поскольку во всех случаях при перетасовке элементов снижение производительности может быть существенным.
Опасность partial и nth
Кроме того, если приглядеться к показанным выше изменениям в рандомизации, то можете заметить разницу между std::nth_element и std::partial_sort. Она может запутать.
std::partial_sort и std::nth_element имеют различие в значении их параметров, в котором легко запутаться. Обе получают 3 итератора:
begin— начало интервалаnthormiddle— значение (и имя) этого параметра различается в этих функцияхend— конец интервала
В функции std::partial_sort средний параметр называется middle, он указывает прямо на место после части интервала, которая должна быть отсортирована. Это значит, что мы не знаем, на какой элемент будет указывать middle — мы только знаем, что это будет один из элементов, которые не нужно сортировать.
В функции std::nth_element этот средний параметр называется nth. Он указывает на единственный элемент, который будет отсортирован. Для всех элементов в [begin, nth) мы знаем лишь то, что они будут меньше или равны *nth, но не знаем, в каком порядке они будут находиться.
Это значит, что если мы хотим найти 10-й по меньшинству элемент контейнера, нам нужно вызывать эти функции немного по-разному:
std::vector values = { /* больше 10 значений */ };
std::nth_element(values.begin(), values.begin() + 9, values.end());
int tenth_element = values[9];
std::vector values = { /* больше 10 значений */ };
std::partial_sort(values.begin(), values.begin() + 10, values.end());
int tenth_element = values[9];
В конечном итоге, после десятков прогонов всех тестов в Google и с помощью удачного ветра случайности мы выявили пару тысяч тестов, которые зависимы от стабильности алгоритмов сортировки и выбора. Поскольку мы также планировали обновить алгоритмы сортировки, этот процесс помог делать это постепенно и надёжно.
В конечном итоге, для исправления всего этого нам понадобилось около года.
Какие сбои вы, вероятно, обнаружите?
Золотые тесты
Во-первых, мы, разумеется, обнаружили множество сбоев в описанных выше золотых тестах, и это было неизбежно. Из мира open source можно посмотреть на ClickHouse22, 23, они тоже решили реализовать описанную выше случайность.
Типичные изменения в золотых тестах
Большинство изменений выглядело именно так — мы создавали правильный порядок и обновляли золотые тесты.
К сожалению, золотые тесты могут быть довольно чувствительными к нагрузкам в продакшене, например, при разворачивании потокового движка — что если некоторые инстансы создают немного отличающиеся результаты для одного и того же шарда? Или что если какой-то алгоритм сжатия случайно использует std::sort и сравнивает контрольную сумму от другого сервиса, в котором реализация не обновилась? Это может вызвать несовпадение контрольных сумм, повышение количества ошибок, проблемы у пользователей и даже потерю данных, и вы не сможете просто заменить алгоритм, потому что это может неожиданным образом повредить нагрузкам в продакшене. Закон Хайрама во всём своём великолепии. Например, чтобы команды смогли мигрировать, нам пришлось инъецировать в пару мест старые реализации.
Ох, чёрт, детерминированность
Некоторые другие изменения могут потребовать перехода от std::sort к std::stable_sort, если требуется детерминированность. Мы рекомендуем написать комментарий о том, почему это важно, поскольку stable_sort гарантирует, что равные элементы будут в том же порядке, что и до сортировки.
Примечание: параметры по умолчанию в других языках отличаются, и, вероятно, это хорошо
Во многих языках24, в том числе в Python, Java, Rust, sort() стабильна по умолчанию и, по-моему, это решение лучше. Например, в Rust есть .sort_unstable(), не имеющий гарантий стабильности, но сообщающий об этом явно. Однако у C++ другие приоритеты, например, использование чего-то не должно делать больше, чем требуется (принцип «ты не платишь за то, что не используешь»). По нашим бенчмаркам std::stable_sort была на 10–15% медленнее, чем std::sort, и распределяла линейную память. Учитывая преимущества в производительности, для кода на C++ это было довольно критично. Мне кажется, что по умолчанию Rust предполагает более строгие ограничения с возможностью их смягчить, а C++ предполагаем более мягкие ограничения с возможностью их ужесточения.
Логические баги
Мы нашли множество мест, где пользователи вызывали неопределённое поведение или создавали неэффективность. Перечислим их по степени возрастания важности.
Сортировка двоичных данных
При сравнении булевой переменной, например, когда вы разделяете данные по существованию какого-то параметра, очень привлекательным кажется использование вызова std::sort.
struct Data {
bool has_property;
// …
};
std::vector data(FillData());
std::sort(data.begin(), data.end(), [](const Data& lhs, const Data& rhs) {
return lhs.has_property < rhs.has_property;
});
Однако для функций сравнения, выполняющих сравнение только по булевым переменным, у нас есть гораздо более быстрые линейные алгоритмы std::partition и его стабильная версия std::stable_partition.
struct Data {
bool has_property;
// …
};
std::vector data(FillData());
/*
Изменяет порядок элементов в интервале [first, last) таким образом,
чтобы все элементы, для которых предикат p возвращает true, предшествовали
элементам, для которых предикат p возвращает false. Относительный порядок
элементов не сохраняется.
*/
std::partition(data.begin(), data.end(), [](const Data& other) {
// Отрицание, поэтому все со свойством переносятся вправо.
return !other.has_property;
});
Даже несмотря на то, что современные алгоритмы хорошо справляются с определением кратности, лучше предпочитать std::partition, хотя бы ради читаемости.
Сортировка больше необходимого
Мы часто встречали паттерн sort+resize.
// Нас интересуют только n сущностей с наибольшими score.
std::sort(vector.begin(), vector.end(),
HasHigherScore());
vector.resize(n);
Из приведённого выше кода мы можем понять, что несмотря на то, что исследовать нужно каждый элемент, сортировка всего vector (позже $inline$n$inline$-ного элемента) не нужна. Скорее всего, компилятор это не оптимизирует.
// We only care about the n entities with the highest scores.
std::partial_sort(vector.begin(),
vector.begin() + n,
vector.end(),
HasHigherScore());
vector.resize(n);
К сожалению, не существует стабильного аналога std::partial_sort, поэтому если требуется детерминированность, нужно исправить компаратор.
Язык C++ сложен
Если в компараторе используется несоответствующий тип, то C++ не предупредит об этом даже при -Weverything. На скриншоте ниже при сортировке вектора float с компаратором std::greater не было выдано ни одного предупреждения.
Отсутствие следования строгому слабому упорядочиванию
При вызове в C++ любых функций упорядочивания, в том числе и std::sort функции сравнения должны соответствовать строгому слабому упорядочиванию, что формально означает следующее:
- Нерефлексивность: $inline$x < x$inline$ ложно
- Асимметрию: $inline$x < y$inline$ и $inline$y < x$inline$ не могут одновременно быть истинными
- Транзитивность: $inline$x < y$inline$ и $inline$y < z$inline$ подразумевают $inline$x < z$inline$
- Транзитивность несравнимости: $inline$x == y$inline$ и $inline$y == z$inline$ подразумевают $inline$x == z$inline$, где $inline$x == y$inline$ означает, что $inline$x < y$inline$ и $inline$y < x$inline$ ложны.
Все эти условия логичны и для оптимизации алгоритмы используют их все. Первые три условия задают строгое частичное упорядочивание, а четвёртое добавляет соотношения эквивалентности для несравнимых элементов.
Как вы могли догадаться, мы столкнулись с нарушением всех условий. Чтобы продемонстрировать их, я ниже покажу скриншоты того, где я их нашёл при помощи Github codesearch (https://cs.github.com). И я не особо старался искать баги, самое важное, что нарушения происходят. После этого мы поговорим о том, как их можно использовать в эксплойтах.
Нарушение нерефлексивности и асимметрии
Под спойлером есть слайдшоу, изучите его.
Все они нарушают правило нерефлексивности, а comp(x, x) возвращает true. Возможно, вы скажете, что это можно не использовать на практике, однако мы получили болезненный урок о том, что даже тесты не всегда помогают.
30 и 31 элемент. Правильное исполнение и SIGSEGV
Вы можете помнить, что для количества элементов до 30 для тривиальных типов (и до 6 для нетривиальных) сортировка LLVM/libcxx использует сортировку вставками, а при бОльших количествах возвращается к quicksort. Однако если передать компаратор, в котором не удовлетворяются условия нерефлексивности и асимметрии, то можно обнаружить, что с 31 элементом программа может перейти в segfault, хотя с 30 элементами работает отлично. Рассмотрим пример, в котором мы хотим переместить все отрицательные элементы вправо и отсортировать все положительные, как и в примерах выше.
https://gcc.godbolt.org/z/17r76q7eo
Мы видели, что пользователи пишут тесты для небольших интервалов, однако когда количество элементов растёт, std::sort может привести к SIGSEGV, а при тестировании это можно упустить; это может стать интересным вектором атаки для вылета программы.
Это используется в реализации libcxx, чтобы ждать, когда какое-то условие окажется ложным, ведь мы знаем, что в какой-то момент будем сравнивать два равных элемента:
// Известно, что идущий вверх поиск защищён, но не идущий вниз.
// Дополним идущий вниз поиск защитой.
// __m по-прежнему защищает идущий вверх __i
while (__comp(*__i, *__m))
++__i;Нарушение транзитивности несравнимости
https://webrtc-review.googlesource.com/c/src/+/251681
Мы можем создать пример, где нарушается четвёртое условие.
Худшее, что может случиться в таком случае с текущей реализацией: элементы не будут отсортированы (без segfaults; это требует доказательства, однако статья и так уже слишком длинная), смотрите:
https://gcc.godbolt.org/z/c71qzM97f
И снова, если использовать меньше 7 элементов, применяется сортировка вставками, и нельзя создать контрпример, в котором std::is_sorted не работает. Хотя теоретически это неопределённое поведение, его очень сложно распознать программами очистки или тестами, и в реальности простые случаи пропускаются.
Этот фрагмент может просто выглядеть так:
std::vector vector_of_doubles(FillData());
std::sort(vector_of_doubles.begin(), vector_of_doubles.end());
Почему? Потому что double/float могут быть NaN, что означает x < NaN и NaN < x ложны, а это означает, что x эквивалентно NaN, то есть д
