Attn: Please route this bug to the Windows SDK team
Summary: The performance of Heap32Next function (http://msdn.microsoft.com/en-us/library/ms683440%28VS.85%29.aspx) in Windows 7 is linear, rather than O(1), with respect to the total number of heap entries in all heap lists.
Graphs of the performance can be found at http://thenewjamesbaker.blogspot.com/2009/11/performance-of-heap32next-on-64-bit.html
Problem is exhibited on
Windows 7 Ultimate 32-bit and 64-bit
Problem is not exhibited on
Windows Server 2003
Windows Vista Ultimate
Windows Server 2008
Performance is the same when walking a small heap (15 entries) or large heap (2 million entries) - the only thing that counts is the total number of entries in all heaps.
One sampled stack during execution:
ntdll.dll!_RtlpWalkHeap@12() + 0x3f bytes
ntdll.dll!_RtlpQueryExtendedInformationHeap@16() + 0x4f5 bytes
ntdll.dll!_RtlpQueryExtendedInformationAllHeaps@12() + 0xe5 bytes
ntdll.dll!_RtlpQueryExtendedHeapInformation@12() + 0xe7 bytes
ntdll.dll!_RtlQueryHeapInformation@20() + 0x1bc76 bytes
ntdll.dll!_RtlQueryProcessHeapInformation@4() + 0x288 bytes
ntdll.dll!_RtlQueryProcessDebugInformation@12() + 0x11492 bytes
kernel32.dll!_Heap32Next@4() + 0x4d bytes
randwin.exe!RAND_poll() Line 231 + 0x9 bytes C++
This stack trace, with calls to functions like "QueryProcessDebugInformation" and "QueryExtendedInformationAllHeaps", makes me fear that some debugging code was somehow left in production?