Using iterators and efficiency.

[Jason]

In C++, but this applies to other languages:

I have two types of node that contain lists of other nodes, their
representation internally is different. I therefore have implemented
iterators.

GetIterator() returns a pointer to the correct iterator for a node.
Unfortunaly I process thousands of nodes, and hence I do thousands of
allocations and deallocations of iterators (which only live a short time
anyway), which slows things down somewhat. Is there a good way round this.

I have thought of getting my nodes to simply inherit their iterator
functionality and then to just use the node as an iterator; this means only
one iteration can proceed at a time - but there is no creation and
destruction of iterators all the time.

C++ Sample:

while ( queue.empty() == false ) // Process items in the queue
{
TrieNode *n = queue.front();
queue.pop();
auto_ptr< TrieIterator > i( n->GetIterator() ); // Create iterator here.

while (!i->isDone())
{
TransitionMap m = i->Current();
if ( m.dest )
{
TrieNode *child = m.dest;
child->SetFail( FindFail(n, m.c) );
queue.push(child);
}
i->Next();
}
}

[Jason]

<rogojel@index.hu> wrote in message
news:c8b850dd.0401160753.22b87ec3@posting.google.com...
> Hi Jason,
> how confident are you that the slow-down is due to the iterator
> creation/destruction? Did you do any profiling on this?
>
> There is a high risk of getting it wrong when people go by their
> intuition in optimizations, instead of using measurements.
>
> I do not mean you did not - just asking.
> Regards

Well reasonably confident, although I havn't done proper measurements. I
posted this question in comp.object becuase there wern't any replies to this
question.

I also have the concern that memory could be fragmented, and perhaps
allocating several thosand iterators seems 'untidy'. Suggestions include:
using functors (aka callback type arangement). One at a time iteration,
provided by the node class, and implicit iteration, whereby the iteration is
controll by the iterator, and thus can maintain it's state on the stack.

[rogojel@index.hu]

Hi Jason,
how confident are you that the slow-down is due to the iterator
creation/destruction? Did you do any profiling on this?

There is a high risk of getting it wrong when people go by their
intuition in optimizations, instead of using measurements.

I do not mean you did not - just asking.
Regards

[Jason]

<rogojel@index.hu> wrote in message
news:c8b850dd.0401190106.6f1aaa62@posting.google.com...
> Just some more questions - there seem to be more (maybe a lot more)
> TransitionMaps that are created and destroyed then iterators. Just as
> a first shot I'd also wonder about the fate of the popped nodes -
> where do they get destroyed?
>
> Nevertheless, it could be the iterators, but before implementing
> anything I'd really make sure that I have the data to back the plan
> up.
>
> Regards

See comp.object if you will, there has been a good old discussion about this
iterator problem.

One TransitionMaps is allocated with the iterator object - it's a private
member. ( So really the iterator doesn't give you anything permanat back -
i.e. you're not allowed to keep the reference to the map after its gone.
Could copy it though with assignment.

The popped nodes are still parts of the entire Trie structure. The stack
mechanism is for either (1) deleting the nodes, or in the sample I gave (2)
working out all the failure states for the nodes by searching for common
prefixes. It's an Aho-Corasick tree, and the code for computing failure
states is in most litrature on the subject.

[Jason]

The reason I say allocating iterators is slow is because I had the self same
algorithm, but using a case statement to switch on object type and iterate
depending on what sort of object it was. This was a few seconds faster -
besides the speed, it doesn't seem good to allocate iterators just to get
polymorphism in this sort of case.

[rogojel@index.hu]

Just some more questions - there seem to be more (maybe a lot more)
TransitionMaps that are created and destroyed then iterators. Just as
a first shot I'd also wonder about the fate of the popped nodes -
where do they get destroyed?

Nevertheless, it could be the iterators, but before implementing
anything I'd really make sure that I have the data to back the plan
up.

Regards