Доброе время суток. Есть сегмент памяти содержащий различные по размеру блоки данных, которые динамично удаляются или добавляются программой. При удалении блока смещаю вверх все нижестоящие блоки, чтобы освободить память перекрыв образовавшийся дыру. Добавляю блок снизу. И все работало быстро, пока не дали задание увеличить обьем перерабатываемой информации в несколько раз. Программа стала заметно тормозить, причем явно на процессе удаления/добавления блоков. Как можно оптимизировать процесс удаления/добавления блоков?
Использовать таблицу указателей на блоки и свободные участки (оствшиеся после удаления блоков), добавлять новые блоки в свободные участки или снизу, выполнять упорядочивание отдельным потоком на другом процессоре. Возможно есть лучшее решение и использование драйвера.
Пробован я индексировать: для сохранения информации о каждом блоке требуется 9 байт в32х (dw адрес начала блока+ dw размер блока+db состояние блока(*свободен/несвободен))и 17 в 64х. При среднем размере блока в 250 байт (хотя есть и 300мб) и кол-ве блоков в 3 миллиона куча памяти уйдет только лишь на хранении информации о блоках (25 гб для 32х). А вот про драйвер можно поподробнее?
Как я понял тебе надо написать аллокатор памяти. Значит первое что тут можно посоветовать - не изобретай велосипед! Вначале ознакомся с существующеми реализациями, а потом уже... Возьми готовую и не трать своё время. Хороший аллокатор достаточно сложен - простая карта памяти тут не проканает. По поводу карты памяти: 1) Память разбивается на равные блоки в N байт. 2) Каждый блок в N байт в карте кодируется 1 битом (0 -свободен, 1 - занят) 3) итого если размер блока в 64 байта например, то для работы с кучей в 50 Mb на карту уйдёт всего 200 Кб памяти. Понятно что если речь идёт о нескольких гигабайтах, то размер карты будет больше... Примерно поэтому и одной карты недостаточно. *Очевидно, что адрес блока определяется порядковым номером в карте.
При фиксированном размере блока вопросов нет, но при неизвестной длине данных надо хранить их размер( для правильного подсчета контрольной CRC32) аллокатор памяти- вроде слышал щас погуглю
При не фиксированной длине выделяемых кусков памяти, эти куски занимают несколько(возможно дробное количество) блоков и длинна куска хранится вместе с указателем на этот кусок. Т.е. Выделение: memory_slice = alloc(slice_size); Освобождение: free(memory_slice,slice_size); А остаток блока, т.е. ту часть которую занимает, но реально не использует кусок, списывается на накладные расходы) И ещё раз говорю, в общем виде проблема "аллокатора памяти" очень обширна и сложна.
а обязательно перемещать старые блоки наверх? сам посуди, больше всего времени занимает именно копирование. Есть ли такая острая необходимость в этом? Я в свое время здорово сэкономил ресурсы, отказавшись от излишнего копирования данных
Sercher Кто ж так делает ?! Какой смысл хранить кучу инфы о свободных блоках в каких-то внешних структурах, если ее можно хранить в самих этих блоках ! Стандартный подход - заводится таблица указателей на св.блоки определенных размеров, например с шагом 8 байт. Такая таблица на 1024 эл-та будет иметь размер всего 4К (или 8К в x64) и хранить инфу о всех свободных блоках размером до 8К. В элементе таблицы хранится только указатель на последний свободный блок данного размера, а остальные блоки увязываются в двухсвязный список и указатели Next\Prev хранятся в самом свободном блоке. Блоки большого размера используются реже и поэтому обычно хранятся в отдельном двухсвязном списке без градации по размерам
Блоки оданакового и маленького размера групировать в секции, и обращатся по вычисленому смещению внутри секции(секция тагже является одним из блоков). Тагже вместо указателей можно использовать двухсвязный список(если скорость доступа не критична(с кешированием обращений)).
