Как я понял по умолчанию std::map выделяет новый блок памяти в куче для каждой пары ключ-значение.
И освобождает его через free() когда мы удаляем пару через map.erase(map.find(key)).
Для ускорения работы, хотел бы поменять его поведение:
например сразу выделять место по 1000 пар ключ-значение, при удалении не вызывать free для каждой пары.
Здравствуйте, maks1180, Вы писали:
M>Как я понял по умолчанию std::map выделяет новый блок памяти в куче для каждой пары ключ-значение. M>И освобождает его через free() когда мы удаляем пару через map.erase(map.find(key)).
M>Для ускорения работы, хотел бы поменять его поведение: M>например сразу выделять место по 1000 пар ключ-значение, при удалении не вызывать free для каждой пары. M>Как это можно сделать ?
Это очевидно. Своим аллокатором.
template<
class Key,
class T,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, T>>
> class map;
Вот только зачем?
Что за задачу решаешь?
Пляски с аллокаторами — оптимизация на спичках очень редкая задача.
Если это для расширения кругозора, то ИМХО лучше потратить время на изучение структур данных и алгоритмов — пользы больше.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, maks1180, Вы писали:
M>Как я понял по умолчанию std::map выделяет новый блок памяти в куче для каждой пары ключ-значение. M>Для ускорения работы, хотел бы поменять его поведение: M>например сразу выделять место по 1000 пар ключ-значение, при удалении не вызывать free для каждой пары.
У std::map есть node interface ровно для этого. Смотри перегрузки методов, принимающие или возвращающие тип std::map<>::node_type.
M>И освобождает его через free() когда мы удаляем пару через map.erase(map.find(key)).
Ну всё же не совсем через free.
Здравствуйте, maks1180, Вы писали:
M>Для ускорения работы, хотел бы поменять его поведение: M>например сразу выделять место по 1000 пар ключ-значение, при удалении не вызывать free для каждой пары.
Сколько элементов в этом мапе? Какого размера?
Существующий код тормозит?
Профилятор это подтверждает?
Другими структурами данных этот мап не заменить?
Какую скорость надо достичь?
Пока, судя по другим вопросам ТС, у меня складывается впечатление, что интерес исключительно академический.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Пока, судя по другим вопросам ТС, у меня складывается впечатление, что интерес исключительно академический.
У меня впечатление такое, что человек занимается преждевременной оптимизацией, отодвинув на задний план остальные вопросы — надежность, поддерживаемость, масштабируемость и пр.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
r> У меня впечатление такое, что человек занимается преждевременной оптимизацией, отодвинув на задний план остальные вопросы — надежность, поддерживаемость, масштабируемость и пр.
ТС — автор Ammyy Admin, поэтому, думается, занимается он не преждевременной оптимизаций.
SVZ>>Пока, судя по другим вопросам ТС, у меня складывается впечатление, что интерес исключительно академический.
R>У меня впечатление такое, что человек занимается преждевременной оптимизацией, отодвинув на задний план остальные вопросы — надежность, поддерживаемость, масштабируемость и пр.
Да, это так — преждевременная оптимизация, переписываю софт, а раз уж начал переписывать, то хочу сразу сделать хорошо, что-бы потом не переделывать.
У софта сейчас нагрузка по 150 тыс соединений, ранее я тестировал и на 300 тыс выдерживал, вот хочу переписать и потом потестировать на 1 млн соединений.
Я понимаю, что моя текуща задача решается увеличением количества серверов, и решается наверно дешевле, чем мои труды.
Но мне для себя хочется сделать, что-бы потом с гордостью сказать, что я написал софт который выдерживает Х нагрузку, и поэтому смогли сократить количество серверов в Y раз.
M>>Для ускорения работы, хотел бы поменять его поведение: M>>например сразу выделять место по 1000 пар ключ-значение, при удалении не вызывать free для каждой пары. M>>Как это можно сделать ?
SVZ>Это очевидно. Своим аллокатором.
Это понятно, просто думал может есть другие варианты или что-то по существу подскажите.
Свой аллокатор будет всегда через ассемблерный call вызываться или может быть заинлайнин ?
SVZ>Если это для расширения кругозора, то ИМХО лучше потратить время на изучение структур данных и алгоритмов — пользы больше.
Это я уже и так неплохо знаю.
Я правильно понимаю, что итератор у map это фактически адрес map::node и поэтому я могу добавлять и удалять другие элементы и итератор останется валидным.
Или это зависит от реализации ?
Здравствуйте, maks1180, Вы писали:
SVZ>>Это очевидно. Своим аллокатором. M>Это понятно, просто думал может есть другие варианты или что-то по существу подскажите. M>Свой аллокатор будет всегда через ассемблерный call вызываться или может быть заинлайнин ?
Т.к. там шаблонная магия, то может быть и заинлайнен.
SVZ>>Если это для расширения кругозора, то ИМХО лучше потратить время на изучение структур данных и алгоритмов — пользы больше. M>Это я уже и так неплохо знаю.
Просто мне кажется, ты не с той стороны пытаешься оптимиздить.
Но т.к. данных для обсуждения нет, а телепаты, как всегда, в отпуске , то и советы общие.
Замена мапа на хеш может дать прирост скорости.
Замена хеша на плоский хеш (на базе массива) может дать прирост. А может и не дать
Отказаться от удаления вообще, "удаленные" элементы переиспользовать.
Ну и т.д., я бы начал с алгоритмической оптимизации. Возможно, тюнить хип и аллокаторы и вовсе не потребуется.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, maks1180, Вы писали:
M>Я правильно понимаю, что итератор у map это фактически адрес map::node и поэтому я могу добавлять и удалять другие элементы и итератор останется валидным. M>Или это зависит от реализации ?
Здравствуйте, maks1180, Вы писали:
M>Да, это так — преждевременная оптимизация, переписываю софт, а раз уж начал переписывать, то хочу сразу сделать хорошо, что-бы потом не переделывать. M>У софта сейчас нагрузка по 150 тыс соединений, ранее я тестировал и на 300 тыс выдерживал, вот хочу переписать и потом потестировать на 1 млн соединений.
Такая вот оптимизация "на всякий случай" всего подряд может привести к обратным результатам — и оптимизации толком не получится, потому что неправильно были выявлены узкие места, и дизайн с архитектурой получатся такими, что в скором времени появится кто-то, кто в очередной раз захочет "переписать все нахрен". И этот порочный круг может повторяться бесконечно.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, maks1180, Вы писали:
M>Как это можно сделать ?
Уже ответили про аллокатор.
Могу дополнить, что прежде всего главный вопрос про выбранную структуру данных.
Нужен ли упорядоченный контейнер, может unordered_map будет более подходящим, а также более и быстрым.
Также начиная с C++17 ассоциативные контейнеры получили дополнительные методы как insert, extract, которые позволяют избежать лишних копирований и выделений памяти.
SVZ>Замена мапа на хеш может дать прирост скорости. SVZ>Замена хеша на плоский хеш (на базе массива) может дать прирост. А может и не дать
Ну у меня как раз через свой хэш написано, разбивается на 1024 корзины и при 300.000 объектов примено 300 шт в корзине.
Но далее по корзине идёт перебор (т.к. там не отсортированы они).
Если ли более интересные реализации хэша ?
Здравствуйте, maks1180, Вы писали:
M>Ну у меня как раз через свой хэш написано, разбивается на 1024 корзины и при 300.000 объектов примено 300 шт в корзине. M>Но далее по корзине идёт перебор (т.к. там не отсортированы они). M>Если ли более интересные реализации хэша ?
Мы делали свой плоский хеш из трёх массивов
std::vector<KEY> Items; // Ключи
std::vector<int> Next; // Список коллизий (односвязный список)
std::vector<int> First; // Голова списка коллизий
Items.size() == Next.size();
это очевидно
Массив First по своей сути это твои корзины.
First.size() >= Items.size()
При добавлении очередного элемента в хеш, если количество элементов превысило число корзин, списки коллизий перестраиваются.
Хеш функция вычисляет положение элемента в массиве First. Но это стандартно.
Про выбор числа корзин.
1024 — очень плохое число. Оно красивое, но даёт много коллизий.
Простые числа используют неспроста.
У нас использовался какой-то коэффициент, чтобы после ресайза размер First не был кратным степени двойки.
В принципе можно брать ряд простых чисел — очень популярное решение. Но на больших размерах этот массив будет расти слишком уж сильно.
Поэтому нужен компромисс.
При таком подходе списки коллизий не вырастали больше 2-3 штук.
Удаление мы не делали. Пришлось бы перестраивать хеш, т.к. индексы поедут, а это дорого. Проще пометить элемент вакантным и при совпадении хеша занять готовое место.
Если известно, сколько примерно будет элементов в хеше, можно заранее выделить память под массив First. Позволит избежать лишних пересчетов хешей.
Ну вот так как-то.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, maks1180, Вы писали:
M>Ну у меня как раз через свой хэш написано, разбивается на 1024 корзины и при 300.000 объектов примено 300 шт в корзине. M>Но далее по корзине идёт перебор (т.к. там не отсортированы они). M>Если ли более интересные реализации хэша ?
Звучит как одна из наивных реализаций.
Рекомендую глянуть на свежие результаты сравнения разных хэш-таблиц, на разработку которых тратится много времени и денег: https://martin.ankerl.com/2022/08/27/hashmap-bench-01/
, то и советы общие.
