programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Rob Spoor
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Junilu Lacar
• Tim Cooke
Saloon Keepers:
• Tim Holloway
• Piet Souris
• Stephan van Hulst
• Tim Moores
• Carey Brown
Bartenders:
• Frits Walraven
• Himai Minh

# Drawing fractals

Ranch Hand
Posts: 73
• Number of slices to send:
Optional 'thank-you' note:
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:

Any obvious ways to improve this?

I suspect I could gain some time by optimizing the access to the image. Code:
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

Greenhorn
Posts: 11
• Number of slices to send:
Optional 'thank-you' note:
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

Ranch Hand
Posts: 1071
• Number of slices to send:
Optional 'thank-you' note:
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.

author and iconoclast
Posts: 24203
44
• Number of slices to send:
Optional 'thank-you' note:

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.

Ranch Hand
Posts: 73
• Number of slices to send:
Optional 'thank-you' note:
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

Author and all-around good cowpoke
Posts: 13078
6
• Number of slices to send:
Optional 'thank-you' note:

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

Ranch Hand
Posts: 73
• Number of slices to send:
Optional 'thank-you' note:
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 ]

Ranch Hand
Posts: 2937
• Number of slices to send:
Optional 'thank-you' note:
I would try using

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

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.

author
Posts: 14112
• Number of slices to send:
Optional 'thank-you' note:

Originally posted by John Smith:
I would try using

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

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.

Ranch Hand
Posts: 73
• Number of slices to send:
Optional 'thank-you' note:
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?

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

Ilja Preuss
author
Posts: 14112
• Number of slices to send:
Optional 'thank-you' note:

Ilja: Is there any faster image class than BufferedImage?

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.

Ranch Hand
Posts: 73
• Number of slices to send:
Optional 'thank-you' note:

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

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
author and iconoclast
Posts: 24203
44
• Number of slices to send:
Optional 'thank-you' note:
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
author
Posts: 14112
• Number of slices to send:
Optional 'thank-you' note:

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.