A DESCRIPTION OF THE REQUEST :
java.util.Arrays is know for being very robuts and works well. It can be improved more if we can optimize some critical routines.

JUSTIFICATION :
It will improve the performance of java.util.Arrays.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
An improvement in the performance of java.util.Arrays
ACTUAL -
It works, but it is not the best implementation possible yet.

---------- BEGIN SOURCE ----------
Problems found:
   /* In this function the loop can start from 1, to remove the if from the loop */
    public static String toString(Object[] a) {
        if (a == null)
            return "null";
        if (a.length == 0)
            return "[]";
 
        StringBuilder buf = new StringBuilder();
 
        for (int i = 0; i < a.length; i++) {
            if (i == 0)
                buf.append('[');
            else
                buf.append(", ");
 
            buf.append(String.valueOf(a[i]));
        }
 
        buf.append("]");
        return buf.toString();
    }

   /* In this function the loop can start from 1, to remove the if from the loop */
    private static void deepToString(Object[] a, StringBuilder buf,
                                     Set<Object[]> dejaVu) {
        if (a == null) {
            buf.append("null");
            return;
        }
        dejaVu.add(a);
        buf.append('[');
        for (int i = 0; i < a.length; i++) {
            if (i != 0)
                buf.append(", ");

            Object element = a[i];
            if (element == null) {
                buf.append("null");
            } else {
                Class eClass = element.getClass();

                if (eClass.isArray()) {
                    if (eClass == byte[].class)
                        buf.append(toString((byte[]) element));
                    else if (eClass == short[].class)
                        buf.append(toString((short[]) element));
                    else if (eClass == int[].class)
                        buf.append(toString((int[]) element));
                    else if (eClass == long[].class)
                        buf.append(toString((long[]) element));
                    else if (eClass == char[].class)
                        buf.append(toString((char[]) element));
                    else if (eClass == float[].class)
                        buf.append(toString((float[]) element));
                    else if (eClass == double[].class)
                        buf.append(toString((double[]) element));
                    else if (eClass == boolean[].class)
                        buf.append(toString((boolean[]) element));
                    else { // element is an array of  customer  references
                        if (dejaVu.contains(element))
                            buf.append("[...]");
                        else
                            deepToString((Object[])element, buf, dejaVu);
                    }
                } else {  // element is non-null and not an array
                    buf.append(element.toString());
                }
            }
        }
        buf.append("]");
        dejaVu.remove(a);
    }
}



In sort2(), we can see this loop:
            for (int k=0; k<numNegZeros; k++)
                a[++j] = -0.0f;
/* As the variable numNegZeros is not used after this loop, we can use it to iterate, instead of the k variable. It can be decrementing up to zero. */


   /* The variable cmp is not needed. We can remove the if's from the inner loop if
     we do not use the cmp variable. This improvement can be applied to the float binarySearch() too. */
    private static int binarySearch(double[] a, double key, int low,int high) {
	while (low <= high) {
	    int mid = (low + high) >> 1;
	    double midVal = a[mid];

            int cmp;
            if (midVal < key) {
                cmp = -1;   // Neither val is NaN, thisVal is smaller
            } else if (midVal > key) {
                cmp = 1;    // Neither val is NaN, thisVal is larger
            } else {
                long midBits = Double.doubleToLongBits(midVal);
                long keyBits = Double.doubleToLongBits(key);
                cmp = (midBits == keyBits ?  0 : // Values are equal
                       (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
                        1));                     // (0.0, -0.0) or (NaN, !NaN)
            }

	    if (cmp < 0)
		low = mid + 1;
	    else if (cmp > 0)
		high = mid - 1;
	    else
		return mid; // key found
	}
	return -(low + 1);  // key not found.
    }

---------- END SOURCE ----------
  xxxxx@xxxxx   2005-03-11 06:50:47 GMT

N/A

These optimizations are not really big wins, but this code
(especially binarySearch) will be extensively scrutinized by
half the students in Data Structures 101.

8 votes!  Wow!
I guess everyone loves micro-optimizations.
Good to know I am not alone...
Let's write some more tests while we're here.
Posted Date : 2007-08-09 15:32:41.0

> In sort2(), we can see this loop:
>             for (int k=0; k<numNegZeros; k++)
>                 a[++j] = -0.0f;
> /* As the variable numNegZeros is not used after this loop, we can use it to iterate, instead of the k variable. It can be decrementing up to zero. */

I do not agree with the "decrementing up to zero" method as I have benchmarked it and prove that the cost for scanning the array backwards is higher than the gain  in "optimising" the loop.

How have you benchmarked it?
It was consistent across multiple runs?

Oh I have benchmarked it using the following applet on serveral computer platforms around me:

http://www.javaworld.com/javaworld/jw-04-1997/jw-04-optimize-p3.html

I have also written a small class to verify this myself; all these test are run multiple times and a considerable time interval in between runs, if that's what you need to know =P

actually one result that I didn't mention - there seem to be a rather unexpected, yet faster way to write the (longer) loops that scan an array.

=== Loop Benchmark ===
--- Empty loop 1453 * 344000 times
for (i = 0; i < array.length; i++)                 2688 ps
for (i = 0; i < local; i++)                        2812 ps
implict i: for (i = 0; i < local; i++)             2812 ps
for (i = local; --i >= 0; )                        2406 ps
--- Loop int array[i] = i;
for (i = 0; i < array.length; i++)                 3813 ps
for (i = array.length; --i >= 0; )                 5033 ps
try { for (i = 0; ; i++) }                         2936 ps

Interesting to see that it's faster to keep looping until we get an ArrayOutOfBoundsException, rather than testing it.  Looks like the JVM could do a little better in optimising loops if that is the case.

Please don't use exceptions for control flow, even if it happens to be faster in some JVM. Such optimizations are not portable across JVMs, this may cause perf regression in JVMs that reuse Sun's code, e.g. IBM or BEA, or (now with OpenJDK) free JVMs. But most important is that using exceptions for that purpose sucks, 10 out of 10 best-practices texts or code validation tools condemn this practice for good reasons. For one thing, I totally hate that when debugging Java apps, it's hard to use exception breakpoints on some exceptions - like NPE - because this triggers lots of bogus exceptions in crappy API and application server code. Right thing to do is *remove* the existing exceptions-as-control-structure from existing code.