[Bug 43224] Freelist scan can result in O(n) time when allocating

wine-bugs at winehq.org wine-bugs at winehq.org
Thu Jun 22 14:52:18 CDT 2017


https://bugs.winehq.org/show_bug.cgi?id=43224

Sebastian Lackner <sebastian at fds-team.de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sebastian at fds-team.de

--- Comment #1 from Sebastian Lackner <sebastian at 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.



More information about the wine-bugs mailing list