Re: [PATCH] migration: savevm_state_insert_handler: constant-time element insertion

[Scott Cheloha]

On Thu, Oct 17, 2019 at 10:43:08AM +0200, Juan Quintela wrote:
> Scott Cheloha <address@hidden> wrote:
> 
> > Registering a SaveStateEntry object via savevm_state_insert_handler()
> > is an O(n) operation because the list is a priority queue maintained by
> > walking the list from head to tail to find a suitable insertion point.
> >
> > This adds considerable overhead for VMs with many such objects.  For
> > instance, ppc64 machines with large maxmem (8T+) spend ~10% or more of
> > their CPU time in savevm_state_insert_handler() before attempting to
> > boot a kernel.
> 
> Ouch ...
> 
> > If we track the head for each priority's subqueue we can insert new
> > elements in constant time.
> 
> We are adding a subqueue by priority, right? (see later comments)

One already exists.  This patch would just make insertion way, way
faster by memoizing the subqueue heads.

> > This commit also introduces a new function,
> > savevm_state_remove_handler(),
> 
> savevm_state_handler_remove()
> 
> search didn't find it O:-)

Whoops, my bad, will fix the commit message for v2.

> > which abstracts the logic for replacing the head of an element's subqueue
> > when removing it.
> 
> I think that it is better if you split the new function creation.  Make
> commit easier to write O:-)

Sure, I'll do that in the v2 patch in the next mail.

> >  static SaveState savevm_state = {
> >      .handlers = QTAILQ_HEAD_INITIALIZER(savevm_state.handlers),
> > +    .handler_pri_head = { [MIG_PRI_DEFAULT ... MIG_PRI_MAX] = NULL },
> 
> Why are you still maintaining the handlers QTAILQ?  Once here will not
> be easier to just change handlers field to be an array
> handlers[MIG_PRI_MAX] field, and adjust callers?
> 
> Changes are only inside this file.
> 
> The code to maintain the subqueue inside the other queue is just as
> complex as chaning all the callers.  What do you think?

I was trying to avoid churning the file more than absolutely
necessary.  There are 18 QTAILQ_FOREACH() loops in savevm.c right now.
Making ~15 of them double-loops doesn't make the code easier to read.

I think incurring slight complexity on insertion/removal to make
insertion fast is well worth the conceptual simplicity of addressing
one big list of elements for every other operation.

> savevm_state_handler_insert() for instance becomes even easier, just a
> QTALIQ_INSERT_TAIL() in the proper queue, right?

Yes, insertion becomes extremely obvious: you just append the element
to the tail of its priority queue, which must already exist.

But see above for the cost.

> I agree with the idea of the patch.  Especially when you told us how bad
> the performance of the current code is.
> 
> Out of curiosity, how many objects are we talking about?

At maxmem=8T I'm seeing about 40000 elements in that list.  At
maxmem=64T I'm seeing around 262000.  The vast majority of these
elements are "spapr_drc" objects, each of which (IIRC) corresponds to
a 256MB chunk of address space.