https://bugs.winehq.org/show_bug.cgi?id=43224
Bug ID: 43224 Summary: Freelist scan can result in O(n) time when allocating Product: Wine Version: unspecified Hardware: x86 OS: Linux Status: UNCONFIRMED Severity: normal Priority: P2 Component: ntdll Assignee: wine-bugs@winehq.org Reporter: ranma42@gmail.com Distribution: ---
Created attachment 58517 --> https://bugs.winehq.org/attachment.cgi?id=58517 Micro-benchmark that shows the degenerate behaviour
The heap implementation in ntdll can be very inefficient for some allocation patterns. Specifically, it is possible that a freelist contains thousands of entries of a given size and it is scanned while looking for a bigger entry, that will not fit in any of those.
This is demonstrated by the attached program. It accepts a size as an argument and will allocate 1000000 elements of that size, deallocate half of them (the "even" ones), then allocate 1000 elements that are just one bit bigger.
For most sizes the program terminates in milliseconds, but in my environment it takes several seconds for sizes 16, 32, 48, 64, 80, 88, 96, 112, 120, 128.
A possible workaround (that I had implemented in the past, for short-lived applications) is to allocate from a freelist whose entries are all at least as big as the block that is being allocated, but that can cause inefficient memory usage.
I noticed that wine includes an implementation of a red-black tree. Would it make sense to organise the free entries as lists in such a tree? That should ensure O(log N) in the worst case. If performance is a concern, it might be possible to use "direct" freelists for small sizes (ensuring that all of the alignment-compatible sizes are covered) and use a tree for bigger sizes.
I am willing to work on this, but I need some directions on what is the best path forward (namely, if we should prefer the memory-inefficient but simpler approach of just allocating from "bigger" freelists or if the tree approach is the desired one).
The bug https://bugs.winehq.org/show_bug.cgi?id=37773 might be related.
https://bugs.winehq.org/show_bug.cgi?id=43224
Sebastian Lackner sebastian@fds-team.de changed:
What |Removed |Added ---------------------------------------------------------------------------- CC| |sebastian@fds-team.de
--- Comment #1 from Sebastian Lackner sebastian@fds-team.de --- This issue is already known since some time, and various solutions have been proposed in the past.
In some cases the performance issue can be solved by using more fine-grained free lists (see for example bug 24256). We also have a similar patch in Wine Staging at the moment. Nevertheless, it only solves the problem for specific block sizes, and has been rejected in the development branch so far.
Another attempt which is worth mentioning is by Nils Kuhnhenn, who tried to implement automatic balancing of free lists (see https://github.com/laino/wine-patches). In general this direction probably isn't that bad, but it makes the code much more complicated and introduces the risk of regressions or other performance issues (especially when using a self-written balancing algorithm instead of well-known tree implementations).
I would say that using a proper tree is the right way to go, but it has to be done in such a way that freelist entries do not require any additional memory allocations. If you plan to use the Wine builtin RBTree, it will probably require some modifications to make it suitable for that purpose (reduce memory overhead, implement alternative lookup functions, ...). To speed up very small allocations, it could also make sense to keep the fixed-size freelists.
Please note that if you want to get a definite answer if a certain approach is acceptable, this bug tracker is not really the right place to ask. Usually development related decisions are discussed on the wine-devel mailing list. In this particular case, quality of the patches and performance comparisons will also play a very important role.
https://bugs.winehq.org/show_bug.cgi?id=43224
--- Comment #2 from Henri Verbeet hverbeet@gmail.com --- For what it's worth, if you do end up working on the memory allocator, note that modern allocators like ptmalloc3/jemalloc/nedmalloc/tcmalloc/etc. typically have per-thread allocation caches to avoid lock contention, which I think is another issue Wine's current allocator suffers from.
https://bugs.winehq.org/show_bug.cgi?id=43224
Sebastian Lackner sebastian@fds-team.de changed:
What |Removed |Added ---------------------------------------------------------------------------- CC| |dmitry@baikal.ru, | |erich.e.hoover@wine-staging | |.com, michael@fds-team.de Staged patchset| |https://github.com/wine-com | |pholio/wine-staging/tree/ma | |ster/patches/ntdll-Heap_Imp | |rovements Status|UNCONFIRMED |STAGED Ever confirmed|0 |1
https://bugs.winehq.org/show_bug.cgi?id=43224
André H. nerv@dawncrow.de changed:
What |Removed |Added ---------------------------------------------------------------------------- CC| |nerv@dawncrow.de Staged patchset|https://github.com/wine-com |https://github.com/wine-sta |pholio/wine-staging/tree/ma |ging/wine-staging/tree/mast |ster/patches/ntdll-Heap_Imp |er/patches/ntdll-Heap_Impro |rovements |vements
https://bugs.winehq.org/show_bug.cgi?id=43224
Józef Kucia joseph.kucia@gmail.com changed:
What |Removed |Added ---------------------------------------------------------------------------- CC| |joseph.kucia@gmail.com See Also| |https://bugs.winehq.org/sho | |w_bug.cgi?id=24256
https://bugs.winehq.org/show_bug.cgi?id=43224
Józef Kucia joseph.kucia@gmail.com changed:
What |Removed |Added ---------------------------------------------------------------------------- See Also| |https://bugs.winehq.org/sho | |w_bug.cgi?id=37773
https://bugs.winehq.org/show_bug.cgi?id=43224
Andrew Eikum aeikum@codeweavers.com changed:
What |Removed |Added ---------------------------------------------------------------------------- CC| |aeikum@codeweavers.com
https://bugs.winehq.org/show_bug.cgi?id=43224
Rémi Bernon rbernon@codeweavers.com changed:
What |Removed |Added ---------------------------------------------------------------------------- Fixed by SHA1| |40b7c3e89a95d6ccb190b234d4a | |d13b3a8304495 Status|STAGED |RESOLVED CC| |rbernon@codeweavers.com Resolution|--- |FIXED
https://bugs.winehq.org/show_bug.cgi?id=43224
Alexandre Julliard julliard@winehq.org changed:
What |Removed |Added ---------------------------------------------------------------------------- Status|RESOLVED |CLOSED
--- Comment #3 from Alexandre Julliard julliard@winehq.org --- Closing bugs fixed in 8.3.
-
wine-bugs＠winehq.org -
WineHQ Bugzilla