[ profi_r: ...можно изменять размер блоков памяти, выделенных HeapAlloc-ом? ]

Да - HeapReAlloc.


[ profi_r: И есть ли у него какая нибудь кратность при установке размера памяти? ]

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

Ммда... ну я и лопух :(

profi_r
Сорри за дезинформацию.

Four-F
Так я вот про что. В Мануалах написано, например, что многие функции, (например FormatMassege()) сами выделяют память и возвращают её указатель.
Память нужно освобадить самому при помощи GlobalAlloc
Но эти функции не рекомендуются ???
Здесь мне совершенно не ясна политика Майкрософт
С одной стороны -- не нужно, а с другой - необходимо :((

profi_r
индексу и размерность массива должна быть изменяемой
А вот у Квантума хороший исходник... :)
Смотри как прикольно...
ОК, рассказываю, тема -- сеперативная и разреженная память. Две замечательные схемы, которые используются не только в памяти, а и БД. Особенно разреженная память.
Я понимаю, что можно было бы ограничится только сепарацией, но люблю красоту алгоритмов до безумия :)))

1. Переменная BlockFirst хранит адрес начала первого блока памяти
2. Переменная BlockCurrent хранит адрес текущего свободного блока.
-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=
Следующую процедуру я называю
SeparateMemAdd -- (от сепаративная память) функция добавляет новый элемент, с указанным индексом.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--=-=-=

SeparateMemAdd              proc
comment /-----------------------------
Вход: index - индекс в списке.
Выход eax - errcode

Алгоритм:
1. Итак, мы имеем несколько блоков памяти.
Каждый блок содержит BLOCK_N_EL количество индексов.
Или элементов, что одно и тоже.

Чтобы добавить новый индекс, мы должны вычислить в каком блоке он находится.

После, если блок заполнен (ситуация = "вставка индекса в середину"), то мы запускаем функцию "разрежения".

При этом формат блоков следующий.

1. Начало блока определено заголовком из двух элементов (dword).
Первый элемент содержит число заполненных элементов, которые содержит блок.
А по сути, он содержит количество индексов, потому что это одно и тоже..

А второй -- индекс первого элемента блока.

2. Последний элемент блока (вопрос засыпка: а как вы думаете, почему не третий??? :)))))

Это указатель на сделующий блок.
Всё.....
Всё... и вы говорите сложно? :)))

--------------------------------------/
;; 1. Проверка на то, содержится ли индекс в текущем 
;; (последнем) блоке.
;; Чтобы это узнать, нужно просто сравнить
;; индекс с которого начинается блок, с текущим.
;; В eax - Индекс
          mov eax,esp__index
;; Получаем index с которого начинается блок.
;; +4*1 -- это смещение второго элемента
          mov edx,BlockCurrent
          sub eax,[edx+4*1]
;; Если индекс в этом блоке продолжаем..
          ja  short $_insert_index  
;; Иначе, наша жизнь усложняется...
;; Здесь я бы мог привести более сложные алгоритмы поиска...
;; Но боюсь вы будете вопить :)))
;; Короче просто вызываем функцию поиска блока с индексом.
;; Не забудьте, что параметр остался в стеке, и он 
;; послужит параметром и этой внутренней функции, которая 
;; кстати не должна освобождать стек!!!!!!!!!
          call GetBlockByIndex
;; Эта функция -- ваше дом задание :)))
$_insert_index:

;; Теперь, как вставить индекс в блок?
;; Во первых надо проверить а есть ли место.
          cmp [edx+0],BLOCK_N_EL
;; Если <=, продолжаем...
          jbe @F

;; Иначе, придётся делать разрежение.
;; Слово умное, а всё легко.
;; Что мы делаем? С того места, куда вставляется индекс, 
;; копируем кусок блока.

;; Находим следующий блок.
;; Эта функция возвращает указатель на следующий блок
;; Если блока нет, она его создаёт...

          push BlockCurrent
          call GetNextBlock
          mov esi,eax 
          sub eax,[edx+4*1] ;; eax = смещение в блоке
          mov ecx,
          sub 
;; Копируем данные начиная с
          lea eax,BlockCurrent+[eax*4]
          push eax   ;; Откуда, 
          push esi   ;; Куда
          push BLOCK_N_EL ;; Сколько
          call MemCopy
          mov BlockCurrent,esi

;; Ну и всё, вставляем индекс
@@:
;; Это я оставлю вам...
;;


SeparateMemAdd              proc

Этот код не работает!!!
В нём много не учтено.... и так далее.
Но я думаю, что довести его до ума будет не столь сложно, тем более, что основные этапы показаны...
И потом, разве интересно, когда всё делают за тебя :))))

Edmond: конечно попробую разобратся в твоем методе но мне всетаки кажется простой МУ [лучше] и проще. Хотя после того, что я прочитал на разных сайтах по поводу фрагментации памяти и т.п. надо еще подумать.

Всем кому интересно зачем нужны HeapAlloc, VirtualAlloc, GlobalAllooc и какое они имеют отношение к сишным операторам new и delete советую посетить www.helloworld.ru/texts/comp/lang/visualc/vc/THEORY/HTM/glava23. htm - там все на русском понятно расписано

А также
http://softs.h10.ru/literature.shtml?topic=visual&book=1&page=head18.htm
http://asterra.by.ru/library/richter4ru/head15.htm
http://firststeps.ru/mfc/winapi/
http://clubpro.spb.ru/cominside/virtual-memory-04.html

Это небольшая часть того, что можно найти набрав скажем в яндексе VirtualAlloc.

[ Edmond: Здесь мне совершенно не ясна политика Майкрософт ]

Да просто FormatMessage такая же древняя. Вот они друг друга и поддерживают.
За столько то лет API накопилась туча - хрен во всем этом разберешься ;-)

Edmond: Я не понял до конца формат блоков - там элементы по порядку содержатся ([1,2,3,4]-[5,6,7,8]-[9,10,x,x]) или вот так ([1,4,3,2]-[8,7,x,5]-[6,9,x,10]) или как ?

profi_r
Да, элементы в блоке идут по порядку!!!!!!
То есть, чтобы вставить элемент между, те нужно подвинуть.
Но выйгрышь именно в том, что подвигать нужно не много, ведь в блоке всего 256*4 байт

То есть в худшем случае ты подвинешь ~ (256-1)*4
Если не нравится можешь взять меньше, 64*4.
Вообще то есть действительно КУЛЬНЫЙ алгоритм....
Только я боюсь, если этот "сложный" тогда как тот назвать?
:)))


Смотри:
Скобки это блок.

([Число записей],[Номер индекса с которого начат блок],
[эл1],[эл2]......[элN],[указатель на следующий блок])

Пример:

([3],[5],[el1],[el2],[el3],....,[pointer->])

Это значит: В блоке 3 элемента, и первый элемент блока имеет индект = 5.
Усёк прелесть?

То есть блок не обязательно может быть заполнен до отказа.. И может быть следующий блок...
Например так:

([3],[5],[el1],[el2],[el3],....,[pointer->])
([3],[8],[el1],[el2],[el3],....,[pointer->])
([2],[11],[el1],[el2],....,[pointer->])

А?
Нравится? :)))

profi_r
Но в БД кстати алгоритмы сложнее на 10 порядков...
Правда они используют эти как базовые....
А дальше мама родная..
Там задача очень интересная....
И система оценки эффективности фрагментации, и что-то только нет....
Тема интересная..
Думаю, после того, как допишу "Управление памятью" расскажу о управлении структурами в БД..

profi_r

Да, и ещё вы ведь не думаете, что память нужно выделять у системы по блокам?
Нет, память выделяется большим куском и делится на блоки.

Вот смотрите Фигурные скобки память взятая у системы (пусть это 4k)

(---------) -- Это блок пустой
(*********) -- Это заполненый

-> указатель на какой блок



1. Состояние 1
Все блоки один за другим.

{
1.(*********)->2
2.(*********)->3
3.(*********)->4
4.(*********)->0
5.(---------)
6.(---------)
7.(---------)
8.(---------)
}

Пусть нужно добавить элемент в блок №3 в звёздочку №6
Смотрите что происходит...

Знак $ : новый элемент

{
1.(*********)->2
2.(*********)->3
3.(*****$---)->5
4.(*********)->0
5.(****-----)->4
6.(---------)
7.(---------)
8.(---------)
}

Edmond: Теперь все ясно - щас сяду за блокнот и напишу че нить.

Тока вот что делать с самими строчками - их длина нестабильна - может быть 1 байт или 200 байт и длина их изменятся должна. Както выделять скажем 80 байт для строчки в которой 1 байт не очень приятно. А если выделять память большим куском для нескольких строчек теряется возможность изменять их размер. Придется писать што-то вроде мэнаджера памяти и при изменении размера копировать строчку в другое место.

Я думаю всетаки выделять память под каждую строчку в отдельности и пусть с их Realloc-ом парится операционка. Тока вот гдето вычитал, что мол HeapAlloc медленнее, чем VirtualAlloc. В моей программе скорость перераспределения памяти не очень нужна но всеже хотелось бы побыстрее :))

profi_r
Да, перед вами Замечательная схема Разреженной + стратификационной памяти..
Вы что думаете он атолько для указателей подходит....???

Для строк даже легче..

Блоки остаются..
Но теперь в блоке хранятся данные переменного размера (строки)
Всё, нам легче, в первых четырёх байтах блока мы храним
сколько байт занято, и последине 4 байта. Всё!!!
Никаких индексов.
В принципе нового ничего нет.
Остаётся одна западлистая мелочь -- учёт того, что строки могут пересекать блоки :))))

Это и есть стратификационная память (то есть память которая разделена, но считается как бы непрерывной)

profi_r
что мол HeapAlloc медленнее, чем VirtualAlloc
Она как раз потому и медленне, что выполняет задачи менеджера.
С Виртуалом чуть легче

2 profi_r: У операционки далеко не такой продвинутый менеджер памяти, чтобы каждую строчку тебе выделять. Он забьётся и загнётся, сожрав при этом памяти на каждую строчку куда больше, чем 200 байт.

Думаешь, почему у менеджеров памяти всяких визуальных сей, стоит проверка на размер выделяемого блока? Большие они выделяют из системного хипа напрямую, а маленькие - через свой собственный механизм, который из системного хипа берёт память большими блоками и возится с выделением её "в розницу" сам.

Вообще, ты бы лучше прикинул, нужна ли тебе на самом деле очень гибкая и продвинутая система? Если это у тебя что-то вроде текстового редактора, то юзер будет периодически сохранять документ, а, может, и автосохранение будет. В это время можно полностью дефрагментировать внутренние структуры данных - ты же их для записи всё равно будешь приводить в порядок.

Возьми типовой размер строчки, и выделяй на каждую блок чуть больше такого размера. Будет меньше - про запас, будет больше - дели её пополам и рассовывай по двум блокам. Добавлять блоки можно для простоты только в конец - это позволит не заморачиваться на учёт освободившихся блоков, ну или список их вести. И так вот от сейва до сейва... ;) Если я не ошибся с твоей предметной областью, то это, пожалуй, самое простое решение. Практически то же самое, что порекомендовал Edmond, но блок почти никогда не будет заполнен до конца... Просто работа внутри одной строки существенно эффективнее, когда достаточно свободного места.

Сохранение с перестройкой внутренних структур можно инициировать самому, когда процент заполнения станет слишком маленьким. Беспорядок же вносится в результате работы пользователя - поэтому, если он привнёс столько беспорядка, значит он уже много сделал. Это даже можно выдавать за фичу. ;)

Ну а если тебе действительно нужна гибкость повыше и выделение памяти до байта, то, из простых и чугунных вариантов, можно посоветовать алгоритм с двумя списками - занятой и свободной памяти. Чтобы уменьшить влияние фрагментации, список свободных областей можно сделать кольцевым. А чтобы соседние освобождающиеся области сливались одну большую, можно в конце свободной области делать указатель на её начало. Вот, в принципе, и всё.

Просто, мне показалось, что ты всё слишком усложняешь. Неоправданное усложнение кода ведёт к увеличению числа ошибок. При программировании на ассемблере это особенно заметно. Другое дело, когда удачно выбраный алгоритм существенно оптимизирует работу. Тогда вариантов нет - надо делать. ;) А экономия полумегабайта памяти, приводящая к перетасовке внутренних структур на каждое нажатие кнопки юзером - это не экономия.

bsl_zcs
Добавлять блоки можно для простоты только в конец - это позволит не заморачиваться на учёт освободившихся блоков, ну или список их вести.
Вообще говоря вариантов -- ТМА. То есть вариаций.
Но методика одна.

Я различаю нескольо задачь в Управлении Памятью и структурами (первые из них):

1. Задача локальной адаптации управления в зависимости от условий
2. Задача размещения...
И так далее

Вот номер 1 -- это как раз, то.

Например, если тебе известно, что строки обычно (в 90%) не больше 256 байт. То тогда, ты и в самом деле можешь спокойно выделять блоками по 256

А вот кстати отдельной структуры по учёту блоков не требуется. :)))
Она уже есть...
Именно поэтому первые четыре байта блока нужны.
Если они ноль -- блок свободен.

Можно выкинуть этот указатель -- и мы получим чистую стратификационную память!!!
Правда там, алгоритмы вставки и модификации чуть сложнее.
Но в принципе -- это проще, чем разреженные блоки памяти.

Короче, в зависимости от ситуации, алгоритм можно подкрутить.