| Message ID | 1415963522-5255-2-git-send-email-pbonzini@redhat.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Fri, 14 Nov 2014 12:12:00 +0100 Paolo Bonzini <pbonzini@redhat.com> wrote: > This completes the optimization from the previous patch, by > removing the KVM_MEM_SLOTS_NUM-iteration loop from insert_memslot. > > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> > --- > virt/kvm/kvm_main.c | 39 +++++++++++++++++++-------------------- > 1 file changed, 19 insertions(+), 20 deletions(-) > > diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c > index c0c2202e6c4f..c8ff99cc0ccb 100644 > --- a/virt/kvm/kvm_main.c > +++ b/virt/kvm/kvm_main.c > @@ -677,31 +677,30 @@ static int kvm_create_dirty_bitmap(struct > kvm_memory_slot *memslot) static void insert_memslot(struct > kvm_memslots *slots, struct kvm_memory_slot *new) > { > - int i = slots->id_to_index[new->id]; > - struct kvm_memory_slot *old = id_to_memslot(slots, new->id); > + int id = new->id; > + int i = slots->id_to_index[id]; > struct kvm_memory_slot *mslots = slots->memslots; > > - if (new->npages == old->npages) { > - *old = *new; > - return; > - } > - > - while (1) { > - if (i < (KVM_MEM_SLOTS_NUM - 1) && > - new->npages < mslots[i + 1].npages) { > - mslots[i] = mslots[i + 1]; > - i++; > - } else if (i > 0 && new->npages > mslots[i - > 1].npages) { > - mslots[i] = mslots[i - 1]; > - i--; > - } else { > - mslots[i] = *new; > - break; > + WARN_ON(mslots[i].id != id); > + if (new->npages != mslots[i].npages) { > + while (1) { > + if (i < (KVM_MEM_SLOTS_NUM - 1) && > + new->npages < mslots[i + 1].npages) { > + mslots[i] = mslots[i + 1]; > + slots->id_to_index[mslots[i].id] = i; > + i++; > + } else if (i > 0 && > + new->npages > mslots[i - > 1].npages) { > + mslots[i] = mslots[i - 1]; > + slots->id_to_index[mslots[i].id] = i; > + i--; > + } else > + break; > } > } > > - for (i = 0; i < KVM_MEM_SLOTS_NUM; i++) > - slots->id_to_index[slots->memslots[i].id] = i; > + mslots[i] = *new; > + slots->id_to_index[mslots[i].id] = i; > } > > static void update_memslots(struct kvm_memslots *slots, Reviewed-by: Igor Mammedov <imammedo@redhat.com> -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
2014-11-14 12:12+0100, Paolo Bonzini: > This completes the optimization from the previous patch, by > removing the KVM_MEM_SLOTS_NUM-iteration loop from insert_memslot. > > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> > --- > virt/kvm/kvm_main.c | 39 +++++++++++++++++++-------------------- > 1 file changed, 19 insertions(+), 20 deletions(-) > > diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c > index c0c2202e6c4f..c8ff99cc0ccb 100644 > --- a/virt/kvm/kvm_main.c > +++ b/virt/kvm/kvm_main.c > @@ -677,31 +677,30 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot) > static void insert_memslot(struct kvm_memslots *slots, > struct kvm_memory_slot *new) > { > - int i = slots->id_to_index[new->id]; > - struct kvm_memory_slot *old = id_to_memslot(slots, new->id); > + int id = new->id; > + int i = slots->id_to_index[id]; > struct kvm_memory_slot *mslots = slots->memslots; > > - if (new->npages == old->npages) { > - *old = *new; > - return; > - } > - > - while (1) { > - if (i < (KVM_MEM_SLOTS_NUM - 1) && > - new->npages < mslots[i + 1].npages) { > - mslots[i] = mslots[i + 1]; > - i++; > - } else if (i > 0 && new->npages > mslots[i - 1].npages) { > - mslots[i] = mslots[i - 1]; > - i--; > - } else { > - mslots[i] = *new; > - break; > + WARN_ON(mslots[i].id != id); > + if (new->npages != mslots[i].npages) { > + while (1) { > + if (i < (KVM_MEM_SLOTS_NUM - 1) && > + new->npages < mslots[i + 1].npages) { (^^^^ whitespace error) > + mslots[i] = mslots[i + 1]; > + slots->id_to_index[mslots[i].id] = i; > + i++; > + } else if (i > 0 && > + new->npages > mslots[i - 1].npages) { > + mslots[i] = mslots[i - 1]; > + slots->id_to_index[mslots[i].id] = i; > + i--; > + } else > + break; We are replacing in a sorted array, so the the direction of our traversal doesn't change, (and we could lose one tab level here,) if (new->npages < mslots[i].npages) { while (i < (KVM_MEM_SLOTS_NUM - 1) && new->npages < mslots[i + 1].npages) { mslots[i] = mslots[i + 1]; slots->id_to_index[mslots[i].id] = i; i++; } else if (new->npages > mslots[i].npages) while (i > 0 && new->npages > mslots[i - 1].npages) { mslots[i] = mslots[i - 1]; slots->id_to_index[mslots[i].id] = i; i--; } (I guess you don't want me to abstract these two loops further :) If the probability of slots with same npages was high, we could also move just the last one from each group, but I think that the current algorithm is already faster than we need. (We'll have to change it into an interval tree, or something, if the number of slots rises anyway.) -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Fri, 14 Nov 2014 14:35:00 +0100 Radim Kr?má? <rkrcmar@redhat.com> wrote: > 2014-11-14 12:12+0100, Paolo Bonzini: > > This completes the optimization from the previous patch, by > > removing the KVM_MEM_SLOTS_NUM-iteration loop from insert_memslot. > > > > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> > > --- > > virt/kvm/kvm_main.c | 39 +++++++++++++++++++-------------------- > > 1 file changed, 19 insertions(+), 20 deletions(-) > > > > diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c > > index c0c2202e6c4f..c8ff99cc0ccb 100644 > > --- a/virt/kvm/kvm_main.c > > +++ b/virt/kvm/kvm_main.c > > @@ -677,31 +677,30 @@ static int kvm_create_dirty_bitmap(struct > > kvm_memory_slot *memslot) static void insert_memslot(struct > > kvm_memslots *slots, struct kvm_memory_slot *new) > > { > > - int i = slots->id_to_index[new->id]; > > - struct kvm_memory_slot *old = id_to_memslot(slots, > > new->id); > > + int id = new->id; > > + int i = slots->id_to_index[id]; > > struct kvm_memory_slot *mslots = slots->memslots; > > > > - if (new->npages == old->npages) { > > - *old = *new; > > - return; > > - } > > - > > - while (1) { > > - if (i < (KVM_MEM_SLOTS_NUM - 1) && > > - new->npages < mslots[i + 1].npages) { > > - mslots[i] = mslots[i + 1]; > > - i++; > > - } else if (i > 0 && new->npages > mslots[i - > > 1].npages) { > > - mslots[i] = mslots[i - 1]; > > - i--; > > - } else { > > - mslots[i] = *new; > > - break; > > + WARN_ON(mslots[i].id != id); > > + if (new->npages != mslots[i].npages) { > > + while (1) { > > + if (i < (KVM_MEM_SLOTS_NUM - 1) && > > + new->npages < mslots[i + > > 1].npages) { > (^^^^ whitespace error) > > + mslots[i] = mslots[i + 1]; > > + slots->id_to_index[mslots[i].id] = > > i; > > + i++; > > + } else if (i > 0 && > > + new->npages > mslots[i - > > 1].npages) { > > + mslots[i] = mslots[i - 1]; > > + slots->id_to_index[mslots[i].id] = > > i; > > + i--; > > + } else > > + break; > > We are replacing in a sorted array, so the the direction of our > traversal doesn't change, (and we could lose one tab level here,) > > if (new->npages < mslots[i].npages) { > while (i < (KVM_MEM_SLOTS_NUM - 1) && > new->npages < mslots[i + 1].npages) { > mslots[i] = mslots[i + 1]; > slots->id_to_index[mslots[i].id] = i; > i++; > } > else if (new->npages > mslots[i].npages) > while (i > 0 && > new->npages > mslots[i - 1].npages) { > mslots[i] = mslots[i - 1]; > slots->id_to_index[mslots[i].id] = i; > i--; > } > > (I guess you don't want me to abstract these two loops further :) > > If the probability of slots with same npages was high, we could also > move just the last one from each group, but I think that the current > algorithm is already faster than we need. > > (We'll have to change it into an interval tree, or something, if the > number of slots rises anyway.) Only if it rises to huge amount, I've played with proposed 512 memslots and it takes ~10000 cycles which is 5% of current heapsort overhead. Taking in account that it's slow path anyway, it's unlikely that there would be need to speedup this case even more. -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 14/11/2014 14:35, Radim Kr?má? wrote: > We are replacing in a sorted array, so the the direction of our > traversal doesn't change, (and we could lose one tab level here,) > > if (new->npages < mslots[i].npages) { > while (i < (KVM_MEM_SLOTS_NUM - 1) && > new->npages < mslots[i + 1].npages) { > mslots[i] = mslots[i + 1]; > slots->id_to_index[mslots[i].id] = i; > i++; > } > else if (new->npages > mslots[i].npages) > while (i > 0 && > new->npages > mslots[i - 1].npages) { > mslots[i] = mslots[i - 1]; > slots->id_to_index[mslots[i].id] = i; > i--; > } > > (I guess you don't want me to abstract these two loops further :) Right. You do not need the "else if" as long as you keep the outer "if (new->npages != mslots[i].npages)". > (We'll have to change it into an interval tree, or something, if the > number of slots rises anyway.) I don't think that's needed, actually. gfn_to_page and gfn_to_memslot are very rarely in the profiles with EPT. Paolo -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
2014-11-14 15:17+0100, Igor Mammedov: > > (We'll have to change it into an interval tree, or something, if the > > number of slots rises anyway.) > Only if it rises to huge amount, I've played with proposed 512 memslots > and it takes ~10000 cycles which is 5% of current heapsort overhead. > Taking in account that it's slow path anyway, it's unlikely that there > would be need to speedup this case even more. Yes, your improvement is great and would work even for higher amounts. I meant that our lookup is currently pretty sad -- O(N) that is presumably optimized by looking at the largest regions first. Maybe we would benefit from O(log N) lookup even with 128 memslots. -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 14/11/2014 15:41, Radim Kr?má? wrote: > Yes, your improvement is great and would work even for higher amounts. > > I meant that our lookup is currently pretty sad -- O(N) that is > presumably optimized by looking at the largest regions first. Yes, that's the optimization. > Maybe we would benefit from O(log N) lookup even with 128 memslots. Maybe, but the common case so far is about 10, and all but two of them are only used at boot time. :) Perhaps we could add a one-item MRU cache, that could help lookups a bit. That's what QEMU does too, by the way. It used to sort the list in MRU-to-LRU order, but that wasn't too thread-friendly so it was switched to biggest-to-smallest (with inspiration taken from KVM). Paolo -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
2014-11-14 15:29+0100, Paolo Bonzini: > On 14/11/2014 14:35, Radim Kr?má? wrote: > > We are replacing in a sorted array, so the the direction of our > > traversal doesn't change, (and we could lose one tab level here,) > > > > if (new->npages < mslots[i].npages) { > > while (i < (KVM_MEM_SLOTS_NUM - 1) && > > new->npages < mslots[i + 1].npages) { > > mslots[i] = mslots[i + 1]; > > slots->id_to_index[mslots[i].id] = i; > > i++; > > } > > else if (new->npages > mslots[i].npages) > > while (i > 0 && > > new->npages > mslots[i - 1].npages) { > > mslots[i] = mslots[i - 1]; > > slots->id_to_index[mslots[i].id] = i; > > i--; > > } > > > > (I guess you don't want me to abstract these two loops further :) > > Right. You do not need the "else if" as long as you keep the outer "if > (new->npages != mslots[i].npages)". True, I'm just an indentation hater. > > (We'll have to change it into an interval tree, or something, if the > > number of slots rises anyway.) > > I don't think that's needed, actually. gfn_to_page and gfn_to_memslot > are very rarely in the profiles with EPT. Ah, that replaces my reply to Igor, thanks. -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/virt/kvm/kvm_main.c b/virt/kvm/kvm_main.c index c0c2202e6c4f..c8ff99cc0ccb 100644 --- a/virt/kvm/kvm_main.c +++ b/virt/kvm/kvm_main.c @@ -677,31 +677,30 @@ static int kvm_create_dirty_bitmap(struct kvm_memory_slot *memslot) static void insert_memslot(struct kvm_memslots *slots, struct kvm_memory_slot *new) { - int i = slots->id_to_index[new->id]; - struct kvm_memory_slot *old = id_to_memslot(slots, new->id); + int id = new->id; + int i = slots->id_to_index[id]; struct kvm_memory_slot *mslots = slots->memslots; - if (new->npages == old->npages) { - *old = *new; - return; - } - - while (1) { - if (i < (KVM_MEM_SLOTS_NUM - 1) && - new->npages < mslots[i + 1].npages) { - mslots[i] = mslots[i + 1]; - i++; - } else if (i > 0 && new->npages > mslots[i - 1].npages) { - mslots[i] = mslots[i - 1]; - i--; - } else { - mslots[i] = *new; - break; + WARN_ON(mslots[i].id != id); + if (new->npages != mslots[i].npages) { + while (1) { + if (i < (KVM_MEM_SLOTS_NUM - 1) && + new->npages < mslots[i + 1].npages) { + mslots[i] = mslots[i + 1]; + slots->id_to_index[mslots[i].id] = i; + i++; + } else if (i > 0 && + new->npages > mslots[i - 1].npages) { + mslots[i] = mslots[i - 1]; + slots->id_to_index[mslots[i].id] = i; + i--; + } else + break; } } - for (i = 0; i < KVM_MEM_SLOTS_NUM; i++) - slots->id_to_index[slots->memslots[i].id] = i; + mslots[i] = *new; + slots->id_to_index[mslots[i].id] = i; } static void update_memslots(struct kvm_memslots *slots,
This completes the optimization from the previous patch, by removing the KVM_MEM_SLOTS_NUM-iteration loop from insert_memslot. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> --- virt/kvm/kvm_main.c | 39 +++++++++++++++++++-------------------- 1 file changed, 19 insertions(+), 20 deletions(-)