[Bug 5709] New: ntdll: Heap implementation has a performance bottleneck

[Wine Bugs]

http://bugs.winehq.org/show_bug.cgi?id=5709

Summary: ntdll: Heap implementation has a performance bottleneck
           Product: Wine
           Version: CVS
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: wine-kernel
        AssignedTo: [e-mail]
        ReportedBy: [e-mail]

Wine's heap implementation (HeapAlloc(), HeapFree(), etc. in dlls/ntdll/heap.c)
is very slow if many small memory blocks are allocated and freed.

I have found this problem with HomeSite 5.2. It's an HTML editor that contains a
syntax checker. The syntax checker needs 120 seconds to load on Wine. Most users
will think that the program has crashed. With the native MSVCRT.DLL (which
contains a custom heap implementation), it takes only 2 seconds. Wine's built-in
MSVCRT.DLL just forwards the C heap functions to the OS heap functions, which
have serious performance problems.

A similar problem has been reported on the mailing list:
http://www.winehq.org/pipermail/wine-devel/2005-February/034095.html

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.

I have created a trace of HomeSite's memory requests and written a program that
replays the trace. The program prints how long it takes to replay the trace. My
measurements:

Wine: 125.0 seconds (HeapAlloc and built-in malloc), 4.5 seconds (native malloc
of MSVCRT.DLL)
Windows 95 (on VMware): 55.0 seconds (HeapAlloc), 4.0 seconds (malloc)
Windows NT 4.0 SP6 (on VMware): 3.6 seconds (HeapAlloc and malloc)

So Wine's HeapAlloc is much too slow. Windows NT 4.0's malloc just calls
HeapAlloc (like Wine).

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