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
