Significant performance improvements to Klipper

Several major performance improvments to Klipper. (These may not be noticeable unless you are a heavy clipboard user, but as someone who likes having a 400-entry clipboard history, this is the difference between instantly responsive and 20 second lags.)

Important: Testing is very welcome, but note that running this code will import your clipboard history into a new format unreadable by older versions of Klipper or plasmashell. If you don't want to lose your clipboard history, you should make a backup of /home/<user>/.local/share/klipper/history2.lst and, when done with testing, copy it back into the folder it came from. You can also delete the history3.lst file and storage folder that will have been created, once you're done.

The changes made:

• Don't save clipboard history when loading it from disk. (Should never have been doing this, but it was a major contributing factor to slow startup times.) !2504 (merged)
• Use xxHash (3rd party hashing library) instead of QCryptographicHash with SHA1 algorithm for hashing clipboard item data. (Justification for adding a 3rd party library below.) See below for reasons why this has been shelved.
• Complete overhaul of the format in which Klipper saves the clipboard history to disk, as well as changes to how images store data internally.
• A few other minor improvements / fixing some oddness which probably never hurt anyone anyway. Hopefully these are self-explanatory.

Do we really need another dependency? Why xxHash?

Change of plan: This is no longer part of this MR, since discussion has led to the conclusion that the changes to the save file format will remove the performance overhead of slow hashing without the need for the extra dependency. The rest of this section remains to document the original argument in favour of these changes. (The commits can still be found at https://invent.kde.org/oshiorns/plasma-workspace/-/tree/work/klipper-use-xxhash.)

I believe yes. I profiled plasmashell startup (using callgrind), because I noticed a long (>20s) lag at Klipper startup, and found that (after fixing that Klipper was saving the history immediately after loading it at startup) 40% of total startup time was spent in the QCryptographicHash::hash function. When I tried replacing this with xxHash for images (images are the biggest issue, because they are so much bigger than text or URLs) the contribution of hashing to startup time disappeared (<1%).

Generally I do not think it makes sense to use a cryptographic hash for Klipper - cryptographic hashes will always prioritise security over speed, and so they are the wrong tool for generating a unique identifier whose only purpose is to distinguish between clipboard entries.

As to why xxHash (https://github.com/Cyan4973/xxHash/) specifically:

• It is BSD licensed, so compatible with Plasma from a license point of view.
• It is exceptionally fast - the README boasts speeds in excess of 30GB/s (aka RAM-limited), more than 35x faster than SHA1. I have verified from my own profiling that it is fast enough to make the contribution from hashing insignificant.
• It is small - on my system (Manjaro) the package is only 322kB.
• It is already installed on the majority of users' systems, due to being a dependency of the almost ubiquitous rsync. (Evidence: https://pkgstats.archlinux.de/packages?query=xxhash reports that it is installed on 92.7% of Arch systems at time of writing, and I assume this is similar for other distros.)

Note: While I believe it is worthwhile for images, for strings and URLs, the use of xxHash over QCryptographicHash will probably never be noticed by anyone. And in fact, with the overhaul of the save system, images will not all be hashed at startup, so even if the hash function for images is left as-is, startup time will be mostly unaffected. However, using a cryptographic hash when much better performance is available seems wasteful, especially when we know that the impact can be very significant.

Note: You may have noticed all the pipelines (except the first one) have failed. This is because xxHash is not installed on the CI runner, so compilation fails due to not being able to find the headers. I would greatly appreciate it if someone could add xxHash to the CI runner for me, if this merge goes through - I do not have the permissions to modify the CI setup scripts.

Why bother with such a significant overhaul of the save system?

I have given a more full description in the commit message (see c5f73303) but in short:

• The old system is a single file containing all the data sequentially.
• This means that saving it requires re-writing every history item.
  • This is especially bad for images, since it requires re-compressing the image to a PNG, which is very slow.
• I have changed it to be separated into:
  • A file (klipper/history3.lst) which stores the ordering of the UUIDs.
  • A folder (klipper/storage/) which contains:
    • A first file containing the data for a single item
    • A second file containing the data for images, which instead use the first file to store metadata and a thumbnail.
• This means that copying a new item only requires writing the new data to disk, not re-writing the existing data. Moving an existing item to the top of the history only requires re-writing the ordering file. This is much faster, and also will not waste disk bandwidth or (in the case of SSDs) write cycles.
• By loading only the first file at startup, only thumbnails and metadata have to be loaded for images. This fixes the issue that just decompressing the PNGs for images was slow enough to be causing significant slowdown (multiple seconds of delay at startup), since the smaller thumbnails are much faster to decompress. This provides enough info to do all the previews of images in the UI.
• As an added bonus, by only lazily loading the full image from disk (impossible under the old system), we hugely reduce RAM usage, since the large images were being stored as bitmaps internally by QPixmap. This reduces plasmashell memory usage on my system from ~900MB to ~200MB.
• If the user opts to not allow the clipboard data to be stored on disk, we can still do better than storing the images as bitmaps. Now, we store the image data compressed in RAM if we are not allowed to write to disk, and only decompress the full image data when needed to load into the active clipboard entry. By storing the image data compressed, on my system it takes up only ~40MB (as opposed to the ~700MB from before).
• The history ordering file (klipper/history3.lst) now stores a version number for the save format separately from just a version number representing the project version. I believe this is more helpful, since it makes it easier to tell if the save file format has actually changed.

You may be aware that the old history file was named history2.lst, not history3.lst. I have made this change to ensure that if a user downgrades, they will not suffer any errors from the old system trying to parse the new format (it does not check version numbers at all...) and instead it will just create a fresh history file. The new system contains everything needed to parse the old format (and should be more extensible if new formats are adopted in future) and will import from an old history file if it exists. (If the format is changed again in future, it would not be necessary to change the name of the file, since there is now a system in place to properly handle save files with a version newer than the currently running code knows how to interpret.)

I hope that this convinces you that if nothing else from this merge request is worth having, this is! I don't know how many people will see as dramatic an impact as I have - I admit I am unusual in sometimes having hundreds of 1920x1080 screenshots in my clipboard history - but I really, really believe this is a performance improvement worth having.

I apologise in advance to whoever has to review the large number of changes this has required... I would have done it more concisely if I could have.

Conclusion

Sorry for writing such a long essay about this, but hopefully you now understand why I have made the choices I have. If not, I am happy to discuss further or revise code if anyone can suggest better ways of doing things.

Thanks a lot for your time!

Oliver