При работе с масштабным количеством кода (скажем, я думаю, что человек способен где-то в голове держать 25-40 тысяч строк кода, всё что больше — уже масштабно), нередко возникают сложные проблемы с миграцией абсолютно любых функций и контейнеров, на которых завязались пользователи. Особенно это ощущается в библиотеках, которые находятся достаточно низко, стандартные библиотеки или неявные гарантии интерфейсов.
Как один из примеров, недавно Google, видимо, обновил свою хэш-функцию в своей библиотеке abseil c CityHash на WyHash, пример сделал он это не боясь, потому что пользователи не имеют право завязываться на порядок элементов в хэшмапе. Как это сделать? Достаточно просто, стоит просто рандомизировать seed у хэш функции и все тесты со временем станут флапающими и красными и это уже проблемы пользователей, которые завязались на такое поведение. Преимущества — способность в любой момент поменять хэш функцию, если вдруг появится новая, более производительная.
У меня в бэклоге давно была идея сделать похожие вещи в стандартной библиотеке. Например, даже стандарт разрешает модифицировать std::hash при разных запусках программы, см https://eel.is/c++draft/hash.requirements#tab:cpp17.hash-row-2-column-3-note-1
Тем не менее, libcxx развивается и мне кажется, что предоставить возможность так делать вполне логичным и в какой-то степени важным для развития. Например, это останавливает стандартную библиотеку от предоставления новой сортировки (пусть даже под флагом), которая в libcxx всё ещё квадратична и написана в 2005, c'mon. Потому что люди могут завязаться на порядок одинаковых элементов как на картинке выше.
Чтобы рандомизировать сортировки и алгоритмы поиска статистики (😏) , можно использовать ASLR для seed и сделать shuffle всего массива, эта штука рандомизирует адреса при запуске бинарного файла и можно воспользоваться грязными свойствами C++ как использования адреса себя при присвоении
В общем, RFC в LLVM по рандомизации сортировки/частичной сортировки и поиска порядковой
https://reviews.llvm.org/D96946
Как один из примеров, недавно Google, видимо, обновил свою хэш-функцию в своей библиотеке abseil c CityHash на WyHash, пример сделал он это не боясь, потому что пользователи не имеют право завязываться на порядок элементов в хэшмапе. Как это сделать? Достаточно просто, стоит просто рандомизировать seed у хэш функции и все тесты со временем станут флапающими и красными и это уже проблемы пользователей, которые завязались на такое поведение. Преимущества — способность в любой момент поменять хэш функцию, если вдруг появится новая, более производительная.
У меня в бэклоге давно была идея сделать похожие вещи в стандартной библиотеке. Например, даже стандарт разрешает модифицировать std::hash при разных запусках программы, см https://eel.is/c++draft/hash.requirements#tab:cpp17.hash-row-2-column-3-note-1
[Note 1: Thus all evaluations of the expression h(k) with the same value for k yield the same result for a given execution of the program. — end note]Так, конечно, не делают стандартные библиотеки, потому что рандомизировать хэши на совсем embedded системах сложно.
Тем не менее, libcxx развивается и мне кажется, что предоставить возможность так делать вполне логичным и в какой-то степени важным для развития. Например, это останавливает стандартную библиотеку от предоставления новой сортировки (пусть даже под флагом), которая в libcxx всё ещё квадратична и написана в 2005, c'mon. Потому что люди могут завязаться на порядок одинаковых элементов как на картинке выше.
Чтобы рандомизировать сортировки и алгоритмы поиска статистики (😏) , можно использовать ASLR для seed и сделать shuffle всего массива, эта штука рандомизирует адреса при запуске бинарного файла и можно воспользоваться грязными свойствами C++ как использования адреса себя при присвоении
static const void* const kSeed = &kSeed;И интерпретировать этот указатель как число. Можно использовать
std::random_device, но так как хедер <random> зависит от <algorithm>, я отбросил идею.В общем, RFC в LLVM по рандомизации сортировки/частичной сортировки и поиска порядковой
https://reviews.llvm.org/D96946