Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 61, средняя оценка - 4.61
PSIAlt
87 / 87 / 8
Регистрация: 19.06.2012
Сообщений: 245
#1

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

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

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

Может у кого-то есть какие-то варианты? Мне что-то ничего в голову не приходит кроме как заранее поделить пул на поля с фиксированным размером N и завести битовое поле в котором храним флаги занято/свободно.. Может подкинете пару идей?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.09.2012, 00:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача с собеседования (аллокатор памяти) (C++):

Быстрый аллокатор - C++
Собственно, необходим аллокатор для быстрого выделения памяти под мелкие объекты, совместимый со стандартными контейнерами (std::list и...

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

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

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

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

Как написать пуловый аллокатор для работы с объектами - C++
Здравствуйте! Подскажите как написать пуловый аллокатор для работы с объектами

23
bgm313
12 / 12 / 2
Регистрация: 27.07.2012
Сообщений: 208
02.09.2012, 00:43 #2
Вот в простом варианте:
2
Миниатюры
Задача с собеседования (аллокатор памяти)  
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
02.09.2012, 00:52 #3
Да фактически ж пул и просят по идее. Выделяете pool_size * sizeof(T) байт под пул, два массива размером в pool_size: один из bool (метки занятых ячеек; думаю, это будет быстрее битовых полей), второй из T* (кеш для указателей в пуле, рассчитывается при инициализации; тоже чуть ускоряет), определяете аллокацию-деаллокацию с помощью placement new и вызова деструктора, вместе с обновлением меток.

Отдельный квест: как ускорить выделение ещё сильнее. Особенно выделение массивов. То есть ускорить нахождение нужного количества пустых блоков. Применять всякие связные списки пустых блоков и т. п.
1
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
02.09.2012, 00:55 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
~OhMyGodSoLong~, Александреску можно почитать на этот счет, по идее в Loki очень быстрый аллокатор для маленьких объектов ( но Александреску в своей библиотеке выделывает с С++ такое, что пытаться сделать что-то такое же просто страшно).
3
PSIAlt
87 / 87 / 8
Регистрация: 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
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
02.09.2012, 01:59 #6
Variadic templates по идее помогут (немного упрощённый пример, но суть понятна). Как без них красиво — не знаю. Разве что пачку шаблонов под allocate(один шаблонный параметр), allocate(два шаблонных параметра), ..., allocate(пять шаблонных параметров).
1
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
02.09.2012, 02:03 #7
~OhMyGodSoLong~, http://liveworkspace.org/code/a3f13f3e790ea5fca45001e52683c39e так немного логичнее будет, мы ведь просто "прокидываем" аргументы.
2
DU
1484 / 1130 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
02.09.2012, 02:35 #8
Вопрос в двух строчках не осветить. Лучше статьи книги поискать, где тема раскрывается.
В частности, в александревску расписан один из возможных вариантов написания собственного распределителя памяти. У Джосатиса в справочнике по STL есть кое-что про требования к совместимым со стандартными распределителями памяти. Где-то еще видел, но всмопнить не могу.
2
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.09.2012, 08:42 #9
Цитата Сообщение от PSIAlt Посмотреть сообщение
Вопрос звучит так: "Напишите быстрый аллокатор памяти"
На самом деле, вопрос не однозначен. Ведь аллокатор это абстрактное название, никак не связанное с контейнерами STL. Поэтому не очевидно, должна ли память выделяться для одного объекта или для нескольких объектов. Уже упомянутый Александреску решил все эти проблемы при помощи классов стратегий, но тебе-то нужно один простенький вариант написать... В общем, первым делом нужно пытать задающего вопросы, чтобы не было разночтений. Это тоже входит в обязанности разработчика, потому что в документации может быть любая чушь написана, которую все по своему понять могут и реализовать вовсе не то, чего изначально думалось.

Ну а по теме могу добавить ещё реализацию аллокатора из буста. Но у Александреску более очевидная реализация и лучше у него подсмотри.
1
PSIAlt
87 / 87 / 8
Регистрация: 19.06.2012
Сообщений: 245
02.09.2012, 09:29  [ТС] #10
Ну про STL ни слова небыло. Имплементить его интерфейсы это отдельная песня насколько я помню=)
Я так понимаю спрашивается просто malloc/free настолько быстрый насколько возможно
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.09.2012, 09:49 #11
Цитата Сообщение от PSIAlt Посмотреть сообщение
Я так понимаю спрашивается просто malloc/free настолько быстрый насколько возможно
Тогда вопрос о количестве объектов встаёт. Если объектов один-два, то ты ничего не выиграешь. Если объектов много, то делай самую простую реализацию, не парясь над совместимостью с STL-аллокаторами. Но я подозреваю, что именно для этих целей аллокатор и подразумевался.
0
PSIAlt
87 / 87 / 8
Регистрация: 19.06.2012
Сообщений: 245
02.09.2012, 17:14  [ТС] #12
Кому интересно - удалось ускорить еще в 3 раза, избавившись от std::bitset
Замеры clock():
Код
new/delete: 921
allocator2: 183
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
02.09.2012, 17:37 #13
И что поставили? Обычный массив bool или типа того? Если да, то теперь это можно в рамочку и прибить подпись "Почему выравнивание данных так важно".
0
PSIAlt
87 / 87 / 8
Регистрация: 19.06.2012
Сообщений: 245
02.09.2012, 17:49  [ТС] #14
По gprof-у больше всео залипали bitset::test и bitset::set, поэтому сделал массив char в котором храню биты и вычисляю бит сам, без bitset
Почти тоже самое(чуток быстрее) - если просто взять массив char (без вычисления битов, один флаг на один байт)

Ну выравнивание да, дело важное, но я так понял когда читаешь 1 байт то выравнивание не особо парит, разве нет?
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
02.09.2012, 18:02 #15
Попробуйте сравнить с int вместо char, это покажет, сколько там теряется на шине памяти (читается-то сразу по четыре байта, а то и по восемь). Но если всё хорошо, там могут работать кеши, потому потери минимальные.

Почему test() и set() так тормозят, есть только одна догадка: они делают range check и он так всё тормозит.
0
02.09.2012, 18:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.09.2012, 18:02
Привет! Вот еще темы с ответами:

Задания с++ с собеседования - C++
Предложите ваши варианты решения заданий 1. Перечислите все проблемы, которые вы видите в данном коде: class Foo { public: ...

Пример из собеседования по C++ - C++
Граждане, есть такой пример: class B { private: virtual void f() { std::cout &lt;&lt; &quot;B::f()&quot; &lt;&lt; std::endl;} public: void g() {...

Задание с собеседования (циклы) - C++
День добрый! Был сегодня на собеседовании, и было такое задание где было такое задание: Описать одним предложением что делает данная...

Собеседования по С++ для джуна - C++
Добрый день, если вы бы проводили собеседования по С++ для джуна - какой вопрос по С++ вы бы припасли как самый сложный? Для...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.