ntdll: Heap implementation has a performance bottleneck

[Michael Kaufmann]

Hi,

I have discovered that Wine's heap implementation (HeapAlloc(), 
HeapFree(), etc. in dlls/ntdll/heap.c) is very slow if many small memory 
blocks are allocated and freed. Somebody has reported this before: 
http://www.winehq.org/pipermail/wine-devel/2005-February/034095.html

HomeSite's syntax checker needs 120 seconds to load on Wine because of 
Wine's poor heap implementation. Most users will think that the program 
has crashed. I have created a trace of HomeSite's memory requests and a 
program to replay them. For details and performance measurements, please 
look at bug 5709 ( http://bugs.winehq.org/show_bug.cgi?id=5709 ).

According to the source code, Wine's heap implementation is described in 
the book "Windows 95 System Programming Secrets". This implementation is 
inefficient: KB225099 ( http://support.microsoft.com/kb/225099/en-us ) 
says that the heap implementation of Windows NT 4.0 SP4 and 2000 is much 
better than the heap implementation of Windows 95.

Does anybody know some details about the heap implementation of Windows 
NT/2000/XP ?

Regards,
Michael

[Frank Richter]

On 18.07.2006 23:21, Michael Kaufmann wrote:
> Hi,
>
> I have discovered that Wine's heap implementation (HeapAlloc(),
> HeapFree(), etc. in dlls/ntdll/heap.c) is very slow if many small memory
> blocks are allocated and freed. Somebody has reported this before:
> http://www.winehq.org/pipermail/wine-devel/2005-February/034095.html

On the topic of memory allocation speed: even the NT allocator is
painstakingly slow, see some charts at:
http://www.nedprod.com/programs/portable/nedmalloc/index.html .

I don't know, would it be technically possible to back heap allocation
by one of these alternative memory allocators mentioned on that page? If
so, you could get a "free" performance advantage over native by simply
using a better allocator (for some programs, at least).

-f.r.

[Alexandre Julliard]

Michael Kaufmann  writes:
> HomeSite's syntax checker needs 120 seconds to load on Wine because of
> Wine's poor heap implementation. Most users will think that the
> program has crashed. I have created a trace of HomeSite's memory
> requests and a program to replay them. For details and performance
> measurements, please look at bug 5709 (
> http://bugs.winehq.org/show_bug.cgi?id=5709 ).

A quick fix is to add more free list entries, and in particular an
entry for very small blocks since your test case seems to create a lot
of them. Something like this seems to work well:

diff --git a/dlls/ntdll/heap.c b/dlls/ntdll/heap.c
index 68a234b..b62c4da 100644
--- a/dlls/ntdll/heap.c
+++ b/dlls/ntdll/heap.c
@@ -88,13 +88,12 @@ #define HEAP_MIN_DATA_SIZE    16
 /* minimum size that must remain to shrink an allocated block */
 #define HEAP_MIN_SHRINK_SIZE  (HEAP_MIN_DATA_SIZE+sizeof(ARENA_FREE))

-#define HEAP_NB_FREE_LISTS   4   /* Number of free lists */
-
 /* Max size of the blocks on the free lists */
-static const DWORD HEAP_freeListSizes[HEAP_NB_FREE_LISTS] =
+static const DWORD HEAP_freeListSizes[] =
 {
-    0x20, 0x80, 0x200, ~0UL
+    0x10, 0x20, 0x30, 0x40, 0x60, 0x80, 0x100, 0x200, 0x400, 0x1000, ~0UL
 };
+#define HEAP_NB_FREE_LISTS  (sizeof(HEAP_freeListSizes)/sizeof(HEAP_freeListSizes[0]))

typedef struct
 {

[Michael Kaufmann]

Alexandre Julliard wrote:
> A quick fix is to add more free list entries, and in particular an
> entry for very small blocks since your test case seems to create a lot
> of them. Something like this seems to work well:

Thank you Alexandre, this patch speeds up HomeSite a lot. It's still not 
as fast as in Windows, but it's OK.

Frank Richter wrote:
> On the topic of memory allocation speed: even the NT allocator is
> painstakingly slow, see some charts at:
> http://www.nedprod.com/programs/portable/nedmalloc/index.html .

Thanks for the link!
> I don't know, would it be technically possible to back heap allocation
> by one of these alternative memory allocators mentioned on that page? If
> so, you could get a "free" performance advantage over native by simply
> using a better allocator (for some programs, at least).

A problem that Wine will be facing is the need to support the HeapWalk 
function. Applications should not use it, because the speed of the heap 
implementation degrades (mentioned on MSDN), but maybe there are 
applications that need it.

Regards,
Michael