#common #java
Java GC 1/2.
Из популярного в java ещё есть сборщик мусора Shenandoah. Как и G1, шенонда -- region based concurrent сборщик мусора.
Сначала происходит параллельная маркировка с двумя паузами до/после. В результате для каждого занятого региона становится понятно, как много живых объектов в нём содержится. Из регионов с небольшим количеством достижимых объектов формируется collection set, из которого происходит фоновое уплотнение в новый регион (concurrent evacuation).
После уплотнения нельзя считать, что регионы, из которых происходило уплотнение, можно ощищать.
На данные в них могут существовать ссылки из других регионов, потому следующим этапом производится перезапись ссылок с данных из старых регионов на данные в уплотнённом (concurrent update refs; тоже паузы до/после). После этого можно считать регионы очищенными и аллоцировать из них память.
Java GC 1/2.
Из популярного в java ещё есть сборщик мусора Shenandoah. Как и G1, шенонда -- region based concurrent сборщик мусора.
Сначала происходит параллельная маркировка с двумя паузами до/после. В результате для каждого занятого региона становится понятно, как много живых объектов в нём содержится. Из регионов с небольшим количеством достижимых объектов формируется collection set, из которого происходит фоновое уплотнение в новый регион (concurrent evacuation).
После уплотнения нельзя считать, что регионы, из которых происходило уплотнение, можно ощищать.
На данные в них могут существовать ссылки из других регионов, потому следующим этапом производится перезапись ссылок с данных из старых регионов на данные в уплотнённом (concurrent update refs; тоже паузы до/после). После этого можно считать регионы очищенными и аллоцировать из них память.
❤1
#common #java
Java GC 2/2.
Ещё одним известным сборщиком мусора в Java является ZGC. По принципу действия он аналогичен Shenandoah с точностью до некоторых локальных оптимизаций, которые, тем не менее, иногда играют значительную роль в использовании. Важным достижением ZGC являются константные stop-the-world паузы.
А ещё есть no-op EpsilonGC.
Вообще весь движ начинается в момент реализации барьеров на чтение/запись. Там какие-то java-специфичные вещи довольно. Если интересно, можно посмотреть докладик Алексея Шипилёва (я так понял, это Полухин из мира жавы).
На картиночке условное сравнение, чтобы выбрать gc по нуждам.
[1]. Shenandoah 1.
[2]. Shenandoah 2.
P.S. На правах рекламы вкину статью про обучение очень больших моделек. Что делать, если они не помещаются на GPU, и как с этим вообще жить: link. Вдруг тут есть любители машинок : )
Java GC 2/2.
Ещё одним известным сборщиком мусора в Java является ZGC. По принципу действия он аналогичен Shenandoah с точностью до некоторых локальных оптимизаций, которые, тем не менее, иногда играют значительную роль в использовании. Важным достижением ZGC являются константные stop-the-world паузы.
А ещё есть no-op EpsilonGC.
Вообще весь движ начинается в момент реализации барьеров на чтение/запись. Там какие-то java-специфичные вещи довольно. Если интересно, можно посмотреть докладик Алексея Шипилёва (я так понял, это Полухин из мира жавы).
На картиночке условное сравнение, чтобы выбрать gc по нуждам.
[1]. Shenandoah 1.
[2]. Shenandoah 2.
P.S. На правах рекламы вкину статью про обучение очень больших моделек. Что делать, если они не помещаются на GPU, и как с этим вообще жить: link. Вдруг тут есть любители машинок : )
👍3❤1
#list
Очередная пачка рандомной инфы.
1. Пару дней дебагал уб. Половину этого времени потратил на то, чтобы исключить false positive срабатывания санитайзеров на fmtlib и хедер stl с итераторами. Делается это при использовании блеклиста санитайзеров. Не знал, что такое есть. Кстати не отдебагал.
2. Недавно стал свидетелем дискуссии про то, как парсить плюсы (навеянной вот этим докладом). Если кратко, предлагается упростить синтаксис плюсов до некоторого достаточного множества конструкций, чтобы не парсить сложные завороты больной фантазии программиста. Умные дяди сказали, что писать самому звучит как не успех, но можно взять популярные опенсорсные проекты вроде tree-sitter.
3. Есть такой факт, что лямбды с пустым списком захвата умеют каститься к указателю на функцию:
Можно явно указать шаблонный тип:
используя builtin
4. Оказывается в большинстве файлов стандартной библиотеки go можно найти флаг
5. C++ sucks.
6. Я человек простой: вижу Аксёнова -- ставлю лайк.
У него оказывается в целом много обзорных докладов про всякие сферы программирования. Вот тут он рассказывает про различные способы сжатия.
Мне оч понравился факт, что дельта-кодирование используется в жизни. Дефолтная задача звучит как что-то вроде есть 10^8 нулей и запросы добавить на отрезок [l; r] число x. После всех запросов вывести итоговый массив. Давайте в
В докладе приводится пример про то, как использовать похожий подход при сжатии неубывающей последовательности чисел. Давайте вместо самой последовательности (например)
построим такую (первое оставляем, остальные заменяем на дельту относительно прошлого):
Теперь все числа в абсолютных значения сильно меньше. Уникальных тоже стало меньше. Можно пробовать жать их более эффективно. Утверждается, что такой подход можно найти в любом более менее популярном поиске вроде гугла, яндеха, sphinx или lucene (про последние может расскажу чуть позже).
7. Крышесносный факт (для меня точно). Существуют не только enum-классы, а и enum-структуры:
Которые вообще ничем не отличаются.
Очередная пачка рандомной инфы.
1. Пару дней дебагал уб. Половину этого времени потратил на то, чтобы исключить false positive срабатывания санитайзеров на fmtlib и хедер stl с итераторами. Делается это при использовании блеклиста санитайзеров. Не знал, что такое есть. Кстати не отдебагал.
2. Недавно стал свидетелем дискуссии про то, как парсить плюсы (навеянной вот этим докладом). Если кратко, предлагается упростить синтаксис плюсов до некоторого достаточного множества конструкций, чтобы не парсить сложные завороты больной фантазии программиста. Умные дяди сказали, что писать самому звучит как не успех, но можно взять популярные опенсорсные проекты вроде tree-sitter.
3. Есть такой факт, что лямбды с пустым списком захвата умеют каститься к указателю на функцию:
typedef int (*fptr_t)();
fptr_t create() {
fptr_t fptr = [] { return 2; }
return fptr;
}
template <typename T>
T apply (T(*f)()) {
return f();
}
int main() {
fptr_t f = create();
apply(f); // компилируется
apply([] {return 3;}); // не компилируется
}Можно явно указать шаблонный тип:
apply<int>(...), но так мы убиваем автоматический вывод типов. А если там что-то более сложное? Можно сделать static_cast<fptr_t>. А можно сделать так:apply(+[] {return 3; });используя builtin
T* operator+(T*). Как по мне магия какая-то)4. Оказывается в большинстве файлов стандартной библиотеки go можно найти флаг
debugMode, который по дефолту стоит false. Если ручками поменять его значение на true, начнётся дебаг вывод всякой служебной инфы. Например можно узнать, что даже при запуске пустой программы у вас создаётся два канала (один на сборщик мусора, один на что-то ещё). Это из доклада про устройство каналов.5. C++ sucks.
6. Я человек простой: вижу Аксёнова -- ставлю лайк.
У него оказывается в целом много обзорных докладов про всякие сферы программирования. Вот тут он рассказывает про различные способы сжатия.
Мне оч понравился факт, что дельта-кодирование используется в жизни. Дефолтная задача звучит как что-то вроде есть 10^8 нулей и запросы добавить на отрезок [l; r] число x. После всех запросов вывести итоговый массив. Давайте в
arr[l] добавлять x, а из arr[r+1] отнимать его. Во время вывода ответа держим текущую сумму и обновляем её из массива.В докладе приводится пример про то, как использовать похожий подход при сжатии неубывающей последовательности чисел. Давайте вместо самой последовательности (например)
[12, 18, 19, 31, ..., 228227, 228228, 228229]построим такую (первое оставляем, остальные заменяем на дельту относительно прошлого):
[12, 6, 1, 12, ..., 1, 1, 1]Теперь все числа в абсолютных значения сильно меньше. Уникальных тоже стало меньше. Можно пробовать жать их более эффективно. Утверждается, что такой подход можно найти в любом более менее популярном поиске вроде гугла, яндеха, sphinx или lucene (про последние может расскажу чуть позже).
7. Крышесносный факт (для меня точно). Существуют не только enum-классы, а и enum-структуры:
enum struct A {asd};Которые вообще ничем не отличаются.
👍10❤1
#cpp #common и может #algo
Вроде как знание о векторах в плюсах довольно тривиальное, но тем не менее.
Общеизвестный факт, что вектор это по факту такая структурка:
Кажется, сделать динамический массив меньшими усилиями ну никак нельзя. В самописных версиях иногда вместо двух чиселок также хранят указатели, а size/capacity вычисляют каждый раз. Можно упороться и хранить их в одной
Стандартная библиотека предлагает для кастомизации своего вектора подсунуть свой аллокатор вторым шаблонным аргументом. И всё. Больше пользователю ничего не надо. Но ведь есть ещё такая важная характеристика как resize policy -- то, как ваш вектор изменяет свой размер. Как много выделить в первой аллокации? 1, 2, 8? С единицы начинать плохо: после первого push_back почти наверняка придёт второй. С восьми тоже плохо: может у нас вектор объектов, каждый из которых 3Мб, а юзать мы хотим всего для трёх элементов. Да и для двойки свой кейс можно придумать.
Теперь про изменение этого размера. В clang довольно дефолтная схема с умножением на 2 (с оговорками). Но есть ощущение, что умножение на 2 оч плохое решение. Точнее, умножение на любую константу плохо. Когда речь идёт о расширении 8->16, это вполне себе хорошее решение (или нет?🧐без знания размера объектов непонятно). Но когда у вас уже 1кк элементов и вы хотите положить ещё пару штук, расширение 1кк->2кк выглядит как из пушки по воробьям.
И что делать?
Как вариант не расти всегда с одинаковой скоростью. Можно смотреть на текущее кол-во элементов. Можно на занимаемую память. И после выбора какой-то границы, расти в 2 раза до неё и в 1.2 после (понятно что тут стоит покрутить и найти компромисс между занимаемой памятью и временем работы в зависимости от ваших данных и паттерна работы с ними). В go в этом плане примерно так и сделано.
Ещё есть вопрос, уменьшаться ли, если размер стал слишком маленький: если у меня capacity на 1кк, а размер 10, то наверное можно было бы пожаться до этих самых 10, а потом расти по обычным правилам. Вроде как так почти никто не делает. Правда слышал, что в каком-то языке реализовано сжатие, если размер в 4 раза меньше вместимости (сходу не вспомнил где).
В студвекторе из подобного есть метод shrink_to_fit, который уменьшает вместимость до размера. Прошу заметить, что метод этот non-binding, i.e. необязательный. Тут авторы вольны делать что хотят. В clang честно пытаются уменьшиться.
Учитывая, что resize policy это что-то, что нельзя описать одним числом, интересно попробовать придумать, как это могло бы выглядеть в стандартной библиотеке. Что-то такое:
где Recap может выглядеть как что-то вроде
Понятно, что всё это можно делать и сейчас, вычисляя новый размер/капасити снаружи и используя
Возвращаясь к теме пооптимизировать вектор, кроме всем известной специализации для булов иногда пишут специализацию для POD-типов, где можно не вызывать конструкторы/деструкторы при различных операциях.
Можно ещё писать контейнеры кусками (вроде дека), чтобы немножко получше жить с аллокациями. Или пробовать хранить мало данных на стеке, прям как sso.
Зачем это всё? А хер его знает. Почти наверняка на практике это вам не пригодится, потому что если вам не хватает
Такие дела.
Вроде как знание о векторах в плюсах довольно тривиальное, но тем не менее.
Общеизвестный факт, что вектор это по факту такая структурка:
template <typename T>
struct vector {
T* data;
int size, capacity;
}Кажется, сделать динамический массив меньшими усилиями ну никак нельзя. В самописных версиях иногда вместо двух чиселок также хранят указатели, а size/capacity вычисляют каждый раз. Можно упороться и хранить их в одной
int64 переменной: первые 4 байта на размер, вторые на вместимость. А можно вообще не хранить размер, а сделать ваш вектор нуль-терминированным и считать длину ручками каждый раз. Раз в k случаев такое тоже работает хорошо. Стандартная библиотека предлагает для кастомизации своего вектора подсунуть свой аллокатор вторым шаблонным аргументом. И всё. Больше пользователю ничего не надо. Но ведь есть ещё такая важная характеристика как resize policy -- то, как ваш вектор изменяет свой размер. Как много выделить в первой аллокации? 1, 2, 8? С единицы начинать плохо: после первого push_back почти наверняка придёт второй. С восьми тоже плохо: может у нас вектор объектов, каждый из которых 3Мб, а юзать мы хотим всего для трёх элементов. Да и для двойки свой кейс можно придумать.
Теперь про изменение этого размера. В clang довольно дефолтная схема с умножением на 2 (с оговорками). Но есть ощущение, что умножение на 2 оч плохое решение. Точнее, умножение на любую константу плохо. Когда речь идёт о расширении 8->16, это вполне себе хорошее решение (или нет?🧐без знания размера объектов непонятно). Но когда у вас уже 1кк элементов и вы хотите положить ещё пару штук, расширение 1кк->2кк выглядит как из пушки по воробьям.
И что делать?
Как вариант не расти всегда с одинаковой скоростью. Можно смотреть на текущее кол-во элементов. Можно на занимаемую память. И после выбора какой-то границы, расти в 2 раза до неё и в 1.2 после (понятно что тут стоит покрутить и найти компромисс между занимаемой памятью и временем работы в зависимости от ваших данных и паттерна работы с ними). В go в этом плане примерно так и сделано.
Ещё есть вопрос, уменьшаться ли, если размер стал слишком маленький: если у меня capacity на 1кк, а размер 10, то наверное можно было бы пожаться до этих самых 10, а потом расти по обычным правилам. Вроде как так почти никто не делает. Правда слышал, что в каком-то языке реализовано сжатие, если размер в 4 раза меньше вместимости (сходу не вспомнил где).
В студвекторе из подобного есть метод shrink_to_fit, который уменьшает вместимость до размера. Прошу заметить, что метод этот non-binding, i.e. необязательный. Тут авторы вольны делать что хотят. В clang честно пытаются уменьшиться.
Учитывая, что resize policy это что-то, что нельзя описать одним числом, интересно попробовать придумать, как это могло бы выглядеть в стандартной библиотеке. Что-то такое:
template <
typename T,
typename Allocator = ... ,
template <typename T> Recap = std::twice>
class vector;где Recap может выглядеть как что-то вроде
template <typename T>
size_t MyRecap(size_t sz, size_t cp) {
if (sz * 4 < cp) { return sz; }
if (cp * sizeof(T) > 10 * kBytesInMB) {
return cp * 1.2;
}
return cp * 2;
}Понятно, что всё это можно делать и сейчас, вычисляя новый размер/капасити снаружи и используя
resize/reserve, но менеджерить размеры не изнутри как неестественно. Возвращаясь к теме пооптимизировать вектор, кроме всем известной специализации для булов иногда пишут специализацию для POD-типов, где можно не вызывать конструкторы/деструкторы при различных операциях.
Можно ещё писать контейнеры кусками (вроде дека), чтобы немножко получше жить с аллокациями. Или пробовать хранить мало данных на стеке, прям как sso.
Зачем это всё? А хер его знает. Почти наверняка на практике это вам не пригодится, потому что если вам не хватает
std::vector, то у вас уже либо все остальные проблемы с производительностью решены, либо очень специфическая задача. Но знать полезно.Такие дела.
👍14❤1
#common #python
Не знаю, насколько вам заходит читать про сборщики мусора, но осталось совсем чуть-чуть : )
Собсна python GC.
Стандартный CPython использует подсчёт ссылок и сборщик мусора с поколениями [habr]. Второй необходим в силу того, что стандартный алгоритм подсчёта ссылок не учитывает циклы, возникающие в процессе жизнедеятельности программы.
Всего тут три поколения, для которых можно задавать границы того, сколько сборок мусора должен пережить объект, чтобы переместиться в следующее поколение.
Для разрешения циклов используется факт, что циклы могут возникнуть лишь при использовании различных контейнеров. Для каждого объекта внутри контейнера производится следующая операция: для всех объектов внутри этого контейнера, на которые ссылается зафиксированный объект, количество ссылок уменьшается на 1. Для всех объектов, счётчик ссылок которых остался больше 1, считается, что на них ссылаются объекты снаружи контейнера. Эти объекты кикаем из множества кандидатов на удаление. Также убираем из этого множества все объекты, на которые ссылаются только что убраные и т.д. Оставшиеся во множестве объекты можно удалять.
Подобный подход встречается и в других языках.
Например, в Kotlin/Native (это не обычный котлин, прошу заметить) такой выбор был сделан из-за простоты метода. Однако недавно от подсчёта ссылок решили отказаться, потому что с ним не получается достигнуть достаточной эффективности.
В отличие от подсчёта ссылок, сборщик мусора можно отключать.
Это может быть полезно для эффективности приложения в случае, если вы уверены, что приложение не создаёт циклов, или же готовы на некоторые утечки памяти в угоду скорости. Получается некоторый аналог неудаляющего аллокатора.
Другой интерпретатор python PyPy имеет cборщик мусора с другой моделью поведения. Incminimark -- инкрементальный трассирующий сборщик мусора с двумя поколениями. Основная настройка -- размер молодого поколения (nursery).
Большие объекты создаётся вне поколений.
Когда-то в PyPy вообще было 6 разных сборщиков, но решили от них отказаться. Ещё пару недель назад у меня была ссылка на старую документацию с пруфами, но сегодня по ней уже ничего нет. Вот так быстро мир меняется.
И CPython, и PyPy предоставляют множество возможностей для полуавтоматического управления сборкой мусора. Есть возможности вручную запускать отдельные минорные/мажорные сборки, временно включать/отключать сборщик мусора,
получать подробную информацию о поведении программы при сборке и т.д.
[1]. Как Instagram отключил gc и получил профит.
[2]. Потом что-то покрутили и вернули.
Не знаю, насколько вам заходит читать про сборщики мусора, но осталось совсем чуть-чуть : )
Собсна python GC.
Стандартный CPython использует подсчёт ссылок и сборщик мусора с поколениями [habr]. Второй необходим в силу того, что стандартный алгоритм подсчёта ссылок не учитывает циклы, возникающие в процессе жизнедеятельности программы.
Всего тут три поколения, для которых можно задавать границы того, сколько сборок мусора должен пережить объект, чтобы переместиться в следующее поколение.
Для разрешения циклов используется факт, что циклы могут возникнуть лишь при использовании различных контейнеров. Для каждого объекта внутри контейнера производится следующая операция: для всех объектов внутри этого контейнера, на которые ссылается зафиксированный объект, количество ссылок уменьшается на 1. Для всех объектов, счётчик ссылок которых остался больше 1, считается, что на них ссылаются объекты снаружи контейнера. Эти объекты кикаем из множества кандидатов на удаление. Также убираем из этого множества все объекты, на которые ссылаются только что убраные и т.д. Оставшиеся во множестве объекты можно удалять.
Подобный подход встречается и в других языках.
Например, в Kotlin/Native (это не обычный котлин, прошу заметить) такой выбор был сделан из-за простоты метода. Однако недавно от подсчёта ссылок решили отказаться, потому что с ним не получается достигнуть достаточной эффективности.
В отличие от подсчёта ссылок, сборщик мусора можно отключать.
Это может быть полезно для эффективности приложения в случае, если вы уверены, что приложение не создаёт циклов, или же готовы на некоторые утечки памяти в угоду скорости. Получается некоторый аналог неудаляющего аллокатора.
Другой интерпретатор python PyPy имеет cборщик мусора с другой моделью поведения. Incminimark -- инкрементальный трассирующий сборщик мусора с двумя поколениями. Основная настройка -- размер молодого поколения (nursery).
Большие объекты создаётся вне поколений.
Когда-то в PyPy вообще было 6 разных сборщиков, но решили от них отказаться. Ещё пару недель назад у меня была ссылка на старую документацию с пруфами, но сегодня по ней уже ничего нет. Вот так быстро мир меняется.
И CPython, и PyPy предоставляют множество возможностей для полуавтоматического управления сборкой мусора. Есть возможности вручную запускать отдельные минорные/мажорные сборки, временно включать/отключать сборщик мусора,
получать подробную информацию о поведении программы при сборке и т.д.
[1]. Как Instagram отключил gc и получил профит.
[2]. Потом что-то покрутили и вернули.
👍5❤1
#algo
Хеш-таблицы 1/2.
1. load factor.
Часто говорят, что важно следить за ним. Ведутся жоские споры (у агрошкольников) о том, какие значения норм, а какие нет. В умных книжках часто пишут, что норм 0.5-0.7. В жизни вам может зайти и 0.99, и может больше единицы, и в районе 0.005. Важно понимать, что важен не сам LF, а средняя глубина поиска. Потому что у вас есть коллизии, которые в одном бакете делают 10 элементов, когда вся таблица на 100. Вроде LF 0.1, а работает медленно. И есть удаления. Которые например при открытой адресации просто помечают элементы удалёнными, не ускоряя поиск. Короче за этим надо следить (в случае открытой адресации видимо вас ждут k костылей, в случае закрытой можно считать LF как максимальное кол-во элементов в бакете делить на размер таблицы).
2. Хеш-функция.
Легко можно выбрать хеш-функцию, посмотрев на её бенчмарки (которые где-то там делали авторы и она всё и вся разносит). Но очевидно, что не будет понятно норм/нет, пока вы не померяете на ваших данных. Ну это ладно. Это известный тезис.
А вот какую выбрать? Может я коллизий поменьше хочу. Тогда может что-то из sha-2 или md5? У них, говорят, коллизий мало. Вон они по 128+ бит хеши выдают. ... А ключи же у нас в районе 64х. Получается надо обрезать. И тут уже ничего не понятно, норм оно будет или нет. Ещё и считается долго. Долго это плохо. Надо помнить, что хеш-функция это на каждую операцию. Потому может лучше "плохо" и быстро с помощью crc32, DJB или fnv (главное чтобы не LoseLose). Хотя можно что-то среднее: SuperFastHash, Murmur, CityHash или Robin-hood (или Hopscotch). Вообще про тему скорости хеш-функций можно вспомнить SMHasher, который считает, сколько функция умеет хешировать в секунду и ещё какие-то характеристики. Но тут тоже стоит помнить, что неважно, сколько она хеширует в секунду, если вы собираетесь её юзать для восьмисимвольных строк (надо мерять).
Бывают ли идеальные хеши? Да! Но надо бы знать ключи заранее и делать предпосчёт, зато юзается быстро и без коллизий :) Тут можно взглянуть на gperf и cmph.
Можно вообще выбрать какое-то семейство функций, и время от времени брать функцию из него.
3. Размер.
Можно зафиксировать вашу таблицу на всю жизнь (и жить с открытой адресацией):
Но что-то подсказывает, что такого хватит ненадолго (хотя мб и хватит). Стандартный путь это как вектор (просто элементов для открытой адресации или например листов для закрытой): реаллокация в k раз, чтобы LF получше стал. Как выбирать k смотрите два поста назад. Можно размеры только степенями двойки. Или можно делать статику снаружи и динамику внутри:
Может быть полезно в случае параллельной таблички или если вы локальность цепочки при закрытой адресации хотите.
4. Ключи.
Иногда нужно хранить какую-то мету, само значение (для сравнений каких-нибудь) или значение хеша. В зависимости от того, насколько много занимает ваша структурка, можно выбирать, хранить например всё в одном массивчике или может ключи/значения отдельно, чтобы в кеши хорошо попадало что надо. Тут конечно всё зависит от вашего паттерна доступа.
Кстати забавно, что если объект жирный, можно попробовать хранить первые k байт его представления и сравнивать их. Или можно вообще не сравнивать изначальные ключи с одинаковыми значениями хеша, если вы уверены в хеш-функции или готовы иногда ошибаться.
Хеш-таблицы 1/2.
1. load factor.
Часто говорят, что важно следить за ним. Ведутся жоские споры (у агрошкольников) о том, какие значения норм, а какие нет. В умных книжках часто пишут, что норм 0.5-0.7. В жизни вам может зайти и 0.99, и может больше единицы, и в районе 0.005. Важно понимать, что важен не сам LF, а средняя глубина поиска. Потому что у вас есть коллизии, которые в одном бакете делают 10 элементов, когда вся таблица на 100. Вроде LF 0.1, а работает медленно. И есть удаления. Которые например при открытой адресации просто помечают элементы удалёнными, не ускоряя поиск. Короче за этим надо следить (в случае открытой адресации видимо вас ждут k костылей, в случае закрытой можно считать LF как максимальное кол-во элементов в бакете делить на размер таблицы).
2. Хеш-функция.
Легко можно выбрать хеш-функцию, посмотрев на её бенчмарки (которые где-то там делали авторы и она всё и вся разносит). Но очевидно, что не будет понятно норм/нет, пока вы не померяете на ваших данных. Ну это ладно. Это известный тезис.
А вот какую выбрать? Может я коллизий поменьше хочу. Тогда может что-то из sha-2 или md5? У них, говорят, коллизий мало. Вон они по 128+ бит хеши выдают. ... А ключи же у нас в районе 64х. Получается надо обрезать. И тут уже ничего не понятно, норм оно будет или нет. Ещё и считается долго. Долго это плохо. Надо помнить, что хеш-функция это на каждую операцию. Потому может лучше "плохо" и быстро с помощью crc32, DJB или fnv (главное чтобы не LoseLose). Хотя можно что-то среднее: SuperFastHash, Murmur, CityHash или Robin-hood (или Hopscotch). Вообще про тему скорости хеш-функций можно вспомнить SMHasher, который считает, сколько функция умеет хешировать в секунду и ещё какие-то характеристики. Но тут тоже стоит помнить, что неважно, сколько она хеширует в секунду, если вы собираетесь её юзать для восьмисимвольных строк (надо мерять).
Бывают ли идеальные хеши? Да! Но надо бы знать ключи заранее и делать предпосчёт, зато юзается быстро и без коллизий :) Тут можно взглянуть на gperf и cmph.
Можно вообще выбрать какое-то семейство функций, и время от времени брать функцию из него.
3. Размер.
Можно зафиксировать вашу таблицу на всю жизнь (и жить с открытой адресацией):
std::pair<K, V> data[1024];Но что-то подсказывает, что такого хватит ненадолго (хотя мб и хватит). Стандартный путь это как вектор (просто элементов для открытой адресации или например листов для закрытой): реаллокация в k раз, чтобы LF получше стал. Как выбирать k смотрите два поста назад. Можно размеры только степенями двойки. Или можно делать статику снаружи и динамику внутри:
std::vector<std::pair<K, V>> data[1024];Может быть полезно в случае параллельной таблички или если вы локальность цепочки при закрытой адресации хотите.
4. Ключи.
Иногда нужно хранить какую-то мету, само значение (для сравнений каких-нибудь) или значение хеша. В зависимости от того, насколько много занимает ваша структурка, можно выбирать, хранить например всё в одном массивчике или может ключи/значения отдельно, чтобы в кеши хорошо попадало что надо. Тут конечно всё зависит от вашего паттерна доступа.
Кстати забавно, что если объект жирный, можно попробовать хранить первые k байт его представления и сравнивать их. Или можно вообще не сравнивать изначальные ключи с одинаковыми значениями хеша, если вы уверены в хеш-функции или готовы иногда ошибаться.
👍6
#algo
Хеш-таблицы 2/2.
5. Пробинг при открытой адресации.
Пробинг -- то, как вы двигаетесь по таблице в поиске свободного места. Очевидно можно линейный:
6. Доп. требования.
Иногда нужно хранить порядок вставки. Тогда давайте рядом хранить двусвязный лист, а в каждом бакете хранить итератор на начало подцепочки этого бакета в листе и размер подцепочки. Ещё кстати и перебор всех элементов за их количество.
А может ещё вы хотите на каком-то интервале читать значения, тогда вам не хеш-таблица нужна, но об этом попозже : )
7. И немного читов.
-- можно как в LRU-кеше при закрытой адресации найденный где-то в глубине листа элемент перемещать в самое начало, чтобы в следующий раз его поиск прошёл быстрее. В открытой адресации наверное тоже можно посвапать аккуратно с удалённым элементом например, но звучит как что-то, где легко споткнуться.
-- хешировать можно не просто пришедший элемент, а что угодно. Можете хешировать хеш от хеша от хеша. Или первые 8 байт объекта. Или для чисел сначала 228 добавить. Короче вертеть как хочешь, абы хорошо было.
-- вместо листа/вектора при закрытой адресации можете хранить что-то другое. В java например с какого-то момента лист превращается в bst.
[1]. Hash map analysis.
[2]. Extendible hashing.
[3]. Я написал самую быструю хеш-таблицу.
[4]. Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step [видео].
[5]. О хеш-таблицах в Clickhouse [видео].
Хеш-таблицы 2/2.
5. Пробинг при открытой адресации.
Пробинг -- то, как вы двигаетесь по таблице в поиске свободного места. Очевидно можно линейный:
offset[i] = i или i*k. Можно квадратический: offset[i] = i*i или даже alpha*i + beta*i*i. Или double hashing: offset[i] = i*hash2(key). Или cuckoo hashing (ну придумали конечно): для любого ключа проверяем две точки от двух хеш-функций; если есть место, вставляем, иначе выбираем одного из этих двух оккупантов и выселяем его, а на его место наш элемент; аналогично делаем с выселенным элементом; если такое повторяется некоторое количество раз, меняем хеш-функцию и рехеш. Прикольно, что такой приём гарантирует O(1) на поиск. 6. Доп. требования.
Иногда нужно хранить порядок вставки. Тогда давайте рядом хранить двусвязный лист, а в каждом бакете хранить итератор на начало подцепочки этого бакета в листе и размер подцепочки. Ещё кстати и перебор всех элементов за их количество.
А может ещё вы хотите на каком-то интервале читать значения, тогда вам не хеш-таблица нужна, но об этом попозже : )
7. И немного читов.
-- можно как в LRU-кеше при закрытой адресации найденный где-то в глубине листа элемент перемещать в самое начало, чтобы в следующий раз его поиск прошёл быстрее. В открытой адресации наверное тоже можно посвапать аккуратно с удалённым элементом например, но звучит как что-то, где легко споткнуться.
-- хешировать можно не просто пришедший элемент, а что угодно. Можете хешировать хеш от хеша от хеша. Или первые 8 байт объекта. Или для чисел сначала 228 добавить. Короче вертеть как хочешь, абы хорошо было.
-- вместо листа/вектора при закрытой адресации можете хранить что-то другое. В java например с какого-то момента лист превращается в bst.
[1]. Hash map analysis.
[2]. Extendible hashing.
[3]. Я написал самую быструю хеш-таблицу.
[4]. Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step [видео].
[5]. О хеш-таблицах в Clickhouse [видео].
👍13❤1
#list
Пам-пам. Наступила очередь пачки рандомных фактов/ссылок/чего-то ещё.
1. Я думаю, уже чуть ли не каждый видел концепты из C++20. Интересный факт, что в текущем виде (авторства Andrew Sutton'а) они называются concepts lite, потому что первые концепты авторства Bjarne Stroustrup выглядели примерно так:
Ух. Тут и семантические ограничения, и синтаксические. И бог весть знает что ещё. Собсна потому текущие концепты это lite. Потому что была вот такая хардовая версия, которую отказались принимать, потому ту мач сложно. Можете вот тут чуть-чуть почитать.
2. В дополнение к концептам хотят подвезти контракты. Конечно по срокам ничего не понятно. Вот так это примерно будет выглядеть:
Можно посмотреть старый пропозал из любопытства.
Вот текущий. Пока ещё есть вопросы по синтаксису. В качестве расширения в будущем ещё предлагают сделать захват по значению переменных (не оч понял зачем).
3. Это конечно же баян, но вот пример:
В таком виде код не скомпилируется, потому что в нашей структурке нет такой функции, и неизвестно, будет ли она в специализации A. Чтобы сообщить, что g() есть в каждой специализации A можно заюзать самую недооценённую фичу:
4. Давайте посмотрим на сигнатуру
Зачем тут возвращается
Тут тоже компаратор -- любой функтор. Но функция ничего не возвращает : ) Лол короч.
5. Интересный факт, что возможность NRVO (т.к. это необязательная оптимизация) выясняется по анализу скоупа, а не конкретного выполняющегося кода. Можно посмотреть примеры и пояснений в этом и следующем постах на канале (кстати довольно интересном) у @cloudy_district.
6. На летней C++ Zero Cost Conf был доклад Тимура Думлера про real-time вычисления. Интересно было как минимум понять, о чём это. Кстати увидел на том же канале : )
Тут есть интересный факт, что нельзя иметь одновременно равновероятный для всех чисел в промежутке рандом, работающий за детерменированное кол-во шагов. Либо одно, либо второе.
7. Ещё у Жени есть очень крутые статьи на хабре. Кажется, пару штук я даже постил. Из последнего мне очень понравилось про Неклассические контейнеры в C++. Увидел бы я её, когда писал пост про вектор...
Кстати из неё узнал, что в бусте некоторым контейнерам можно задавать политику ресайза. Правда в довольно простом виде, но всё же.
8. Интересная заметка о том, как отлаживать bash-скрипты.
9. Как и зачем писать хороший код. Доклад Григория Петрова на Golang Conf 2019. Кстати довольно известный, я так понял, в локальных кругах чувак. По крайней мере он вёл несколько промежуточных бесед на Highload++ Foundation 2022 в середине мая. Что-то удалось посмотреть, почти всё не удалось посмотреть. Будем полгода ждать записи, отсматривать и рассказывать вам.
Пам-пам. Наступила очередь пачки рандомных фактов/ссылок/чего-то ещё.
1. Я думаю, уже чуть ли не каждый видел концепты из C++20. Интересный факт, что в текущем виде (авторства Andrew Sutton'а) они называются concepts lite, потому что первые концепты авторства Bjarne Stroustrup выглядели примерно так:
concept EqualityComparable<typename T> {
requires constraint Equal<T>;
requires axiom Equivalence_relation<Equal<T>, T>;
// if x == y then for any Predicate p, p(x) == p(y)
template <Predicate p>
axiom Equality(T x, T y, P p) {
x == y => p(x) == p(y);
}
// inequality is the negation of equality
axiom Inequality(T x, T y) {
(x != y) == !(x == y);
}
};Ух. Тут и семантические ограничения, и синтаксические. И бог весть знает что ещё. Собсна потому текущие концепты это lite. Потому что была вот такая хардовая версия, которую отказались принимать, потому ту мач сложно. Можете вот тут чуть-чуть почитать.
2. В дополнение к концептам хотят подвезти контракты. Конечно по срокам ничего не понятно. Вот так это примерно будет выглядеть:
int f(int x, int y)
[[ expects: x > 0 ]] // precondition
[[ expects: y > 0 ]] // precondition
[[ ensures r: r < x + y ]] // postcondition
{
int z = (x - x%y) / y;
[[ assert: z >= 0 ]]; // assertion
return z + y;
}Можно посмотреть старый пропозал из любопытства.
Вот текущий. Пока ещё есть вопросы по синтаксису. В качестве расширения в будущем ещё предлагают сделать захват по значению переменных (не оч понял зачем).
3. Это конечно же баян, но вот пример:
template <class T> struct A {
void g() {}
};
template <class T> struct C : A<T> {
void f() { g(); }
};В таком виде код не скомпилируется, потому что в нашей структурке нет такой функции, и неизвестно, будет ли она в специализации A. Чтобы сообщить, что g() есть в каждой специализации A можно заюзать самую недооценённую фичу:
this:template <class T> struct C : A<T> {
void f() { this->g(); }
// or using A<T>::g;
};4. Давайте посмотрим на сигнатуру
std::for_each:template<class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f);Зачем тут возвращается
UnaryFunction? Подразумевается, что ваш функтор может быть быть классом с каким-то стейтом, потому нужно вернуть итоговый функтор. Интересно, что в std::sort логика другая:template<class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);Тут тоже компаратор -- любой функтор. Но функция ничего не возвращает : ) Лол короч.
5. Интересный факт, что возможность NRVO (т.к. это необязательная оптимизация) выясняется по анализу скоупа, а не конкретного выполняющегося кода. Можно посмотреть примеры и пояснений в этом и следующем постах на канале (кстати довольно интересном) у @cloudy_district.
6. На летней C++ Zero Cost Conf был доклад Тимура Думлера про real-time вычисления. Интересно было как минимум понять, о чём это. Кстати увидел на том же канале : )
Тут есть интересный факт, что нельзя иметь одновременно равновероятный для всех чисел в промежутке рандом, работающий за детерменированное кол-во шагов. Либо одно, либо второе.
7. Ещё у Жени есть очень крутые статьи на хабре. Кажется, пару штук я даже постил. Из последнего мне очень понравилось про Неклассические контейнеры в C++. Увидел бы я её, когда писал пост про вектор...
Кстати из неё узнал, что в бусте некоторым контейнерам можно задавать политику ресайза. Правда в довольно простом виде, но всё же.
8. Интересная заметка о том, как отлаживать bash-скрипты.
9. Как и зачем писать хороший код. Доклад Григория Петрова на Golang Conf 2019. Кстати довольно известный, я так понял, в локальных кругах чувак. По крайней мере он вёл несколько промежуточных бесед на Highload++ Foundation 2022 в середине мая. Что-то удалось посмотреть, почти всё не удалось посмотреть. Будем полгода ждать записи, отсматривать и рассказывать вам.
👍6🔥1
#algo
Вероятностные структуры данных 1/2.
Иногда бывают задачи, когда вы готовы пожертвовать точностью каких-то значений ради скорости работы/любой другой характеристики. Пробежимся по самым известным.
1. Фильтр Блума решает задачу проверки значения во множестве. Изначально это какой-то битсет размера m и рядом k хеш-функций. При добавлении элемента во множество с помощью хеш-функций определяется k битов, которые устанавливаются в 1. Теперь при необходимости проверить, находится ли элемент во множестве, считаем от него все хеш-функции и проверяем, правда ли, что все интересующие нас биты установлены в 1. Проблемы: иногда могут возникать ложноположительные срабатывания (элемента нет, а мы ответили, что есть); нельзя удалять элементы (один и тот же бит может быть установлен различными элементами). В таком виде два фильтра легко объединять/пересекать (побитовое ИЛИ/И множеств). В отличие от хеш-таблиц (или чего-то подобного) фильтр блума может являться универсальным множеством (все биты == 1).
Есть разные вариации: вместо 0/1 можно хранить числа и при добавлении инкрементить соответствующие значения, а при удалении декрементить (counting bf); вместо одного counting bf можно хранить n независимых (bitwise почему-то); spectral bf — оптимизированный counting; aging bf, который поддерживает операцию удаления и не хранит старые данные; stable bf, в котором мы рандомно декрементим несколько значений, после чего k значениям устанавливаем максимальные значения (утверждается, что рано или поздно получится достичь какого-то константного кол-ва нулей, магия); A^2 bf — теп memory efficient implementation; ну и конечно более менее умеющий в удаление bf (если кратко, разрешается некоторые участки помечаются как collision-unsafe, и удаление из них не происходит).
Тут ещё можно считать конкретные размеры битсета и кол-во хеш-функций исходя из допустимой пропорции ошибок.
Иногда юзается в кешах или как вспомогательная структура для других сд.
Ещё можно строить key-value хранилище на bf. Если вам нужно что-то вроде
Ещё давайте такой пример. Нам нужно на устройстве пользователя (допотопный мобильный телефон == мало памяти) понимать, звонит нам спамер или нет. Давайте все телефоны из базы спамерских закинем в bf. Чтобы избежать false-positive срабатываний, пройдёмся по всему множеству телефонов (для 10циферных вполне реально) и выпишем рядом с bf номера, на которых мы ошибаемся (их не будет много, порядка единиц при хорошем bf). Теперь если bf говорит, что номер спамерский, проверим, есть ли он в отдельно выписаных. И теперь мы умеем точно отвечать при очень маленьких затратах памяти. Тут можно почитать реальные кейсы.
А ещё можно на них bst строить. А ещё можно в борах юзать. Ух короче.
Основной link.
2. Count-min sketch помогает насчитать частотность различных объектов (например у нас есть бесконечный поток данных, и хочется уметь выдавать примерную частоту появления объектов, причём с очень маленькими затратами на время/память).
Структура очень простая: k хеш-таблиц фиксированного размера (можно одного, можно разных). Изначально все они заполнены нулями. Как только нужно добавить объект, инкрементим соответствующую этому объекту ячейку в каждой хеш-таблице. При запросе узнать частоту объекта, берём значения объекта из каждой хеш-таблицы и считаем минимум. Собственно всё. Понятно, что чем больше хеш-табличек вы берёте, тем ближе ответ будет к реальному, иначе из-за коллизий может получится завышенным.
Ещё если знаем, что элемент есть во множестве, можно удалять.
Только пишется это обычно не как несколько хеш-таблиц, а матрицей + хеш-функцию на каждую строку.
Ещё их легко объединять и (если одно множество строго подмножество второго) вычитать.
Тут (осторожно, скачается пдфка) есть про применение в безопасности, базах данных и даже биоинформатике.
Вероятностные структуры данных 1/2.
Иногда бывают задачи, когда вы готовы пожертвовать точностью каких-то значений ради скорости работы/любой другой характеристики. Пробежимся по самым известным.
1. Фильтр Блума решает задачу проверки значения во множестве. Изначально это какой-то битсет размера m и рядом k хеш-функций. При добавлении элемента во множество с помощью хеш-функций определяется k битов, которые устанавливаются в 1. Теперь при необходимости проверить, находится ли элемент во множестве, считаем от него все хеш-функции и проверяем, правда ли, что все интересующие нас биты установлены в 1. Проблемы: иногда могут возникать ложноположительные срабатывания (элемента нет, а мы ответили, что есть); нельзя удалять элементы (один и тот же бит может быть установлен различными элементами). В таком виде два фильтра легко объединять/пересекать (побитовое ИЛИ/И множеств). В отличие от хеш-таблиц (или чего-то подобного) фильтр блума может являться универсальным множеством (все биты == 1).
Есть разные вариации: вместо 0/1 можно хранить числа и при добавлении инкрементить соответствующие значения, а при удалении декрементить (counting bf); вместо одного counting bf можно хранить n независимых (bitwise почему-то); spectral bf — оптимизированный counting; aging bf, который поддерживает операцию удаления и не хранит старые данные; stable bf, в котором мы рандомно декрементим несколько значений, после чего k значениям устанавливаем максимальные значения (утверждается, что рано или поздно получится достичь какого-то константного кол-ва нулей, магия); A^2 bf — теп memory efficient implementation; ну и конечно более менее умеющий в удаление bf (если кратко, разрешается некоторые участки помечаются как collision-unsafe, и удаление из них не происходит).
Тут ещё можно считать конкретные размеры битсета и кол-во хеш-функций исходя из допустимой пропорции ошибок.
Иногда юзается в кешах или как вспомогательная структура для других сд.
Ещё можно строить key-value хранилище на bf. Если вам нужно что-то вроде
k->v \in [0; 10], давайте держать 11 bf, и по значению v решать, в какой bf добавить ключ. При получении значения пройдёмся по всем bf и в котором нашли ключ, такое и значение.Ещё давайте такой пример. Нам нужно на устройстве пользователя (допотопный мобильный телефон == мало памяти) понимать, звонит нам спамер или нет. Давайте все телефоны из базы спамерских закинем в bf. Чтобы избежать false-positive срабатываний, пройдёмся по всему множеству телефонов (для 10циферных вполне реально) и выпишем рядом с bf номера, на которых мы ошибаемся (их не будет много, порядка единиц при хорошем bf). Теперь если bf говорит, что номер спамерский, проверим, есть ли он в отдельно выписаных. И теперь мы умеем точно отвечать при очень маленьких затратах памяти. Тут можно почитать реальные кейсы.
А ещё можно на них bst строить. А ещё можно в борах юзать. Ух короче.
Основной link.
2. Count-min sketch помогает насчитать частотность различных объектов (например у нас есть бесконечный поток данных, и хочется уметь выдавать примерную частоту появления объектов, причём с очень маленькими затратами на время/память).
Структура очень простая: k хеш-таблиц фиксированного размера (можно одного, можно разных). Изначально все они заполнены нулями. Как только нужно добавить объект, инкрементим соответствующую этому объекту ячейку в каждой хеш-таблице. При запросе узнать частоту объекта, берём значения объекта из каждой хеш-таблицы и считаем минимум. Собственно всё. Понятно, что чем больше хеш-табличек вы берёте, тем ближе ответ будет к реальному, иначе из-за коллизий может получится завышенным.
Ещё если знаем, что элемент есть во множестве, можно удалять.
Только пишется это обычно не как несколько хеш-таблиц, а матрицей + хеш-функцию на каждую строку.
Ещё их легко объединять и (если одно множество строго подмножество второго) вычитать.
Тут (осторожно, скачается пдфка) есть про применение в безопасности, базах данных и даже биоинформатике.
👍8
#algo
Вероятностные структуры данных 2/2.
3. HyperLogLog используют, чтобы узнать примерное количество уникальных элементов в мультимножестве.
Тут у нас опять есть k хеш-функций, каждая из которых выдаёт значения от 0 до 2^64-1. Значение хеш-функции это какая-то последовательность из 64 нулей и единиц. Теперь немного помахаем руками. Будем считать, что наши хеш-функции "хорошие", i.e. плюс-минус равномерно распределены (хотя вообще-то мы хотим этого для всех структур). Тогда хеш равновероятно может начаться с нуля и единицы (с p=1/2). Аналогично с 01 с p=1/4, с 001 с p=1/8, 0001 — 1/16 и т.д. Т.е. если мы встретили хеш с префиксом 0000001 (а такое могло произойти только с p=1/128), то мы можем сказать, что в мультимножестве примерно 128 элементов (на больших числах конечно же). Конечно же такая оценка может легко сломаться, если нам попадётся один случайный хеш с длинным префиксом нулей. Для обхода все элементы потока делят на несколько подпотоков (например по очереди отправляют сначала в 1й, потом во 2й, в 3й и в 4й), считают максимальную длину префикса в каждом подпотоке среди всех хеш-функций (например 1, 5, 8, 3) и считают среднее гармоническое на страшные коэффициенты из тервера:
Сейчас есть следующая проблема: если неаккуратно делить на подпотоки, то какой-нибудь частый элемент, дающий маленький хеш, испортит нам все подпотоки. Потому давайте номер подпотока определять по первым k битам хеша. Т.е. если у нас пришёл объект с хешом
Такая структура легко мержится. Предположим у нас есть посчитанный HLL для мультимножества A (массив из n чисел, где n — кол-во подпотоков, а i-е число в нём — позиция самой правой единицы в этом подпотоке) и HLL для B, то смержить их это за O(n) посчитать максимум из двух для каждой ячейки. Соответственно HLL легко параллелится (каждый чанк мультимножества считаем независимо, а потом мержим).
Если немного покумекать-покрутить включения-исключения, можно научиться пересекать/вычитать несколько HLL.
HLL юзается в redis (или статья), или например под капотом для approx_count_distinct в других бд.
4. MinHash используется для оценки мощности пересечения множеств (например будем считать два текста похожими, если множества их слов похожи; можем не храня эти огромные тексты таким примитивным методом задетектить плагиат). Тут вводится коэффициент Жаккара:
Берём k хеш-функций. Считаем значения всех хеш-функций для каждого элемента множества A. Среди значений каждой хеш-функции берём минимум. Получаем массив из k элементов, каждый из которых равен минимальному значению некоторой хеш-функции на этом множестве. Повторяем то же для множества B. И теперь считаем коэффициент Жаккара двух векторов с хешами. Утверждается, что он очень хорошо приближает
Иногда вместо k хеш-функций берут одну, но считают k её минимальных значений. Или одну по разным простым модулям.
Ну и тут link на какие-то юзкейсы.
Вот такую магию люди придумывают, а у нас до сих пор горячую воду отключают на две недели. Мир контрастов.
Вероятностные структуры данных 2/2.
3. HyperLogLog используют, чтобы узнать примерное количество уникальных элементов в мультимножестве.
Тут у нас опять есть k хеш-функций, каждая из которых выдаёт значения от 0 до 2^64-1. Значение хеш-функции это какая-то последовательность из 64 нулей и единиц. Теперь немного помахаем руками. Будем считать, что наши хеш-функции "хорошие", i.e. плюс-минус равномерно распределены (хотя вообще-то мы хотим этого для всех структур). Тогда хеш равновероятно может начаться с нуля и единицы (с p=1/2). Аналогично с 01 с p=1/4, с 001 с p=1/8, 0001 — 1/16 и т.д. Т.е. если мы встретили хеш с префиксом 0000001 (а такое могло произойти только с p=1/128), то мы можем сказать, что в мультимножестве примерно 128 элементов (на больших числах конечно же). Конечно же такая оценка может легко сломаться, если нам попадётся один случайный хеш с длинным префиксом нулей. Для обхода все элементы потока делят на несколько подпотоков (например по очереди отправляют сначала в 1й, потом во 2й, в 3й и в 4й), считают максимальную длину префикса в каждом подпотоке среди всех хеш-функций (например 1, 5, 8, 3) и считают среднее гармоническое на страшные коэффициенты из тервера:
k*(2^(-1) + 2^(-5) + 2^(-8) + 2^(-3))^(-1)
Примерно столько элементов в нашем мультимножестве. Сейчас есть следующая проблема: если неаккуратно делить на подпотоки, то какой-нибудь частый элемент, дающий маленький хеш, испортит нам все подпотоки. Потому давайте номер подпотока определять по первым k битам хеша. Т.е. если у нас пришёл объект с хешом
0010|0010...01, то по первым например 4 битам мы определим, что его подпоток номер 2, а считать позицию первой единицы будем начиная с 5ого бита (в этом примере она равна 3). Если в этом подпотоке уже был элемент с единицей дальше, то просто забываем эту тройку, иначе, если это дальше, чем было до текущего момента, считаем, что 3 у нас самая далёкая. Таким образом частые элементы будут портить один и тот же подпоток.Такая структура легко мержится. Предположим у нас есть посчитанный HLL для мультимножества A (массив из n чисел, где n — кол-во подпотоков, а i-е число в нём — позиция самой правой единицы в этом подпотоке) и HLL для B, то смержить их это за O(n) посчитать максимум из двух для каждой ячейки. Соответственно HLL легко параллелится (каждый чанк мультимножества считаем независимо, а потом мержим).
Если немного покумекать-покрутить включения-исключения, можно научиться пересекать/вычитать несколько HLL.
HLL юзается в redis (или статья), или например под капотом для approx_count_distinct в других бд.
4. MinHash используется для оценки мощности пересечения множеств (например будем считать два текста похожими, если множества их слов похожи; можем не храня эти огромные тексты таким примитивным методом задетектить плагиат). Тут вводится коэффициент Жаккара:
J(A, B) = |пересечения|/|объединения|
Как это работает.Берём k хеш-функций. Считаем значения всех хеш-функций для каждого элемента множества A. Среди значений каждой хеш-функции берём минимум. Получаем массив из k элементов, каждый из которых равен минимальному значению некоторой хеш-функции на этом множестве. Повторяем то же для множества B. И теперь считаем коэффициент Жаккара двух векторов с хешами. Утверждается, что он очень хорошо приближает
J(A, B). Тут можно считать пересечение двух векторов не как множеств, а совпадение по позициям.Иногда вместо k хеш-функций берут одну, но считают k её минимальных значений. Или одну по разным простым модулям.
Ну и тут link на какие-то юзкейсы.
Вот такую магию люди придумывают, а у нас до сих пор горячую воду отключают на две недели. Мир контрастов.
👍8🤯3
#list
1. Оч забавный факт, что до C++11 не оставить пустую строку в конце хедера приводило к ub. Препроцессор был настолько глупым, что не догадывался вставить после директивы include перевод строки. Пример:
Прикиньте, если последней строкой шёл комментарий.
2. Немного пропозалов:
- =delete("message"): добавление сообщения при удалении метода/перегрузки;
- добавление saturation arithmetic (это когда все операции ограничены каким-то диапазоном значений);
- разрешить static_assert(false). Сейчас вот такой код не скомпилируется:
Иногда хочется, чтобы работало. Для обхода используют некоторый контекстозависимый trait:
- explicit lifetime managment.
3. Два интересных предложения от рускоязычного сообщества:
- новые математические функции: std::sincos, std::invsqrt, std::rem;
- запретить удаление incomplete классов.
4. На одном из докладов Highload++ чувак из Яндекс Go рассказывал, как они ускорялись. И одним из методов были так называемые hedged requests: сначала вы посылаете запрос (на более подходящую реплику, если у вас есть такая информация), а после него с какой-то небольшой задержкой повторяете (куда-нибудь ещё). В итоге у вас есть несколько запросов, которые выполняются наперегонки. Как только приходит первый ответ, берём его результат и игнорируем остальные. Прикона.
5. Иногда пишут двусвязные списки как xor-листы. В таком случае вместо двух указателей next prev хранится их xor. Таким образом вы можете перемещаться по листу только от начала до конца. Если же вы попали в какую-то ноду случайно, вы не сможете получить адреса её соседей.
1. Оч забавный факт, что до C++11 не оставить пустую строку в конце хедера приводило к ub. Препроцессор был настолько глупым, что не догадывался вставить после директивы include перевод строки. Пример:
Imagine foo.h:
blah blah blah<no newline>
Now bar.c:
#include "foo.h"
#include "grill.h"
Result:
blah blah blah#include "grill.h"Прикиньте, если последней строкой шёл комментарий.
2. Немного пропозалов:
- =delete("message"): добавление сообщения при удалении метода/перегрузки;
- добавление saturation arithmetic (это когда все операции ограничены каким-то диапазоном значений);
- разрешить static_assert(false). Сейчас вот такой код не скомпилируется:
if constexpr (true) {
int x;
} else {
static_assert(false);
}Иногда хочется, чтобы работало. Для обхода используют некоторый контекстозависимый trait:
static_assert(!std::is_same<T, T>::value);- explicit lifetime managment.
3. Два интересных предложения от рускоязычного сообщества:
- новые математические функции: std::sincos, std::invsqrt, std::rem;
- запретить удаление incomplete классов.
4. На одном из докладов Highload++ чувак из Яндекс Go рассказывал, как они ускорялись. И одним из методов были так называемые hedged requests: сначала вы посылаете запрос (на более подходящую реплику, если у вас есть такая информация), а после него с какой-то небольшой задержкой повторяете (куда-нибудь ещё). В итоге у вас есть несколько запросов, которые выполняются наперегонки. Как только приходит первый ответ, берём его результат и игнорируем остальные. Прикона.
5. Иногда пишут двусвязные списки как xor-листы. В таком случае вместо двух указателей next prev хранится их xor. Таким образом вы можете перемещаться по листу только от начала до конца. Если же вы попали в какую-то ноду случайно, вы не сможете получить адреса её соседей.
👍15❤1
#highload
Вы почти наверняка знаете про LRU (Last Recently Used) кеш. Давайте на всякий случай вспомним. Мы храним до k некоторых значений, при этом поддерживая время последнего обращения. При появлении в кеше k+1-ого элемента удаляем элемент, к которому обращение было "давнее" всего. Делается это просто: держим лист ключей (в начале самые молодые по времени обращения элементы, в конце самые старые) и мапку из ключа в итератор этого листа. При необходимости удалить, просто кикаем из листа последний элемент. При необходимости обновить время обращения к элементу, получаем из мапки итератор на ноду листа и переставляем её в самое начало. Базово так. У Антона Полухина есть интересный доклад про оптимизацию LRU. Речь о том коде, который является базой для кешей в половине случаев, которые я у нас вижу. Да, вы может видели мнения, что LRU -- неудачник среди кешей, но часто его хватает.
Чуть менее примитивным вариантов является сегментированный LRU. По факту это несколько LRU. Сначала кладём в первый кеш. При запросе элемента из него, перемешаем во второй. И т.д. Эти кеши условно можно называть cold, warm и hot (в случае трёх частей). Как будто поколения в сборщиках мусора.
Прокачаным LRU является 2Q. Тут есть три части. Первая (in) + вторая (out) -- обычная FIFO очередь. При добавлении в кеш элемент кладётся в in. Со временем он переходит в out (который обычно значительно больше in). Третья часть -- hot cache (например LRU). Элементы из in вытесняются в out.
Если запрашивается элемент, который в in, с ним ничего не происходит. Если который в out, он перемещается в hot. Если элемент был вытеснен в out и не запрашивается, он просто удаляется из кеша при достижении какого-то размера.
Юзается в postgres.
Хотя когда-то в postgres использовался ARC (adaptive replacement cache), но там тёрки за патенты с IBM. Суть в том, что у вас есть две части: L1 (для recently used элементов) и L2 (для частоиспользуемых элементов). Каждая L часть состоит тоже из двух частей: из самих элементов кеша (T) и из удалённых из него элементов (B/ghosts lists), которые тем не менее ещё трекаются. Если элемент из B1 опять появляется в кеше, он возвращается в T1. При этом один элемент из T2 вытесняется в B2. И наоборот. Такое взаимодействие вот.
LFU -- least frequently used. У каждого элемента есть счётчик количества обращений. Элемент с наименьшим значением счётчика удаляется. Если элементов с минимальным значением несколько, по порядку FIFO. Понятно, что очень просто сделать такое с помощью std::set, но есть алгоритм, который позволяет вставку, lookup и удаление за O(1) (опять хеш-таблица и связанные списки специфического вида).
Есть ещё несколько разных стратегий:
- MRU: удаляем последний использованный элемент (бережём старые элементы);
- Mid point LRU: сегментированный LRU с двумя частями (cold, hold);
- MQ: сегментированный LRU, в котором запоминается место, из которого элемент вытесняется (если знание о месте из кеша не пропало). При повторном появлении в кеше, он вставляется в это место. Так можно быстрее прогревать кеш при циклической ротации элементов.
- алгоритм Белади: отбрасывать из кеша ту информацию, которая не понадобится в будущем дольше всего. Так как в общем случае невозможно предсказать, когда в следующий раз пригодится именно эта информация, то на практике подобная реализация невозможна (в общем случае). Можно вычислить опытным путём, после чего сравнить такую реализацию с текущим кешом;
- pseudo-LRU: оптимизированный LRU, позволяющий тратить гораздо меньше памяти.
=============================
Заканчиваю вот универ. Чувствую, как появляется больше времени на (пора)ботать, пусть и последние несколько месяцев ничего почти по нему не делал. Хочется наконец найти силы и методично разобрать огромный накопившийся беклог + попробовать в пару начинаний. Непонятно, как оно получится и получится ли вообще, но если будут предприниматься какие-то действия, обязательно поделюсь.
Вы почти наверняка знаете про LRU (Last Recently Used) кеш. Давайте на всякий случай вспомним. Мы храним до k некоторых значений, при этом поддерживая время последнего обращения. При появлении в кеше k+1-ого элемента удаляем элемент, к которому обращение было "давнее" всего. Делается это просто: держим лист ключей (в начале самые молодые по времени обращения элементы, в конце самые старые) и мапку из ключа в итератор этого листа. При необходимости удалить, просто кикаем из листа последний элемент. При необходимости обновить время обращения к элементу, получаем из мапки итератор на ноду листа и переставляем её в самое начало. Базово так. У Антона Полухина есть интересный доклад про оптимизацию LRU. Речь о том коде, который является базой для кешей в половине случаев, которые я у нас вижу. Да, вы может видели мнения, что LRU -- неудачник среди кешей, но часто его хватает.
Чуть менее примитивным вариантов является сегментированный LRU. По факту это несколько LRU. Сначала кладём в первый кеш. При запросе элемента из него, перемешаем во второй. И т.д. Эти кеши условно можно называть cold, warm и hot (в случае трёх частей). Как будто поколения в сборщиках мусора.
Прокачаным LRU является 2Q. Тут есть три части. Первая (in) + вторая (out) -- обычная FIFO очередь. При добавлении в кеш элемент кладётся в in. Со временем он переходит в out (который обычно значительно больше in). Третья часть -- hot cache (например LRU). Элементы из in вытесняются в out.
Если запрашивается элемент, который в in, с ним ничего не происходит. Если который в out, он перемещается в hot. Если элемент был вытеснен в out и не запрашивается, он просто удаляется из кеша при достижении какого-то размера.
Юзается в postgres.
Хотя когда-то в postgres использовался ARC (adaptive replacement cache), но там тёрки за патенты с IBM. Суть в том, что у вас есть две части: L1 (для recently used элементов) и L2 (для частоиспользуемых элементов). Каждая L часть состоит тоже из двух частей: из самих элементов кеша (T) и из удалённых из него элементов (B/ghosts lists), которые тем не менее ещё трекаются. Если элемент из B1 опять появляется в кеше, он возвращается в T1. При этом один элемент из T2 вытесняется в B2. И наоборот. Такое взаимодействие вот.
LFU -- least frequently used. У каждого элемента есть счётчик количества обращений. Элемент с наименьшим значением счётчика удаляется. Если элементов с минимальным значением несколько, по порядку FIFO. Понятно, что очень просто сделать такое с помощью std::set, но есть алгоритм, который позволяет вставку, lookup и удаление за O(1) (опять хеш-таблица и связанные списки специфического вида).
Есть ещё несколько разных стратегий:
- MRU: удаляем последний использованный элемент (бережём старые элементы);
- Mid point LRU: сегментированный LRU с двумя частями (cold, hold);
- MQ: сегментированный LRU, в котором запоминается место, из которого элемент вытесняется (если знание о месте из кеша не пропало). При повторном появлении в кеше, он вставляется в это место. Так можно быстрее прогревать кеш при циклической ротации элементов.
- алгоритм Белади: отбрасывать из кеша ту информацию, которая не понадобится в будущем дольше всего. Так как в общем случае невозможно предсказать, когда в следующий раз пригодится именно эта информация, то на практике подобная реализация невозможна (в общем случае). Можно вычислить опытным путём, после чего сравнить такую реализацию с текущим кешом;
- pseudo-LRU: оптимизированный LRU, позволяющий тратить гораздо меньше памяти.
=============================
Заканчиваю вот универ. Чувствую, как появляется больше времени на (пора)ботать, пусть и последние несколько месяцев ничего почти по нему не делал. Хочется наконец найти силы и методично разобрать огромный накопившийся беклог + попробовать в пару начинаний. Непонятно, как оно получится и получится ли вообще, но если будут предприниматься какие-то действия, обязательно поделюсь.
👍16
#list
Чуть-чуть разгребаюсь с беклогом (со скоростью черепахи конечно). Вот вам пачка ссылок почитать:
1. У Жени (автора @cxx95) есть вот такая замечательная статья про создание нового ключевого слова в C++: defer. И не читами с деструкторами и макросами, а честным патчем кланга.
2. В посте выше обнаружилась ссылка на статью про историю LLVM (местами правда со спорными тезисами). Довольно интересно.
3. The true price of virtual functions in C++.
Тут можно почитать о том, какие проблемы возникают при использовании виртуальных функций (с пруфами в виде бенчмарков) и о том, как с этим попытаться побороться, если вам оч надо. Стало чуть понятнее, почему иногда вместо наследования упарываются с CRTP.
4. Хороший (хотя может и немного скучноватый) доклад про рандом в плюсах. Тут разбирается их концептуальное устройство, какие-то проблемы с реализацией своего рандома и немного best practice.
По проблемам есть такой пример: пусть e -- какой-то random engine. Мы хотим сэмулировать бросок кубика:
Но такое решение имеет несколько проблем, из-за которых кубик становится не совсем честным. Предлагаю посмотреть : )
5. Ещё у меня есть список интересных вопросов на stackoverlfow, которыми хотелось бы поделиться (по чуть-чуть конечно🙃):
- про branch prediction;
- почему
- про использование
====================
В Москве видел машины убера с надписью Uber -> ub. Надеюсь, это не о качестве их кода.
Чуть-чуть разгребаюсь с беклогом (со скоростью черепахи конечно). Вот вам пачка ссылок почитать:
1. У Жени (автора @cxx95) есть вот такая замечательная статья про создание нового ключевого слова в C++: defer. И не читами с деструкторами и макросами, а честным патчем кланга.
2. В посте выше обнаружилась ссылка на статью про историю LLVM (местами правда со спорными тезисами). Довольно интересно.
3. The true price of virtual functions in C++.
Тут можно почитать о том, какие проблемы возникают при использовании виртуальных функций (с пруфами в виде бенчмарков) и о том, как с этим попытаться побороться, если вам оч надо. Стало чуть понятнее, почему иногда вместо наследования упарываются с CRTP.
4. Хороший (хотя может и немного скучноватый) доклад про рандом в плюсах. Тут разбирается их концептуальное устройство, какие-то проблемы с реализацией своего рандома и немного best practice.
По проблемам есть такой пример: пусть e -- какой-то random engine. Мы хотим сэмулировать бросок кубика:
e() % 6 + 1Но такое решение имеет несколько проблем, из-за которых кубик становится не совсем честным. Предлагаю посмотреть : )
5. Ещё у меня есть список интересных вопросов на stackoverlfow, которыми хотелось бы поделиться (по чуть-чуть конечно🙃):
- про branch prediction;
- почему
std::reduce требует для операции коммутативность (мы когда-то писали свой и не налагали такие требования, потому возник вопрос; спойлер: для векторизации);- про использование
auto вместе с приватными типами. ====================
В Москве видел машины убера с надписью Uber -> ub. Надеюсь, это не о качестве их кода.
👍8
#pub #algo
Пиу-пау.
Если вам так же как и мне нравится узнавать интересные (пусть и бесполезные) идеи, которые вы никогда на практике не заюзаете, предлагаю почитать мою новую статью про нестандартные (но простые) структуры данных.
https://habr.com/ru/post/673776/
Пиу-пау.
Если вам так же как и мне нравится узнавать интересные (пусть и бесполезные) идеи, которые вы никогда на практике не заюзаете, предлагаю почитать мою новую статью про нестандартные (но простые) структуры данных.
https://habr.com/ru/post/673776/
👍17👎1🔥1
#common
(сейчас будет капитан очевидность, но получите)
Я очень люблю рефакторить.
Прям кипятком ссусь. Сегодня в любом более менее взрослом проекте с несколькими разработчиками огромное количество кода. Всю смысловую нагрузку уже давно невозможно держать в голове. Ты можешь понимать какие-то основные подходы написанного. Может даже детали реализации (зачем именно так что-то было сделано). Но помнить абсолютно всё нереально. И это проблема.
Размеры текущей кодовой базы, в которой вы ежедневно сидите, только растут. С каждой новой таской вы приходите в пусть даже уже и знакомые (хотя часто всё равно нет) места и тратите время на то, чтобы понять вводные, которые вам код предоставляет. Иногда вы пытаетесь разобраться даже в своём собственном коде (я вот недавно наткнулся на непонятное место, которое накодил полгода назад; пришлось покопаться и вспомнить, что меня сподвигло на такой код). Рассогласованность действий разработчиков тоже подкидывает хаоса. Кто-то может сидеть в конкретном сервисе довольно продолжительное время, а кто-то мимокрокодилом пролетел и закоммитил что-то некрасивое/объёмное просто потому что он не знал, что принято/можно сделать лучше. После какого-то времени начинаешь замечать, что одни действия делаются по-разному, что где-то используются обобщения для сокращения количества кода, а где-то нет. С приходом новых участников возникает всё больше вопросов, почему тут сделано так, а тут нет. На это всё тратится время. Очень драгоценное время.
Чтобы со всем этим бороться, можно:
1. Помнить про ревью.
Делать хорошее ревью это важно. Не только с точки зрения корректности логики, но и удачности технической реализации. У меня иногда прохождение ревью занимает столько же, сколько и сама задача (и это не потому что я говнокодер, честно; а потому что ревьюеры обладает более широкой экспертизой и оставляют замечательные комментарии).
Отдавать на ревью не одному человеку. Понятно, что кто-то понимает конкретно в этом месте больше, чем другие. У меня недавно был кейс, когда один коллега оставил неплохое, но небольшое ревью на пр, а чувак из соседней команды, которому пр попался совершенно случайно, накидал комментов ещё на два целых рабочих дня. И всё по делу. Понятно, что тут стоит найти компромисс между полезностью и потраченным количеством человекачасов, но если есть возможность, почему ей не воспользоваться.
Если у вас нет практики ревью (такое бывает, да), всеми силами пытаться её ввести или хотя бы просить ревью на свои задачи. Особенно поначалу это позволяет многому научиться.
2. Тратить время не только на продуктовые задачи, но и на технические. Если в планы на следующий отрезок времени/спринт/самое ближайшее будущее у вас есть возможность запланировать/сделать/убедить коллег в необходимости что-нибудь зарефакторить, постарайтесь этим заняться. Это облегчит жизнь не только вам, но и всем разработчикам вокруг.
3. Ради бога, если вы в процессе решения задачи увидели что-то, что можно позже исправить, запишите это. А то некрасивый код так и останется неисправленным, пусть и обнаруженным. Всё помнить нереально и неполезно.
Сейчас речь идёт именно о (не)больших технических изменениях, потому что крупных продуктовых рефакторингов за свой небольшой опыт я пока не увидел (может вот сейчас наблюдаю за стартом такого процесса). Там всё примерно так же, только чуточку сложнее.
Есть кстати движение под названием Dead Code Society, которое продвигает идею выпиливания неиспользуемого кода. Слышал, что в больших компаниях есть похожие внутренние штуки (например довольно сильное в Meta). У нас тоже вроде что-то такое имеется, но как там у ребят успехи, хз. Свечку не держал.
UPD.
Рад, что вы пользуетесь реакциями кроме 👍 : )
Но их особенно приятно видеть.
(сейчас будет капитан очевидность, но получите)
Я очень люблю рефакторить.
Прям кипятком ссусь. Сегодня в любом более менее взрослом проекте с несколькими разработчиками огромное количество кода. Всю смысловую нагрузку уже давно невозможно держать в голове. Ты можешь понимать какие-то основные подходы написанного. Может даже детали реализации (зачем именно так что-то было сделано). Но помнить абсолютно всё нереально. И это проблема.
Размеры текущей кодовой базы, в которой вы ежедневно сидите, только растут. С каждой новой таской вы приходите в пусть даже уже и знакомые (хотя часто всё равно нет) места и тратите время на то, чтобы понять вводные, которые вам код предоставляет. Иногда вы пытаетесь разобраться даже в своём собственном коде (я вот недавно наткнулся на непонятное место, которое накодил полгода назад; пришлось покопаться и вспомнить, что меня сподвигло на такой код). Рассогласованность действий разработчиков тоже подкидывает хаоса. Кто-то может сидеть в конкретном сервисе довольно продолжительное время, а кто-то мимокрокодилом пролетел и закоммитил что-то некрасивое/объёмное просто потому что он не знал, что принято/можно сделать лучше. После какого-то времени начинаешь замечать, что одни действия делаются по-разному, что где-то используются обобщения для сокращения количества кода, а где-то нет. С приходом новых участников возникает всё больше вопросов, почему тут сделано так, а тут нет. На это всё тратится время. Очень драгоценное время.
Чтобы со всем этим бороться, можно:
1. Помнить про ревью.
Делать хорошее ревью это важно. Не только с точки зрения корректности логики, но и удачности технической реализации. У меня иногда прохождение ревью занимает столько же, сколько и сама задача (и это не потому что я говнокодер, честно; а потому что ревьюеры обладает более широкой экспертизой и оставляют замечательные комментарии).
Отдавать на ревью не одному человеку. Понятно, что кто-то понимает конкретно в этом месте больше, чем другие. У меня недавно был кейс, когда один коллега оставил неплохое, но небольшое ревью на пр, а чувак из соседней команды, которому пр попался совершенно случайно, накидал комментов ещё на два целых рабочих дня. И всё по делу. Понятно, что тут стоит найти компромисс между полезностью и потраченным количеством человекачасов, но если есть возможность, почему ей не воспользоваться.
Если у вас нет практики ревью (такое бывает, да), всеми силами пытаться её ввести или хотя бы просить ревью на свои задачи. Особенно поначалу это позволяет многому научиться.
2. Тратить время не только на продуктовые задачи, но и на технические. Если в планы на следующий отрезок времени/спринт/самое ближайшее будущее у вас есть возможность запланировать/сделать/убедить коллег в необходимости что-нибудь зарефакторить, постарайтесь этим заняться. Это облегчит жизнь не только вам, но и всем разработчикам вокруг.
3. Ради бога, если вы в процессе решения задачи увидели что-то, что можно позже исправить, запишите это. А то некрасивый код так и останется неисправленным, пусть и обнаруженным. Всё помнить нереально и неполезно.
Сейчас речь идёт именно о (не)больших технических изменениях, потому что крупных продуктовых рефакторингов за свой небольшой опыт я пока не увидел (может вот сейчас наблюдаю за стартом такого процесса). Там всё примерно так же, только чуточку сложнее.
Есть кстати движение под названием Dead Code Society, которое продвигает идею выпиливания неиспользуемого кода. Слышал, что в больших компаниях есть похожие внутренние штуки (например довольно сильное в Meta). У нас тоже вроде что-то такое имеется, но как там у ребят успехи, хз. Свечку не держал.
UPD.
Рад, что вы пользуетесь реакциями кроме 👍 : )
Но их особенно приятно видеть.
👍15🤡10👏4🤔4👌3😱1
#highload
Взаимодействие фронта с беком в средней REST-экосистеме выглядит как какое-то количество эндпоинтов (ручек) со стороны бекенда, которые дёргаются фронтом. На бекенде может считаться, что хорошо бы разделить логику одного частого действия на некоторое количество действий поменьше, чтобы сделать вызовы быстрее, а систему более переиспользуемой. С другой стороны, клиенту может быть неудобно пользоваться подобными решениями, т.к. вместо похода в одну ручку необходимо сделать несколько походов в разные, что очевидно повышает вероятность ошибки.
Потому возникло такое понятия, как backend for frontend: набор ручек как прослойка между бекендом и фронтендом, которые объединяют популярные (и логические) связки вызовов ручек.
Давайте поймём, какие плюсы мы получаем от внедрения такого подхода.
Во-первых, при обычных походах из клиента сразу в бекенд, каждый поход это передача данных по сети из внешнего мира внутрь экосистемы сервиса. На это тратится время пользователя. При использовании bff первоначальный запрос уходит в bff, после чего все запросы от него к сервисам бекенда делаются внутри (например) одного дата-центра (что вообще-то почти бесплатно).
Во-вторых, при использовании bff появляется возможность отдавать не просто результаты GET/POST/других запросов, из которых необходимо на устройстве пользователя согласно некоторой логике создавать отображение, а отдавать готовую html-разметку для тупого её отображения (мб с js-скриптами). Вы разгружаете клиент: ему достаточно сделать всего один запрос (ещё слышал, что индексирующие роботы при поиске делают лишь один запрос по адресу, потому ранжирование будет более точным и на основе всех данных, а не куска, который вернула всего одна ручка). На bff можно удалять ненужные данные, пришедшие с бекенда (информацию, ненужную для отображения/удалить ненужные данные при пагинации). Соответственно можно и менять status code ответа (т.к. правила для бекенда возвращать не 200 не всегда удобны для фронтенда и 200 им вполне сгодилось бы).
Выглядит конечно, как бекенд-разработчики делают свои дела где-то в сторонке, а фронтенд вынужден в этом жить и что-то изобретать. Может и так. Но если всем норм, поч нет : )
Взаимодействие фронта с беком в средней REST-экосистеме выглядит как какое-то количество эндпоинтов (ручек) со стороны бекенда, которые дёргаются фронтом. На бекенде может считаться, что хорошо бы разделить логику одного частого действия на некоторое количество действий поменьше, чтобы сделать вызовы быстрее, а систему более переиспользуемой. С другой стороны, клиенту может быть неудобно пользоваться подобными решениями, т.к. вместо похода в одну ручку необходимо сделать несколько походов в разные, что очевидно повышает вероятность ошибки.
Потому возникло такое понятия, как backend for frontend: набор ручек как прослойка между бекендом и фронтендом, которые объединяют популярные (и логические) связки вызовов ручек.
Давайте поймём, какие плюсы мы получаем от внедрения такого подхода.
Во-первых, при обычных походах из клиента сразу в бекенд, каждый поход это передача данных по сети из внешнего мира внутрь экосистемы сервиса. На это тратится время пользователя. При использовании bff первоначальный запрос уходит в bff, после чего все запросы от него к сервисам бекенда делаются внутри (например) одного дата-центра (что вообще-то почти бесплатно).
Во-вторых, при использовании bff появляется возможность отдавать не просто результаты GET/POST/других запросов, из которых необходимо на устройстве пользователя согласно некоторой логике создавать отображение, а отдавать готовую html-разметку для тупого её отображения (мб с js-скриптами). Вы разгружаете клиент: ему достаточно сделать всего один запрос (ещё слышал, что индексирующие роботы при поиске делают лишь один запрос по адресу, потому ранжирование будет более точным и на основе всех данных, а не куска, который вернула всего одна ручка). На bff можно удалять ненужные данные, пришедшие с бекенда (информацию, ненужную для отображения/удалить ненужные данные при пагинации). Соответственно можно и менять status code ответа (т.к. правила для бекенда возвращать не 200 не всегда удобны для фронтенда и 200 им вполне сгодилось бы).
Выглядит конечно, как бекенд-разработчики делают свои дела где-то в сторонке, а фронтенд вынужден в этом жить и что-то изобретать. Может и так. Но если всем норм, поч нет : )
👍2👎1
#list
1. Для меня было большим сюрпризом, что в плюсах идентификатором может быть любая последовательность utf-символов. Как часто это бывает, человек, рассказавший об этом, выяснил совершенно случайно (из-за неверной раскладки).
2. Как известно,
С другой стороны, преимущество вектора это расположение данных в памяти подряд и скорость доступа к случайному элементу. В случае очереди с приоритетами это довольно важно. В случае стека нет. Ему это просто не нужно.
3. В std::forward_list нет метода size. Я так понимаю, что поинт такой: если вы используете односвязный список, вы пытаетесь экономить, потому экономьте максимально.
4. Известный факт, что методы/функции не умеют в частичную специализацию. Но что делать, если очень хочется? Можно написать обёртку с помощью структуры/класса.
5. Чувак на хабре рассказал про плюсы и выгорание.
6. Пост про мощь f-строк в питоне.
7. Очень забавный опрос про парадокс вагонетки с абсурдными вопросами. Займёт минут 10-15, но может вы что-то для себя поймёте : )
8. За последнюю статью на хабре у меня появилась возможность пригласить одного участника. Так что если вы не являетесь полноправным членом этого сообщества, но у вас есть желание что-нибудь запостить, приходите в лс. Если мне зайдёт (не хочется его в пустоту отдать), обязательно приглашу вас. Я не обладаю широкой экспертизой, но смогу накинуть каких-то комментариев по содержанию.
================
Недавно две недели наблюдал, как чувак пытался сбилдить проект на маке с M1. Решением для компиляции какой-то допотопной библиотеки было перенести объявление переменной чуть выше. Я думаю, вы понимаете, почему это может что-то починить, но в вакууме звучит как угар.
Поступило предложение запилить пропозал про выпиливание C++. Иногда я тоже об этом думаю.
1. Для меня было большим сюрпризом, что в плюсах идентификатором может быть любая последовательность utf-символов. Как часто это бывает, человек, рассказавший об этом, выяснил совершенно случайно (из-за неверной раскладки).
2. Как известно,
std::stack, std::queue, std::priority_queue это адаптеры (контейнеры, которые используют в качестве базы другой контейнер). С std::queue всё понятно. Тут определённо стоит использовать std::deque. У std::priority_queue по дефолту используется std::vector. Тут тоже всё хорошо. Но у std::stack используется std::deque. Seems strange. Ведь нам нужно только push_back, back и pop_back. Откуда такая неконсистентность? Я где-то читал, что это сделано, чтобы стек можно было использовать с некопируемыми объектами, ведь дек реаллоцируется без копирования. Но этот аргумент применим и к очереди с приоритетами. Короч тут непонятно.С другой стороны, преимущество вектора это расположение данных в памяти подряд и скорость доступа к случайному элементу. В случае очереди с приоритетами это довольно важно. В случае стека нет. Ему это просто не нужно.
3. В std::forward_list нет метода size. Я так понимаю, что поинт такой: если вы используете односвязный список, вы пытаетесь экономить, потому экономьте максимально.
4. Известный факт, что методы/функции не умеют в частичную специализацию. Но что делать, если очень хочется? Можно написать обёртку с помощью структуры/класса.
5. Чувак на хабре рассказал про плюсы и выгорание.
6. Пост про мощь f-строк в питоне.
7. Очень забавный опрос про парадокс вагонетки с абсурдными вопросами. Займёт минут 10-15, но может вы что-то для себя поймёте : )
8. За последнюю статью на хабре у меня появилась возможность пригласить одного участника. Так что если вы не являетесь полноправным членом этого сообщества, но у вас есть желание что-нибудь запостить, приходите в лс. Если мне зайдёт (не хочется его в пустоту отдать), обязательно приглашу вас. Я не обладаю широкой экспертизой, но смогу накинуть каких-то комментариев по содержанию.
================
Недавно две недели наблюдал, как чувак пытался сбилдить проект на маке с M1. Решением для компиляции какой-то допотопной библиотеки было перенести объявление переменной чуть выше. Я думаю, вы понимаете, почему это может что-то починить, но в вакууме звучит как угар.
Поступило предложение запилить пропозал про выпиливание C++. Иногда я тоже об этом думаю.
👍8😁3👎1
#cpp
Набрёл на путеводитель по неопределённому поведению (Nekrolm/ubbok). Оставлю удовольствие прочесть вам это самостоятельно, а я расскажу об интересных вещах, моментах которые я не знал/не осознавал.
1. Одним из способов проверки уб в вашем коде может быть тестирование функций/методов на компиляции с помощью constexpr (т.к. в constexpr контексте неопределённое поведение не компилируется).
2. Integer promotion.
В С++ арифметические операции определены не для всех числовых типов. Например, для всех типов меньше int’а их нет. В таких случаях перед выполнением операций над любым указанным типом (даже беззнаковым!!) происходит приведение к int (знаковому!):
Здесь будет переполнение int, которое является уб. Стало страшно.
4. std::min объявлен как (одна из версий)
Из-за того, что тут возвращается ссылка, можно легко получить висячую ссылку:
Если вам это критично, можно использовать версию с
5.
И вот так делать не стоит:
Это unspecified.
6. Посмотрим на такой код:
Как думаете, что он выведет?
Неправильно. Результатом будет 0 1 1.
Я давно знал, что
7. В С++ есть правило: если что-то может быть засчитано за объявление функции, оно будет за него засчитано. И тут начинается разного рода флекс.
Когда-то в начале второго курса я хотел инициализировать поля класса с помощью вызова конструктора круглыми скобками, но программа упорно не компилировалась. Тогда я понял проблему лишь спустя несколько часов после сдачи контрольной работы. Будьте внимательными.
8. Интересный пример:
К любому адресу можно добавить как минимум 1, т.к. любой объект грубо говоря считается массивом из одного элемента, и вы таким образом можете получить
Этот код содержит уб:
Несмотря на то, что указатель
9. gcc 1.7 в некоторых случаях уб (которое получалось задетектить) пытался запускать одну из нескольких игр.
Большинство разделов довольно известные кмк, но знание о таких моментах давались мне долгими вечерами на протяжении лет из десятков разных источников. Тут же всё структурированно, много примеров и понятных пояснений. Обязательно найдите время почитать.
===================
Если у вас есть свободное время, можете поправить опечатки/ошибки. Или может даже вкинуть свой необычный пример неопределённого поведения. Так сказать стать open source community member.
Как правильно заметил автор, 80% проблем с уб от висячих ссылок. Я когда-то смотрел лекции Ильи Мещерина по плюсам, где он сказал, что несколько раз в крупных проектах дебагал висячие ссылки. Тогда я посмеялся и подумал, как такое можно вообще допустить, а буквально через месяц 8 часов провёл за ровно тем же занятием на работе. Больше не смеюсь.
Набрёл на путеводитель по неопределённому поведению (Nekrolm/ubbok). Оставлю удовольствие прочесть вам это самостоятельно, а я расскажу об интересных вещах, моментах которые я не знал/не осознавал.
1. Одним из способов проверки уб в вашем коде может быть тестирование функций/методов на компиляции с помощью constexpr (т.к. в constexpr контексте неопределённое поведение не компилируется).
2. Integer promotion.
В С++ арифметические операции определены не для всех числовых типов. Например, для всех типов меньше int’а их нет. В таких случаях перед выполнением операций над любым указанным типом (даже беззнаковым!!) происходит приведение к int (знаковому!):
unsigned short x = 0xFFFF;
unsigned short y = 0xFFFF;
auto z = x * y;Здесь будет переполнение int, которое является уб. Стало страшно.
4. std::min объявлен как (одна из версий)
template< class T >
constexpr const T& min( const T& a, const T& b );Из-за того, что тут возвращается ссылка, можно легко получить висячую ссылку:
const auto& x = std::min(1, 2);Если вам это критично, можно использовать версию с
std::initializer_list. Она возвращает по значению:template< class T >
constexpr T min( std::initializer_list<T> ilist );5.
std::make_tuple применяет грубо говоря std::decay_t ко всем аргументам. Это вроде факт известный. Но интересно, что случай, когда аргументом является std::reference_wrapper обрабатывается отдельно, из-за чего тип такого аргумента станет T&.И вот так делать не стоит:
std::tie(x, y) = std::tie(y, x);Это unspecified.
6. Посмотрим на такой код:
std::vector<bool> v;
v.push_back(false);
std::cout << v[0] << " ";
const auto b = v[0];
auto c = b;
c = true;
std::cout << c << " " << b;Как думаете, что он выведет?
Я давно знал, что
std::vector<bool> таит в себе опасности, но чтобы такие… 7. В С++ есть правило: если что-то может быть засчитано за объявление функции, оно будет за него засчитано. И тут начинается разного рода флекс.
Когда-то в начале второго курса я хотел инициализировать поля класса с помощью вызова конструктора круглыми скобками, но программа упорно не компилировалась. Тогда я понял проблему лишь спустя несколько часов после сдачи контрольной работы. Будьте внимательными.
8. Интересный пример:
int x = 5;
auto x_ptr = &x; // валидный указатель, его МОЖНО разыменовывать
auto x_end_ptr = (&x) + 1; // валидный указатель, но его НЕЛЬЗЯ разыменовывать
auto x_invalid_ptr = (&x) + 2; // невалидный указатель, само его существование недопустимо.К любому адресу можно добавить как минимум 1, т.к. любой объект грубо говоря считается массивом из одного элемента, и вы таким образом можете получить
end() этого массива (только не разыменовывайте). Двигаться дальше -- уб. Этот код содержит уб:
std::string str = "hell";
str.erase(str.begin() + 4 + 1 - 3);Несмотря на то, что указатель
str.begin() + 4 + 1 - 3 является валидным указателем, на моменте прибавления единицы мы получаем невалидный указатель, лежащий за end() строки -> ub. 9. gcc 1.7 в некоторых случаях уб (которое получалось задетектить) пытался запускать одну из нескольких игр.
Большинство разделов довольно известные кмк, но знание о таких моментах давались мне долгими вечерами на протяжении лет из десятков разных источников. Тут же всё структурированно, много примеров и понятных пояснений. Обязательно найдите время почитать.
===================
Если у вас есть свободное время, можете поправить опечатки/ошибки. Или может даже вкинуть свой необычный пример неопределённого поведения. Так сказать стать open source community member.
Как правильно заметил автор, 80% проблем с уб от висячих ссылок. Я когда-то смотрел лекции Ильи Мещерина по плюсам, где он сказал, что несколько раз в крупных проектах дебагал висячие ссылки. Тогда я посмеялся и подумал, как такое можно вообще допустить, а буквально через месяц 8 часов провёл за ровно тем же занятием на работе. Больше не смеюсь.
👍12
#list
1. Недавно думал, почему пустая структура в C++ всегда весит один байт (стандарт требует, чтобы у двух различных объектов были различные адреса).
Давайте подумаем, что может сломаться, если так сделать.
Как в таком случае должны выглядеть массивы? По факту это будет n элементов (число n компилятор часто хранит слева от указателя), расположенных по одному адресу. Т.к. объект нулевого размера не хранит данных, а всю информацию о типе компилятор имеет, можно все вызовы функций делать от одного адреса (это никак на объект не повлияет). В случае, когда мы делаем
Понятно, что как будто можно было бы в такое научиться, но язык и так очень нетривиален, чтобы ещё такие навороты делать. Хотя зачатки подобного уже есть (EBO/EBCO,
Вообще зачем об этом думать. Например я в последнее время часто использую такую структуру:
которая используется для tag dispatching. И раз такой аргумент нужен только для выбора перегрузки функции, можно было бы его оптимизировать в ноль байт. Как-то от этого и раскрутилась мысль.
Кстати Rust умеет как-то с типами нулевого размера работать: раз, два. Может какой-нибудь поклонник этого языка расскажет чуть больше в комментариях : )
2. Я думаю, все знакомы с правилом пяти. Оно гласит, что если вы определяете что-то одного из конструктор копирования/перемещения, аналогичных
Интересно, что такой подход как будто противоречит single-responsibility principle, который говорит, что класс должен отвечать за что-то одно. Поинт в том, что если у вас определён хотя бы что-то одно из указанного, вы должны определить все пять == научить объект манипулировать данными ещё как-то кроме методов, поддерживающих некоторый инвариант класса.
Потому гораздо полезнее правило нуля: не писать никого вообще. И вы наверняка им пользовались. Если у вас в полях класса есть какие-то нетривиальные объекты, компилятор сам справится корректно их скопировать/переместить/удалить. Потому что, на самом деле, писать что-то из пяти этих особых методов вам нужно очень редко (чему конечно противоречит опыт обучения, когда мы постоянно переписываем какие-то (не)стандартные контейнеры и пишем подобное постоянно).
3. Чувак поясняет, почему double/float в любом языке программирования на самом деле не вещественные числа (спойлер: формально с точки зрения математики числа в компьютере не могут представить все вещественные числа). Статью заминусили. Как мне кажется, вполне справедливо, потому что если все в мире понимают о чём речь, зачем воду мутить?
4. Известный факт, что можно объявлять структуры/классы в функциях/методах. Но почему-то нельзя так же объявить шаблон структуры/класса. Причин никаких это запрещать не обнаружил. Даже нашёл бумагу с исправлением: link.
1. Недавно думал, почему пустая структура в C++ всегда весит один байт (стандарт требует, чтобы у двух различных объектов были различные адреса).
Давайте подумаем, что может сломаться, если так сделать.
Как в таком случае должны выглядеть массивы? По факту это будет n элементов (число n компилятор часто хранит слева от указателя), расположенных по одному адресу. Т.к. объект нулевого размера не хранит данных, а всю информацию о типе компилятор имеет, можно все вызовы функций делать от одного адреса (это никак на объект не повлияет). В случае, когда мы делаем
arr[i], компилятор может отдавать один и тот же элемент. Если объект используется как обёртка над какими-то операциями (в конструкторе/деструкторе), их вызов корректен (правда деструктор дважды по одному адресу это ub, но, предположим, закостылили). При итерировании по массиву мы помним число n, потому понимаем, когда пора остановиться, а когда начинается ub -> можем пытаться оптимизировать. По этим же причинам удаление массива -- операция конечная. Конечно возникают проблемы с реализацией end() для кастомных контейнеров, т.к. элемент, расположенный за последним, становится недостижимым, но условно можно обязать пользователей определять end() как arr + sizeof(char). На этом поиск проблем я остановил. Хотя есть ощущения, что сломается что-то гораздо более сложное (целый мир strict aliasing). Понятно, что как будто можно было бы в такое научиться, но язык и так очень нетривиален, чтобы ещё такие навороты делать. Хотя зачатки подобного уже есть (EBO/EBCO,
[[no_unique_address]], VLA/FAM о которых я уже упоминал). Вообще зачем об этом думать. Например я в последнее время часто использую такую структуру:
template <typename T>
struct To {};которая используется для tag dispatching. И раз такой аргумент нужен только для выбора перегрузки функции, можно было бы его оптимизировать в ноль байт. Как-то от этого и раскрутилась мысль.
Кстати Rust умеет как-то с типами нулевого размера работать: раз, два. Может какой-нибудь поклонник этого языка расскажет чуть больше в комментариях : )
2. Я думаю, все знакомы с правилом пяти. Оно гласит, что если вы определяете что-то одного из конструктор копирования/перемещения, аналогичных
operator= или деструктора, вы должны написать и все остальные. Это не требование компиляторов, а правило хорошего тона, иначе вступают в силу сложные правила того, как работает компилятор при генерации остальных методов. Интересно, что такой подход как будто противоречит single-responsibility principle, который говорит, что класс должен отвечать за что-то одно. Поинт в том, что если у вас определён хотя бы что-то одно из указанного, вы должны определить все пять == научить объект манипулировать данными ещё как-то кроме методов, поддерживающих некоторый инвариант класса.
Потому гораздо полезнее правило нуля: не писать никого вообще. И вы наверняка им пользовались. Если у вас в полях класса есть какие-то нетривиальные объекты, компилятор сам справится корректно их скопировать/переместить/удалить. Потому что, на самом деле, писать что-то из пяти этих особых методов вам нужно очень редко (чему конечно противоречит опыт обучения, когда мы постоянно переписываем какие-то (не)стандартные контейнеры и пишем подобное постоянно).
3. Чувак поясняет, почему double/float в любом языке программирования на самом деле не вещественные числа (спойлер: формально с точки зрения математики числа в компьютере не могут представить все вещественные числа). Статью заминусили. Как мне кажется, вполне справедливо, потому что если все в мире понимают о чём речь, зачем воду мутить?
4. Известный факт, что можно объявлять структуры/классы в функциях/методах. Но почему-то нельзя так же объявить шаблон структуры/класса. Причин никаких это запрещать не обнаружил. Даже нашёл бумагу с исправлением: link.
👍2🤔1
#list
1. В последней статье на хабре я писал про sparse set и приводил ссылку на реализацию в folly. Правда он был insert-only. Но ведь одна из его фишек именно в том, что его можно быстро чистить. Потому решил закоммитить это счастье (впервые что-то на кодерском коммичу в чужие репозитории; раньше коммитил в какие-то опенсорс сайтики: англ e-maxx и несколько других про алгоритмы). У меты интересный флоу работы с пр-ами: подписать какое-то соглашение (вроде норм), увидеть упавшие билды (мастер тоже не собирается), ревью, после чего твой пр они переносят во внутреннюю экосистему, где двое суток что-то собирается, и потом закрывают пр и видимо мержат опенсорсную версию folly и внутреннюю. Необычно.
Ещё у меня есть коммит в userver, но честно говоря, не коммит а параша)
2. Недавно увидел фичу на ютубе (хотя есть она давно): если навести на таймлайн видео, над красно-серой полоской будет полупрозрачная серая полоса, похожая на рельеф холмов в профиль. Это частота просмотров различных частей видео. Не знаю, как это реализовано, но, думаю, можно с использованием t-digest. Эта структура данных позволяет относительно дёшево хранить распределения величин. В ней у вас есть какое-то количество центроидов (центроид == диапазон значений + их количество в этом диапазоне). Если при просмотре пользователь задел диапазон, увеличиваете счётчик в центроиде для этого диапазона, после чего можете сгладить эти значения для красивого отображения.
Ещё такую структуру можно использовать для подсчёта перцентилей какой-то метрики. Например для промежутка от 0 до 100 процентов взять 200 центроидов и для любого значения (p50, p95, p98) брать префиксную сумму значений центроидов по этой метрике. Такая сд и реализуется не прям сложно, и является довольно информативной (особенно учитывая, что абсолютная точность вам не нужна).
3. Тут окончили обсуждать C23 (да, C; не C++). На первый взгляд выглядит, как будто C начинает местами догонять — и даже обгонять — плюсы, но мы-то знаем, что пропасть бесконечна…
Вот часть того, что комитет решил добавить в C23 (более полный список можете найти тут):
- #embed — возможность получать данные из внешних файлов на компиляции. По опыту go (
-
- гарантированное two’s complement для представления чисел;
- несколько новых директив препроцессора:
- уже знакомые из плюсов атрибуты:
-
- nullptr;
- немного прокачали енамы;
- constexpr;
- всякие литералы для чисел, разделитель разрядов
Факт, что принимающая ноль аргументов в C функция должна помечаться
Но я никогда не думал, что будет, если написать в плюсовом стиле:
Такая функция принимает любое число аргументов, но работать с ними как с
1. В последней статье на хабре я писал про sparse set и приводил ссылку на реализацию в folly. Правда он был insert-only. Но ведь одна из его фишек именно в том, что его можно быстро чистить. Потому решил закоммитить это счастье (впервые что-то на кодерском коммичу в чужие репозитории; раньше коммитил в какие-то опенсорс сайтики: англ e-maxx и несколько других про алгоритмы). У меты интересный флоу работы с пр-ами: подписать какое-то соглашение (вроде норм), увидеть упавшие билды (мастер тоже не собирается), ревью, после чего твой пр они переносят во внутреннюю экосистему, где двое суток что-то собирается, и потом закрывают пр и видимо мержат опенсорсную версию folly и внутреннюю. Необычно.
Ещё у меня есть коммит в userver, но честно говоря, не коммит а параша)
2. Недавно увидел фичу на ютубе (хотя есть она давно): если навести на таймлайн видео, над красно-серой полоской будет полупрозрачная серая полоса, похожая на рельеф холмов в профиль. Это частота просмотров различных частей видео. Не знаю, как это реализовано, но, думаю, можно с использованием t-digest. Эта структура данных позволяет относительно дёшево хранить распределения величин. В ней у вас есть какое-то количество центроидов (центроид == диапазон значений + их количество в этом диапазоне). Если при просмотре пользователь задел диапазон, увеличиваете счётчик в центроиде для этого диапазона, после чего можете сгладить эти значения для красивого отображения.
Ещё такую структуру можно использовать для подсчёта перцентилей какой-то метрики. Например для промежутка от 0 до 100 процентов взять 200 центроидов и для любого значения (p50, p95, p98) брать префиксную сумму значений центроидов по этой метрике. Такая сд и реализуется не прям сложно, и является довольно информативной (особенно учитывая, что абсолютная точность вам не нужна).
3. Тут окончили обсуждать C23 (да, C; не C++). На первый взгляд выглядит, как будто C начинает местами догонять — и даже обгонять — плюсы, но мы-то знаем, что пропасть бесконечна…
Вот часть того, что комитет решил добавить в C23 (более полный список можете найти тут):
- #embed — возможность получать данные из внешних файлов на компиляции. По опыту go (
go:embed) это и код экономит, и пользователя в рантайме не задевает. Удобно. В плюсах такое тоже тащат (последнее обновление было 20ого апреля);-
__has_include, который подъехал в C++20;- гарантированное two’s complement для представления чисел;
- несколько новых директив препроцессора:
#warning, #elifdef, #elifndef;- уже знакомые из плюсов атрибуты:
[[deprecated]], [[fallthrough]], [[maybe_unused]], [[nodiscard]] и [[noreturn]];-
realloc() с нулевым размером запрашиваемой памяти становится undefined behaviour (Andrei Alexandrescu на одном из докладов на CppCon сказал, что всего два человека в мире знают, когда правильно эту функцию использовать, похехал). Интересно, что такое изменение позволяет делать🤔;- nullptr;
- немного прокачали енамы;
- constexpr;
- всякие литералы для чисел, разделитель разрядов
‘ как в плюсах, удаление триграфов (давно пора, хотя мы когда-то чуть-чуть так лабы в универе обфусцировали), auto (но я не нашёл пруфов, только на reddit писали) и ещё много всего. Факт, что принимающая ноль аргументов в C функция должна помечаться
void довольно известный:int f(void) {}Но я никогда не думал, что будет, если написать в плюсовом стиле:
int f() {}Такая функция принимает любое число аргументов, но работать с ними как с
VA_ARGS не получится: для этого нужно иметь хотя бы один аргумент. Например так:void f(int numargs, ...) {}👍7