87 / 87 / 1
Регистрация: 19.06.2012
Сообщений: 245
|
|
1 | |
Задача с собеседования (аллокатор памяти)02.09.2012, 00:16. Показов 24959. Ответов 23
Метки нет (Все метки)
Вопрос звучит так: "Напишите быстрый аллокатор памяти"
Как я его понимаю: можно пожертвовать растратой памяти, всякими наворотами, возможно максимальной величиной обьекта.. Может у кого-то есть какие-то варианты? Мне что-то ничего в голову не приходит кроме как заранее поделить пул на поля с фиксированным размером N и завести битовое поле в котором храним флаги занято/свободно.. Может подкинете пару идей?
0
|
02.09.2012, 00:16 | |
Ответы с готовыми решениями:
23
Аллокатор памяти общего назначения Задача с собеседования Кастомный аллокатор Аллокатор в chrome |
12 / 12 / 3
Регистрация: 27.07.2012
Сообщений: 208
|
|
02.09.2012, 00:43 | 2 |
Вот в простом варианте:
2
|
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
|
|
02.09.2012, 00:52 | 3 |
Да фактически ж пул и просят по идее. Выделяете pool_size * sizeof(T) байт под пул, два массива размером в pool_size: один из bool (метки занятых ячеек; думаю, это будет быстрее битовых полей), второй из T* (кеш для указателей в пуле, рассчитывается при инициализации; тоже чуть ускоряет), определяете аллокацию-деаллокацию с помощью placement new и вызова деструктора, вместе с обновлением меток.
Отдельный квест: как ускорить выделение ещё сильнее. Особенно выделение массивов. То есть ускорить нахождение нужного количества пустых блоков. Применять всякие связные списки пустых блоков и т. п.
1
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
02.09.2012, 00:55 | 4 |
Сообщение было отмечено как решение
Решение
~OhMyGodSoLong~, Александреску можно почитать на этот счет, по идее в Loki очень быстрый аллокатор для маленьких объектов ( но Александреску в своей библиотеке выделывает с С++ такое, что пытаться сделать что-то такое же просто страшно).
3
|
87 / 87 / 1
Регистрация: 19.06.2012
Сообщений: 245
|
||||||
02.09.2012, 01:42 [ТС] | 5 | |||||
Состряпал вариант... Не слишком убого?
Код
new/delete: 921 allocator2: 557
0
|
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
|
|
02.09.2012, 01:59 | 6 |
Variadic templates по идее помогут (немного упрощённый пример, но суть понятна). Как без них красиво — не знаю. Разве что пачку шаблонов под allocate(один шаблонный параметр), allocate(два шаблонных параметра), ..., allocate(пять шаблонных параметров).
1
|
В астрале
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
|
|
02.09.2012, 02:03 | 7 |
~OhMyGodSoLong~, http://liveworkspace.org/code/... e52683c39e так немного логичнее будет, мы ведь просто "прокидываем" аргументы.
2
|
1500 / 1146 / 165
Регистрация: 05.12.2011
Сообщений: 2,279
|
|
02.09.2012, 02:35 | 8 |
Вопрос в двух строчках не осветить. Лучше статьи книги поискать, где тема раскрывается.
В частности, в александревску расписан один из возможных вариантов написания собственного распределителя памяти. У Джосатиса в справочнике по STL есть кое-что про требования к совместимым со стандартными распределителями памяти. Где-то еще видел, но всмопнить не могу.
2
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
02.09.2012, 08:42 | 9 |
На самом деле, вопрос не однозначен. Ведь аллокатор это абстрактное название, никак не связанное с контейнерами STL. Поэтому не очевидно, должна ли память выделяться для одного объекта или для нескольких объектов. Уже упомянутый Александреску решил все эти проблемы при помощи классов стратегий, но тебе-то нужно один простенький вариант написать... В общем, первым делом нужно пытать задающего вопросы, чтобы не было разночтений. Это тоже входит в обязанности разработчика, потому что в документации может быть любая чушь написана, которую все по своему понять могут и реализовать вовсе не то, чего изначально думалось.
Ну а по теме могу добавить ещё реализацию аллокатора из буста. Но у Александреску более очевидная реализация и лучше у него подсмотри.
1
|
87 / 87 / 1
Регистрация: 19.06.2012
Сообщений: 245
|
|
02.09.2012, 09:29 [ТС] | 10 |
Ну про STL ни слова небыло. Имплементить его интерфейсы это отдельная песня насколько я помню=)
Я так понимаю спрашивается просто malloc/free настолько быстрый насколько возможно
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
02.09.2012, 09:49 | 11 |
Тогда вопрос о количестве объектов встаёт. Если объектов один-два, то ты ничего не выиграешь. Если объектов много, то делай самую простую реализацию, не парясь над совместимостью с STL-аллокаторами. Но я подозреваю, что именно для этих целей аллокатор и подразумевался.
0
|
87 / 87 / 1
Регистрация: 19.06.2012
Сообщений: 245
|
|
02.09.2012, 17:14 [ТС] | 12 |
Кому интересно - удалось ускорить еще в 3 раза, избавившись от std::bitset
Замеры clock(): Код
new/delete: 921 allocator2: 183
0
|
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
|
|
02.09.2012, 17:37 | 13 |
И что поставили? Обычный массив bool или типа того? Если да, то теперь это можно в рамочку и прибить подпись "Почему выравнивание данных так важно".
0
|
87 / 87 / 1
Регистрация: 19.06.2012
Сообщений: 245
|
|
02.09.2012, 17:49 [ТС] | 14 |
По gprof-у больше всео залипали bitset::test и bitset::set, поэтому сделал массив char в котором храню биты и вычисляю бит сам, без bitset
Почти тоже самое(чуток быстрее) - если просто взять массив char (без вычисления битов, один флаг на один байт) Ну выравнивание да, дело важное, но я так понял когда читаешь 1 байт то выравнивание не особо парит, разве нет?
0
|
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
|
|
02.09.2012, 18:02 | 15 |
Попробуйте сравнить с int вместо char, это покажет, сколько там теряется на шине памяти (читается-то сразу по четыре байта, а то и по восемь). Но если всё хорошо, там могут работать кеши, потому потери минимальные.
Почему test() и set() так тормозят, есть только одна догадка: они делают range check и он так всё тормозит.
0
|
87 / 87 / 1
Регистрация: 19.06.2012
Сообщений: 245
|
|
02.09.2012, 18:37 [ТС] | 16 |
Заглянул в исходники, там джигурда вобще... Внутернние методы возращают обьекты вроде std::_Base_bitset<16ul> и с ними уже делаются перегруженные операции типа &... И да, ренж чек он тоже делает) Короче будет уроком - не юзать пока не в курсе как оно работает
0
|
Временно недоступен
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
|
|
02.09.2012, 18:55 | 17 |
вопрос по коду на картинке: переменная allocp объявлена как static char *, но она не внутри функции. Она будет вести себя так же, как если бы это была переменная static внутри функции?
Т.к. написано "следующая свободная позиция" - как бы намекает на поведение static-переменных
0
|
Временно недоступен
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
|
|
02.09.2012, 19:36 | 19 |
Да. А её поведение (точнее поведение компилятора относительно неё) в данном куске кода аналогично тому, которое было бы, если бы она была static и внутри функции alloc?
0
|
02.09.2012, 19:39 | 20 |
Да, внутри функции она точно так же создавалась бы единожды при входе в программу и сохраняла свое значение вплоть до завершения, локальная static переменная подобна глобальной, но с усеченной областью видимости.
1
|
02.09.2012, 19:39 | |
02.09.2012, 19:39 | |
Помогаю со студенческими работами здесь
20
Быстрый аллокатор Класс аллокатор Пишем аллокатор Пародия на стековый аллокатор Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |