[Bug 18921] New: O(n) hash_table_add causes winedbg to take 20 minutes to dump stack when chromium crashes
http://bugs.winehq.org/show_bug.cgi?id=18921
Summary: O(n) hash_table_add causes winedbg to take 20 minutes to dump stack when chromium crashes Product: Wine Version: 1.1.23 Platform: PC OS/Version: Linux Status: NEW Severity: normal Priority: P2 Component: dbghelp AssignedTo: wine-bugs@winehq.org ReportedBy: dank@kegel.com CC: eric.pouech@orange.fr
In bug 15206, I mentioned that windbg was too slow to be usable. I ran oprofile while winedbg was churning, and the time appears to all be spent on one line of code in dlls/dbghelp/storage.c:
void hash_table_add(struct hash_table* ht, struct hash_table_elt* elt) { ... 569217 89.8978 : for (p = &ht->buckets[hash]; *p; p = &((*p)->next));
Looks like we need to modify struct hash_table and some of its operators to allow a more efficient append operation there.
Fixing this bug will be one more step towards being friendly to developers who use Visual Studio and expect our tools to be able to handle .pdb files well.
http://bugs.winehq.org/show_bug.cgi?id=18921
--- Comment #1 from Henri Verbeet hverbeet@gmail.com 2009-06-13 05:48:22 --- Replacing the list with a standard Wine list should already make the insert less expensive, since you can just add to the tail. Large tables will still degenerate into linked lists though, since as far as I can see the table is never resized. If duplicate symbols could be handled in a different way (e.g. storing them as a list in a single entry), the RB-tree in include/wine/rbtree.h could be used.
http://bugs.winehq.org/show_bug.cgi?id=18921
--- Comment #2 from Eric Pouech eric.pouech@orange.fr 2009-06-13 08:12:04 --- we're eating lots of memory with loading at once all the symbols using a wine list would add an extra pointer I'd suggest simply keeping a pointer to the last object in the bucket, that would be sufficient regarding Henri's comment, we could have several symbols with same names (static vars in different compilation units for example), but never same name & same address... it just requires (famous last words) to adapt the comparison function A+
http://bugs.winehq.org/show_bug.cgi?id=18921
--- Comment #3 from Dan Kegel dank@kegel.com 2009-06-14 12:06:10 --- Eric has a patch that solves this particular bottleneck and gets the time down from 20 minutes to 6 minutes. The next bottleneck, he says, has to do with the fact that we sort the symbol table on every insert rather than in batches.
http://bugs.winehq.org/show_bug.cgi?id=18921
--- Comment #4 from Eric Pouech eric.pouech@orange.fr 2009-06-27 01:01:43 --- improvement as of #3 has been committed to git likely another 70% improvement
http://bugs.winehq.org/show_bug.cgi?id=18921
Dan Kegel dank@kegel.com changed:
What |Removed |Added ---------------------------------------------------------------------------- Status|NEW |RESOLVED Resolution| |FIXED
--- Comment #5 from Dan Kegel dank@kegel.com 2009-10-05 13:33:44 --- Fixed well enough for now. I'll file another bug next time I hit a performance problem here.
http://bugs.winehq.org/show_bug.cgi?id=18921
Alexandre Julliard julliard@winehq.org changed:
What |Removed |Added ---------------------------------------------------------------------------- Status|RESOLVED |CLOSED
--- Comment #6 from Alexandre Julliard julliard@winehq.org 2009-10-09 11:14:11 --- Closing bugs fixed in 1.1.31.
-
wine-bugs＠winehq.org