United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-4802637 (coll) Minor change to TreeMap.getEntry comparison code for performance
JDK-4802637 : (coll) Minor change to TreeMap.getEntry comparison code for performance

Details
Type:
Bug
Submit Date:
2003-01-14
Status:
Resolved
Updated Date:
2012-10-08
Project Name:
JDK
Resolved Date:
2005-09-04
Component:
core-libs
OS:
windows_xp
Sub-Component:
java.util:collections
CPU:
x86
Priority:
P4
Resolution:
Fixed
Affected Versions:
1.4.0
Fixed Versions:

Related Reports

Sub Tasks

Description
Name: nt126004			Date: 01/13/2003


FULL PRODUCT VERSION :
java version "1.4.0"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.0-b92)
Java HotSpot(TM) Client VM (build 1.4.0-b92, mixed mode)

FULL OPERATING SYSTEM VERSION :
All

ADDITIONAL OPERATING SYSTEMS :
ALL


A DESCRIPTION OF THE PROBLEM :
Enhancement to:

    /**
     * Returns this map's entry for the given key, or <tt>null</tt> if the map
     * does not contain an entry for the key.
     *
     * @return this map's entry for the given key, or <tt>null</tt> if the map
     *                does not contain an entry for the key.
     * @throws ClassCastException if the key cannot be compared with the keys
     *                  currently in the map.
     * @throws NullPointerException key is <tt>null</tt> and this map uses
     *                  natural order, or its comparator does not tolerate 
     *                  <tt>null</tt> keys.
     */
    private Entry getEntry(Object key) {
        Entry p = root;
        while (p != null) {
            int cmp = compare(key,p.key);
            if (cmp == 0)
                return p;
            else if (cmp < 0)
                p = p.left;
            else
                p = p.right;
        }
        return null;
    }



Suggestion: as cmp == 0 will return false in most of the
cases, the following code will be more efficient



    private Entry getEntry(Object key) {
        Entry p = root;
        while (p != null) {
            int cmp = compare(key,p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
TreeMap Line number 338 through 350

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
Enhancement to:

    /**
     * Returns this map's entry for the given key, or <tt>null</tt> if the map
     * does not contain an entry for the key.
     *
     * @return this map's entry for the given key, or <tt>null</tt> if the map
     *                does not contain an entry for the key.
     * @throws ClassCastException if the key cannot be compared with the keys
     *                  currently in the map.
     * @throws NullPointerException key is <tt>null</tt> and this map uses
     *                  natural order, or its comparator does not tolerate *
     *                  <tt>null</tt> keys.
     */
    private Entry getEntry(Object key) {
        Entry p = root;
        while (p != null) {
            int cmp = compare(key,p.key);
            if (cmp == 0)
                return p;
            else if (cmp < 0)
                p = p.left;
            else
                p = p.right;
        }
        return null;
    }



Suggestion: as cmp == 0 will return false in most of the cases, the following
code will be more efficient



    private Entry getEntry(Object key) {
        Entry p = root;
        while (p != null) {
            int cmp = compare(key,p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

---------- END SOURCE ----------

CUSTOMER WORKAROUND :
Suggestion: as cmp == 0 will return false in most of the
cases, the following code will be more efficient



    private Entry getEntry(Object key) {
        Entry p = root;
        while (p != null) {
            int cmp = compare(key,p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }
(Review ID: 179402) 
======================================================================

                                    

Comments
EVALUATION

Will be fixed as part of JSR166 maintenance
###@###.### 2005-03-09 03:05:45 GMT
                                     
2005-03-09



Hardware and Software, Engineered to Work Together