Monthly Archives: December 2013

A brief history of Dolphin’s performance and memory usage

Since I took over Dolphin’s maintainership almost a year and a half ago, we have not only fixed lots of bugs and improved many details which make Dolphin more pleasant to use, but also made quite a few changes under the hood to make Dolphin faster and less memory-hungry. The other day, I compiled a few different Dolphin versions and ran some benchmarks to see how much has changed during the past 18 months.

The most straightforward way to get an idea of an application’s performance is to see how it can handle a large amount of data, so I created 100,000 empty files in a new directory using

touch a{1..100000}.txt

I then built the tags v4.9.0, v.4.10.0, v.4.11.0, and the KDE/4.12 branch (to be precise, commit f863968b7) of the kde-baseapps repository in release mode, and checked how long it takes to open the directory with my rather old computer (Athlon 64 X2 5000+ CPU) in all view modes: Icons, Compact, and Details. For all my tests, I used the same recent KDE/4.12 checkout of kdelibs (commit 3028cc4b6). I opened the directory in Dolphin once and then closed the application before starting the measurements, to ensure that the files are cached by the kernel, and that slow disk reads with non-reproducible access times do not add noise to the results.

The time required to load the directory is measured and written to the shell that Dolphin is run from with a simple patch. After the initial loading, I pressed F5 eight times and calculated the mean value of all results to reduce random fluctuations. Here are the results:

performanceMoreover, I measured with KSysGuard how much memory the Dolphin process uses. The memory usage fluctuates less than the time which is required for loading the directory, but still, I started Dolphin five times and calculated the mean value.

memoryI hope that you like these results as much as I do! All Dolphin users should see similar relative savings, but the absolute values might obviously be different. E.g., the memory usage will be much lower on a 32-bit system because all pointers need only 4 bytes instead of 8.

I will tell you in a minute how these savings were achieved, but let me first make some remarks, which will also answer the questions that some readers might already have.

  • The timer whose measurements the first plot is based on is started just before the KDirLister’s openUrl(const KUrl&) method is called, and stopped when the files are shown on the screen. In v4.9.0 and v4.10.0, the CPU and disk were still busy for quite some time after that, because Dolphin versions before 4.11.0 loaded the icons for all files in the background (some details can be found in a recent blog post). In v4.10.0, it took more than two minutes on my system until this process was completed. During these two minutes, the memory consumption grew very slowly, but constantly, until it reached the final value which is shown in the second plot. In v4.9.0, that took even much longer due to some inefficiencies which were fixed before v4.10.0 (for example this one). Therefore, it was not really possible to perform detailed memory usage measurements for v4.9.0. I just took a single data point and found that there is not a huge difference between v4.9.0 and v4.10.0.
  • The reason why Details View often requires more memory than the other view modes is that the correct handling of expanded folders requires some additional data, and earlier Dolphin versions initialized the corresponding data structures even if it was not clear yet if these data would be needed or not. This is also the reason why Details View was the slowest view mode in v4.9.0 and v4.10.0.
  • In Icons and Compact View, more time is spent on the item layout because the height of a row (in Icons View) or the width of a column (in Compact View) depends on the file names. In Icons View, we calculate how many lines of text will be shown under each icon, and in Compact View, we calculate the width of the text (which is slightly cheaper because no line breaks have to be taken into account). This information is needed to initialize the scroll bar correctly. We might consider using guessed values for the files far from the ones which are visible on the screen, but ensuring that this works correctly in all cases when scrolling in the view, and no subtle bugs occur when items which had their on-screen size guessed suddenly become visible, and the maximum value of the scroll bar needs to be updated, is not trivial.

Now I will summarize some of the main ideas that were used to achieve these results. Maybe some of them are also interesting for other applications and libraries.

Dolphin 2.2/KDE SC 4.10.0

  • Emmanuel Pescosta speeded up sorting by modifying our Merge Sort implementation such that it makes use of multiple CPU cores.
  • He also modified a function that is responsible for loading icons: all recently loaded icons are now cached, which reduces the CPU and memory usage if there are many items shown on the screen which share the same icon.

Dolphin 4.11.0

Dolphin 4.12.0 (not yet released)

  • The view receives all data for each item from the class KFileItemModel in a QHash<QByteArray, QVariant>. The QByteArray key is something like “text”, “size”, “iconName”, “iconPixmap”, etc., and QVariant is a very flexible data type that can wrap, e.g., a QString or a QPixmap. In earlier Dolphin versions, KFileItemModel initialized this QHash for every item in the current directory before anything was shown in the view. This took quite a bit of time and memory – there is a Qt Quarterly article which visualizes the overhead that QHash adds to the actual data that it stores. In most cases, we now initialize this QHash lazily, i.e., only just before the item that it belongs to is really shown on the screen. The corresponding patch could only work because some code that relied on the QHash always being initialized had also been modified (1, 2, 3).
  • Even if we have to initialize the QHash for an item, we do not store “default” values any more. One example: the QHash stores, among other things, the information if the item is “expandable”, i.e., if it is a non-empty folder that can be expanded in Details View. However, if we have a
    QHash<QByteArray, QVariant> hash

    that does not contain the key “isExpandable”, then

    hash.value("isExpandable").toBool()

    will return false. Therefore, it is not necessary to store the value “false” at all.

    Similarly, storing other kinds of data in the QHash which are equal to the default values returned by QHash::value(key) is not necessary.

  • Sorting the files “naturally”, i.e., sorting them such that the order in the view is
    file1.txt
    file2.txt
    ...
    file9.txt
    file10.txt

    rather than

    file1.txt
    file10.txt
    file2.txt
    ...

    is quite time-consuming because the string comparison function

    KStringHandler::naturalCompare(const QString &a, const QString &b)

    essentially has to chop the two strings a and b into little “number” and “text” chunks, which are then compared in a locale-aware way.

    Qt 5 provides a class QCollator (public API since Qt 5.2 thanks to the awesome work of Aleix Pol), which can be used to pre-compute a “sort key” for every QString in advance. Comparing two “sort keys” is much faster than comparing the QStrings in a natural and locale-aware fashion. This means that O(N log(N)) expensive comparisons are replaced by O(N) “sort key” calculations, which might be expensive, and O(N log(N)) cheap comparisons.

    However, it turned out that we can improve the sorting performance even while we are still using Qt 4.8. The key observations are:

    1. Sorting the items with QString’s operator “<” as the comparison function is very fast.
    2. After this fast sorting, the order of the items is not totally correct, but most of the time, the order is quite close to the correct one.
    3. The number of comparisons that our Merge Sort implementation needs is greatly reduced if the order of the items is “mostly correct”.

    Therefore, we now sort the items twice: first using QString’s operator “<“, and then using KStringHandler::naturalCompare. This simple change reduced the time required for sorting by 63% in my tests.

    Some readers will probably have noted that there is a sorting algorithm which is designed to make use of input data which are “mostly sorted” already, and which might therefore improve the performance even further: Timsort, which is used, e.g, as the default sort algorithm in Python (1, 2). Maybe we will use it in future Dolphin releases.

  • In the class KItemListViewLayouter, which is responsible for the layout of the items in the view, we calculated and stored some redundant data for all files in the current directory: both the size of an item (i.e., how much space the icon and text need on the screen, that is 2 numbers for width and height), and the rectangle that contains the item (storing a rectangle requires 4 numbers). Before an item was shown on the screen, the rectangle was adjusted according to the current value of the scroll bar(s). Now we only store the size and the position of the top-left corner of the rectangle. The final rectangle can easily be constructed from these once it is necessary.

Outlook

I still have some ideas for improvements inside Dolphin, but as Mark Gaiser pointed out in his comment to a review request, the major remaining consumer of huge amounts of memory is the class UDSEntry from kdelibs. I assume that few people know this class, but it’s being used indirectly by every application that uses the KIO framework to access directory contents either directly or indirectly (e.g., via the “Open/Save File” dialog).

UDSEntry is used to transmit all kinds of information about files from kioslaves (which are the helper applications that read files from disk, or access remote files via sftp, smb, etc.) to the applications. A first optimization which is already in the master branch of kdelibs is to make use of Milian Wolff’s implicit sharing trick once more. The idea is that the user name and the group are very often the same for many files in a directory. Therefore, the function that receives the UDSEntries from the kioslave now checks if, e.g., the user name for a file is the same as the one for the previous file. If that is the case, the same implicitly shared QString is used for both. If all files in a directory belong to the same user, the same implicitly shared QString will be used for all.

In the benchmarks I discussed at the beginning of this post, there were 100,000 copies of my user name, and 100,000 copies of the group name “users” in memory – it should be obvious that this is not really efficient.

I will discuss further possibilities to optimize UDSEntry in a future blog post. For the time being, here are the raw data for the plots above, including the benchmark results for the master branches of kde-baseapps and kdelibs, which include the first UDSEntry optimization:results

Conclusion

I hope that I made clear what the key ideas are, and that these might be useful also for some readers of this post:

  • Do not determine large amounts of data in advance if it is likely that most of these data will never be needed.
  • Do not store redundant data: think twice if everything that is stored in memory is really needed, or if there is another solution that can achieve the same with less memory.
  • Make use of implicit sharing: if there are many QStrings, QByteArrays, or other implicitly shared data in an application, many of which are likely to be equal, check if they can share their memory.
  • If some calculation takes very long, try to find a more efficient algorithm.

Finally, I would like to thank everyone who helped to make these improvements possible. In particular, I would like to mention Mark Gaiser, who loves to stress-test file managers with half a million files and share his findings on our mailing list. Without his challenges, some of the work presented here might not have happened.

Dolphin 4.11

Dolphin 4.11.0 has been released some time ago, and since we are approaching the 4.12 release already, I guess it’s about time that I summarize the most important changes.Dolphin-4-11

The screenshot shows a new feature which can come in handy in many situations: the “Filter Bar”, which you can enable, e.g., by pressing Control+I, can now be locked, such that the filter string remains unchanged when visiting different folders. Thanks to Stuart Citrin for this contribution!

Here is a summary of the other changes which make Dolphin more pleasant to use:

“Tree View” improvements

Emmanuel Pescosta, who has contributed a lot of bug fixes to recent Dolphin releases, greatly improved the handling of expanded folders in Details View. The code is much more robust now, and lots of bugs are fixed: Bug 304565, bug 311912, bug 312890, bug 315593, bug 306219, bug 320335.

Reduced memory usage

I already told you some time ago that we do not load icons and previews for all files in the current folder in advance any more. A nice side effect of this change is that the memory which would be needed to store this information is now saved.

There are a few more changes in Dolphin 4.11 which help to reduce the memory consumption:

  • For each file or folder, all relevant information is stored in a QHash<QByteArray, QVariant>. The QByteArray keys are, e.g., “text”, “date”, “size”, “iconName”, etc. In previous Dolphin releases, all these keys were stored N times in memory for a folder with N items. Since Dolphin 4.11.0, we make use of the fact that QByteArray is one of Qt’s implicitly shared classes, and let all QByteArrays with equal contents use the same memory location for their data. The motivation for this change, which can reduce the overall memory consumption by about 10%, was a blog post by Milian Wolff. See git commit 7e532911, review request 110686.
  • In a few cases, we used a QList to store items of a data type which requires more size than a pointer. In that case, QList does not store the items directly, but allocates space for them on the heap, and stores pointers to them. Therefore, there is an overhead of one pointer for each item, plus any overhead that the memory allocator adds.
    Simply replacing QList by QVector therefore saves a lot of memory in these cases. See git commit 8aea59bb, review request 111304.

How much the memory consumption decreases when upgrading to Dolphin 4.12 depends on the number of files in the current folder, the view mode, and some other factors. For large folders, it is not uncommon to see a 30% reduction.

Since allocating a lot of memory in many small chunks is a rather expensive operation, these changes also improve Dolphin’s performance.

Performance improvements

Some time ago, I wrote a post about the O(N²) run time behavior that can occur when using a container such as QList, QVector, or std::vector, and adding or removing many items in an inefficient way. Dolphin also had a few functions with quadratic worst-case complexity, which could be triggered by creating, deleting, or filtering many files with a particular pattern. These functions were rewritten such that they have O(N) worst-case complexity, and are even a bit faster in all cases:

  • KFileItemModel::removeItems(). See git commit ff3267c6, review request 108540.
  • KFileItemModel::insertItems(). See git commit fba053e9, review request 110355.
  • KItemListView::slotItemsRemoved(). See git commit 6c157fcb, review request 111398.

There are a few more changes which can save many CPU cycles in some situations:

  • Bug 299565: Avoid an unnecessary resorting when items are changed. See git commit d70a4811, review request 111146.
  • When switching from, e.g., “Sort by Name” to “Sort by Date”, or changing the sort order, we accidentally converted all URLs to a QString and then back to a KUrl, which was quite expensive. This is now fixed. See git commit bf2618d7, review request 111700.
  • Moreover, the performance is also improved by not loading icons and previews for all files. In earlier Dolphin versions, one could notice that the CPU and disk remain busy for a very long time after entering a large directory.

Preparations for porting to KDE Frameworks

There is no KDE Framworks port of Dolphin yet, but a few changes were made to make the porting easier:

  • Remove use of KIO::SlaveConfig. See git commit e45d4310, review request 107421.
  • Handle Shift key presses in the context menu without KModifierKeyInfo. See git commit 58fc982e, review request 110303.

Bug fixes in the view engine

  • Bug 301800: Fix “truncated header” in Details View with non-Oxygen styles. See git commit 25f208eb, review request 111608.
  • Bug 322212: Fix incorrect scroll position after changing the URL. See git commit 02e41237, review request 111557.
  • Bug 302373: Prevent that removing items can cause icons to overlap. See git commit 6e1a8774, review request 111630.
  • Bug 319951: Prevent that items may disappear from Details View after deleting other items. See git commit ba2c5c71, review request 111486.

Improvements concerning the “Move to Trash”/”Delete” actions in the context menu

Handling these actions is less trivial than it seems – note that pressing “Shift” while Dolphin’s context menu is open transforms the “Move to Trash” action into “Delete” (at least if the latter is not enabled permanently in the settings dialog). The behavior of the context menu of the DolphinPart, which can be used in Konqueror, was different before KDE SC 4.11, but both implementations still shared some of the code for these actions, which made the code a bit buggy and the maintenance complicated.

This is only one of the things concerning “Move to Trash” and “Delete” which was improved greatly in Dolphin 4.11:

  • Factored out the “Delete/Move To Trash” action into its own class. See git commit 8e023ae9, review request 108802.
  • Bug 307254: Do not delete files if the user clicks “Move to Trash” in the context menu while Shift is pressed. See git commit fda03a10, review request 107509.
  • Bug 294013bug 297510: Disable “Move to Trash” and “Delete” inside archives, which are read-only from Dolphin’s point of view. See git commit 4cd23183, review request 111160.
  • Bug 261762: Do not show the “Move To Trash” action in context menu for remote URLs. See git commit e688a52e, review request 111206.
  • Make it clear that the “Trash/Delete” confirmation applies to all KDE applications. See git commit ff712cbb, review request 111324.

Usability improvements

  • Bug 157593: Switch location bar back to breadcrumb mode when pressing Enter if “Editable location bar” is not enabled in the settings. See git commit e74dfee5, review request 107748.
  • Bug 297140: Return the focus from the filter bar to the view when pressing Enter. See git commit 2f011473, review request 109020.
  • Bug 301276: Move “Bluetooth” to the “Devices” section of the Places Panel. See git commit 05fb8186, review request 109622.
  • Bug 315722: Scroll the view to a new file after it has been pasted. See git commit e92b4ba2, review request 109950.
  • Bug 312872: If the URL changes, hide the widget that shows error messages. See git commit 5324fcd3, review request 110369.
  • Bug 310049: Make it easier to drag and drop items in the Places Panel. See git commit 6bcc70a1, review request 110342.
  • Bug 304775: Remove the confusing “decoration icon” in the KMessageWidget. See git commit c8264896, review request 110327.
  • Bug 312296: Allow to open multiple selected folders in new tabs. See git commit 05d9210e, review request 110371.
  • Do not allow drops on the “Search”/”Recent” entries in the Places Panel. See git commit 27553914, review request 110348.
  • Do not allow creating entries for files in the Places Panel. See git commit 2b700c50, review request 110347.
  • Bug 196035: Open archives in a new tab on middle click. See git commit afcf8961, review request 110487.
  • Focus the view where items are dropped. See git commit 08eae43a, review request 110167.
  • Bug 319373: Do not use a fixed width for the zoom slider and the “free space” widget in the status bar. See git commit 3e172053, review request 110966.
  • Use the Nepomuk2::FileMetaDataConfigWidget for configuring what kind of data is shown in the Information Panel. See git commit 626f4cb6, review request 111294.

Bug fixes

  • Bug 233335: Select the correct items if pasted/dropped files have to be renamed because of a name conflict. See git commit fd65a97b, review request 107351.
  • Bug 181337: Make grouping by “Date” more consistent. See git commit d7845775, review request 108667.
  • Make the handling of the view’s palette more robust. See git commit 71be3439, review request 110505.
  • Bug 318442: Fix searching in hidden folders. See git commit 85ea7bda, review request 110697.
  • Bug 319119: Fix incorrect item name in the view if a “Rename” operation fails. See git commit 0d0b9583, review request 110922.
  • Make sure that the “drop” indicator is hidden if an item is not hovered any more. See git commit 92854f90, review request 111037.
  • Bug 321286: Make it possible to select files like “a_b” using keyboard search. See git commit e401d892, review request 111102.
  • Bug 321299: Do not try to connect to Nepomuk if it is not running. See git commit 44791e7f.
  • Bug 299646: Enable KIO error reporting when using non-inline renaming. See git commit cafbdb59, review request 111111.
  • Bug 318534: Make sure that changing the view works even if the settings file is not writable. See git commit 4e80918a, review request 111120.
  • Bug 321359: Handle music files with more than one “Artist” correctly. See git commit 4b0498a4.
  • Bug 192139, bug 256338, bug 293220, bug 309076: Fix crash when dropping URLs on the URL navigator’s drop down menus. See git commit 669ee325, review request 111273.
  • Bug 322348: Make sure that removed tags are also removed in the view. See git commit 5b81abea, review request 111505.
  • Bug 283475, bug 318217: Don’t try to open .desktop files with http/https URLs inside Dolphin,. See git commit f14352f1, review request 111674.
  • Bug 321778: Escape HTML-like file names in the status bar, which prevents a freeze of the application if there is a file with a malicious name. See git commit 4450f844, review request 111746.
  • Bug 323170: Escape HTML-like file names also in the tool tip for the status bar. See git commit d9b111b0, review request 111836.
  • Bug 299156: Handle ramfs mounts correctly so copying files to them works (this was a bug in kdelibs). See git commit af114cc9, review request 111115.

Code simplifications

Removing code without loss of functionality or replacing complex code by a shorter and simpler version is always very rewarding because it makes future maintenance easier. Sometimes, the simplification itself is even sufficient to fix bugs.

  • Simplifcations in the version control code. See git commits 173efe0b and cb6d1080, review request 107656.
  • Simplifications in the sorting code. See git commit ccbc9916, review request 108386.
  • Bug 294616, bug 311947: Replace the code which compares expanded items while sorting, which was quite complex and caused some crashes which were hard to reproduce, by a simple, robust and faster solution. See git commit b80384ca, review request 108766.

Thanks!

Many people provided patches or advice, helped with managing the endless stream of incoming bug reports, or used the master branch for their daily work and reported any regressions before they had the chance to cause serious trouble:

Aurélien Gâteau, Christoph Feck, Daniel Kreuter, David Faure, Dawit Alemayehu, Emmanuel Pescosta, Fabio D’Urso, Hrvoje Senjan, Jekyll Wu, Jens Rutschmann, Kai Uwe Broulik, Romário Rios, Simeon Bird, Stuart Citrin, Thomas Lübking, Vishesh Handa and Weng Xuetian. If I forgot anyone, please let me know.

Also the contributions by the people who work on documentation, translation, preparation of the released tarballs, packaging, and system administration are greatly appreciated! Without their help, it would not be possible to run a project like Dolphin successfully.