[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations
From: |
Tetsuo Handa |
Subject: |
Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations |
Date: |
Sat, 16 Dec 2017 13:31:24 +0900 |
Michael S. Tsirkin wrote:
> On Sat, Dec 16, 2017 at 01:21:52AM +0900, Tetsuo Handa wrote:
> > My understanding is that virtio-balloon wants to handle sparsely spreaded
> > unsigned long values (which is PATCH 4/7) and wants to find all chunks of
> > consecutive "1" bits efficiently. Therefore, I guess that holding the values
> > in ascending order at store time is faster than sorting the values at read
> > time.
>
> Are you asking why is a bitmap used here, as opposed to a tree?
No. I'm OK with "segments using trees" + "offsets using bitmaps".
> It's
> not just store versus read. There's also the issue that memory can get
> highly fragmented, if it is, the number of 1s is potentially very high.
> A bitmap can use as little as 1 bit per value, it is hard to beat in
> this respect.
>
I'm asking whether we really need to invent a new library module (i.e.
PATCH 1/7 + PATCH 2/7 + PATCH 3/7) for virtio-balloon compared to mine.
What virtio-balloon needs is ability to
(1) record any integer value in [0, ULONG_MAX] range
(2) fetch all recorded values, with consecutive values combined in
min,max (or start,count) form for efficiently
and I wonder whether we need to invent complete API set which
Matthew Wilcox and Wei Wang are planning for generic purpose.
- [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, (continued)
- [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Wei Wang, 2017/12/12
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Tetsuo Handa, 2017/12/12
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Wei Wang, 2017/12/13
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Tetsuo Handa, 2017/12/13
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Wei Wang, 2017/12/13
- Re: [Qemu-devel] [virtio-dev] Re: [PATCH v19 3/7] xbitmap: add more operations, Wei Wang, 2017/12/14
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Tetsuo Handa, 2017/12/14
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Matthew Wilcox, 2017/12/14
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Tetsuo Handa, 2017/12/15
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Michael S. Tsirkin, 2017/12/15
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations,
Tetsuo Handa <=
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Matthew Wilcox, 2017/12/16
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Tetsuo Handa, 2017/12/16
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Matthew Wilcox, 2017/12/15
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Matthew Wilcox, 2017/12/15
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Wang, Wei W, 2017/12/17
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Matthew Wilcox, 2017/12/17
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Wei Wang, 2017/12/17
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Matthew Wilcox, 2017/12/17
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Wei Wang, 2017/12/16
- Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations, Matthew Wilcox, 2017/12/14