http://bugs.winehq.org/show_bug.cgi?id=14168
--- Comment #23 from Hans Leidekker hans@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.