Drawing fractals

[Carl Pettersson]

I've created a screensaver that paints fractals, and, unsurprisingly, it is not very fast. I don't really need it to run quickly, but I thought it'd be a good exercise to make it better. Currently I have a BufferedImage, which is colored pixel by pixel in for-loops. When the whole image is done, I draw it to screen.
My guess is that I can't really get the calculation to run quicker without going to assembly or something like it. Calculation code:

private int iterateJul(double x, double y, double cre, double cim) {
 // maxIt is an final int with value 250
 double zre = x, zim = y, zrel;
 int it = 0;
 while ((zre * zre + zim * zim) < 2.3 && it < maxIt) {
  zrel = zre;
  zre = zre * zre - zim * zim + cre;
  zim = 2 * zrel * zim + cim;
  it++;
 }
 return it;
}

Any obvious ways to improve this?

I suspect I could gain some time by optimizing the access to the image. Code:

private void drawJulia(double cX, double cY) {
 frac = new BufferedImage(scrX, scrY, BufferedImage.TYPE_INT_RGB);
 Graphics g = this.getGraphics();
 double coordX = 0, coordY = 0;
 double renY, renX;
 int it;
 
 for (renX = minx; coordX < scrX; renX += (maxx - minx) / scrX, coordX++) {
        coordY = 0;
  for (renY = miny; coordY < scrY; renY += (maxy - miny) / scrY, coordY++) {
   it = iterateJul(renX, renY, cX, cY);
   if (it == maxIt) {
    frac.setRGB((int) coordX, (int) coordY, Color.black.getRGB());
   } else {
    frac.setRGB((int) coordX, (int) coordY, colAr[it].getRGB());
   }
  }
 }
 g.drawImage(frac, 0, 0, null);
 try {
  Thread.yield();
 } catch (Exception ex) {
 }
}

Is there a better image class, perhaps VolatileImage? I didn't use it because I wasn't very interesting in suddenly losing the image, but as a render with existing code takes approx. one second, it might not be catastophic.

Suggestions?

Best regards
Carl Pettersson

[Olaf Kummer]

Small improvement: You compute zre*zre and zim*zim twice, when a single multiplication would suffice. Use: while (true) {... if (...) break; ...}. Adding a number to itself is often faster than multiplying it by two.

That's going to earn you a few percent, but nothing impressive.

Maybe(!) fixed point arithmetic with ints/longs can buy you another few percent, but that requires some thought.

Olaf

[Steven Bell]

If you want to make it faster you must use a profiler to find out what is slow first. If you just try to look for things that you think are slow you will probably end up spending alot of time for very little improvement.

[Ernest Friedman-Hill]

Originally posted by Olaf Kummer:

That's going to earn you a few percent, but nothing impressive.

Actually, the floating-point multiplies are the lion's share of the work that gets done here; I'd expect this to have a fairly large impact.

[Carl Pettersson]

Olaf: Changed according to your suggestions, improved avg. rendering time by about 20 millisec. How do you mean using int/long? I need the decimal part of the doubles...

Steven: I ran the profilers I found in java.exe;

Output from java -Xprof:

Compiled + native Method
55.5% 1817 + 0 FracSave.iterateJul
16.8% 548 + 0 FracSave.drawJulia
14.1% 461 + 0 java.awt.image.BufferedImage.setRGB
10.0% 327 + 0 java.awt.image.PackedColorModel.equals
0.7% 20 + 2 java.awt.image.DirectColorModel.getDataElements
0.1% 2 + 0 java.awt.Color.<init>
97.1% 3175 + 2 Total compiled

Flat profile of 84.50 secs (4903 total ticks): AWT-Windows

Interpreted + native Method
100.0% 0 + 4902 sun.awt.windows.WToolkit.eventLoop
0.0% 0 + 1 sun.awt.windows.WToolkit.init
100.0% 0 + 4903 Total interpreted



From java -Xrunhprof:cpu=samples,depth=15, where "self" > 1.0%

CPU SAMPLES BEGIN (total = 400) Thu Jun 09 11:01:08 2005
rank self accum count trace method
1 47.00% 47.00% 188 300241 sun.awt.windows.WToolkit.eventLoop
2 22.00% 69.00% 88 300407 FracSave.iterateJul
3 6.00% 75.00% 24 300396 java.awt.image.DirectColorModel.getDataElements
4 4.25% 79.25% 17 300406 java.awt.image.DataBufferInt.<init>
5 2.50% 81.75% 10 300411 java.awt.image.PackedColorModel.equals
6 2.50% 84.25% 10 300405 java.lang.Thread.yield
7 2.25% 86.50% 9 300456 sun.awt.windows.WToolkit.shutdown
8 2.00% 88.50% 8 300414 java.awt.Color.darker
9 2.00% 90.50% 8 300408 FracSave.drawJulia
10 1.25% 91.75% 5 300410 java.awt.image.BufferedImage.setRGB

The major performance decrease seems to come from the event loop, I have MouseMotion and Key Listeners implemented to exit if there is any input (since it is a screensaver). Can I change the polling rate on the listeners? Removing them altogether reduces rendering time by approx. 50%, but that leaves me with the problem of having to alt-F4:ing from a screensaver, not very good

[William Brogden]

Can I change the polling rate on the listeners?

Polling? Listeners don't poll, they get events. If the mouse is not moving - no events. If removing listeners halves the rendering time, something strange is going on. What code executes for every listener event?
Bill

[Carl Pettersson]

Only a System.exit(0);, I'll rerun the tests under more controlled circumstances (and no running background processes).

/edit:
Avg. time to calculate drawJulia(0, 0) with 500 iterations:
With Listeners 2109.4
Without 2107.2

I can't have done everything right when I did it last time, not a significant difference there really.

[ June 09, 2005: Message edited by: Carl Pettersson ]
[ June 09, 2005: Message edited by: Carl Pettersson ]

[John Smith]

I would try using

setRGB(int startX, int startY, int w, int h, int[] rgbArray, int offset, int scansize)

instead of

setRGB(int x, int y, int rgb)


That is, instead of setting pixels one at a time, calculate them all in advance and display the entire image in a single method call. It must be faster.

[Ilja Preuss]

Originally posted by John Smith:
I would try using

setRGB(int startX, int startY, int w, int h, int[] rgbArray, int offset, int scansize)

instead of

setRGB(int x, int y, int rgb)


That is, instead of setting pixels one at a time, calculate them all in advance and display the entire image in a single method call. It must be faster.

Notice that frac already is a BufferedImage. I'd agree if he were drawing directly to the screen, but putting a buffer in front of a buffer is more likely to *decrease* performance, in my experience.

[Carl Pettersson]

Ilja: Is there any faster image class than BufferedImage? I got a recommendation to look at MemoryImageSource, but haven't got it to work properly yet, so I don't know if it's better.

Also, how much performance gain will I see with moving variable declarations outside the iteration methods?

/edit:
Looked a bit on the iteration, why is the first of these blocks approx 20% faster?

// Quicker
zrel = zre;
zre = zre*zre - zim*zim + cre;
zim = 2*zrel*zim + cim;
if((zre*zre + zim*zim) > 2.3) {
 break;
}
it++;
if(it >= maxIt) {
 break;
}

// Slower
a = zre * zre;
b = zim * zim;
if ((a + b) > 2.3) {
 break;
}
zrel = zre;
zre = a - b + cre;
c = zrel * zim;
zim = c + c + cim;
it++;
if(it >= maxIt) {
 break;
}

It seems odd, since the second version should reduce the number of calculations needed
[ June 14, 2005: Message edited by: Carl Pettersson ]

[Ilja Preuss]

Originally posted by Carl Pettersson:
Ilja: Is there any faster image class than BufferedImage?

Sorry, I don't know enough about this to give advice.

Also, how much performance gain will I see with moving variable declarations outside the iteration methods?

Moving declarations of local variables inside a method typically doesn't have any effect on the byte code. If you meant something else, I'd advise to try it...

Looked a bit on the iteration, why is the first of these blocks approx 20% faster?

Here's my guess: local variables reside on the stack or in a processor register. Calculations in a register are much faster than calculations done on the stack - depending on the processor, the variable content might even need to be moved from the stack to a register to operate on it. The second solution uses more local variables - probably more than fit into the processor's registers on the platform you are testing.

Which once again shows us that performance optimization is a more complicated job than it looks like at first sight, and that you need to back up your speculations with experimentation.

[Carl Pettersson]

Originally posted by Ilja Preuss:
Moving declarations of local variables inside a method typically doesn't have any effect on the byte code. If you meant something else, I'd advise to try it...

I meant as in making the variable a class variable like this

// from
void methodName {
int a;
// Do stuff
}
 
// to
int a;
void methodName {
// Do stuff
}

I thought it should be faster, since I don't really need to declare new variables for each iteration. Somewhere through moving variable declarations outside of methods to try it out, I did something wrong, and render time went up by 500% Can't figure out what it is, tried moving everything back in, but that didn't help anything...

[Ernest Friedman-Hill]

Declaring a variable takes essentially zero work -- the first five, especially, are free. But accessing a member variable is much more expensive than accessing a local; so much so that if a method is iterating over a large array, declaring a local variable that's initialized to point to the member array and then using that local can be a noticeable performance boost.

[Ilja Preuss]

Originally posted by Ernest Friedman-Hill:
Declaring a variable takes essentially zero work -- the first five, especially, are free.

And that's because an additional local variable just changes the size of the method's stack frame, which needs to be allocated anyway.