Быстрый доступ к (отсортированному) TList

Question

Мой проект (работающий на Delphi 6!) Требует список распределений памяти (TMemoryAllocation), который я храню в объекте, который также содержит информацию о размере выделения (FSize) и о том, используется ли выделение или свободно (FUsed), Я использую это, в основном, как GarbageCollector и как способ постоянно использовать свое приложение для выделения / освобождения памяти (и для этого требуется множество выделений / освобождений).

Всякий раз, когда моему проекту требуется выделение, он просматривает список, чтобы найти свободное выделение, которое соответствует требуемому размеру. Для этого я использую простой цикл for:

for I := 0 to FAllocationList.Count - 1 do
begin
  if MemoryAllocation.FUsed and (MemoryAllocation.FSize = Size) then
...

Чем дольше мое приложение запускает, этот список увеличивается до нескольких тысяч элементов, и он значительно замедляется, поскольку я запускаю его очень часто (несколько раз в секунду).

Я пытаюсь найти способ ускорить это решение. Я думал о сортировке TList по размеру выделения. Если я сделаю это, я должен использовать какой-то разумный способ доступа к списку для нужного размера при каждом вызове. Есть ли какой-нибудь простой способ сделать это?

Другой способ, о котором я думал, - это иметь два списка TL. Один для Неиспользованного и один из Используемых распределений. Это означало бы, что мне придется извлекать TList.Items из одного списка и все время добавлять в другой. И я все еще должен был бы использовать цикл for, чтобы пройти (теперь) меньший список. Будет ли это правильный путь?

Другие предложения также приветствуются!

Answer 1

У вас есть несколько возможностей:

• Конечно, используйте проверенный диспетчер памяти как FastMM4 или некоторые другие, предназначенные для лучшего масштабирования для многопоточных приложений;
• Изобретай колесо.

Если ваше приложение очень чувствительно к распределению памяти, возможно, есть некоторые отзывы об изобретении колеса:

• Используйте размер блоков, например, на 16-ти кратное число байтов, затем сохраняйте один список на размер блока, чтобы вы могли быстро найти "хорошее" семейство блоков, и вам не нужно будет хранить каждый отдельный размер блока в памяти (если он свой в список байтов, это блоки 32 байта);
• Если вам нужно перераспределение, попытайтесь угадать лучший увеличивающийся фактор для уменьшения объема памяти;
• Сортируйте ваши блоки по размеру, затем используйте бинарный поиск, который будет намного быстрее, чем обычный цикл i:= 0 to Count-1;
• Сохраняйте блок удаленных элементов в списке, в котором можно искать, когда вам нужен новый элемент (чтобы вам не пришлось удалять элемент, просто пометьте его как свободный - это сильно ускорит, если список огромен);
• Вместо использования списка (который будет иметь некоторые проблемы со скоростью при удалении или вставке отсортированных элементов с огромным количеством элементов) используйте связанный список как для элементов, так и для освобожденных элементов.

Это определенно не так просто, так что вы можете захотеть взглянуть на некоторый существующий код раньше или просто положиться на существующие библиотеки. Я думаю, вам не нужно кодировать это распределение памяти в вашем приложении, если только FastMM4 недостаточно быстр для вас, в чем я очень сомневаюсь, потому что это отличный кусок кода!