Sending a lot of images with the graphics protocol lead to noticeable freezes

[Nogesma]

Describe the bug
When sending a lot of images/frames with the graphics protocol, kitty becomes noticeably slower for each additional image load operation.

I've tracked this down to the disk_cache.c find_hole function, in particular the HASH_SORT of all the disk cache entries, which happens on each cache write operation.
Because this expensive operation happens inside a lock, it causes noticeable freezes when sending multiple images when the cache contains a lot of entries.

I encountered this issue when implementing an emote picker for Xithrius/twitch-tui#524. It requires me to load a lot of twitch emotes, which are mostly animated images, with some containing hundreds of frames. With some twitch channels having a few thousand emotes, the cache can become quite large.
Testing and loading all those images for one twitch channel resulted in a cache containing ~40k entries.
Note that those images are all small in size, and I am not close to hitting the storage quota.
I am loading those images lazily, but kitty starts to struggle after reaching a cache with a few thousand entries, which can in some cases be only ~50 emotes (each having 20-40 frames).

For this use case of sending a lot of images, without doing any deletion, the find_hole function call is not really necessary, and just commenting it out speeds up things greatly. There also seems to be a defrag operation happening when the cache gets too fragmented.

My question is, would it be possible to look into optimizing the disk cache when it contains a lot of entries? Or would it be best for me to start keeping track of which image has not been used recently, and tell kitty to delete it, to keep the number of cache entries low.

It would also probably be good to consider adding a maximum number of images quota, in addition to the maximum storage quota, to avoid DOS attacks.

To Reproduce
Steps to reproduce the behavior:

1. Send a lot of images to kitty using the graphics protocol
2. Once the disk cache starts to have a few thousand entries, kitty becomes really slow

[kovidgoyal]

Wouldn't a simple fix be to have a deletion counter which tracks the
largest available hole size and its position in the file and the number
of holes. Only call find_hole

(largest_hole_size == 0 && num_of_holes > 0) || (largest_hole_size > required_size)

this way for your case of appending lots of images without a deletion,
find_hole wont be called until the cache is full. Once the cache is full
one would evict the oldest n images such that n is as small as possible
and the total size of the evicted images is greater than required_size.
So once again we can avoid calling find_hole.

Of course once deletions come into play, find_hole becomes necessary,
but again its frequency can be reduced by only doing it when cache is
limit is reached and then, depending on the value of the deletion
counter, either call find_hole or do a defrag.

Indeed, one could even maintain a list of the last N holes rather than
simply tracking the number and max size for more sophisticated handling.

[Nogesma]

I think keeping a list of all holes would make it possible to avoid calling find_hole completely.
It would also mean that one needs to handle merging adjacent holes, and this is probably an expensive operation. Calling defrag when the number of holes becomes too large might solve this issue.
In any case, any solution that avoids sorting the list of entries too often should be faster, and solve my issue.

I also had a quick other unrelated question, I don't think it's possible to delete all images stored by kitty at once, as the d=A key will not delete virtual refs. I am deleting them by id for now but would it be possible to have a delete command for all images, including Unicode placeholders?

[kovidgoyal]

I also had a quick other unrelated question, I don't think it's possible to delete all images stored by kitty at once, as the d=A key will not delete virtual refs. I am deleting them by id for now but would it be possible to have a delete command for all images, including Unicode placeholders?

Unicode placeholders can only be deleted by deleting their associated
text, otherwise there are various issues as the lifetimes of unicode
placeholders are not tied to the underlying image data.

@sergei-grechanik should be able to elucidate those issues.

[sergei-grechanik]

Yes, the intended approach when using Unicode placeholders is to erase the text and let the image itself be deleted automatically when the total size/count limit is reached. Deleting an image by id is ok too, but it's still recommended to erase the placeholder text, because there is no guarantee that a redraw will be triggered.

Adding a key to delete all images, including virtual ones, is possible, but I wouldn't recommend actually using it, since it will break images in other panes/windows when running in tmux, for example. (However, there is still value in having such a key for testing purposes).

[Nogesma]

Okay, I was interested in just cleaning up when my program exits, and at this point the screen does not have any placeholders, and will not use the images anymore. The size limit won't get reached either.

I think for my purpose deleting them by id is fine, but having a key for all of them would be a nice to have. Especially since removing them one by one is actually O(n!) instead of O(n), if I interpreted the code correctly.

[kovidgoyal]

This should be fixed in the vt branch. I havent tested the performance,
but find_hole() is now O(1)

[Nogesma]

I just tested it and it works great, thanks a lot!

[kovidgoyal]

I also just added a new deletion mode to delete images by range of ids. You can specify the upper limit of the range to be the max image id value to delete all images.
cebdc93

[Nogesma]

Nice, thanks again!