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

Nick Roberts
2008-05-01T12:06:26Z

> > > Also, the double loop may prove to be slow for large number of children.
> >
> > I was thinking that only a small number of children would ever exist
> > simultaneously. Scrolling might make that a larger number but maybe
> > it could be arranged to delete children that go out of view.
>
> You are right, we do that in DSF-GDB. However, such a double loop can become
> prohibitive relatively quickly, at numbers lower than when children start
> being deleted. For example, DSF-GDB allows for 1000 varObjs simultaneously,
> before doing any deletion. This may not prove too slow, but it creates
> a requirement on the frontend to do proper management of varObjects, to
> avoid any issues. If we can avoid the double loop (and its string
> comparisons), we would benefit, no?

The double loop is O(N*N). I guess it could be reduced to O(N*log(N))
using some kind of sorting algorithm.

> > > I was thinking that we could keep order of children as they are defined
> > > (current behaviour) but not fill them all, until requested.
> > > We could create the full Vector of children as is done now by
> > >
> > > while (VEC_length (varobj_p, var->children) < var->num_children)
> > > VEC_safe_push (varobj_p, var->children, NULL);
> >
> > I guess this would remove the need for a second loop but it seems wasteful
> > on memory. Previously children variable objects were stored as a linked
> > list and, as I have said before, I do think this is more suitable as
> > objects can then be inserted and removed at any point in the sequence of
> > children.
>
> Yes, linked list seem more suited for this usecase. But I gather from
> Volodya's emails that vectors have benefits that we should not ignored, so
> let's continue the discussion with vectors. 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_.

> > > We can even improve on that by doing the following: instead of
> > > allocating the vector for all children, we can allocate the vector for
> > > the children up to start+number*stride.
> >
> > The variables start, number and stride might be selectable by the user but
> > I'm thinking that "number" used by Gdb will be controlled by how many
> > elements are visible on the screen. What happens with your approach when
> > new elements become visible and new children need to be created?
>
> Here is a simplified example. Say you have an array of a 1000 integers and
> we can show 10 elements on the screen. The user 'opens' the array,
> revealing the first 10 elements. The user then jumps-scrolls to position
> 500 revealing postions 500 to 509. I imagine a set of commands to be
> something like this:
>
> -var-list-children -f 0 -n 10 var1
> -var-list-children -f 500 -n 10 var1
>
> The first call to var-list-children would allocate a vector of size (number+start = 0+10).
> And create those 10 children varObjs.
> The second call would expand that vector to a size of (number+start = 500+10).
> And create those 10 children varObjs.
> Positions 10 to 499 would remain NULL since we haven't create the children yet (and we may
> never create them, if the user does not scroll there.)
>
> Is that what you were asking?

It looks like it's only a big saving if the user never moves far from the
start of the array.

--
Nick http://www.inet.net.nz/~nickrob