[Bug 43224] New: Freelist scan can result in O(n) time when allocating
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(a)winehq.org Reporter: ranma42(a)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. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=43224 Sebastian Lackner <sebastian(a)fds-team.de> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |sebastian(a)fds-team.de --- Comment #1 from Sebastian Lackner <sebastian(a)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. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=43224 --- Comment #2 from Henri Verbeet <hverbeet(a)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. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=43224 Sebastian Lackner <sebastian(a)fds-team.de> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |dmitry(a)baikal.ru, | |erich.e.hoover(a)wine-staging | |.com, michael(a)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 -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=43224 André H. <nerv(a)dawncrow.de> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |nerv(a)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 -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=43224 Józef Kucia <joseph.kucia(a)gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |joseph.kucia(a)gmail.com See Also| |https://bugs.winehq.org/sho | |w_bug.cgi?id=24256 -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=43224 Józef Kucia <joseph.kucia(a)gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- See Also| |https://bugs.winehq.org/sho | |w_bug.cgi?id=37773 -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=43224 Andrew Eikum <aeikum(a)codeweavers.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |aeikum(a)codeweavers.com -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=43224 Rémi Bernon <rbernon(a)codeweavers.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Fixed by SHA1| |40b7c3e89a95d6ccb190b234d4a | |d13b3a8304495 Status|STAGED |RESOLVED CC| |rbernon(a)codeweavers.com Resolution|--- |FIXED -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
https://bugs.winehq.org/show_bug.cgi?id=43224 Alexandre Julliard <julliard(a)winehq.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|RESOLVED |CLOSED --- Comment #3 from Alexandre Julliard <julliard(a)winehq.org> --- Closing bugs fixed in 8.3. -- Do not reply to this email, post in Bugzilla using the above URL to reply. You are receiving this mail because: You are watching all bug changes.
participants (2)
-
wine-bugs＠winehq.org -
WineHQ Bugzilla