|
From: Christoph B. <bar...@or...> - 2007-07-19 12:55:03
|
Am Donnerstag, 19. Juli 2007 schrieb Christoph Bartoschek:
> The obvious answer for such a big number of contexts could be that we
> really have introduced a lot of new context. But can the number grow by
> such an extent?
I've looked at some tracebacks and I see that the current hashtable with 30011
entries is too small for the program.
For example there is a rectangle processing routine that works recursive in
this way:
vois simplify(Rectangle rect) {
if (rect.size() < THRESHOLD) {
do_work(rect);
} else {
simplify(rect.quadrant(1));
simplify(rect.quadrant(2));
simplify(rect.quadrant(3));
simplify(rect.quadrant(4));
}
}
I see a recursion depth of about 9 in the current execution. This leads to
4^9 = 262144 different execution contexts. Severall different calls to such a
method easily lead to millions of execution contexts.
Greetings
Christoph
|
|
From: Nicholas N. <nj...@cs...> - 2007-07-20 00:05:07
|
On Thu, 19 Jul 2007, Christoph Bartoschek wrote: > I've looked at some tracebacks and I see that the current hashtable with 30011 > entries is too small for the program. A general comment: there's a module m_oset.c which defines the OSet type. It implements an AVL tree. When I added it, it was intended to replace the Vg_HashTable type, the idea being that it would scale better as it had no fixed limits. But it turned out to have noticeable worse constant factors, and most people aren't running programs nearly as large as the ones you are, so the Vg_HashTable is still used. It might be worth trying the OSet instead of the Vg_HashTable for some of these structures. The interfaces are pretty similar. Nick |