Bug 28987 - IdentityHashMap inefficiency
Summary: IdentityHashMap inefficiency
Status: RESOLVED FIXED
Alias: None
Product: classpath
Classification: Unclassified
Component: classpath (show other bugs)
Version: 0.92
: P3 normal
Target Milestone: 0.93
Assignee: Tom Tromey
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2006-09-08 19:02 UTC by Tom Tromey
Modified: 2006-10-03 16:34 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2006-09-28 17:09:37


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Tom Tromey 2006-09-08 19:02:02 UTC
Currently IdentityHashMap uses tombstones to mark deleted slots.
However, since this class uses linear probing, it can take advantage
of Knuth's "algorithm R" (section 6.4) instead.  This is more efficient.

Also some variant of Martin's patch should go in:

http://developer.classpath.org/pipermail/classpath-patches/2006-April/001430.html
Comment 1 Tom Tromey 2006-09-28 17:09:37 UTC
Testing a patch.
Comment 2 cvs-commit@developer.classpath.org 2006-10-03 16:34:05 UTC
Subject: Bug 28987

CVSROOT:	/cvsroot/classpath
Module name:	classpath
Changes by:	Tom Tromey <tromey>	06/10/03 16:33:13

Modified files:
	java/util      : IdentityHashMap.java 
	.              : ChangeLog 

Log message:
		PR classpath/28987:
		* java/util/IdentityHashMap.java (tombstone): Removed.
		(emptyslot): Removed.
		(nullslot): New field.
		(IdentityHashMap): Don't fill array.
		(clear): Fill with null.
		(hash): Now final.  Use linear probing.
		(xform): New method.
		(unxform): Likewise.
		(removeAtIndex): Likewise.
		(clone, containsKey, containsValue, entrySet, get, hashCode,
		keySet, put, remove, values): Updated.
		(IdentityIterator, IdentityEntry): Likewise.
		(writeObject): Likewise.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/classpath/java/util/IdentityHashMap.java?cvsroot=classpath&r1=1.19&r2=1.20
http://cvs.savannah.gnu.org/viewcvs/classpath/ChangeLog?cvsroot=classpath&r1=1.8640&r2=1.8641



Comment 3 Tom Tromey 2006-10-03 16:34:06 UTC
Fix checked in.