Possibility? of infinite loop in MultinameHashtable::get
Haghighat, Mohammad R
mohammad.r.haghighat at intel.com
Mon Jan 14 22:02:19 PST 2008
Cool! This property doesn't hold for all instances of quadratic probing,
as stated here:
http://cs.nyu.edu/courses/fall07/V22.0102-002/lectures/hashing-102-fa07.
ppt#307,33,Slide%2033
More specifically, the plain h(k,i) = (h(k)+i^2) mod n results in the
repetition of digits 0, 1, 4, 9 in some order.
However, when n is a power of 2 and the right coefficients are used, as
is the case in Tamarin: h(k,i) = (h(k)+ i(i+1)/2) mod n, the generated
numbers are distinct in the sequence. The proof is at the very bottom of
http://en.wikipedia.org/wiki/Quadratic_probing
Thanks,
- moh
-----Original Message-----
From: Thomas Reilly [mailto:treilly at adobe.com]
Sent: Monday, January 14, 2008 5:10 PM
To: Haghighat, Mohammad R; tamarin-devel at mozilla.org
Subject: RE: Possibility? of infinite loop in MultinameHashtable::get
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