Possibility? of infinite loop in MultinameHashtable::get

Edwin Smith edwsmith at adobe.com
Mon Jan 14 17:15:19 PST 2008


The quadratic probe function being used will hit all cells in the table
(eventually) so the only way the probe won't terminate is if the table
is 100% full, which is prevented by the load factor being .8.  I'll try
and dig up a reference on this and post it.  there should at least be a
link in the code but i'm not finding it now.
Ed

-----Original Message-----
From: tamarin-devel-bounces at mozilla.org
[mailto:tamarin-devel-bounces at mozilla.org] On Behalf Of Haghighat,
Mohammad R
Sent: Monday, January 14, 2008 8:00 PM
To: tamarin-devel at mozilla.org
Subject: Possibility? of infinite loop in MultinameHashtable::get


I've been looking at optimizing the "get" method of MultinameHashtable,
which is often the hottest VM function. It seems that its implementation
is at risk of infinite loop not only at insertion time but also during
lookups. For lookups, when a match is found the method doesn't return
the match before it inspects all the possible collisions until it finds
an empty slot. This is done to check if there's an ambiguous binding.
Even if the occupancy of the table is below the load factor, it is
conceivable that all cells in the collision chain might be occupied. In
such a case, the get method will not terminate. This is more probable
with small tables. A remedy could be to rehash the table upon the first
revisit of the first cell. 

- moh
_______________________________________________
Tamarin-devel mailing list
Tamarin-devel at mozilla.org
https://mail.mozilla.org/listinfo/tamarin-devel


More information about the Tamarin-devel mailing list