Question about threading

[SuF]

Hey anyone with knowledge of threads, I need some help (aka I'm too lazy to use Google). I've got this code from my fractal program (only giving a small chunk because the whole program is fairly large)

public void iterate()
    {
        ArrayList<Square> temp = new ArrayList<Square>();
        for (int a = squares.size() - 1; a >= 0; a--)
        {
            Square[] b = squares.get(a).iterate();
            for (Square c : b)
            {
                temp.add(c);
            }
            squares.remove(a);
        }
        squares = temp;
    }

Now, every time the fractal is changed I need to reset it (which just erases the ArrayList squares and puts back the initial seed square into it) and iterate back up to the iteration number that the fractal is on (up to 9 times).

The only speed issue on my computer (fairly good i7) is that when you go to undo multiple things it lags up (because with each undo it has to clear the fractal and iterate 9 times if I'm looking at the 9th generation which is default).

What I'm thinking is that if I create another method iterate(int gen) that will iterate from the start (aka reset the fractal) to the generation (number of iterations) I give in gen, I could split it into a number of different threads on like the 2nd or third generation where there will be like 4 or 16 squares. Then each of those 4 to 16 threads would iterate one square, which turns into 4 and then those 4, etc, etc until it is finished.

I'm not sure it will improve speed (which is really fast anyways) but I'd love to make it just a bit faster to stop the catch on undo. Anyone want to explain the general gist of how I'd go about doing that? I've never really worked with threads before so I really only have a slight clue on what the hell I'm doing.

Thanks

 

[The Fat Controller]

Here's how I'd do it:

Make a class MyThread that extends Thread, which takes a Square and returns a collection of Squares.

Create a queue with just the seed Square in it, and have each MyThread object popping the front of the queue for a Square with a depth property less than the depth limit. The Squares that your MyThreads return go on the back of the queue.

When the front of the queue has a Square where depth property == depth limit, then you're done.

There might be concurrency issues with multiple threads taking the same Square off the front of the queue and things like that, so you'd need to use a threadsafe queue. ConcurrentLinkedQueue looks like one.

 

[SuF]

I've never used a queue before so I didn't even think of that but it seems like a good idea. What is this depth property your talking about? There really isn't a way to determine how many Squares there will end up being in the end (since sometimes a Square will not split into 4 Squares), if that is what you were talking about.

 

[Nullware]

I would say don't do threading yet because you don't absolutely need to. It's a pain and also it implies that you have tried everything else and you already have the optimal single-threaded solution to the problem at hand.

I modified part of your iterate() function to be somewhat more efficient. Behavior seems to be the same as before. Hopefully it's enough or at least it helps you in looking for other performance related issues.

    public void iterate()
    {
        ArrayList<Square> temp = new ArrayList<Square>();
        int length = squares.size()-1;
        // Having the condition of a for loop be a function's return value that is always changing is expensive
        // this means the function must be called at each loop iteration since the condition can't be cached
        for (int a = 0; a <= length; a++)
        {  
            // Index from the back of the array since we are counting up now
            Square[] b = squares.get(length - a).itterate();
            for(Square c: b)
            {
                temp.add(c);
            }
            // We don't need to remove any elements from squares since we just figure out which one to take next
           // remove() is arguably expensive because of the number of times it is called and it is working with a dynamic list structure
            //squares.remove(a);
        }
        squares = temp;
    }

 

[The Fat Controller]

I meant depth like in a tree data structure. So the seed would have depth 0, children of the seed depth 1, grandchildren depth 2 etc.

You could put the Squares that were done splitting into some results array, and only keep Squares that still needed splitting in the queue that your threads would be working with.

 

[SuF]

I think I understand what Fat Controller is saying...? Put another variable into each Square that says what generation it is in and as they hit 9th (Or whatever) throw them into the done array. Or am I making shit up?

@Nullware

I didn't even really try to make it more efficient. I forgot I had just copied and pasted it from my old code I threw together a year ago. I did some tests and iterating to the 9th gen takes about 2 ms. I did it 100 times and yours saves about 10-20 ms over the 100 loops of iterating to 9.

Since its so fast to get to 9, I'm thinking that if you undo like 9000 times quickly, the bottleneck is painting the fractal onto the canvas and not actually iterating the fractal.

 

[Nullware]

I think I understand what Fat Controller is saying...? Put another variable into each Square that says what generation it is in and as they hit 9th (Or whatever) throw them into the done array. Or am I making shit up?

@Nullware

I didn't even really try to make it more efficient. I forgot I had just copied and pasted it from my old code I threw together a year ago. I did some tests and iterating to the 9th gen takes about 2 ms. I did it 100 times and yours saves about 10-20 ms over the 100 loops of iterating to 9.

Since its so fast to get to 9, I'm thinking that if you undo like 9000 times quickly, the bottleneck is painting the fractal onto the canvas and not actually iterating the fractal.

If that's the case then the real question becomes should you really be painting that often?

Maybe only paint when it's reached the final step or something since seeing the intermediate steps is arguably not that useful.

 

[SuF]

If that's the case then the real question becomes should you really be painting that often?

Maybe only paint when it's reached the final step or something since seeing the intermediate steps is arguably not that useful.

Well the idea is that you hit undo and it undoes the last change to the fractal. I think making it so that if you hit undo multiple times in rapid success, it waits to paint until all the undo's are done seems like too much of a hassle just to make it not hang for the half second it does.

 

[mrjohnson]

Coming from a professional programmer you don't need threads for this specific situation and I would probably stay away from threads unless really necessary for your purpose and starting with the speed issue I'd recommend not using any method calls in the definition of a for loop

do you understand what you're doing when you say

int i = squares.size();

you are calling a method that goes and grabs this item for you which could be a "BIG" pain in the ass why don't you just say

int i = squares.size();

for( i; blah; blah--){}

much easier

 

[SuF]

Coming from a professional programmer you don't need threads for this specific situation and I would probably stay away from threads unless really necessary for your purpose and starting with the speed issue I'd recommend not using any method calls in the definition of a for loop

do you understand what you're doing when you say

int i = squares.size();

you are calling a method that goes and grabs this item for you which could be a "BIG" pain in the ass why don't you just say

int i = squares.size();

for( i; blah; blah--){}

much easier

I actually tried doing basically that. Didn't save any time at all.

 

[super_]

        int length = squares.size()-1;
        [color=red]// Having the condition of a for loop be a function's return value that is always changing is expensive
        // this means the function must be called at each loop iteration since the condition can't be cached[/color]
        for (int a = 0; a <= length; a++)
        {  
            ...

Erm... what?
First, I advise you to look here, at the Content Creation Wiki, for a look at what we're covering.

From what I can see, the loop condition has no method call:

for (int a = squares.size() - 1; [color=red]a >= 0;[/color] a--)

Not only that, but your "optimization" actually produces slower raw code... firstly, your code creates two local variables to use in the loop statement rather than only one; in addition, your condition each time checks one local variable against another, which is far more expensive than the original check that only checks one local variable against 0.
Compare SuF's original:

L_head:
    aload_1
    invokevirtual java/util/ArrayList.size:()I
    iconst_1
    isub
    istore_2
    goto L_cond
L_body:
    ...
    iinc 2,-1
L_cond:
    iload_2
    ifge L_body

... to yours:

    aload_1
    invokevirtual java/util/ArrayList.size:()I
    iconst_1
    isub
    istore_2
L_head:
    iconst_0
    istore_3
    goto L_cond
L_body:
    ...
    iinc 3,1
L_cond:
    iload_3
    iload_2
    if_icmple L_body

All-in-all, however, pedantic premature peep-hole micro-optimizations (like what you thought you were doing) have very little effect seeing as the JVM (including the JIT compiler) do dynamic runtime analysis which is far more effective than the gains you tried to make here. Don't waste your time... to quote Donald Knuth: 97% of the time, premature optimization is the root of all evil.