RE: [PATCH:MI] Return a subset of a variable object's children

Marc Khouzam
2008-05-01T14:22:30Z

> The double loop is O(N*N). I guess it could be reduced to O(N*log(N))
> using some kind of sorting algorithm.
>
> > To me, the advantage of your
> > patch is far larger in the fact that we no longer need to create all
> > children varObj at once; my impression is that the memory allocation is a
> > small optimization in caparison. Is that a correct impression? Besides,
> > currently, the memory is immediately allocated, so things wouldn't be any
> > worse :-)
>
>It's not just a question of memory allocation. It's computationally
>inefficient because Gdb has to traverse a large sparsely populated vector every
>time it operates on it. It wouldn't be any _worse_ than current Gdb, but I was
>trying to make it significantly _better_.

You are right. I was focusing on making the proposed algorithm more efficient
but I didn't think about the other uses of the vector of children.

So, as you mention above, keeping the vector ordered (without empty spaces),
can reduce to O(N*log(N)). If fact, I think it would be reduced to O(log(N))
since we would only need to find the location of the first new child; the position
of all other new children created in the same var-list-children can be determined
from that first position.
The expense would be in the insertion though, as the vector would have to be
mem-copied N times, one for each child that is not at the end of the vector.
I wonder if that is acceptable...

Marc