Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Рациональное распределение памяти

Автор: tofreesky 28.7.2010, 01:17

Что вы думаете по этому поводу. Имеется некоторая служная описаная структура. В программе кол-во этих структур в массиве динамично.  Что лучше использовать? Заранее выделенный максимально доступный массив этих эллементов. Или выделять их динамически? Кол-во эллементов может быть от самого маленького, до самого большого. Я думаю лучше иметь, маленький массив таких структур на случай если число их будет меньше того что есть. А если больше то выделять память. Просто не хочется из-за маленького кол-ва дергать диспетчер памяти в ОС.  Кто что думает по этому вопросу, надеюсь я понятно выразился.

Автор: djamshud 28.7.2010, 01:26

realloc, если хотите хранить свои структуры непременно одним куском. Другой вариант - использовать связные структуры данных вроде списков. В порядке бреда еще можно предложить написать свой максимально задроченный на ваши структуры менеджер памяти (userspace-овый). .... realloc - это я на языке си выразился. В общем имелся в виду буфер изменяемого размера.

Автор: tofreesky 28.7.2010, 09:59

Код struct abc {  int a;  float b;  char c; }; int func() {  int StructNum = rand() % 0x1000;  struct abc structures_1[0x50];  struct abc *structures_2;  if(StructNum <= 0x50)  {   // Работаем с уже выделенным буфером  }   else  {   // Сис. функции для работы с памятью   structures_2 = (struct abc*) malloc(StructNum);   free(structures_2);  }  } Вот что примерно я описал в первом сообщении

Автор: djamshud 28.7.2010, 10:41

>struct abc structures_1[0x50]; И вы в любом случае забиваете стек этой ерундой... Лучше имхо всегда делать через malloc. А если функция вызывается много раз, указатель можно вынести из функции (сделать его глобальным, статическим или передаваемым через параметр) и работать с ним, довыделяя под него при необходимости память.

Автор: tofreesky 28.7.2010, 11:04

В стеке резирвируется память под локальные переменные всего лишь  SUB ESP, sizeof(abc)*StructNum + выравнивание А через malloc и т.п. мы дергаем диспетчер памяти. Добавлено через 3 минуты и 53 секунды А смысл в том что если кол-во эллементов будет маленьким, то не рационально дергать сис. функции для работы с памятью.

Автор: baldina 28.7.2010, 11:24

std::deque

Автор: djamshud 28.7.2010, 11:56

tofreesky, func вызывается многократно?

Автор: gustavomarginale 30.7.2010, 03:34

В одной большой программе, к которой я причастен, во время работы разбираются разные выражения из текстовых файлов, написанных юзером, парсятся структурированные данные и т.п. Во время этих процессов постоянно рождаются структуры разных видов. Процесс разбора - это только создание новых структур, очень редко нужно удаление. Просим у ОС память большими кусками, метра по 4. Это наша свободная память. Какому-то модулю нужно где-то сохранить структуру - он пишет в начало свободного блока, а байт после этой структуры делает новым началом свободного места. Кончилось всё место - попросили новые 4 мегабайта у ОС.Очень редко кому-то какая-то структура перестаёт быть нужной, т.к. основное время работы идёт "построение" цепей структур или деревьев из них. Когда завершён "проход" и использованы результаты этих построений, мы просто освобождаем эти блоки, выделенные у ОС за пару вызовов ядра, сдувая все наши построения максимально быстро для нового прохода. Модулю не понадобилась ранее созданная структура - он просто забывает о её существовании. То, что она остаётся в памяти волнует мало кого, таких структур - 1%.

Автор: tofreesky 30.7.2010, 09:40

Тут еще вопрос в том что не рационально было бы вызывать malloc для выделения памяти в 500 байт допустим. А в третьем посте мое предложение. И еще вот ситуация: как лучше сделать, если кол-во элементов постояно увеличивается, и я пользуюсь realloc часто для раздутия массива, изначально кол-во мы не знаем.

Автор: gustavomarginale 1.8.2010, 23:01

Ну допустим кол-во структур постоянно увеличивается. Realloc - фтопку, ведь он нужен, когда программист хочет иметь пепрерывный кусок памяти. А нам зачем? Мы можем выделять по 4 мегабайта. И ими распоряжаться так: в начале каждого выделяемого блока оставлять 4 байта (или 8 для 64bit) под хранение адреса следующего блока. Начинать использовать этим блоком, не трогая эти первые байты. Сохранять в нём наши структуры, пока он не кончится. Кончился - выделить новый блок, его адрес записать в первые 4-8 байт предыдущего. Нарисую картинку. Красные блоки - то, что нам выдала ОС. Чёрные - это список наших структур, в блоках хранящийся. Можно обойтись без указателей внутри чёрных стуктур. Просто в каждый красный блок сохранять структуры вплотную, зная, сколько он вмещает, выделяя новый по необходимости. Читать весь список наших структур - переодически прыгая по красным указателям.

Автор: baldina 3.8.2010, 17:44

Цитата И еще вот ситуация: как лучше сделать, если кол-во элементов постояно увеличивается Цитата Нарисую картинку. гм. кто-нить заметил? Цитата(baldina @  28.7.2010,  11:24 ) std::deque

Автор: tofreesky 4.8.2010, 23:13

И еще вопрос, ведь очень не правильно делать, если постоянно через realloc расширять память, под структура маленьких размеров (20-40 байтов)

Автор: baldina 5.8.2010, 17:54

походу меня все игнорируют... :( tofreesky, теория:  если требуется произвольный доступ к контейнеру, то следует использовать массив - он хранится линейно, трудоемкость доступа O(1) если требуется динамический контейнер, размер которого неизвестен, то следует использовать список - он распределяется динамически, трудоемкость добавления/удаление O(1) если требуется и то, и другое, придется использовать более сложную структуру данных, которая неплохо добавляет и неплохо осуществляет доступ. как любой компромис, производительность на соответствующих операциях похуже массива и списка, но в целом достигаем баланса. как: память выделяется блоками. внутри блока доступ к элементам O(1), а в целом - гораздо лучше O(n). при добавлении/удалении перераспределение памяти будет происходить реже (зависит от размера блока). практика: 1. std::deque. реализован как список блоков http://alenacpp.blogspot.com/2006/12/vector-vs-deque.html 2. std::vector несмотря на использование непрерывной памяти может оказаться достаточно эффективным. дело в том, что распределитель памяти по умолчанию не дергает alloc при каждом добавлении элемента, а распределяет с запасом (часто используется простой, но эффективный алгоритм, вдвое увеличивающий выделяемую память при каждом вызове) 3. существует множество алгоритмов управления памятью. универсального нет. Под стандартной библиотекой находится современная ОС, и ее алгоритмы не так уж плохи  Так что "дергать" менеджер памяти может не так уж плохо. 4. если заранее известен характер распределения памяти, можно использовать boost::pool 5. в случае небольшого (до 1000) числа элементов разница в производительности разных способов хранения скорее всего не будет заметна...  ЗЫ: а есть ли реальная проблема, или вопрос задан из академического интереса? практика уже показала непригодность std::vector или std::list или самопального контейнера?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)