On Thu, Oct 17, 2019 at 10:43:08AM +0200, Juan Quintela wrote:
> Scott Cheloha <chel...@linux.vnet.ibm.com> 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.
