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

[Juan Quintela <quintela@redhat.com>]

Scott Cheloha <cheloha@linux.vnet.ibm.com> wrote:

Hi

> 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)

> This commit also introduces a new function,
> savevm_state_remove_handler(),

savevm_state_handler_remove()

search didn't find it O:-)

> 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:-)


>  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?

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


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?

Later, Juan.