Name: jk109818 Date: 07/28/2003


FULL PRODUCT VERSION :
Replicated on 1.4.2 at work. Here at home it is
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 OS VERSION :
Microsoft Windows 2000 [Version 5.00.2195]

EXTRA RELEVANT SYSTEM CONFIGURATION :
  Duplicated on two different Win2000 machines (Work Dell + home machine branded by local computer store)

A DESCRIPTION OF THE PROBLEM :
This is similar to 4517075, except that it affects setValue(), not getValue(), and has not been fixed. Because setValue() calls itself twice on its two arguments, it can take exponential time in acyclic graphs with ladder-like structure.

The demo code in steps to reproduce includes a more detailed explanation.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Compile and run the following

import javax.swing.Spring;

/** Demonstrate exponential cost of setValue() in Spring.max.
 * One suggestion is not to do anything in setValue() if the
 * new value is equal to the current value. I encountered this
 * while trying to set up a grid with a network of springs
 * where grid position n+1 was the maximum of (grid position
 * n plus the width of a component at n) over all components
 * at n. Finding the maximum width of all components at n before
 * doing the sum produces a better layout as well as reducing
 * the cost, but does not cope with components that span multiple
 * grid cells.
 *
 * I think this is a trap, and should at least be documented.
 */
public class Springer
{
  private static void test(int numLevels)
  {
    Spring springa = Spring.constant(1);
    Spring springb = Spring.constant(1);
    for (int i = 0; i < numLevels; i++)
    {
      Spring springc = Spring.max(springa, springb);
      Spring springd = Spring.max(springa, springb);
      springa = springc;
      springb = springd;
    }
    System.out.println("Before set with " + numLevels + " levels");
    long before = System.currentTimeMillis();
    springa.setValue(1);
    long after = System.currentTimeMillis();
    System.out.println("After set with " + numLevels +
      " levels took " + (after - before) + " ms");
  }
  public static void main(String[] s)
  {
    for (int i = 20; i < 40; i++)
    {
      test(i);
    }
  }
}


EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
I was hoping that the time for Spring.max would increase only polynomially with the size of the graph - linearly would be nice.
ACTUAL -

Before set with 20 levels
After set with 20 levels took 211 ms
Before set with 21 levels
After set with 21 levels took 430 ms
Before set with 22 levels
After set with 22 levels took 812 ms
Before set with 23 levels
After set with 23 levels took 1582 ms
Before set with 24 levels
After set with 24 levels took 3315 ms
Before set with 25 levels
After set with 25 levels took 6980 ms
Before set with 26 levels
After set with 26 levels took 13900 ms
Before set with 27 levels

(lost patience with it at this point)

ERROR MESSAGES/STACK TRACES THAT OCCUR :
Stack trace shows deep recursion:

      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:367)
      at javax.swing.Spring$MaxSpring.setValue(Spring.java:368)
      at Springer.test(Springer.java:31)
      at Springer.main(Springer.java:40)


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
See steps to reproduce
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Don't use ladder networks with max! I coded a version of spring.max that doesn't recurse if it is asked to set itself to the value that it already has, and that fixed my particular problem. I conjecture that this is a reasonably general solution, because the top values of such networks will tend to have the same preferred value, but I don't have enough experience to tell for sure. Some warning about this in the documentation would be nice.

PS - sorry for the strange ID, but I got fed up when Sun messed around with their registration names yet again and I couldn't manage to get back my old mcdowella id.
(Incident Review ID: 191693)
======================================================================