Как сделать свой аллокатор

Обновлено: 05.07.2024

Насколько я могу судить, требования к распределителю, который будет использоваться с STL контейнеры размещены в таблице 28 раздела 17.6.3.5 стандарта С++ 11.

Я немного смущен в отношении взаимодействия между некоторыми из этих требований. Для типа X , который является распределителем для типа T , тип Y , который является "соответствующий класс распределителя" для типа U , экземпляры a , a1 и a2 of X и экземпляр b Y , таблица говорит:

Выражение a1 == a2 оценивается как true , только если выделено хранилище из a1 может быть освобождено a2 и наоборот.

Выражение X a1(a); хорошо сформировано, не выходит через исключение, и после этого a1 == a истинно.

Выражение X a(b) хорошо сформировано, не выходит через исключение и после a == b .

Я прочитал это, сказав, что все распределители должны быть конструктивно-копируемыми в таких что копии являются взаимозаменяемыми с оригиналами. Хуже того, то же самое true через границы типов. Это кажется довольно обременительным требованием; в виде насколько я могу судить, это делает невозможным большое количество типов распределителей.

Например, скажем, у меня был класс freelist, который я хотел использовать в своем распределителе, чтобы кэшировать освобожденные объекты. Если я что-то не упустил, я не мог включить экземпляр этого класса в распределитель, поскольку размеры или выравнивания T и U могут различаться, и, следовательно, списки фриланда несовместимо.

Правильны ли мои интерпретации?

Я читал в нескольких местах, что С++ 11 улучшил поддержку для "stateful распределители ". Как это обстоятельство, учитывая эти ограничения?

Есть ли у вас какие-либо предложения о том, как делать то, что я пытаюсь делать? То есть, как я могу включить состояние выделенного типа в свой распределитель?

В общем, язык вокруг распределителей кажется неаккуратным. (Например, пролог к ​​таблице 28 говорит, что a имеет тип X& , но некоторые из выражения redefine a .) Кроме того, по крайней мере поддержка GCC является несоответствующей. Что объясняет эту странность вокруг распределителей? Это просто нечасто используемая функция?

ОТВЕТЫ

Ответ 1

1) Правильны ли мои интерпретации?

Вы правы, что ваш бесплатный список не подходит для распределителей, он должен иметь возможность обрабатывать несколько размеров (и выравниваний) для соответствия. Это проблема для свободного списка.

2) Я прочитал в нескольких местах, что С++ 11 улучшил поддержку "генераторов с сохранением состояния". Как это обстоятельство, учитывая эти ограничения?

Это не так улучшилось, как родилось. В С++ 03 любой экземпляр распределителя должен был быть эквивалентен другому экземпляру того же типа, что фактически делало невозможным использование генераторов с сохранением состояния.

3) Есть ли у вас какие-либо предложения о том, как делать то, что я пытаюсь сделать? То есть, как я могу включить состояние выделенного типа в свой распределитель?

Ваш распределитель должен быть гибким, потому что вы не должны точно знать, какую память (и какие типы) он должен выделить. Это требование необходимо, чтобы изолировать вас (пользователя) от внутренних компонентов контейнера, который использует распределитель.

Да, это дорогостоящее требование.

4) В общем, язык вокруг распределителей кажется неаккуратным. (Например, пролог к ​​таблице 28 говорит, что предполагается, что a имеет тип X &, но некоторые из выражений переопределяют a.) Кроме того, по крайней мере поддержка GCC является несоответствующей. Что объясняет эту странность вокруг распределителей? Это нечасто используемая функция?

Стандарт вообще не так просто читать, а не только распределители. Вы должны быть осторожны.

Чтобы быть педантом, gcc не поддерживает распределители (это компилятор). Я предполагаю, что вы говорите о libstdС++ (реализация стандартной библиотеки поставляется с gcc). libstdС++ является старым, и поэтому он был скроен С++ 03. Он был адаптирован к С++ 11, но пока не полностью соответствует (по-прежнему использует Copy-On-Write для строк). Причина в том, что libstdС++ имеет большой упор на двоичную совместимость, и ряд изменений, требуемых С++ 11, нарушит эту совместимость; поэтому их следует тщательно вводить.

Ответ 2

Равенство распределителей не означает, что они должны иметь точно такое же внутреннее состояние, только то, что они должны оба освобождать память, которая была распределена с помощью распределителя. Радиальное распределение распределителей a == b для распределителя a типа X и распределителя b типа Y определено в таблице 28 как "такое же, как a == Y::template rebind ::other(b) ". Другими словами, a == b , если память, выделенная с помощью a , может быть освобождена распределителем, созданным путем восстановления b до a value_type .

Ваши сторонние распределители не должны освобождать узлы произвольного типа, вам нужно только освободить память, выделенную FreelistAllocator , с помощью FreelistAllocator ::template rebind ::other . Учитывая, что FreelistAllocator ::template rebind ::other является тем же самым типом, что и FreelistAllocator в большинстве нормальных реализаций, этого довольно легко достичь.

Ответ 3

Я прочитал это, сказав, что все распределители должны быть построены с возможностью копирования таким образом, чтобы копии были взаимозаменяемы с оригиналами. Хуже того, то же самое верно для границ типов. Это кажется довольно обременительным требованием; насколько я могу судить, это делает невозможным большое количество типов распределителей.

Тривиально удовлетворять требованиям, если распределители являются легким дескриптором на некотором ресурсе памяти. Просто не пытайтесь встроить ресурс в отдельные объекты распределителя.

Например, скажем, у меня был класс freelist, который я хотел использовать в моем распределителе, чтобы кэшировать освобожденные объекты. Если я чего-то не упускаю, я не мог бы включить экземпляр этого класса в распределитель, потому что размеры или выравнивания T и U могут отличаться, и поэтому списки фрилансистов несовместимы.

[allocator.requirements] пункт 9:

Распределитель может ограничивать типы, на которых он может быть создан, и аргументы, для которых может быть вызван его член construct . Если тип не может использоваться с определенным распределителем, класс allocator или вызов construct могут не создаваться.

ОК, чтобы ваш распределитель отказался выделить память для чего-либо, кроме T . Это предотвратит его использование в контейнерах на основе node, таких как std::list , которым необходимо выделить собственные внутренние типы node (а не только контейнер value_type ), но он отлично работает для std::vector

  1. В нескольких местах я читал, что С++ 11 улучшает поддержку "распределенных состояний". Как это обстоятельство, учитывая эти ограничения?

Ограничения до С++ 11 были еще хуже!

Теперь ясно указано, как распределители распространяются между контейнерами при копировании и перемещении и как ведут себя различные операции с контейнерами, когда их экземпляр распределителя заменяется другим экземпляром, который не может сравниться с оригиналом. Без этих разъяснений неясно, что должно было произойти, если, например, вы обменяли два контейнера с помощью генераторов с сохранением состояния.

  1. Есть ли у вас предложения по тому, как делать то, что я пытаюсь сделать? То есть, как я могу включить состояние выделенного типа в свой распределитель?

Не вставляйте его непосредственно в распределитель, храните его отдельно и назначайте его распределителем указателем (возможно, умным указателем, в зависимости от того, как вы планируете управление ресурсом ресурса).

Не пытайтесь поддерживать распределение для всех типов, если вам нужно только его поддерживать.

  1. В общем, язык вокруг распределителей кажется неаккуратным. (Например, пролог к ​​таблице 28 говорит, что предполагается, что a имеет тип X &, но некоторые из выражений переопределяют a.)

Кроме того, по крайней мере поддержка GCC является несоответствующей.

Это не 100%, но будет в следующей версии.

Что объясняет эту странность вокруг распределителей? Это нечасто используемая функция?

Да. И там много исторического багажа, и его трудно назвать широко полезным. Моя презентация ACCU 2012 содержит некоторые детали, я буду очень удивлена, если после прочтения вы подумаете, что можете сделать это проще; -)

Не только на C++. Новые технологии, процессы и Agile.

пятница, 29 августа 2008 г.

Mallocator или как написать свой аллокатор

В блоге Visual C++ Team рассказывается как писать собственный аллокатор. Там сказано, что наследование от std::allocator будет не лучшей идеей и приводится пример аллокатора на основе malloc() и free(). В примере достаточно много комментариев и показано, что поменять, чтобы получить аллокатор на свой вкус. Это хорошая отправная точка, если собираетесь написать свой аллокатор.

Всем привет, решил сам организовывать память в своих приложениях, и написал свои простые аллокаторы памяти, все работает прекрасно, но одна проблема: если в классе есть виртуальные методы, то они почему-то не хотят вызываться, и постоянно вылетает ошибка segmentation fault. Почему так? понятно что под виртуальные методы отдельно выделяется память, но я пробовал уже и по 1МБ под класс выделять, один фиг не хочет работать :( Вот код пуллового аллокатора:



А объекты-то каким образом создаются в выделенной памяти?


Так в этом и проблема. Ты конструкторы-то вообще не вызываешь. Даже дефолтные. Кто у тебя будет заполнять таблицы виртуальных функций? Сделай нормальный аллокатор, подобно std::allocator. Ну или operator new перегрузи. Это же кошмар, что ты показал.


Попробуйте использовать placement new.


Вот тут-то и ошибка. Конструктор это не только ваш код, но еще и закулисные действия, в том числе и инициализация vtbl.

placement new - самый легкий в вашем случае путь, но он потребует всегда получать сначала указатель, а так же заставит вызывать руками деструкторы.

Перегрузка стандартных operator new(глобально или только для вашей иерархии типов) - способ тоже простой, но ненаглядный при чтении кода.

Своя версия перегрузки operator new в которую вы передаете свой объект для выделения памяти(инстанс PoolBuffer'а или как там он у вас называется). Так же потребует некой дополнительной функции для уничтожения объектов, которая будет дергать деструктор, а затем возвращать память.

Реализация полноценного аллокатора(под требования Стандарта), позволит использовать свою стратегию управления памятью со стандартными(и сторонними) контейнерами. Можно сочетать с предыдущим пунктом.


решил сам организовывать память в своих приложениях

Версия 1.0
говноаллокатор, работает лишь бы хоть как-то
основан на связном списке блоков, при выделении перебирает тупо все
при освобождении смотрит на соседние блоки, свободны ли они, чтобы присоединиться к ним

проверьте на ошибки плзfree = true;
rem-

TarasB
А что ж ты мне втирал, когда я писал аллокатор пару месяцев назад? Я думал ты профи аллокаторов, а тут вот как - пишешь какое-то первое говнецо :)

Sergio
Напомни тему, я уже забыл.
Что ж ты не зашёл в мою тему про алгоритмическую сложность? Кстати, у тебя с ней как? Логарифма от числа свободных блоков добился? Я вот собираюсь пока.
Кстати, у меня в ресайзе лажа где-то. Где - не знаю, но ассерт срабатывает.

Ща я встрою твой аллокатор в свой тест.

а кто ни буть может объснить нафига это нужно? если достаточно сделать пулов по степени 2^n под аллокации фиксированного размера, с аллокацией за О(1), удалением за О(1) и отсутствием фрагментации, по которым и раскидывать запросы на выделение.

thevlad
Ну когда много пулов, то сложнее думать, какого размера их делать, вдруг один пустой будет, другой переполнится. А ещё переголова же. Допустим, мне надо 1025 байтов, а твои пулы выделят 2048. А на самом деле 1025 байтов я запросил для вектора на всякий случай, а реально мне надо 600 байтов. 4х-кратная переголова выходит.

Я нашёл ошибку в ресайзе, но короче влом говорить и перевыкладывать, просто не ползуйтесь реаллокацией.
Кстати, обратите внимание на интерфейс функции realloc. Он намного лучше подходит для векторов стрингов, чем классический.

TarasB
можно сделать режим профайлинга в котором собирается статистика, а затем выбирается оптимальные размеры для пулов. Но даже если посчитать, что размер выделения равномерно случайно распределенная величина, то при разбиении по степения 2^n потери в среднем будут 25% от размера всей памяти пулов, что ни так уж и много, особенно если учитывать что используется кастомный аллокатор в основном под мелкие объекты . Зато, все операции за O(1) и самое главное отсутствие фрагментации.

TarasB
> Кстати, обратите внимание на интерфейс функции realloc. Он намного лучше
> подходит для векторов стрингов, чем классический.
Классическая интерфейс realloc - общепризнанный говнокод.

thevlad
> и самое главное отсутствие фрагментации.
ну как бы тебе сказать.
пулы же не рядом в памяти находятся

TarasB
почему бы им не находится рядом, если они выделяются практически одновременно. с точки зрения пользователя это обычный malloc, free, вся логика раскидывания по пулам тривиальна и спрятана внутри.

thevlad
> почему бы им не находится рядом
Не понял.
Тебе надо 100500 объектов размером 1024 байта и 100500 объектов размером 2048 байтов*
Ты создаёшь два пула, так вот, как сделать так, чтобы они находились друг от друга на расстоянии больше мегабайта?

*вернее, я не знаю, сколько кого понадобится, я знаю, что мне всего надо 100500 объектов, но так каак я не знаю заранее, какого они будут размера, то я выделяю место с запасом в обоих пулах, это тоже слабое место такой модели

Sergio
> TarasB
> А что ж ты мне втирал, когда я писал аллокатор пару месяцев назад? Я думал ты
> профи аллокаторов, а тут вот как - пишешь какое-то первое говнецо :)

Почему если Тарас в треде, то обязательно рядом с его ником будет слово "говно" ? :)

Читайте также: