Re: [Qemu-block] Performance impact of the qcow2 overlap checks

[Max Reitz]

On 01.02.2017 10:58, John Snow wrote:
> On 01/31/2017 05:28 PM, Max Reitz wrote:
>> On 31.01.2017 13:23, John Snow wrote:
>>> On 01/23/2017 11:29 AM, Max Reitz wrote:

[...]

>>> I think what you are pointing out with refcount blocks not being
>>> essential to protect is probably pretty sufficient as an optimization,
>>> too. Or I guess we can merge your ~real~ series to help optimize things.
>>
>> Or Berto's idea works out to be good enough. :-)
>>
> 
> Follow your dreams!

https://dl.dropboxusercontent.com/u/48755239/savable/gifs/1349921181250.gif

>>> I know in the little qcheck utility I wrote I use RBtrees of ranges that
>>> get merged together; the tool doesn't really care which kinds of
>>> metadata it is, it just knows that it has "metadata" that should be
>>> protected. I think it's fast enough. If the qcow2 is kept fairly
>>> defragmented, it's REALLY fast. IIRC, your patchset has something
>>> similar, so it should be fast enough too.
>>
>> Nothing fancy. It's based on a bitmap of metadata information (more like
>> a nibble-map, though) that is RLE compressed for areas not currently in
>> use. Simple, algorithmically speaking, but makes it harder to calculate
>> the runtime complexity than using a "real" structure, I admit.
>>
>> Max
>>
> 
> It's a real structure! It's just got some properties that are difficult
> to analyze :) You just need to consider a load factor alpha and some
> kind of probabilistic distribution describing sector usage for the
> bitmap, right?

Yes, it's a... errr... Heuristic... Adaptive... Load-balancing...
Algorithm designed specifically for this use case!

> You could probably at least pick a few common cases and calculate that way.
> 
> Or don't. :)

I was taught always to do benchmarks. Even if I could prove that
implementation A always had to be slower than B. Always do benchmarks.
You can never tell anything without.

Good thing you can show anything with benchmarks. I'm not sure yet
whether I want to show my thing to be good or bad, though.

Max

signature.asc
Description: OpenPGP digital signature