Comments 34
Так вот это объединение — весьма дорогая операция. Я сделал линейным поиском примыкающих сверху и снизу от освобождаемого. Но может, есть идеи получше?
Кстати, описание неточное — аллокатор потому и watermark, что в начала каждого блока и стоит ватермарка — занят он или свободен. К сожалению, ватермарки не помогли с объединением, потому что иногда сверху, например — не «наша» память.
у блока есть заголовок, в котором лежит размер этого и предыдущего блока, статус блока(занят/свободен)У автора не возникло затруднения использовать «заголовок» вместо так называемой «ватермарки». Это не делает описанее менее точным.
Это даже как-то называется, но я не помню как)
Но, как вы понимаете, могут начать образовываться дыры, в которых 2 и более свободных блоков — память дефрагментированна, при высвобождении можно просматривать соседние блоки, и в случае, когда один или два свободны — мержить их в один.
С точностью наоборот: фрагментирована. Дефрагментация — процесс исключения фрагментации.
Бегать только по свободным улучшает скорость в среднем в два раза, но это всё равно линия.
Это точно не машинный перевод?
Аллокатор как часть ОС? А зачем? Обычно ОС предоставляют низкоуровневые вызовы, резервирующие память страницами, вроде sbrk/mmap в POSIX или VirtualAlloc в Windows, а уже поверх них в userspace реализуется что-нибудь вроде malloc. Последний может быть и не нужен, если вы запускаете на своей ОС какую-нибудь Java, где свой аллокатор, который непосредственно в тот же mmap бегает.
Например, с своими кастомным malloc, как прикажете шарить память, выделенную разными библиотеками (линкованными с несовместимыми версиями libc или даже со статическими libc)? Ядро и сервисы всякие не имеют возможности освобождать буфера юзерспейса и память, выделенную друг-другом. А без этого трудно внедрить общесистемный стандарт данных высокого уровня.
Собственно, простая задача — как передавать строки и массивы двоичных данных между библиотеками и программами не думая о бинарной совместимости. В том смысле, что передать передать легко, но кто освобождать буфер будет в тяжёлых случаях, когда вызываются всякие отложенные callback и вы не контролируете момент вызова?
А в Windows, например, можно вполне безопасно обмениваться OLE-совместимыми строками между программами на совершенно разных языках (лишь бы типы данных OLE поддерживались, но это стандарт по Win и его поддерживаются все языки).
Для какой-нибудь специфической задачи/железа оно может и имеет смысл.
А вот в общем…
Осенью прошлого года подумалось попробовать "тот самый" аллокатор мелких объектов из книжки Александреску. Как раз для них самих (для мелких объектов).
Ок, нашёл либу, отревьювил, адаптировал под современные реалии (тогда же не было ещё move-семантики в плюсах, а нынче почему бы не воспользоваться?) По итогу взлетело, поведение соответствует ожидаемому и вроде всё здорово. Код прямой, как палка, и вроде не содержит никаких явных затыков…
Угумс… Делаем бенч, аллоцируем/освобождаем в цикле с десяток миллионов чанков случайной длины (такой, чтоб именно в алгоритм аллокатора попадало). И ровно то же самое — "стандартным" malloc/free… И тут внезапно(?) оказывается, что "тот самый" аллокатор 10-летней давности даже близко не стоит к штатному из glibc. Разница по скорости вышла чудовищная (чуть ли не в сотню раз). Никакие улучшения/оптимизации ситуацию существенно не улучшили. Потому что "штатный" пилился и улучшался все эти годы; добавлялась многопоточность; оптимизировались алгоритмы и подходы, и по итогу соревноваться с ним стало весьма сложно.
И в итоге было решено оставить затею и, не выпендриваясь, пользоваться "штатными" средствами. Ну, в крайнем случае — jmalloc (благо, он не требует пересборки и легко цепляется через LD_PRELOAD).
Дело в том, что освобождение и так более сложная операция чем выделение, так еще все усложняется тем, что интерфейс delete повторяет интерфейс free() и при использовании стороннего аллокатора, прежде чем начать что-то удалять, необходимо понят, а какого размера объект указатель на который нам передали? А это отдельная песня, с блокировками, походами по таблицам и т.д.
мне почему-то вот тут сразу вспомнилась "знаменитая" книжка "Visual C++ 6.0 для компьютеров и программирования" под авторством некоего Секунова. А запомнилась она по одному пассажу, который я до сих пор помню: Не всегда понятно, когда использовать delete а когда delete[], и это определяется, как правило, методом "научного тыка".
Я не поленился и нашёл это место. Книга называется «Самоучитель Visual C++ 6», PDF-версия не распознана,
Я даже не вчитывался, это действительно неплохой «сюрприз». Вот интересно, в те годы ещё copy&swap idiom не изобрели, что ли? Потому что она сразу убирает проверку на равенство указателей, убирает дублирование кода и избавляет от ошибок при всех этих операциях.
Я не призываю не пользоваться новым, однако стоит понимать, тот оверхед который с ними приходит, и корректно выбирать задачи которые ими решаются.
Да там нет особого оверхеда.
Просто специфическая реализация широко используемых библиотек использует разные современные бустеры и фичи современных процессоров, так что даже будучи написанной на С++ (я не про аллокатор прямо сейчас, а в целом) влёгкую окажется намного быстрее "велосипедов" хотя бы за счёт скрупулёзности, выверенности и оптимизации под конкретные архитектуры.
Например: де-ескейпим строчку из json: ходим в цикле по символам; видим обратный слэш — обрабатываем, иначе просто копируем символ их входа на выход (т.е. в конце цикла есть немудрёная строчка *dest++ = *src++
. Что может быть проще?
Ага, заменяем эту строчку на memchr('\') + последующий memmove найденного куска без слэшей — и несмотря на вызовы функций вместо вроде бы линейного кода получаем ускорение раза в полтора (на типовых строках, где экранированных символов около 10%). И всё потому что и memchr и memmove отлично разбираются в архитектурах современных процессоров, а потому умеют делать свою задачу настолько оптимально и быстро, что в профайлере занимают какую-то долю процента.
Согласен с предыдущими комментами — если вы пишете ОС, то вам нужен не malloc, а аналог sbrk\mmap. Для malloc cоветую покурить jemalloc (https://github.com/jemalloc/jemalloc). Там учтены уже все детские болезни велосипедных аллокаторов (как-то: оптимизация вызовов sbrk\mmap, локов для многопоточных приложений, фрагментации, кешей, специфика архитектуры процев, разные логики на большие\малые выделения и т.п). Без глубокого закапывания в эти детали лезть в какую-либо оптимизацию вообще не стоит, O(N) и так сойдет.
Написание собственного неплохого менеджера памяти