Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.60/133: Рейтинг темы: голосов - 133, средняя оценка - 4.60
87 / 87 / 1
Регистрация: 19.06.2012
Сообщений: 245
1

Задача с собеседования (аллокатор памяти)

02.09.2012, 00:16. Показов 24959. Ответов 23
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вопрос звучит так: "Напишите быстрый аллокатор памяти"
Как я его понимаю: можно пожертвовать растратой памяти, всякими наворотами, возможно максимальной величиной обьекта..

Может у кого-то есть какие-то варианты? Мне что-то ничего в голову не приходит кроме как заранее поделить пул на поля с фиксированным размером N и завести битовое поле в котором храним флаги занято/свободно.. Может подкинете пару идей?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.09.2012, 00:16
Ответы с готовыми решениями:

Аллокатор памяти общего назначения
Добрый день! В ВУЗе задали написать аллокатор памяти общего назначения на С++, но у меня нет ни...

Задача с собеседования
Всем привет! Недавно был на собеседование. Было много вопросов по строкам. Такое объявление строки...

Кастомный аллокатор
Не уверен, что это "для начинающих", но этот раздел подходил больше всех. Итак, объясню вкратце...

Аллокатор в chrome
Всем привет, начал изучать исходники хрома, в аллокаторе, метод realloc должен возвращать nullptr...

23
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
Состряпал вариант... Не слишком убого?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define MAX_SZ 32
#define MAX_ITEM 1000
 
class Alloc2 {
        static char buf[MAX_ITEM * MAX_SZ];
        static bitset<MAX_ITEM> bufmap;
        static int freeblock;
public:
template <typename T>
        static T *allocate(void) {
                int i;
                static_assert( sizeof(T) < MAX_SZ, "Max size for this allocator excessed " );
                for(i=freeblock; i<MAX_ITEM; i++) {
                        if( !bufmap.test(i) )
                                break;
                }
                if( i==MAX_ITEM ) throw new bad_alloc();
                bufmap.set(i, true);
                freeblock=i+1;
                return static_cast<T*> (new (&buf[MAX_SZ*i]) T());
        }
template <typename T>
        static void deallocate(T *ptr) {
                int i = ( ((char*)ptr)-&buf[0] )/MAX_SZ;
                if( !bufmap.test(i) ) throw new logic_error("Wrong deallocate");
                ptr->~T();
                bufmap.set(i, false);
                if( freeblock > i ) freeblock=i;
        }
};
int Alloc2::freeblock=0;
bitset<MAX_ITEM> Alloc2::bufmap = bitset<MAX_ITEM>();
char Alloc2::buf[MAX_ITEM * MAX_SZ];
 
//......
        for(long i=0; i<c; i++) {
                for(int j=0; j<3; j++){
                int *a = Alloc2::allocate<int>();
                *a=5;
                Alloc2::deallocate( a );
                }
        }
Вроде бы по замерам clock() неплохо, но может быть можно лучше?...
Код
new/delete: 921
allocator2: 557
И еще вопрос: как сделать чтобы allocate умел прокидывать параметры конструктора во внутрь Placement new ?
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
DU
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
Цитата Сообщение от PSIAlt Посмотреть сообщение
Вопрос звучит так: "Напишите быстрый аллокатор памяти"
На самом деле, вопрос не однозначен. Ведь аллокатор это абстрактное название, никак не связанное с контейнерами 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
Цитата Сообщение от PSIAlt Посмотреть сообщение
Я так понимаю спрашивается просто malloc/free настолько быстрый насколько возможно
Тогда вопрос о количестве объектов встаёт. Если объектов один-два, то ты ничего не выиграешь. Если объектов много, то делай самую простую реализацию, не парясь над совместимостью с 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
Цитата Сообщение от bgm313 Посмотреть сообщение
Вот в простом варианте:
вопрос по коду на картинке: переменная allocp объявлена как static char *, но она не внутри функции. Она будет вести себя так же, как если бы это была переменная static внутри функции?
Т.к. написано "следующая свободная позиция" - как бы намекает на поведение static-переменных
0
545 / 344 / 12
Регистрация: 05.11.2010
Сообщений: 1,076
Записей в блоге: 1
02.09.2012, 19:25 18
Глобальная static переменная (а также static, объявленная внутри любого namespace) имеет ограниченную область видимости в пределах данного cpp файла, ты об этом?
1
Временно недоступен
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
02.09.2012, 19:36 19
Цитата Сообщение от Герц Посмотреть сообщение
Глобальная static переменная (а также static, объявленная внутри любого namespace) имеет ограниченную область видимости в пределах данного cpp файла, ты об этом?
Да. А её поведение (точнее поведение компилятора относительно неё) в данном куске кода аналогично тому, которое было бы, если бы она была static и внутри функции alloc?
0
545 / 344 / 12
Регистрация: 05.11.2010
Сообщений: 1,076
Записей в блоге: 1
02.09.2012, 19:39 20
Да, внутри функции она точно так же создавалась бы единожды при входе в программу и сохраняла свое значение вплоть до завершения, локальная static переменная подобна глобальной, но с усеченной областью видимости.
1
02.09.2012, 19:39
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.09.2012, 19:39
Помогаю со студенческими работами здесь

Быстрый аллокатор
Собственно, необходим аллокатор для быстрого выделения памяти под мелкие объекты, совместимый со...

Класс аллокатор
Какие требования к написанию класса Аллокатора?

Пишем аллокатор
дабы не захламлять и так уже захламленную тему про перегрузку операторов создаю новую тему,...

Пародия на стековый аллокатор
здравствуйте, решил тут чуток поиграться... сделать аллокатор чтобы данные в статическом буфере...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru