Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the insertion sort
On Fri, 14 Nov 2014 12:12:00 +0100
Paolo Bonzini pbonz...@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 pbonz...@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 imamm...@redhat.com
--
To unsubscribe from this list: send the line unsubscribe kvm in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the insertion sort
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 pbonz...@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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the insertion sort
On Fri, 14 Nov 2014 14:35:00 +0100
Radim Krčmář rkrc...@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 pbonz...@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 ~1 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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the insertion sort
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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the insertion sort
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 ~1 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the insertion sort
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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 1/3] kvm: memslots: track id_to_index changes during the insertion sort
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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
