Category Archives: C++

Things dealing with the C++ programming language.

Speed up!

So. Matthias Fuchs of “Speeding up KGet with Callgrind” fame pointed out to me on IRC the other day that KIconLoader seemed to still be using a lot of time to load icon image data, even when the icon should have already been cached.

I managed to confirm the issue. Turns out that when I ported KIconLoader to use KSharedDataCache, I didn’t employ KIconLoader’s other cache (a pixmap cache [1]) in all the instances where it made sense. Specifically, the pixmap cache only had things added when an entry was also added to the KSharedDataCache.

But this doesn’t always make sense. The KSharedDataCache is shared across all KDE Platform-based processes, but there’s a different pixmap cache for every KIconLoader. So, it’s perfectly possible to have many processes never have to add an icon to the KSharedDataCache.

Now, new pixmaps that are read from a KSharedDataCache are added to a KIconLoader’s own personal pixmap cache to avoid trying to search the KSharedDataCache next time. This has the potential to significantly speedup icon-based operations, especially in situations where an application uses the same pixmaps over and over. This speedup is in trunk (future 4.6) and will also be released with KDE Platform 4.5.2.

Matthias (and Ingo Klöcker) provided another speedup, by converting some slow QString-based operations to use a QStringBuilder class introduced in Qt 4.6. This gave an 8% speedup on an icon microbenchmark, so not insignificant. This one will only be in KDE Platform 4.6 at this point, although I wouldn’t feel horrible if it were to be backported also.

Incidentally, this was the first I’d heard of regarding QStringBuilder, so it’s something I’d recommend brushing up on if you haven’t heard of it yet. The QStringBuilder documentation is part of the QString API reference (search for “More Efficient String Construction”).

[1] Every KIconLoader instance also has its own pixmap cache, which holds QPixmaps, while KIconLoader’s KSharedDataCache holds QImages.

KSharedDataCache

So in my last post I had mentioned some of the issues that have been encountered with KPixmapCache, and that I was working on a separate implementation.

Based on the fact that the underlying code is easily made more general purpose I’ve gone ahead and went down that path. With that in mind, the current code I have is available from a branch of kdelibs that I’ve made a few hours ago, called kdelibs-shareddatacache, available from /branches/work. This branch adds a class called KSharedDataCache, adds a KImageCache which operates on top of KSharedDataCache, and updates Plasma::Theme and KIconLoader to both use KSharedDataCache.

I don’t have time to go over the implementation details (I’ll try to do so this week if I get time though) but I will throw out the following:

  • My port of KIconLoader was so much of a hack that the original KIconCache is still there! It’s just not being used for icons. I think the Plasma::Theme work is a little cleaner but probably could be better handled itself.
  • Changing the icons requires a separate patch to kdebase/runtime/kcontrol/icons that I will apply if this should ever land in trunk. (It’s a bit faster too…)
  • On the topic of speed, I don’t have any benchmarks, mostly because that wasn’t the reason I was mucking about in the cache. It seems a bit faster to me but I’ve done no formal testing.
  • My larger concern was correctness. Absolutely everything is locked (double-locked in one particular scenario I was able to think of, look in the code if you’re interested…) and things seem to pass the consistency tests I’ve been able to throw at it now. The limited testsuite for kiconloader seems to work as well.
  • This work depends on having a pthreads library with “process-shared” locking primitives (at the very least mutexes) but I have not added relevant CMake checks yet.
  • Now that I think about it I also probably should be using timeouts and checking some more return codes here and there.

It’s available if you’re interested though. If you do go this route, I have an auxiliary tool which you can use to view the contents of a cache:

It obviously requires the headers for the new classes so you will need to have installed the modified kdelibs. You can download the source from http://purinchu.net/dumping-ground/cacheviewer-1.0.tar.bz2. When it asks for a cache name, just give it one of the *.kcache files in your /var/tmp/kdecache-$USER directory (examples: icon-cache or plasma_theme_Aya (or whatever theme you’re using)).

(By the way, isn’t it *scary* that the icon cache had been accessed more than 100,000 times in a 12-hour period? ;)

Bug of Legend

So. Those of you who notice the things I post will presumably notice I haven’t blogged as much recently. Essentially it’s because I have less time for development between school and work (I’m on shore duty so I don’t deploy, but I’m in charge of a division so my hours are still substantial).

The spare time I have had over the past month I’ve mostly spent trying to (re) fix my new favorite bug ever, bug 182026 which is a crash bug in KPixmapCache::discard().

You should hopefully have no clue about what KPixmapCache is other than that it’s what’s crashing most of your favorite apps, so I’ll give you the rundown. Back when KDE 4 was being developed and we were shifting to use the shiny SVG icons and graphics everywhere it was noticed that rendering SVG graphics took rather more time than simply loading a PNG from disk. So, instead of loading a SVG file from disk every single time it was needed, the end result (a PNG) was cached to disk instead, and a quick check is done to ensure that the underlying SVG file didn’t change. I didn’t write the code but thought it was interesting and committed a couple of bug fixes and now I apparently maintain it. =D

For efficiency reasons that on-disk cache is accessed by each KDE process using a shared memory segment (although it then gets inefficient again by using I/O operations anyways, but that’s for later). Anytime you have multiple processes or threads accessing a shared resource you need a way to handle that contention to make sure that the sensitive parts of the code are only being run by one thread at a time.

The second problem that was reported as 182026 was that the “discard” feature of the cache seemed to cause crashes for a lot of people. (Although oddly enough, not for any of the 3 test systems I have. Call me lucky…). The idea of discarding the cache contents is that the application code knows that something changed which means that essentially all of the stored graphics will not be needed. The major way most people see this is by changing Plasma themes (where the old theme’s graphics are now useless) or by changing the icon theme.

The underlying issue is that ::discard() uses essentially no locking. Instead it tells the shared caches to reload themselves on their next operation (a process referred to as “invalidation”), disconnects from shared memory, and deletes the cache file on disk. Or at least, it used to. Merely adding locking helps, but is solving the wrong problem. Any time the cache is disconnected from shared memory, it will try to reconnect later, re-creating the file on disk if necessary (and it is necessary in this case). But this is all just to say that the cache is now empty, there’s no underlying reason that we have to deallocate everything just to turn around and reallocate it.

So when I committed my fix for 182026, I did the following:

  • I added a flag to the cache to mark if it was simply empty or not. This allows me to discard the cache without having to disconnect it from shared memory or invalidate it.
  • Made KPixmapCache::discard() take the cache lock first before it did any of that.
  • When copying the cache for resizing, KSaveFile is used instead of truncating the cache (especially in case any cache locks have to be broken due to timeouts)

Unfortunately my initial fix had the side effect of breaking the “cache” part of KPixmapCache as it would never find cached items again. It was noticed by a KDE Games developer though so 4.4.2 should still be good to go now that I’ve fixed that.

A final side note is that I think I need to change the code that deletes an entire named cache to discard the cache as well for those processes that already have it attached to shared memory.

I have an alternative shared-memory cache implementation which I hope to integrate for KDE Platform 4.5 or 4.6 (although it may simply end up as KSharedCache or similar instead of merely replacing KPixmapCache due to API additions in KPixmapCache I don’t feel like supporting). At some point in between I may write a post about the underlying cache architecture and some “Do”s and “Don’t”s but I think I’ll just stop here for now. :P

Tooling around

Some minor things:

Temporary confusion: On a mailing list the other day someone was having issues with the following type of code:

const char *name = m_obj.byteArray().constData();
printf("%s", name); // kaBOOM

So what was wrong? In this case, usage of a pointer that was freed. Freed, in this case, by the QByteArray object that was created and destroyed all on the same line. In other words, this part: m_obj.byteArray() returns a new QByteArray (called a temporary object since it is not named by the programmer). The .constData() tacked onto it grabs the address of the data in that QByteArray.

Unfortunately, by the time you’ve used the pointer on the next line, the temporary QByteArray has been destroyed. Now that pointer you have is dangling into unallocated memory and who knows what will happen. Maybe it will work, maybe it won’t, but it’s technically undefined behavior.

The solution is to assign that QByteArray to some local variable first, that way the compiler won’t destroy it on you. Also note that passing this pointer to an enclosing function is also fine, like this:

printf("%s", m_obj.byteArray().constData());

The compiler will make sure that all of the temporaries invoked to handle a function call will be alive until after that function has run (destroying temporaries is done as the last step of that entire expression). This is what makes the qPrintable() function useful.

Also I saw a interesting link about GCC optimization on Hacker News. Basically the -Os (optimize for size) flag ends up being the fastest compilation option in many cases. This is due to the fact that it takes so long to access data that is not in the cache for modern day architectures (in comparison to CPU speed) that it is often better to do a lot of extra work for the CPU if it will mean that the code size is smaller. I’ve used this flag for awhile with no ill effects (on the other hand, no blindingly obvious speedups either ;) It’s something to think about when you’re playing with your compilation flags.

Yay, it’s been so long since an uninformed C++ rant.

You may start by reading The Tailor, off of Planet GNOME.

Back? Good. Let’s deconstruct the points :) (Quotes are abridged and not direct quotes because I don’t feel like doing the copy-editing required)

  • Methods should be virtual by default so inheritance works. Well, inheritance at run-time, since inheritance still works just fine. To be honest this is probably one other thing that could have been different between class and struct, is class having all methods be virtual while you need to specify it with struct, so that you can still write simple classes with little to no overhead, such as QColor for instance. Then again, you could actually spend the 5 minutes it takes to understand non-virtual functions (hey wait, we already know how non-virtual functions work! :) and move on with your life. Also, this is snark’s most frustrating issue with C++… I don’t know if he’s referring to the same language I am but there’s about a half-million things more annoying than virtual in C++.
  • You need to have virtual base destructors in classes with virtual methods otherwise Bad Things Happen with no warning. Except that there is a warning. Fair argument though, I remember even Qt wasn’t immune when the warning was first introduced (or turned on with -Wall) by g++.
  • It’s annoying to use multiple inheritance because you have to be really careful. Then don’t use multiple inheritance, just like GTK+ and Java don’t use it.
  • Conversion constructors are annoying because they enable a type of bug, which the C++ guys thoughfully included a keyword for to avoid automatic conversion. If this kind of bug really trips you up, don’t use conversion constructors at all. Hey, less code to write!
  • C++ lets me do other unsafe things. True. So does C, Python, Perl, Ruby, and etc. etc. etc. Are we really supposed to pine for languages that put you in a straightjacket? If you don’t like features which are potentially unsafe, then don’t use features which are potentially unsafe.
  • Don’t respond that the language isn’t at fault because that proves you’re drinking the Kool-Aid No language is without fault, but it hardly seems sporting to say that C++ is bad because it gives you more options. If you want a more restrictive language then use Java or C#.

Or to put it another way, I don’t like spicy foods. At all. But you don’t see me blogging about how spicy food is horrible, OOHHHHH NOOOO HOW DO YOU EATZ SPICY FOOD????, etc. The reason I don’t is because I know that many people enjoy spicy food, and because I DON’T HAVE TO EAT IT IF I DON’T WANT TO.

On the same note here, most of these points against C++ are things that other programmers actually desire. I like implicit conversions in some cases (although I’d rather have an implicit keyword than explicit). I certainly like having the option to have simple classes that don’t necessarily have to have a vtable, even if that means I need to remember to make my methods and destructors virtual.

Worse yet, this is a rant with no solution. C++ can’t change now, and there are plenty of popular languages out there where this list of complaints don’t apply. So why the rant on C++ when you could be writing your Vala application? Or to bring back the tailor analogy, if you could tell that the suit didn’t fit when you put it on, why did you buy it anyways, when there were other perfectly good suits available, and other men fit into your poor-fitting suit just fine?

I suspect that snark has never actually used C++ for anything substantial. Or if he did, I’m very shocked that “templates” didn’t make his list at all…

More programming tips

In the spirit of my series of programming tips articles I thought I would go ahead and throw out some more:

  • If you are using QAction, QCheckBox, QRadioButton, or similar classes, then you need to be wary of the differences between the toggled(bool) signal and the triggered(bool) (for QAction) or clicked(bool) (for button-like classes) signals.

    These two signals are used in two different situations. toggled(bool) is always for if the value of the action or button being checked changes, for any reason. This means that if an QRadioButton had not been checked, and it is set to being checked, it will then emit a toggled(true). You would use this signal if you needed to update your GUI based on whether an action is checked for instance.

    The other signal (triggered or clicked) are used when you need to perform an action based on a user action. For instance, if you had a "[ ] Show Wikipedia content" on your menu bar, you may want to bring up that window as soon as the user clicks on it. On the other hand, if you were changing the checked status of the action internally to your code but didn’t want the window to pop up, you’d want to use the triggered signal.

  • If you’re not continuing to study then you’re not going to get any better at programming. I’ll generally visit programming.reddit.com (and also the C++ and Perl sub-reddits) and sometimes you’ll catch a new technique that is neat. For instance:
  • From Mr. Edd’s C++ blog: You can use the not-well-known feature of C++ to give “pointers to member data” to allow for assigning a null pointer to smart pointer classes, while not allowing any other pointers to be assigned. His writeup covers everything so I’ll refer you to that but suffice to say that something like “smart_ptr service = 0 would work, while “smart_ptr service = &newService” would not. This is useful in basically any place where you want to allow a null pointer to be assigned by not any other kind of pointer.
  • Another interesting tidbit is the restrict keyword, available in C since the C99 revision. Sadly, it is not available in C++, not even the upcoming C++0x standard, except as a compiler extension. The use of the keyword is fairly low-level, and is explained in this article for Cell processor development.

Hopefully you’ve learned something neat (and useful and not merely contrived!)

The RANDU pseudo-random number generator

On my homepage I have for awhile mentioned that I wanted to get my symposium project posted someday.

I’ve finally had a chance to touch up the code I used in the symposium and I’ll briefly mention here what this is all about.

In the late 60’s IBM developed a random number generator for its System/360 computers called RANDU. The algorithm was designed to be fast and have an easy implementation. Unfortunately it had a lot of deficiencies associated with it as well, including some glaring anomalies which are visible if you plot RANDU-generated points in 3 dimensions.

View of RANDU points looking like a uninteresting random distribution in a cube (click to enlarge)

This view of a RANDU-derived point distribution doesn’t look so bad. But if you rotate around the view a little bit, you’ll see this:

View of RANDU points looking like a set of planes (click to enlarge)

That doesn’t look very random at all. This type of testing is referred to as spectral testing, and it carries on to greater than 3 dimensions even (although it’s hard for us to visualize of course). Spectral testing is just one of a series of different tests that scholars use to determine how “random” psuedo-random number generators really are.

RANDU was bad in other ways too. Although it could output up to 2^32 or so different numbers it started repeating numbers long before that point (which makes the output not-very-random at all).

Anyways, this was the essence of my symposium project. It was a program I used to aid my demonstration, written in Qt 3 on Linux and then cross-compiled to Windows using a free (as in beer) Borland compiler running under Wine (I forgot what patch I used to eventually make it work). (The Qt 3 I used came with C++ GUI Programming with Qt 3 as a non-commercial license).

The program itself was derived from a series of programs I used in my Computer Graphics class (where we basically implemented 3-D primitives ourselves instead of with OpenGL — this was the first time I got to use OpenGL’s 3-D features), so that’s what the rotation and scale features are for (as in, I didn’t take them out).

As I mentioned, I ported the program to Qt 4. I used this as my opportunity to learn how to use the git source control program, which I’m liking more and more as we go. The final result is available from this link, with 3 random number generators, including RANDU.

I’ve fixed many stupid programming mistakes but a lot of the history is still evident in the code (such as scaling all the random numbers to 0-1000.0 arbitrarily. :))

Another programming tidbit

Now that Super Bowl weekend is over (Go Steelers!) it’s time to get back to fixing bugs and typing up code. That brings me to my helpful tidbit for today.

A few JuK bugs have been related to this issue, and I just saw a second kdelibs bug today which I think is related to this (the actual bug is unimportant) so I think it’s important to get out the following message: QObjects do not free you up from having to write proper destructors.

Here’s a more detailed explanation of the problem. Let’s say you have a widget, which has a private d pointer. Your widget itself contains several sub widgets which are children of your widget. One or a few of these widgets rely on an object contained in your d-pointer. It may look something like this:

A simple class diagram

Of course, graphically illustrated the problem might seem obvious here, especially if you know how QObject’s destructor works: If you delete the d pointer while the View is still using it then you run the very real risk of a crash. This can occur if your destructor looks like this, for instance:

Widget::~Widget() {
  delete d;
}

After your ~Widget has run then your d pointer and its DataStore are no more, but your View and Button are still alive. This is usually OK, as the QObject destructor will delete them and there will be no memory leak. However, if anything happens to the View which would cause it to access the DataStore object before the program gets to that point, then you have a crash on your hands. The race window is very small here if you’re racing with an event handler for instance. The problem is a lot easier if View uses DataStore in its destructor since it will pretty much always crash there.

If DataStore had somehow been a child of View there wouldn’t have been an issue (since QObject deletes children first), but that unnecessarily fouls up the class design and besides, it’s usually either not possible or desirable. But when you have situations where you have children that depend on siblings for their functionality, you must delete them manually in your destructor or else the effectively random order that is chosen by QObject is what you’ll get, which can lead to hard-to-reproduce crashes. In this case, we would delete View before we deleted the d pointer. We don’t have to delete the Button manually since it does not depend on any of its siblings, although it doesn’t hurt either.

Quick tips

I’ve rounded up some useful tips, none of which are really important enough to warrant a post just by themselves. So without further ado…

  • If you’re running kdesvn-build, you can use the --refresh-build option to force the given modules to be built with a clean build directory. But what if you didn’t want to do that for all of the modules on the command line? What you can do instead is create a file called .refresh-me in the toplevel of the module’s build directory (e.g. build/kdelibs/.refresh-me). When kdesvn-build rebuilds the module, if it finds that file it will perform the build process as if –refresh-build had been passed. Since –refresh-build involves deleting the build directory this is a one-time-only event. Next time you build everything will work normally.
  • Konqueror deserves several posts on its unique gems just on its own. But one thing I’ll mention is the address bar. There are two different keystrokes that I know of to quickly select the address bar: CtrlAlt - O will select the address in the address bar, handy if you just need to make a quick change to go to a different address. Ctrl - L on the other hand, will delete the text in the address bar first. I think this is a holdover from earlier days to be honest though, as since the URL is selected by default I can’t think of anything that Ctrl - L can do that is easier than using CtrlAlt - O. Update 2:One of the commenters pointed out that the selection buffer gets overwritten using Alt – O but is maintained with Ctrl – L. (i.e., when you middle-mouse-click to paste).
  • Do you use QDataStream? If so then it is imperative that you set the version of the stream. What I mean by this is that sometimes the binary representation changes depending on what version of Qt you are using. So a stream saved by a older version of Qt may be unable to be read using a newer version of Qt with the default version settings. QDataStream is backwards compatible; you just need to know what version to set the stream to. The process is described in the API documentation. Basically you need to set a specific version before writing and before reading. Some types (such as the integer types) are guaranteed not to change their representation, which you can use for versioning.
  • If you are a Qt programmer, then Thiago’s description of QString behavior is required reading.
  • Many people know that the C++ delete operator can safely be called on 0. Per the standard, this is also true for the delete[] operator, so you don’t need to check for null either way. (Of course, there are reports of compilers that screw it up for delete[], sometimes you can’t have your cake and eat it too).
  • And on that note, C++ has an interesting behavior that makes some variadic functions harder to use safely. To wit:
    • C has a NULL macro to represent the null pointer. Typically it would be along the lines of #define NULL ((void*) 0) or thereabouts. void * can be converted to any other pointer type so this is valid.
    • In C++ however, you can’t convert pointer types all willy-nilly. So the #define NULL ((void*) 0) doesn’t work. Instead you use plain 0, which C++ guarantees will be converted to the null pointer when used in a pointer context.
    • The key word here is “used in a pointer context”. Some variadic functions assume that the last parameter will be of a so-called sentinel value. It is up to the programmer to ensure they pass the sentinel correctly, and with the right type. For instance, many gstreamer varargs functions assume a null pointer will be the final argument.
    • If you use the NULL keyword things will work great in C and C++… if you’re on a system where int and pointers have the same size. On 64-bit systems this is not necessarily true.
    • The problem is that NULL is defined to plain 0 for C++. When 0 is passed as the last argument it is assumed to be of int type, not of a pointer type. For most 64-bit systems this will involve placing only 32-bits of 0 on the stack instead of the required 64-bits, and “undefined behavior” results.
    • The solution I used when I encountered this problem in KDE 3’s JuK was to simply define a GST_NULL that did the right thing. Other options are manually casting to a pointer type every time you use one of the vararg functions. But it’s something to keep in mind anytime you’re using variadic functions.
  • The upcoming revision to the C++ standard will include an actual null pointer instead of faking it with 0 and at least this kind of issue can be fixed. Some compilers have already included such a feature (including GCC) and so you may have never encountered this problem.

That’s enough food for thought for now though, hopefully this is enlightening reading for most. Update: The keyboard shortcut is Alt – O, not Ctrl – O.

Improved crossfadiness

So I’ve made a few more changes to the crossfading code in JuK. This should hopefully fix crossfading issues completely for people. However, life is weird sometimes. phonon-gst went from being completely unusable (it would crash with JuK) to being the best option right now (perfect crossfading, at least here). phonon-xine, due to the way crossfading is now implemented sounds slightly crackly sometimes while playing music back. Even with the new crossfading routine, incoming music starts out at a high volume before fading in, although it does sound smoother.

Basically what used to happen is that JuK would pipe the music directly from the file to the Audio Output object. Phonon allows you to insert effects into that audio path, which is how crossfading works. You simply start playing the next song with a fader effect, set to fade in, and at the same time insert a fader effect into your currently playing stream set to fade out. Unfortunately phonon-gst has issues with removing effects from an audio path it looks like, which is why I was getting crashes. Even when I fixed the crashes by simply leaking the object as an experiment, the crossfading was horrid under phonon-gst as it takes seemingly forever to setup the fader and insert it into the audio path.

So what I’ve done is to simply insert the fader effect into the path from the start, and simply tell it to fade at the right time. Presto! Except that doing this seems to cause artifacts with phonon-xine output sometimes… *sigh*. But for now now it looks like phonon-gst has gone from unsupported to the best option for JuK at this point, hopefully all the backends will work equally well by KDE 4.1 though.

In other news, kdesvn-build in /trunk will allow you to build the Phonon pseudo-module. I say pseudo because there is no phonon module. It is developed in kdesupport. However I’ve been informed that the correct place for most users to build phonon from would be /branches/phonon/4.2. kdesvn-build has a couple of hacks that would support pulling it from the right location but still wouldn’t be able to build it due to the module layout. So I’ve added a bit of special support for it. I also changed the sample rc file to show how to build Phonon 4.2. If it’s important enough I’ll go ahead and make a 1.6.1 release.

Is there anyone looking forward to C++0x more than I am right now? :) The linked Wikipedia page has tons of changes, some which worry me a bit due to syntax (for example, lambda functions). Then again, I’ve never seen a good syntax for lambda functions, although I’m sure it’s just me.

But things like an auto keyword to allow for automatic type deduction? Very nice. For example, instead of doing:

for ( QList<QWidget *>::ConstIterator it = list.begin(); it != list.end(); ++it() ) {
  // use *it
}

you could do:

for ( auto it = list.constBegin(); it != list.constEnd(); ++it ) {
  // use *it
}

I did have to change begin/end to constBegin/constEnd to make sure that the non-detaching forms of the iterator are used, but this may be something that g++ is able to deduce as well someday.

Probably the biggest other feature I’m looking forward to is the “rvalue references”, which will allow for constructors that “move” data instead of having to copy them over. Qt has kind of mitigated the problem somewhat in their shared classes but you can benefit from this even in non-Qt-using code. There’s many other improvements too, I just wonder how long they’ll take to get into a g++ which we can use for KDE development. :)