On Fri, Jul 24, 2026 at 05:37:50PM +0800, Weimin Xiong wrote: > From: Xiong Weimin <[email protected]> > > The vhost_log_sync_range() function iterates through all memory sections > for each call, resulting in O(N^2) complexity when syncing dirty > bitmaps. This is inefficient for guests with many memory sections. > > Optimize this by: > 1. Checking if a section overlaps with [first, last] range before > calling vhost_sync_dirty_bitmap() > 2. Early exit when section starts beyond the requested range
As any optimization, I expect actual perf measurements showing an improvement to be included please. > Signed-off-by: Xiong Weimin <[email protected]> > --- > hw/virtio/vhost.c | 18 +++++++++++++++-- > 1 file changed, 15 insertions(+), 3 deletions(-) > > diff --git a/hw/virtio/vhost.c b/hw/virtio/vhost.c > index 1234567890ab..fedcba098765 4321006 > --- a/hw/virtio/vhost.c > +++ b/hw/virtio/vhost.c > @@ -280,11 +280,21 @@ static void vhost_log_sync(MemoryListener *listener, > static void vhost_log_sync_range(struct vhost_dev *dev, > hwaddr first, hwaddr last) > { > - int i; > - /* FIXME: this is N^2 in number of sections */ > - for (i = 0; i < dev->n_mem_sections; ++i) { > - MemoryRegionSection *section = &dev->mem_sections[i]; > - vhost_sync_dirty_bitmap(dev, section, first, last); > + int i, j; > + bool section_dirty = false; > + > + for (i = 0; i < dev->n_mem_sections; ++i) { > + MemoryRegionSection *section = &dev->mem_sections[i]; > + hwaddr section_start, section_end; > + > + /* Skip sections that don't overlap with [first, last] */ > + section_start = section->offset_within_address_space; > + section_end = section_start + int128_get64(section->size) - 1; > + > + if (section_end < first || section_start > last) { > + continue; > + } > + > + vhost_sync_dirty_bitmap(dev, section, first, last); So it is still O(N^2) right? It just skips calling it for some sections. > } > } >
