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

[Nick Roberts <nickrob at snap dot net dot nz>]

 > > > 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