[Qemu-devel] Re: [PATCH 1/4] Add a scatter-gather list type and accessors

[Avi Kivity]

Anthony Liguori wrote:
> > malloc() will never fail on Linux with overcommit enabled; since 
> > Linux is fairly useless without overcommit, it means you'll never see 
> > a failure.
>
> Sure it will.  You just have to run out of VA space.

That's not recoverable, and is certainly a qemu bug if it happens.  
Especially on 47-bit hosts.

> > > > I expect this to trigger rarely since the allocation hint should 
> > > > suffice nearly 100% of the time.  But in case we miss, it's better 
> > > > to reallocate as little as possible.
> > > >
> > > > (what I really want is std::vector<>)
> > >
> > > Which I'm pretty sure has a linear growth strategy :-)
> >
> > Not in any of the implementations I'm familiar with.  I believe 
> > std::vector<> is required to have amortized O(1) append operations.
>
> Linear growth doesn't imply element-by-element growth.  You can have a 
> coefficient > 1.

If you have a coefficient, then it's exponential growth, even if it's 
less than two.  If you have an addition, then it's linear growth, even 
if the addend is greater than one.

 size *= k -> exponential
 size += k -> linear


--
I have a truly marvellous patch that fixes the bug which this
signature is too narrow to contain.