Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 61, средняя оценка - 4.61
PSIAlt
 Аватар для PSIAlt
86 / 86 / 8
Регистрация: 19.06.2012
Сообщений: 245
02.09.2012, 00:16     Задача с собеседования (аллокатор памяти) #1
Вопрос звучит так: "Напишите быстрый аллокатор памяти"
Как я его понимаю: можно пожертвовать растратой памяти, всякими наворотами, возможно максимальной величиной обьекта..

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

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

Отдельный квест: как ускорить выделение ещё сильнее. Особенно выделение массивов. То есть ускорить нахождение нужного количества пустых блоков. Применять всякие связные списки пустых блоков и т. п.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
02.09.2012, 00:55     Задача с собеседования (аллокатор памяти) #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
~OhMyGodSoLong~, Александреску можно почитать на этот счет, по идее в Loki очень быстрый аллокатор для маленьких объектов ( но Александреску в своей библиотеке выделывает с С++ такое, что пытаться сделать что-то такое же просто страшно).
PSIAlt
 Аватар для PSIAlt
86 / 86 / 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 ?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
02.09.2012, 01:59     Задача с собеседования (аллокатор памяти) #6
Variadic templates по идее помогут (немного упрощённый пример, но суть понятна). Как без них красиво — не знаю. Разве что пачку шаблонов под allocate(один шаблонный параметр), allocate(два шаблонных параметра), ..., allocate(пять шаблонных параметров).
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
02.09.2012, 02:03     Задача с собеседования (аллокатор памяти) #7
~OhMyGodSoLong~, http://liveworkspace.org/code/a3f13f...5001e52683c39e так немного логичнее будет, мы ведь просто "прокидываем" аргументы.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
02.09.2012, 02:35     Задача с собеседования (аллокатор памяти) #8
Вопрос в двух строчках не осветить. Лучше статьи книги поискать, где тема раскрывается.
В частности, в александревску расписан один из возможных вариантов написания собственного распределителя памяти. У Джосатиса в справочнике по STL есть кое-что про требования к совместимым со стандартными распределителями памяти. Где-то еще видел, но всмопнить не могу.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.09.2012, 08:42     Задача с собеседования (аллокатор памяти) #9
Цитата Сообщение от PSIAlt Посмотреть сообщение
Вопрос звучит так: "Напишите быстрый аллокатор памяти"
На самом деле, вопрос не однозначен. Ведь аллокатор это абстрактное название, никак не связанное с контейнерами STL. Поэтому не очевидно, должна ли память выделяться для одного объекта или для нескольких объектов. Уже упомянутый Александреску решил все эти проблемы при помощи классов стратегий, но тебе-то нужно один простенький вариант написать... В общем, первым делом нужно пытать задающего вопросы, чтобы не было разночтений. Это тоже входит в обязанности разработчика, потому что в документации может быть любая чушь написана, которую все по своему понять могут и реализовать вовсе не то, чего изначально думалось.

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

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

Почему test() и set() так тормозят, есть только одна догадка: они делают range check и он так всё тормозит.
PSIAlt
 Аватар для PSIAlt
86 / 86 / 8
Регистрация: 19.06.2012
Сообщений: 245
02.09.2012, 18:37  [ТС]     Задача с собеседования (аллокатор памяти) #16
Заглянул в исходники, там джигурда вобще... Внутернние методы возращают обьекты вроде std::_Base_bitset<16ul> и с ними уже делаются перегруженные операции типа &... И да, ренж чек он тоже делает) Короче будет уроком - не юзать пока не в курсе как оно работает
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
02.09.2012, 18:55     Задача с собеседования (аллокатор памяти) #17
Цитата Сообщение от bgm313 Посмотреть сообщение
Вот в простом варианте:
вопрос по коду на картинке: переменная allocp объявлена как static char *, но она не внутри функции. Она будет вести себя так же, как если бы это была переменная static внутри функции?
Т.к. написано "следующая свободная позиция" - как бы намекает на поведение static-переменных
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
02.09.2012, 19:25     Задача с собеседования (аллокатор памяти) #18
Глобальная static переменная (а также static, объявленная внутри любого namespace) имеет ограниченную область видимости в пределах данного cpp файла, ты об этом?
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
02.09.2012, 19:36     Задача с собеседования (аллокатор памяти) #19
Цитата Сообщение от Герц Посмотреть сообщение
Глобальная static переменная (а также static, объявленная внутри любого namespace) имеет ограниченную область видимости в пределах данного cpp файла, ты об этом?
Да. А её поведение (точнее поведение компилятора относительно неё) в данном куске кода аналогично тому, которое было бы, если бы она была static и внутри функции alloc?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.09.2012, 19:39     Задача с собеседования (аллокатор памяти)
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
02.09.2012, 19:39     Задача с собеседования (аллокатор памяти) #20
Да, внутри функции она точно так же создавалась бы единожды при входе в программу и сохраняла свое значение вплоть до завершения, локальная static переменная подобна глобальной, но с усеченной областью видимости.
Yandex
Объявления
02.09.2012, 19:39     Задача с собеседования (аллокатор памяти)
Ответ Создать тему
Опции темы

Текущее время: 21:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru