использую в своей программе сабж. элемент списка состоит из двух двойных слов: содержимое и указатель на следующий элемент. элементы создаются функцией GlobalAlloc. по окончании работы программы список бросается в файл, а при старте восстанавливается. вот при восстановлении большого списка из файла (сотни тыс. элементов) процесс этот растягивается на оччень продолжительное время... можно ли както оптимизировать этот процесс?
Вместо GlobalAlloc использовать HeapAlloc. Ещё быстрее - для каждого списка использовать отдельный Heap объект и когда надо освободить память не надо вызывать HeapFree на каждый елемент списка а просто удалить весь Heap объект через HeapDestroy.
AsmGuru62 HeapAlloc скорость увеличил, но всеже сотни тысяч вызовов видимо не могут пройти быстро использовать свой хип для каждого списка не удобно - размер списка заранее не известен. напрашивается решение - выделять области к примеру по 4к по мере заполнения... это сильно усложнит функции добавления и удаления элементов, но другого выходя я не вижу
Сохранять и читать содержимое всех элементов одним сплошным куском. В качестве указателя на элемент использовать не абсолютный адрес следующего элемента списка, а смещение от начала большого куска, который содержит все данные. Т.е. указателем на следующий элемент будет не его абсолютный адрес, а nextEntryOffset И можно будет всего один раз использовать VirtualAlloc/ReadFile
Sickle Скорость проверялась в DEBUG или в RELEASE Build? Heap_xxx API очень медленный в DEBUG. Я тестировал свой менеджер против Heap_xxx API - API аллоцирует пол-миллиона блоков в секунду в RELEASE. Не хило однако! Мне удалось побить этот результат на сотню миллисекунд, не более - и только за счёт того, что мой менеджер памяти не годится для multi-threaded access. Кстати, почему играет роль неизвестность размера списка? ведь HeapAlloc() безразмерный. Ну начни его с 2-х страниц (8Кб), а там, если надо - Windows поддаст больше - пока хватит памяти.
хм.. я тестировал в DEBUG билде. полмилиона говоришь... надо проверить, такая скорость меня вполне устроит!
могу для masm32 кинуть исходник, на моем 256 мГц 100.000.000 dword'ов пушит секунды за 4. Размер указывать требуется. Тестировал вот так: newobject ASet mov ecx,10000000 l1: method esi,ASet,aPush,ecx loop l1
Sickle А в чем вообще смысл использования односвязного списка большого размера, да еще загружаемого из файла. Минусы очевидны: 1) неэффективное использование памяти - на 4 байта "содержимого" приходится еще 12 байт обслуги (4 на next + 8 заголовок блока кучи), 2) лишние тормоза как при загрузке, так и при работе со списком. А в чем плюсы ? Не проще ли использовать массив с VirtualAlloc'ом или нужна вставка элементов в середину списка ? Резервирование диапазона адресов в несколько мегабайт "каши не просит", т.е. памяти не занимает и на фоне доступных 2Гб это капля в море. А насчет "сильно усложнит функции добавления и удаления элементов" это большое преувеличение если элементы добавляются только в конец или\и в начало списка, по крайней мере это будет заметно быстрее и намного экономнее HeapAlloc Если все же нужен список, то лучше использовать вариант со смещениями, предлагаемый cresta
вобщем, удалось добиться приличной скорости. дело в том, что при загрузке таблицы из файла я использовал функцию добавления элемента, в которой происходит контроль на дублирующиеся элементы (если такое значение в списке есть, то оно не добавляется). естественно, это требует просмотра всего списка. сделал отдельную функцию добавления без контроля - скорость вполне устраивает. пришлось дополнительно хранить указатель на последний элементы списка, но это ерунда. leo возможно я приду к такой организации, действительно, список довольно прожерливая структура...
