Re: [PATCH v19 3/7] xbitmap: add more operations

On Sat, Dec 16, 2017 at 01:31:24PM +0900, Tetsuo Handa wrote:

Michael S. Tsirkin wrote:

quoted

On Sat, Dec 16, 2017 at 01:21:52AM +0900, Tetsuo Handa wrote:

quoted

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.

What makes you think that the radix tree (also xbitmap, also idr) doesn't
sort the values at store time?

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.

The xbitmap absolutely has that ability.  And making it generic code
means more people see it, use it, debug it, optimise it.  I originally
wrote the implementation for bcache, when Kent was complaining we didn't
have such a thing.  His needs weren't as complex as Wei's, which is why
I hadn't implemented everything that Wei needed.