Talk:Toad/Tree Code

From old wiki

I haven't looked at the code in any real concept analysis but it seems like a nice system. Some code details that might or might not have an impact:

• Your threading flags are not thread safe. Meaning that you can very well have threads running at the same time that you are trying to prevent from running at the same time. They are booleans so the writes and reads to them are atomic but the differents threads views of them are not synchronized.
• Busy wait. You have at least one busy wait in there (while(addingInProcess){};

). It uses valuable CPU time and could have a big effect on RR@Home performance (time wise) if it isn't a very rare case. Regardless it is bad practice.

• Thread priorities, now this is a complicated matter, possbly having different effects on different platforms too. Could also cause starvation and combined with the busy wait above could have some nasty side effects. It could also have changed the busy wait to be less of a problem (but far from solving it). I would not make use of the thread priorities myself. Rather some systme of only doing the lower priority stuff if some condition is met. Such as: "Haven't run the rebuild in a while/since a certain number of inserts" etc.
• Are nodes and leafs thread safe somehow? It is harder to see directly from the code as it might be on a higher level. The buffer Vector is thread safe but that only helps when modifying the actual buffer (add and remove).
• A very minor thing, the following can be replaced with one statement:

Leaf leaf = (Leaf)buffer.get(0);
buffer.remove(leaf);

Could instead be written as:

Leaf leaf = (Leaf)buffer.remove(0);

-- Pulsar

Thanks for the feedback.

• I will synchronise those flags for the next version.
• I knew about the busy wait, but it shouldn't be a problem the way I use the tree it was just a precaution. I launch the rebuild operation just once at the beginning of the round so there should not be any leaf to add before it starts. The only case where it would happen would be if at the end of the previous round one leaf was remaining in the buffer.
• Thread priorities, well I was not that keen on using them either. I put them in so I would not have to restart the adding thread (treeThread), this allowed me to have a single thread running for it. The priorities prevent the thread from using too much CPU time when there is nothing to do. I guess I could restart the thread when I have a new entry and the thread is not running. The rebuildThread is just run once at the beginning of each round, thread priority here was just used to make the tree available sooner.
• Nodes and leaf are not thread safe. But there is only two threads operating on the tree either treeThread or rebuildThread, I made sure with the flags that only one them operate on the tree, I dont want to put flags inside the tree structure. The buffer is used by the main thread of the robot to add leaves in it and treeThread remove them.
• Ok I'll change that.

-- Florent

Ahh you are just rebuilding once in every round, that explains it. Regarding the flags, it would work if you made them volatile if everyone was using a java 5 VM or later. Now I'm afraid you indeed have to synchronize :( -- Pulsar