std :: map стандартная производительность распределителя по сравнению с блочным распределителем

Question

Я читал в поваренной книге по оптимизации C++, что стандартный распределитель для контейнеров STL, такой как std :: list, std :: set, std :: multi_set, std :: map , e std :: multi_map может быть заменен более производительным блочным распределителем .

Блок-распределитель имеет более высокую производительность, низкую фрагментацию и эффективное кэширование данных.

Я нашел в Интернете FSBAllocator, который утверждает, что он быстрее, чем стандарт. http://warp.povusers.org/FSBAllocator/

Я пробовал с станд :: картой и обнаружил, что, кажется, быстрее, на самом деле, но мой вопрос, как может быть реализация STL настолько медленнее, чем конкретный распределитель и каков недостатки другого распределителя чем стандарт, с точки зрения мобильности и надежности? Мой код должен компилироваться на различных архитектурах (win32, osx, linux). У кого-то есть опыт работы с этим блоком распределения фиксированного размера?

Answer 1

Блок-распределитель выполняет одно большое выделение для свободного хранилища/кучи, а затем внутренне разбивает эту память на куски. Один из недостатков заключается в том, что он выделяет этот фрагмент (который должен быть большим и часто указываться пользователем для каждого использования) прямо вверх, поэтому, даже если вы не используете его все, эта память привязана. Во-вторых, стандартный распределитель памяти построен поверх нового/delete, который, в свою очередь, часто строится поверх malloc/free. Хотя я не помню, гарантирован ли malloc/free быть потокобезопасным при любых обстоятельствах, обычно это так.

Но в конце концов причина того, почему блок-распределители работают так хорошо, состоит в том, что они имеют информацию, которая отсутствует для стандартных распределителей, и им не нужно покрывать очень широкий набор вариантов использования. Например, если вы сделали std::map< int, int >(), и он выделил 1mb, вы, вероятно, были бы разозлены, но если вы сделаете std::map< int, int, std::less<int>, block_alloc< 1024 * 1024 > >(), вы ожидаете его. Стандартные распределители не выделяются в блоках, они запрашивают новую память через новые, новые, в свою очередь, не имеют контекста вообще. Он получает запрос на память произвольного размера и должен найти непрерывное количество возвращаемых байтов. Большинство реализаций состоит в том, что у них есть набор областей памяти, которые они поддерживают разным кратным (например, регион на 4 байта более или менее, вероятно, гарантированно присутствует, так как запросы на 4 байта очень распространены). Если запрос не является четным, ему становится сложнее возвращать хороший кусок, не теряя пространства и вызывая фрагментацию. В принципе, управление памятью произвольных размеров очень сложно сделать, если вы хотите, чтобы она была близка к постоянному времени, низкой фрагментации, потокобезопасности и т. Д.

Документация Boost pool allocator содержит некоторую полезную информацию о том, как хороший блок-распределитель может работать.