Dolphin bugs fixed in May 2013

Again, we have a new bug fix release. Here are the bug fixes that Dolphin users who upgrade can benefit from:

  • Bug 304918: Update the ‘Recently Accessed’ and ‘Search For’ sections of the Places Panel when Nepumuk is started or stopped. See git commit 24609e78, review request 110323.
  • Bug 255819: Ensure that manual changes of the icon for the ‘Sort By’ toolbar button are remembered. See git commit f12345a5, review request 109966.
  • Bug 319660: When dropping the trash in a directory, create a link, rather than copying the trash contents to that directory. See git commit 6072f58c.
  • Bug 319747: Fix crash when copying many files. See git commit 1b9726e2.
  • Bug 315796: Make it possible to change the parameters of ‘read only’ search queries. See git commit 2c68fe33, review request 110324.
  • Bug 309740: Prevent that files in expanded folders are shown with a size of 16 EiB while they are being changed. See git commit 56cf52db, review request 110428.
  • Bug 299675: Fix problems when moving files out of or into expanded folders in Details View. See git commit a79c3a39, review request 110401.
  • Bug 319336: Fix a crash that could happen when editing the tags of a file. See git commit 2080bc1d.

Thanks to Daniel Faust, David Faure, and Vishesh Handa!

Some Thoughts On Algorithmic Complexity, Part 1

When people develop and maintain software, they usually try to make sure that their code not only works well, but also that it runs fast. There are many different ways to make code perform better. It can be as simple as choosing reasonable compiler options, or as hard as rewriting some code in assembly.

If you see some code that takes long to run, you should not start optimizing by looking into the little details though. The first questions that you should ask is: are we actually using the right algorithm for the job? Are there any design mistakes that make things much worse than they need to be? This is especially important if you don’t know in advance how much input the code will have to handle. It should be obvious that it makes a difference if a list that needs to be sorted contains 1000 or 1 million items. However, how big that difference actually is depends on the choice of the algorithm and its correct implementation.

If you are not interested in mathematics or theoretical computer science, feel free to skip the next sections. Maybe the example programs at the end of the post will be interesting for you nonetheless, at least if you are fairly familiar with programming.

Big O notation

The exact time f(N), measured in milliseconds, CPU cycles, or some other suitable unit, that an algorithm requires if it is given an input of size N (N could be the length of a list or the length of a string, for example) is often less interesting than the growth rate, i.e., how fast that time grows if N becomes larger and larger. Is it constant, or does it increase logarithmically, linearly, or even worse?

To classify the so-called run-time complexity of an algorithm, one often uses the big-O notation. It can be used to provide an upper limit for f(N) in a rather simple way, even if writing down f(N) exactly would yield a very complex expression. The idea is to use a simple function g(N), and say that

f(N)=O(g(N))

if there is a constant c such that

f(N)\le c\, g(N)

for any N, i.e., if this constant times g(N) is an upper bound for f(N). Simple example: if

f(N)=4 N+\log_2(N)+2,

we could write f(N)=O(N) because the linear term 4 N is the one which grows fastest, such that the total value f(N) is always smaller than some constant times N.

Typical orders (of growth) that often occur in algorithms in the software that we use include O(1), O(log N), O(N), and O(N log N).

I’ll give some examples for situations where these occur:

O(1) constant: a simple example in the Dolphin context would be showing the files and folders on the screen. Even if you have 100,000 items in a directory, only a small, constant number of them can be shown at the same time, so the effort required to draw them should not depend on N at all.
O(\log N) logarithmic: the classical example is binary search. If you are given a sorted list of N items, and you have to find a particular item, you might start by looking at the element in the middle. This tells you if you have to look at the first or in the second half of the list. It is easy to show that applying this procedure repeatedly will yield the right item in \log_2 N steps.
O(N) linear: a Dolphin example would be loading the data for all files in a directory (like the name, size, and other things that we might want to show in the view).
O(N \log N) If a good sorting algorithm is used to sort a list of N items, this is the typical number of comparisons of two items that are required, and hence, also a measure of the time that will be needed to sort the list.
O(N^2) quadratic: this is something that you really want to avoid, unless you can guarantee that you will never have to handle really many items, or there really is no better solution for your problem. If you are not sure if a better solution exists, you should look for one. Really.

Best case, average case, and worst case

Things are often a bit more complicated: the run-time complexity of an algorithm can depend on the actual input data. For example, certain sorting algorithms might work better if the input data are (almost) sorted, and worse for certain other kinds of data.

Therefore, one often states the best case, average case, and worst case run-time complexity of an algorithm. Which of these is most important depends strongly on what you know in advance about the input data. If they are always in a certain form, an algorithm that has a good best-case performance just for that kind of data might be preferable. On the other hand, if the input data might come from an untrusted source, ensuring a reasonable worst-case performance should have the highest priority if you want to prevent that you and your users will be the target of algorithmic complexity attacks.

Why am I telling you all this?

This is an obvious question that you might ask now. Everyone who develops software should be familiar with those things already, right? Well, it turns out that a lot of real-world code does have a worst-case (or, sometimes, even an average) run-time complexity that is worse than it needs to be, either because the wrong algorithm has been chosen, or because a tiny mistake in the implementation makes things go terribly wrong if a certain kind of input is fed into the algorithm. This is why I thought it might be a good idea to write a series of blog posts to raise people’s awareness of these issues.

Example

Let’s start with a simple example, and assume that we have to write a function that replaces all occurrences of a certain character in a plain C string by another character. E.g., replace ‘u’ by ‘o’ in the string ‘algurithm’ to obtain the right spelling ‘algorithm’. Let us also ignore that we don’t actually use plain null-terminated C strings much in KDE/Qt code, and that solutions for this problem exist already.

Any algorithm to solve this problem will have to go through all N characters of the string once, and look at and possibly replace each character. So we would expect that the run-time complexity is O(N).

This is a possible solution that we could come up with:

void replace1(char* text, char oldChar, char newChar)
{
    for (unsigned int i = 0; i < strlen(text); ++i) {
        if (text[i] == oldChar) {
            text[i] = newChar;
        }
    }
}

Some will already see the flaw in this implementation, but I assume that many would just verify that this function works nicely for a few examples and then happily use it. It might even work OK in real world applications for some time, that is, until someone uses this function to handle a very long string.

A small benchmark that tests this function for strings with lengths between 100,000 and 800,000 characters can be found in my personal KDE scratch repository. The following plot shows the time in milliseconds as function of the input size (plots were generated with qtestlib-tools).

1

When you see this plot, you immediately realize that the time depends quadratically on the input size. So our algorithm has a run-time complexity of O(N^2), rather than the expected O(N). This results in an unacceptable run time of 8 seconds just for going through 800,000 characters and replacing some of them! If you are doing something like this in the main thread of an application, the GUI will be completely frozen during that time.

What went wrong?

The problem is the condition ‘i < strlen(text)’ in the for loop. This condition is evaluated after each execution of the loop, i.e., N times. Moreover, strlen(text) must go through the entire string, because it looks for the terminating null character, which defines the end of the string. This means that the O(N) function strlen(const char*) is executed N times. Now it is obvious why our function is O(N^2).

Correcting the mistake

Here is a better version of the function, and benchmark results that show that it needs only linear time. Note that the time to handle 800,000 characters has been reduced from 8 seconds to 1.5 milliseconds:

void replace2(char* text, char oldChar, char newChar)
{
    const unsigned int length = strlen(text);
    for (unsigned int i = 0; i < length; ++i) {
        if (text[i] == oldChar) {
            text[i] = newChar;
        }
    }
}

2

What about the compiler?

Maybe some readers will now ask if an optimizing compiler shouldn’t be able to see that calculating the length of the string repeatedly is unnecessary, and thus optimize the first version of our code such that it becomes O(N). It turns out that such an optimization is impossible because using our function to replace any char by 0 will actually change the length of the string inside the loop.

Do professional developers really write code which has such problems?

Yes, they do. According to an article that I once read on the web (I cannot find it at the moment, unfortunately – if you do, please add a comment!), the “strlen in for loop condition” issue once caused huge problems in the computer system of a bank. Moreover, there is still a lot of code out there which has similar problems, even if they are sometimes less obvious. In the next posts in this series, I’ll tell you about some further examples, which will be fixed in KDE 4.11.

Dolphin bugs fixed in April 2013

Here are the bugs which were fixed in Dolphin for last week’s release:

  • Aureliéns efforts to make our hover animation as good as possible were not over yet: one little bug remained after his recent fixes. For details, see git commit c3a7ba4e, review request 109960.
  • Bug 316129: When entering a directory, load the icons for the visible icons first, rather than loading all icons in random order. See git commit 52a38ee9, review request 109843.
  • Bug 317827: Fix possible crash when filtering items. See git commit 34d0ad72.
  • Bug 316285: Fix crash in the accessibility code. See git commit f8bf2577.
  • Bug 317772: Disable the non-working Find/Replace actions when renaming inline. See git commit a16562cd.
  • Bug 193298: Make sure that the correct free space for the current device is shown when viewing a folder with a name whose beginning coincides with a mount point. See git commit 4f2ecbab, review request 110225.
  • Bug 318942: When renaming multiple files, make sure that the “Rename” button is enabled if and only if there is exactly one connected sequence of ‘#’ symbols. See git commit cbb2a4cf, review request 110223.
  • Bug 305734: Fix the problem that selected hidden items are hard to see with certain color schemes. See git commit 572513a1, review request 110164.
  • Bug 302037: Prevent that the view URL changes unexpectedly when the Terminal Panel is enabled and the current path is a symbolic link to a directory. See git commit 2e123de9, review request 110233.

Thanks for providing patches, helpful analysis and testing proposed fixes: Aurélien Gâteau, David Faure, Emmanuel Pescosta, and Jekyll Wu.

Dolphin bugs fixed in March 2013

Here is a summary of the bug fixes that Dolphin users who upgrade to last week’s release can benefit from:

  • Bug 288824: Fix the problem that no custom icons are shown for folders which are accessed via NFS and some other file systems. See git commit 6369b556 for the infrastructure in kdelibs, and commit b8c9aa55 for the patch that makes Dolphin use it.
  • Bug 316335: Make sure that children of expanded directories are removed from the  model if the parent is collapsed, and prevent that they reappear when the filter is removed. See git commit acec0e65, review request 109343.
  • Bug 315619: Do not skip rows in Details View when scrolling by clicking the empty area of the scroll bar. See git commit 6ba70a6f, review request 109210.
  • Bug 316615: If files with multiple types are selected, show the services for the file type ‘octet stream’ in the context menu. See git commit 4da8e6cd.
  • Bug 316016: Another kdelibs issue that caused Dolphin to not update the view properly. This one was about the deletion of a directory not being noticed and could be fixed thanks to good instructions to reproduce the bug provided by the forum user gedgon. See git commit 1f6d6cfc.
  • Bug 316300: Fixed a bug in the code that prevents the unintended execution of commands in the Terminal Panel when changing the view. This bug could lead to the command being executed in some corner cases. See git commit 6be6988f, review request 109431.
  • Bug 315693: Ensure that the Information panel shows “&” in filenames correctly. See git commit 914b8d88, review request 109129.
  • Bug 295300: Make sure that F5 reloads all expanded directories when viewing a remote directory. See git commit d3ad8f59, review request 109488.
  • A follow-up to the fix for bug 299371: Fix transition between normal and hover images. See git commit 472608e8, review request 109614, and Aurelién’s blog post for details about his smart debugging tricks.
  • Bug 317018: Fix a crash in the Mercurial plugin when deselecting a file to commit. See git commit 1f1392a6.
  • Bug 315569: Group files by name correctly also for non-ASCII file names. See git commit 02f4a69f, review request 109457.

Thanks to everyone who helped to make these bug fixes possible: Aurélien Gâteau, David Faure, Emmanuel Pescosta, Martin Koller, Pierre Sauter, Vishesh Yadav, Weng Xuetian.

Dolphin bugs fixed in February 2013

Last week KDE released the latest bug fix release. It contains the following changes in Dolphin:

  • Bug 315298: Fix crash when clicking an action in the context menu for a removed device in the Places Panel. See git commit 547d10aa, review request 108989.
  • Bug 299371: Fix blinking when moving the mouse over an hidden item. See git commit 12d41a88, review request 108858.
  • Bug 313342: When changing the “Single click/Double click” setting, apply these changes immediately. See git commit 17eeee6b.
  • Bug 315315: Prevent expensive re-layoutings when opening folders with many items. See git commit daf12b8e, review request 108984.
  • Bug 315210: When deleting an expanded folder which contains filtered files, make sure that those files do not reappear after clearing the filter. See git commit e053ecdc, review request 108976.
  •  At least the first part of Bug 252483: update the “Trash” icon in the Places Panel after restoring files. See git commit bf7cdfca.

Patches were provided by A. Janardhan Reddy, Aniket Anvit, Aurélien Gâteau, and David Faure – thanks!

If you use the “Show in Groups” feature and you have some files with non-ASCII names, you might be able to help us with a fix for next month’s bug fix release. Currently, some things do not quite work right, see the left side of the screenshot below. We have a patch that makes it look like the right side, but I would like to make sure that we don’t break anything in the 4.10 branch. Feel free to download the patch from the review request, and report any regressions there or in the bug report. Thanks.

Grouping

 

Dolphin 2.2 is there!

I told you about the changes in Dolphin 2.2 some time ago already. Here is a summary of the last bugs that were fixed during the beta/RC phase:

  • Bug 311582: Fix another “View fails to update after changes in the directory” issue. See git commit 74b0d33a.
  • Bug 310770: Use the correct default settings for Nepomuk. See git commits 530c743a, fe4bb558, review request 107464.
  • Bug 304299: Use only one application instance when opening multiple files if possible. See git commit e45a847d, review request 107305.
  • Bug 311782: Do not show “Directory loading has been cancelled” message if an error occurs. See git commit 07ee7c06, review request 107787.
  • Use the new Nepomuk2::MetaDataWidget for the Information Panel, which provides many improvements compared to KFileMetaDataWidget. See git commits 487d6dd5, da5b7dcd, 32d5e287.
  • Fix crash when browsing contents of Bluetooth device. See git commit 90c7fd40.
  • Bugs 262464, 312812313992: Show file names in plain text, even if the file name contains HTML tags. See git commits 4e6d2d84, e27c4b3a, f05e18db, 8a97ca66, review requests 108291, 108336, 108307, 108584. Nice example that shows how tricky it can be to get something right that looks extremely trivial.
  • Bug 312679: Fix crash when sorting by “Date” and the modification time of some files is close to a shift to/from daylight saving time. See git commit 715f00a9, review request 108309. This was actually caused by the new parallel sorting algorithm – it turned out that comparing dates is not reentrant.
  • Bug 311794: Show correct duration for audio files. See git commit d23631d0, review request 108281.
  • Bug 314338: Do not delay the popup menu when clicking the “Create New” toolbar button. See git commit 4d9af664, review request 108397.
  • Bug 290736: Select the correct item as the new current item after deleting files. See git commit 14e5ba5b, review request 108356.
  • Bug 302264: Fix crash when showing version-controlled directories. See git commit a9d7ebbc, review request 107656.
  • Use the correct icon size in the “Edit places entry” dialog. See git commit 99f200d2, review request 108443.
  • Bug 313151: Allow “timeline” URLs as homepage. See git commit 87a4eb9e, review request 108428.
  • Bug 313466: Make the “A folder cannot be dropped into itself” message less intrusive. See git commit c1051731, review request 108483.
  • Do not update Nepomuk data more often than necessary. See git commit af280715, review request 108543.

Those who have not upgraded to Dolphin 2.2 yet can enjoy at least the bug fixes that are also in the last bug fix update for Dolphin 2.1:

Thanks!

These changes were made possible by the following people who helped by submitting or testing patches, analysing tricky issues, or providing extremely useful bug reports that made finding even the root cause of mysterious bugs easy: Adrián Chaves Fernández, Andrea Scarpino, Christophe Giboudeaux, David Faure, Emmanuel Pescosta, Hugo Pereira Da Costa, Johann Bergles, Kai Uwe Broulik, Michael Jansen, Sandro Mani, Simeon Bird, Vishesh Handa, and Xuetian Weng. If I forgot anyone, please let me know!

But these are not the only people who helped during the last weeks. Burkhard Lück did a great job keeping the manual up to date, and Christoph Feck and Jekyll Wu deal with a large part of the incoming bug reports. And without translators, the release team, packagers, and sysadmins, we would not be able to ship Dolphin to you.

Recent mailing list problems

This is just a short notification for anyone who tried to subscribe to or send a message to the kfm-devel mailing list recently. These actions have probably failed because there was a configuration problem last week. Its origin is unclear to me, but thanks to Ben Cooksley from our awesome sysadmin team, the problem has been found and fixed.

If you tried to

  • subscribe to the list, but did not get a confirmation message, or
  • send a message to the list which did not get through (you can check this in the list archives)

during the last 10 days, please just try again. Sorry for the inconvenience.

How to make Dolphin crash less, and other changes in KDE 4.9.4

A few weeks ago, I woke up in the middle of the night and could not sleep (fortunately, this happens very rarely). I took the advice that I once read, got up and tried to do something useful. I checked my e-mail and found a new bug report about a random crash that had been reported many times before, but whose cause had always been a mystery. Therefore, I was quite excited when I saw that this report contained step-by-step instructions to reproduce the crash. Once I could use GDB and Valgrind to investigate the crash, fixing it was easy (while handling events, never ever delete a QObject unless you are 100% sure that no event is waiting to be delivered to that object). Many thanks to G. Christ for making this fix possible!

In other news, David Faure fixed a bug in KDirLister that sometimes caused Dolphin to not notice changes in the current directory. This bug had been discussed intensively in Dolphin’s forum, and this discussion actually led to the discovery of a reliable way to trigger the problem.

Here is a summary of other changes in KDE 4.9.4:

  • Bug 310465: Fix failure to switch the view mode in directories where the .directory file is not writable or readable. See git commit 56407d94, review request 107458.
  • Bug 308018: Fix crash when clicking a context menu entry while renaming an item. See git commit 951cb9c3.
  • Bug 217575: Select all pasted files in the view, even if the paste operation was interrupted by a ‘File exists’ dialog. See git commit b25059e8, review request 107237.
  • Bug 304615, bug 296802: Don’t show files as ‘cut’ any more if the clipboard contents change. See git commits 41208058 and 59908290, review request 107390.
  • Bug 309498: Make the Play/Stop button in the Infomation Panel use the correct icon size. See git commit cc069353.
  • Bug 211472: Fix the problem that changes in directories are not noticed sometimes. See git commit 75da8e81.
  • Bug 310579, bug 282257: Fix a frequently reported random crash. See git commit a6f07452.

Ben Cooksley, Christoph Feck, David Faure, Emmanuel Pescosta, G. Christ, Jaime Torres, Jekyll Wu, and Kai Uwe Broulik provided patches or other helpful information that helped to fix these bugs, or helped by testing the patches.

Unfortunately, some regressions made it into the final KDE 4.9.4 packages (two in Dolphin, bug 311206 and bug 311246, and one in kdelibs: bug 311214). Our apologies go to users of KDE 4.9.4 who were or still are suffering from these problems. We fixed them immediately after they were reported, and some of the packagers, who do a fantastic job each month to bring a new bug fix release to our users, have even provided updated KDE 4.9.4 packages, which means that you might not see these regressions at all on your system. If you build KDE from source, you can apply the patches attached to this message to fix the problems. Again, sorry for the trouble and thanks to everyone who helped to fix them.

Regressions are a huge annoyance for everyone, so I’ll make sure that those parts of Dolphin that can easily be broken by accident will have a better unit test coverage in the future. For those who don’t know what unit tests are: when building Dolphin (or many other parts of KDE) from source, you can not only run cmake, make, and make install, but also ‘make test’ to perform an automated check of the basic functionality.

Also manual testing can help a lot: if you use the 4.9 or master branches or packages made from them, you update them frequently, and you notice anything that suddenly stops working, report it as soon as possible. Then we can look at the problem and make sure that it is fixed before the next release. Early feedback has often helped to identify such problems, but not everyone uses the software in the same way, and it’s impossible for one person to test her/his typical use cases every day. The more testing we get before the release, the better the result will be.

On the way to Dolphin 2.2

KDE 4.10 Beta 1 has been released this week, so I thought it would be nice to summarize the changes that went into the master branch during the last few months. Here is a current screenshot that shows some of them:

New Features

  • Àlex Fiestas added support for MTP devices (like phones) to the Places Panel, making use of Philipp Schmidt’s MTP kioslave. Check if your distribution provides packages for kio-mtp if you want to try it. I’m quite happy that I can finally transfer files to and from my phone easily in KDE (if you wonder why it shows up twice in the panel: that’s because the phone’s internal memory and the SD card are separate devices). See Àlex’ blog post (which also provides information about building kio-mtp yourself) and the review request for more information.
  • Amandeep Singh, assisted by Frederik Gladhorn, implemented accessibility features in Dolphin. Now you can have the current item shown zoomed in KMag.
  • Some people missed an easy way to resize the icons in the Places Panel in KDE 4.9. For those who didn’t know: Dophin’s Places Panel had been rewritten, and the automatic resizing of the icons when the panel was resized (or in some other situations, like when a ‘Place’ with a long name was created or removed) was dropped. We now have an ‘Icon Size’ submenu in the panel’s context menu, just like in the tool bar. I think that this is the best solution: users who want bigger icons can just choose their favourite size.
  • Dolphin 1.x provided two different ways to rename files: ‘inline renaming’ and renaming using a dialog. This changed some time ago due to the view engine rewrite. In KDE 4.8, inline renaming was not ready yet. In KDE 4.9, it replaced the dialog completely (except for the case that multiple files are renamed at the same time), but some people actually got used to the dialog and missed it. In KDE 4.10, you will be able to choose again. Emmanuel Pescosta added a checkbox to the settings dialog.
  • Ivan Čukić made it possible to report the current directory to the activity manager, such that it can easily tell what your most favourite directories are. You can disable this in the System Settings, ‘Workspace Behavior’ if you don’t want the activity manager to keep a log of your directories and documents.

Performance Improvements

Emmanuel Pescosta worked hard to make Dolphin faster:

  • The part of Dolphin that keeps track of the previews that need to be generated did not handle its internal data structures in the most efficient way. Look at the review request for details and for the impressive Callgrind data.
  • Loading a folder with many files can be very slow. It turns out that much of this slowness is due to the “natural sorting” of the items, which makes sure that “image10.jpg” comes after “image9.jpg”, and not between “image1.jpg” and “image2.jpg”. There have been some ideas how the “natural comparison” of two file names can be made faster, but this requires a lot of work. In KDE 4.10, we still use the old comparison function, but make use of all CPU cores on your system to keep the delay when opening a large directory short. Look at the final version of the patch to see how little code you need to make Mergesort use multiple threads with QtConcurrent!
  • The icons which are shown for files and folders if previews are disabled are now cached to save CPU cycles and memory.

More little improvements

The improvements in Dolphin 2.2 were made possible by the following people who contributed patches, provided advice on patches while they were still work-in-progress, and tested features early to report problems and regressions: Alex Fiestas, Amandeep Singh, Christoph Feck, Emmanuel Pescosta, Frederik Gladhorn, Hrvoje Senjan, Ivan Čukić, Jekyll Wu, Kai-Uwe Broulik, Panos Kanavos, Vishesh Handa, and Weng Xuetian. Thanks for your help! If I forgot anyone, please let me know.

If you test Dolphin and find any regressions (or old bugs which haven’t been reported yet), please report them at https://bugs.kde.org/.