[Ltrace-devel] [RFC 1/5] vect: Fix vect_reserve for large count

[Edgar E. Iglesias]

On Fri, Oct 05, 2012 at 06:38:17PM +0200, Petr Machata wrote:
> edgar.iglesias at gmail.com writes:
> 
> >  vect_reserve(struct vect *vec, size_t count)
> >  {
> >  	if (count > vec->allocated) {
> > -		size_t na = vec->allocated != 0 ? 2 * vec->allocated : 4;
> > +		/* Allocate 4 extra slots for growth.  */
> > +		size_t na = count + 4;
> >  		void *n = realloc(vec->data, na * vec->elt_size);
> >  		if (n == NULL)
> >  			return -1;
> 
> That changes performance characteristics of vect_pushback from O(1) to
> O(n).  What problem are you seeing that is fixed by this?
> 
> If we are that memory-tight, perhaps we could have a call like
> vect_done, which would allocate a new buffer with exact number of slots,
> copy stuff there, and release the old buffer (or keep it around for next
> vect_init?).  Or there could be a separate ctor taking slot count as an
> argument, which we would use to pre-allocate things like value arrays,
> where we have a guess on the number of elements.  It depends on what
> problem you are trying to solve.

Hi,

I traced a few large binaries and the largest count I've seen so far
is 6. Im mostly concerned with fixing the the bug when count ends up
beeing smaller than vec->allocated. If we change the base from 4 to
8, we'd probably not use the reallocation path very often.

Feel free to drop my patch and just edit in whatever fix you prefer.

Cheers