[Bug 14168] visual studio 2005 installer too slow, msi O(n^2) behavior?

[wine-bugs at winehq.org]

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





--- Comment #23 from Hans Leidekker <hans at meelstraat.net>  2009-12-09 03:44:06 ---
Henri's rbtree implementation brings the time spent in the "loading
components" phase down from 50 to 5 minutes on my machine.

I wrote an alternative patch that keeps a sorted array in addition to
the hash and uses that for lookups after the buckets are filled up to
a certain amount.

This should use less memory than an rbtree, but overall performance
is only good if the assumption holds that most strings are added at
initialization time, because each addition causes a rebuild of the
entire index.

As it turns out this installer shows the worst possible behavior for this
algorithm; although the vast majority of strings are added at initialization
time (as in every installer), it does a whole bunch of lookups, inserts
one string, and repeats.

-- 
Configure bugmail: http://bugs.winehq.org/userprefs.cgi?tab=email
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.