Why does the Heap32Next () function work so slowly on Windows 7?
If you are doing system programming under Windows, you might notice that the very useful functions of Heap32First / Heap32Next and others from the same family began to work much slower since Windows 7. What happened to them?
Let's go back to far 1992. Developed by Windows 3.1. One of the new components in it was ToolHelp. He allowed a little digging in the guts of the OS kernel. For us, the most interesting features are those that allow you to view data in a heap. Since Windows 3.1 used cooperative multitasking , calling such functions one could be sure that the contents of the heap would not change between the HeapFirst and HeapNext calls, because the OS did not have the right to interrupt the process and switch the context to the other. Here were the times!
Separately, it should be noted that ToolHelp was not a component of the OS kernel. He screwed the side. The reason was that the development of ToolHelp ended already closer to the release of Windows 3.1 and the kernel development team did not want to destabilize it at such a late stage. So everything that ToolHelp does, it does "outside", and this imposes some restrictions.
Widows 95 added 32-bit versions of the same functions to ToolHelp.
')
So what am I talking about ... oh yeah, Heap32Next.
In the 32-bit version of ToolHelp, you can view data on the heap using Heap32First and Heap32Next function calls. The implementation of these functions in Windows 95 worked as follows: a call to Heap32First allocated a certain amount of memory and saved its size in the HEAPENTRY32.dwResvd field. Each subsequent call to Heap32Next used this value to read the next block of memory. The last call to Heap32Next (the one that returned FALSE) freed the allocated memory. You have already seen the problem here, right? If for some reason we want to finish viewing the memory before reaching the end of the heap (the user canceled the action, the timeout expired, we found what we were looking for), then we immediately get a memory leak. Unlike other similar sets of WinAPI functions (like FindFirstFile / FindNextFile / FindClose), here we have no function like Heap32Close. The only way to free up memory is to get to the end with Heap32Next. Also, Windows 95 has changed the multitasking model. It became possible that between two consecutive calls to Heap32Next, the data in the heap was changed by another process. However, this situation was not handled by the functions of the ToolHelp component.
Both of the above problems look very serious, but, according to the creators of these functions, they were intended only for diagnostic purposes. The very name of the ToolHelp component should have prompted the developer to think that it can be used in development and debugging, but not in the end product for users.
Everything changed when the Windows transition to the NT kernel. The developers of Windows NT paid significant attention to the stability of the system and did not want to have a memory leak in the design, even if auxiliary functions. Since there was no guarantee that the programmer would always reach the end of the heap using Heap32Next, as well as there was no way to allow him to complete the pass earlier, it was decided to free all allocated memory before returning from Heap32First and Heap32Next. When the application called Heap32First, this function took a heap snapshot, returned its first block, and released the snapshot. When the application called Heap32Next, a heap snapshot was taken again, the second block was returned and the snapshot was released again. And so on, you get the idea.
As a result of the implementation of this algorithm, O (n²) operations were required to view n memory blocks.
So why did it become slower in Windows 7?
Prior to Windows 7, the above snapshot of the memory area was taken into a fixed-size buffer. It contained information about a quarter of a million blocks of memory on the heap. With such an implementation, a hard limit was obtained by itself for the worst case of calling the Heap32First / Heap32Next functions. In Windows 7, this buffer was increased, because there were complaints from developers of some diagnostic utilities that they rest on its size. The developers of the Windows kernel decided that it was better to let the functions run slowly and correctly than quickly and erroneously. Thus, O (n²) was added to the not very beautiful complexity of O (n²) and a large constant due to the increased buffer size.
This sad story about functionality, which was designed as an auxiliary in times of cooperative multitasking, and then failed to upgrade sufficiently well in future versions of the OS. At the moment, the Heap32First / Heap32Next functions live in the Windows kernel under the slogan “a family has a black sheep.” No one likes them, but you just can't take something from the kernel and throw it away: good backward compatibility is what Windows is on.
But, fortunately, you can always add something new that works more correctly. In this case, the HeapWalk function has become such a “new” one . It has O (n) complexity, but is limited by the ability to read only the memory of the current process. If you want to read the memory of other processes - you have no alternatives other than Heap32First / Heap32Next. You can be comforted by the fact that doing something like this is still most often needed for diagnostic purposes, on the developers' machines. And here correctness is more important than performance.
Let's go back to far 1992. Developed by Windows 3.1. One of the new components in it was ToolHelp. He allowed a little digging in the guts of the OS kernel. For us, the most interesting features are those that allow you to view data in a heap. Since Windows 3.1 used cooperative multitasking , calling such functions one could be sure that the contents of the heap would not change between the HeapFirst and HeapNext calls, because the OS did not have the right to interrupt the process and switch the context to the other. Here were the times!
Separately, it should be noted that ToolHelp was not a component of the OS kernel. He screwed the side. The reason was that the development of ToolHelp ended already closer to the release of Windows 3.1 and the kernel development team did not want to destabilize it at such a late stage. So everything that ToolHelp does, it does "outside", and this imposes some restrictions.
Widows 95 added 32-bit versions of the same functions to ToolHelp.
')
So what am I talking about ... oh yeah, Heap32Next.
In the 32-bit version of ToolHelp, you can view data on the heap using Heap32First and Heap32Next function calls. The implementation of these functions in Windows 95 worked as follows: a call to Heap32First allocated a certain amount of memory and saved its size in the HEAPENTRY32.dwResvd field. Each subsequent call to Heap32Next used this value to read the next block of memory. The last call to Heap32Next (the one that returned FALSE) freed the allocated memory. You have already seen the problem here, right? If for some reason we want to finish viewing the memory before reaching the end of the heap (the user canceled the action, the timeout expired, we found what we were looking for), then we immediately get a memory leak. Unlike other similar sets of WinAPI functions (like FindFirstFile / FindNextFile / FindClose), here we have no function like Heap32Close. The only way to free up memory is to get to the end with Heap32Next. Also, Windows 95 has changed the multitasking model. It became possible that between two consecutive calls to Heap32Next, the data in the heap was changed by another process. However, this situation was not handled by the functions of the ToolHelp component.
Both of the above problems look very serious, but, according to the creators of these functions, they were intended only for diagnostic purposes. The very name of the ToolHelp component should have prompted the developer to think that it can be used in development and debugging, but not in the end product for users.
Everything changed when the Windows transition to the NT kernel. The developers of Windows NT paid significant attention to the stability of the system and did not want to have a memory leak in the design, even if auxiliary functions. Since there was no guarantee that the programmer would always reach the end of the heap using Heap32Next, as well as there was no way to allow him to complete the pass earlier, it was decided to free all allocated memory before returning from Heap32First and Heap32Next. When the application called Heap32First, this function took a heap snapshot, returned its first block, and released the snapshot. When the application called Heap32Next, a heap snapshot was taken again, the second block was returned and the snapshot was released again. And so on, you get the idea.
As a result of the implementation of this algorithm, O (n²) operations were required to view n memory blocks.
So why did it become slower in Windows 7?
Prior to Windows 7, the above snapshot of the memory area was taken into a fixed-size buffer. It contained information about a quarter of a million blocks of memory on the heap. With such an implementation, a hard limit was obtained by itself for the worst case of calling the Heap32First / Heap32Next functions. In Windows 7, this buffer was increased, because there were complaints from developers of some diagnostic utilities that they rest on its size. The developers of the Windows kernel decided that it was better to let the functions run slowly and correctly than quickly and erroneously. Thus, O (n²) was added to the not very beautiful complexity of O (n²) and a large constant due to the increased buffer size.
This sad story about functionality, which was designed as an auxiliary in times of cooperative multitasking, and then failed to upgrade sufficiently well in future versions of the OS. At the moment, the Heap32First / Heap32Next functions live in the Windows kernel under the slogan “a family has a black sheep.” No one likes them, but you just can't take something from the kernel and throw it away: good backward compatibility is what Windows is on.
But, fortunately, you can always add something new that works more correctly. In this case, the HeapWalk function has become such a “new” one . It has O (n) complexity, but is limited by the ability to read only the memory of the current process. If you want to read the memory of other processes - you have no alternatives other than Heap32First / Heap32Next. You can be comforted by the fact that doing something like this is still most often needed for diagnostic purposes, on the developers' machines. And here correctness is more important than performance.
Source: https://habr.com/ru/post/352056/
All Articles