How do I optimize this postfix expression tree for speed?

Question

Thanks to the help I received in this post:

I have a nice, concise recursive function to traverse a tree in postfix order:

deque <char*> d;
void Node::postfix()
{
    if (left != __nullptr) { left->postfix(); } 
    if (right != __nullptr) { right->postfix(); } 
    d.push_front(cargo);
    return;
};

This is an expression tree. The branch nodes are operators randomly selected from an array, and the leaf nodes are values or the variable 'x', also randomly selected from an array.

char *values[10]={"1.0","2.0","3.0","4.0","5.0","6.0","7.0","8.0","9.0","x"};
char *ops[4]={"+","-","*","/"};

As this will be called billions of times during a run of the genetic algorithm of which it is a part, I'd like to optimize it for speed. I have a number of questions on this topic which I will ask in separate postings.

The first is: how can I get access to each 'cargo' as it is found. That is: instead of pushing 'cargo' onto a deque, and then processing the deque to get the value, I'd like to start processing it right away.

Edit: This question suggests that processing the deque afterwards is a better way.

I don't yet know about parallel processing in c++, but this would ideally be done concurrently on two different processors.

In python, I'd make the function a generator and access succeeding 'cargo's using .next().

See the above Edit.

But I'm using c++ to speed up the python implementation. I'm thinking that this kind of tree has been around for a long time, and somebody has probably optimized it already. Any Ideas? Thanks

Answer 1

Assuming that processing a cargo is expensive enough that locking a mutex is relatively cheap, you can use a separate thread to access the queue as you put items on it.

Thread 1 would execute your current logic, but it would lock the queue's mutex before adding an item and unlock it afterwards.

Then thread 2 would just loop forever, checking the size of the queue. If it's not empty, then lock the queue, pull off all available cargo and process it. Repeat loop. If no cargo available sleep for a short period of time and repeat.

If the locking is too expensive you can build up a queue of queues: First you put say 100 items into a cargo queue, and then put that queue into a locked queue (like the first example). Then start on a new "local" queue and continue.