Possibility? of infinite loop in MultinameHashtable::get
treilly at adobe.com
Mon Jan 14 17:09:46 PST 2008
There's a proof out there somewhere that a power of 2 hashtable w/
quadratic probe with the right constants hits every slot in the table
before repeating. Thus no infinite loop if the table isn't full.
> -----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 5: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
More information about the Tamarin-devel