Почему функция Heap32Next() работает так медленно на Windows 7?

https://blogs.msdn.microsoft.com/oldnewthing/20120323-00/?p=8023
  • Перевод
Если вы занимаетесь системным программированием под 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. Утешаться можно тем, что делать что-то подобное всё-таки чаще всего нужно в диагностических целях, на машинах разработчиков. И здесь корректность всё же важнее производительности.

Инфопульс Украина

175,00

Creating Value, Delivering Excellence

Поделиться публикацией
Комментарии 12
    +2
    Какой-то адовый костыль
      0
      Создаётся ощущение, что адовый костыль — вся Windows (и вообще вся софто-индустрия).
        0
        Если бы только софто-индустрия…

        Простейший пример: современные светодиодные лампочки было бы гораздо проще и их было бы удобнее использовать, если бы их не нужно было бы вкручивать в пресловутый E27.

        Это то, что я называю «всюду лошади»… Причём тут лошади? Ну уж байку-то про лошадей и шаттл все слышали, я надеюсь (она, кстати, и к современному Falcon 9 относится, хотя там размеры чуток другие, так как его по шоссе возят).

        Вся современная цивилизация — это костыль на костыле… и это никого не удивляет… кроме софтописателей. Просто многие из них ещё помнят относительно недавние времена, когда всё было новое, делалось с нуля и своих «лошадей» ещё не существовало. Но это, на самом деле, было довольно давно — современным поколениям представить что когда-то можно было творить свободно… что всё, вот совсем всё можно было сделать под себя… довольно-таки сложно (а времена когда под себя можно сделать и железо тоже помнят разве что старожилы вроде пресловутого Бабаяна… им ещё тяжелее, чем нам в современном мире).
          0
          В софтописании как раз костыли легче всего и дешевле исправлять. В отличии от, например, строений.
            0
            Теоретически да. На практике сталкиваешься с поддержкой легаси, в итоге там, где в строительстве здание сносят и строят заново, в софтописательстве накручивают костыли.
              0
              Но через сколько снесут здание или массив сданий, а через сколько перепишут код.
              0
              Ага, конечно. Вот как раз статья в тему у нас. Предлагайте «лёгкий и простой способ» исправления Heap32Next, я вас слушаю…
        +1
        Можно заинжектиться в другой процесс и хипволкать в своё удовольствие.
          0
          обычно куча имеет список свободных блоков, оптимизированный тем или иным способом, а занятые вычисляются. Неужели было так сложно найти свободный блок А с максимальным адресом меньше адреса текущего блока (или начало кучи), свободный блок Б с минимальным адресом большим текущего блока (или конец кучи) и итерировать только диапазон занятых блоков внутри между А и Б? В нем можно легко найти текущий блок и от него перейти к следующему.

            0
            Этот диапазон может измениться во время работы программы, ОС то теперь многозадачные и могут работать на многоядерных ЦП.
              0
              Если они могут измениться во время поиска, то и тем более во время создания снапшота, всё изменится.
              Если они умеют блокировать изменения на время создания снапшота, что мешает их же блокировать на время поиска?
                –1
                Если они умеют блокировать изменения на время создания снапшота, что мешает их же блокировать на время поиска?
                Наличие мозгов?

                Снапшот делает ядро операционной системы, ускорить или, главное, замедлить этот процесс программа пользователя никак не в силах.

                Поиск же выполняет программа пользователя и у нас даже нет никакой возможности узнать о том, что программа уже всё нашла и больши ничего искать не будет.

                Вы статью-то читали или как? Это даже не «сейчас, сынок, только дискетку доформатирую», а чистая возможность любой программе поставить всю систему «колом».

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое