[Перевод] Почему функция Heap32Next() работает так медленно на Windows 7?
Если вы занимаетесь системным программированием под Windows, то могли бы заметить, что весьма полезные функции Heap32First/Heap32Next и другие из того же семейства стали работать существенно медленнее начиная с Windows 7. Что же с ними случилось?
Давайте перенесёмся в далёкий 1992 год. Разрабатывается Windows 3.1. Одним из новых компонентов в ней стал ToolHelp. Он позволил немного покопаться во внутренностях ядра ОС. Для нас в нём наиболее интересны функции, позволяющие просматривать данные в куче (heap). Поскольку Windows 3.1 использовала кооперативную многозадачность, вызывая подобные функции можно было быть уверенным в том, что содержимое кучи не изменится между вызовами HeapFirst и HeapNext, ведь у ОС не было права прервать выполнение процесса и переключить контекс на выполнение другого. Вот были времена!
Отдельно следует отметить, что ToolHelp не был компонентом ядра ОС. Его прикрутили сбоку. Причиной было то, что разработка ToolHelp закончилась уже ближе к релизу Windows 3.1 и команда разработки ядра не хотела на столь позднем этапе дестабилизировать его. Так что всё, что делает ToolHelp, он делает «снаружи», а это накладывает некоторые ограничения.
Widows 95 добавил в ToolHelp 32-битные версии тех же функций.
Так, о чём это я… Ах да, Heap32Next.
В 32-битной версии ToolHelp вы можете просматривать данные в куче с помощью вызовов функций Heap32First и Heap32Next. Реализация этих функций в Windows 95 работала следующим образом: вызов Heap32First выделял некоторое количество памяти и сохранял его размер в поле HEAPENTRY32.dwResvd. Каждый следующий вызов Heap32Next использовал это значение для чтения следующего блока памяти. Последний вызов Heap32Next (тот, который возвращал FALSE) освобождал выделенную память. Вы уже увидели здесь проблему, правда? Если по каким-то причинам мы хотим закончить просмотр памяти не дойдя до конца кучи (пользователь отменил действие, закончился таймаут, мы нашли то, что искали), то мы сразу получаем утечку памяти. В отличии от других аналогичных наборов функций WinAPI (вроде FindFirstFile/FindNextFile/FindClose) здесь у нас нет никакой функции вроде Heap32Close. Единственный способ освободить память — дойти с помощью Heap32Next до конца. Также Windows 95 изменилась модель многозадачности. Стала возможной ситуация, когда между двумя последовательными вызовами Heap32Next данные в куче были изменены другим процессом. Однако, эта ситуация никак не обрабатывалась фукциями компонента ToolHelp.
Обе вышеописанные проблемы выглядят очень серьёзными, но, по мнению создателей данных функций, они предназначались лишь для диагностических целей. Само название компонента ToolHelp должно было натолкнуть разработчика на мысль, что его можно использовать при разработке и отладке, но никак не в конечном продукте для пользователей.
Всё изменилось при переходе Windows на ядро NT. Разработчики Windows NT уделяли существенное внимание стабильности системы и никак не хотели иметь утечку памяти в дизайне пусть даже вспомогательных функций. Поскольку не было никакой гарантии, что программист всегда будет доходить с помощью Heap32Next до конца кучи, равно как и не было никакого способа дать ему возможность завершить проход раньше, то было решено освобождать всю выделенную память перед возвратом из Heap32First и Heap32Next. Когда приложение вызывало Heap32First, эта функция делала снимок кучи, возвращала первый её блок и освобождала снимок. Когда приложение вызывало Heap32Next, снова делался снимок кучи, возвращался второй блок и снимок снова освобождался. И так далее, вы уловили идею.
В результате реализации данного алгоритма для просмотра n блоков памяти требовалось O (n²) операций.
Так почему же это стало работать медленнее в Windows 7?
До Windows 7 вышеупомянутый снимок области памяти делался в буфер фиксированного размера. Он содержал информацию около четверти миллиона блоков памяти в куче. При такой реализации сам собой получался жесткий лимит для худшего случая вызова функций Heap32First/Heap32Next. В Windows 7 этот буфер был увеличен, поскольку были жалобы разработчиков некоторых диагностических утилит на то, что они упираются в его размер. Разработчики ядра Windows решили, что лучше пусть функции работают медленно и правильно, чем быстро и ошибочно. Таким образом к и так не сильно красивой сложности O (n²) добавилась ещё и большая константа из-за возросшего размера буфера.
Эта грустная история о функциональности, которая проектировалась в качестве вспомогательной во времена кооперативной многозадачности, а затем не смогла достаточно качественно проапгрейдится в следующих версиях ОС. В данный момент функции Heap32First/Heap32Next живут в ядре Windows под лозунгом «в семье не без урода». Никто их не любит, но просто так взять и выбросить что-то из ядра нельзя: хорошая обратная совместимость — это то, на чём стоит Windows.
Но, к счастью, всегда можно добавить что-то новое, работающее более корректно. Таким «новым» в данном случае стала функция HeapWalk. Она имеет сложность O (n), но при этом ограничена возможностью читать память лишь текущего процесса. Если вы хотите читать память других процессов — у вас нет альтернатив кроме Heap32First/Heap32Next. Утешаться можно тем, что делать что-то подобное всё-таки чаще всего нужно в диагностических целях, на машинах разработчиков. И здесь корректность всё же важнее производительности.
