Possibility? of infinite loop in MultinameHashtable::get

Thomas Reilly 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
> https://mail.mozilla.org/listinfo/tamarin-devel
> 


More information about the Tamarin-devel mailing list