Re: [Xen-devel] [PATCH 10/31] libxl: Crash (more sensibly) on malloc failure

[Ian Jackson <Ian.Jackson@xxxxxxxxxxxxx>]

Ian Campbell writes ("Re: [Xen-devel] [PATCH 10/31] libxl: Crash (more 
sensibly) on malloc failure"):
> On Wed, 2012-04-11 at 12:04 +0100, Ian Jackson wrote:
> > NB that libxl__ptr_add needs to be rewritten not to be quadratic in
> > the number of pointrs added (!)
> 
> Isn't it O(N) in numbers of pointers?

Yes, each addition is O(N).  Adding N pointers is O(N^2).

> I also just noticed that the initial:
>    /* fast case: we have space in the array for storing the pointer */
>     for (i = 0; i < gc->alloc_maxsize; i++) {
>         if (!gc->alloc_ptrs[i]) {
>             gc->alloc_ptrs[i] = ptr;
>             return 0;
>         }
>     }
> is a bit suboptimal since we never remove a ptr from the array, so we
> may as well track the max actually used. Then the fast path might
> actually be fast...

I thought we used to have a function for removing pointers from the gc
but I see that it has gone.  So yes this could be rewritten fairly
simply.

Ian.

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel