On 09.12.19 23:03, Eric Blake wrote:
> On 12/9/19 11:58 AM, Max Reitz wrote:
>> On 09.12.19 17:30, Max Reitz wrote:
>>> On 02.12.19 15:09, Vladimir Sementsov-Ogievskiy wrote:
>>>> Hi again!
>>>>
>>>> Still forgotten bug-fix :(
>>>>
>>>> Is it too late for 4.2?
>>>
>>> Sorry. :-/
>>>
>>> Yes, I think I just forgot it.  I don’t think it’s too important for
>>> 4.2, so, well, it isn’t too bad, but...  Sorry.
>>>
>>>> I can't imagine better test, and it tests exactly what written in
>>>> https://bugzilla.redhat.com/show_bug.cgi?id=1712636
>>>>
>>>> (Hmm, actually, I doubt that it is real use-case, more probably it's
>>>> a bug in management layer)
>>>>
>>>> So, take this with test or without test, to 4.2 or 5.0.
>>>
>>> I was thinking of seeing whether I could write a quicker test, but of
>>> course we should take the patch either way.
>>
>> OK, I give up.  It’s very much possible to create an image with 65535
>> bitmaps very quickly (like, under a second) outside of qemu, but just
>> opening it takes 2:30 min (because of the quadratic complexity of
>> checking whether a bitmap of the same name already exists).
> 
> Can we fix that to use a hash table for amortized O(1) lookup rather
> than the current O(n) lookup?

Not unreasonable, considering that this is probably what we would’ve
done from the start in any language where hash tables are built in.

But OTOH when you have 66k bitmaps, you probably have other problems.
Like, writes being incredibly slow, because all those bitmaps have to be
updated.

(Well, you can technically have 99 % of them disabled, but who’d do such
a thing?)

((Maybe I’ll look into it.))

Max