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
Add an attachment (proposed patch, testcase, etc.)

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.