commit-classpath
[Top][All Lists]
Advanced

[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&amp;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/







reply via email to

[Prev in Thread] Current Thread [Next in Thread]