[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[patch #2485] java.util.HashMap#rehash performance improvement
From: |
Mark Wielaard |
Subject: |
[patch #2485] java.util.HashMap#rehash performance improvement |
Date: |
Thu, 29 Apr 2004 18:46:24 -0400 |
User-agent: |
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.6) Gecko/20040413 Galeon/1.3.14 (Debian package 1.3.14a-1) |
This mail is an automated notification from the patch tracker
of the project: classpath.
/**************************************************************************/
[patch #2485] Latest Modifications:
Changes by:
Mark Wielaard <address@hidden>
'Date:
Thu 04/29/04 at 22:46 (Europe/Amsterdam)
What | Removed | Added
---------------------------------------------------------------------------
Resolution | None | Fixed
Status | Open | Closed
------------------ Additional Follow-up Comments ----------------------------
Thanks. I committed the following (slightly different from your original):
2004-04-29 Mark Wielaard <address@hidden>
Reported by address@hidden [patch #2485]
* java/util/HashMap.java (rehash): Add entry at start of bucket.
diff -u -r1.27 HashMap.java
--- java/util/HashMap.java 22 Apr 2004 11:24:39 -0000 1.27
+++ java/util/HashMap.java 29 Apr 2004 22:41:34 -0000
@@ -743,18 +743,9 @@
{
int idx = hash(e.key);
HashEntry dest = buckets[idx];
-
- if (dest != null)
- {
- while (dest.next != null)
- dest = dest.next;
- dest.next = e;
- }
- else
- buckets[idx] = e;
-
HashEntry next = e.next;
- e.next = null;
+ e.next = buckets[idx];
+ buckets[idx] = e;
e = next;
}
}
It is actually a bit of a micro optimisation since your hash function has to be
pretty for this to be noticable. But bad hash functions are not that rare so I
guess this will help at least someone.
Cheers,
Mark
/**************************************************************************/
[patch #2485] Full Item Snapshot:
URL: <http://savannah.gnu.org/patch/?func=detailitem&item_id=2485>
Project: classpath
Submitted by: 0
On: Fri 01/16/04 at 20:15
Category: None
Priority: 5 - Normal
Resolution: Fixed
Assigned to: mark
Originator Email: address@hidden
Status: Closed
Summary: java.util.HashMap#rehash performance improvement
Original Submission: The entries in one bucket are stored in a linked list. On
rehashing, we need to re-add every entry. Currently, we search the end of that
linked list and add the entry there. Which causes O(n^2) performance in the
worst case, i.e. when every entry is in the same bucket. This should really be
O(n).
With the attached patch, we get rid of the loop that finds the end of the list,
and instead add the entry at the beginning. This is just what addEntry() does
when adding entries normally.
Follow-up Comments
------------------
-------------------------------------------------------
Date: Thu 04/29/04 at 22:46 By: mark
Thanks. I committed the following (slightly different from your original):
2004-04-29 Mark Wielaard <address@hidden>
Reported by address@hidden [patch #2485]
* java/util/HashMap.java (rehash): Add entry at start of bucket.
diff -u -r1.27 HashMap.java
--- java/util/HashMap.java 22 Apr 2004 11:24:39 -0000 1.27
+++ java/util/HashMap.java 29 Apr 2004 22:41:34 -0000
@@ -743,18 +743,9 @@
{
int idx = hash(e.key);
HashEntry dest = buckets[idx];
-
- if (dest != null)
- {
- while (dest.next != null)
- dest = dest.next;
- dest.next = e;
- }
- else
- buckets[idx] = e;
-
HashEntry next = e.next;
- e.next = null;
+ e.next = buckets[idx];
+ buckets[idx] = e;
e = next;
}
}
It is actually a bit of a micro optimisation since your hash function has to be
pretty for this to be noticable. But bad hash functions are not that rare so I
guess this will help at least someone.
Cheers,
Mark
-------------------------------------------------------
Date: Fri 03/12/04 at 14:35 By: mark
Will take a look at this, but after 0.08.
File Attachments
-------------------
-------------------------------------------------------
Date: Fri 01/16/04 at 20:15 Name: diff.txt Size: 619KB By: None
http://savannah.gnu.org/patch/download.php?item_id=2485&item_file_id=2526
For detailed info, follow this link:
<http://savannah.gnu.org/patch/?func=detailitem&item_id=2485>
_______________________________________________
Message sent via/by Savannah
http://savannah.gnu.org/
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [patch #2485] java.util.HashMap#rehash performance improvement,
Mark Wielaard <=