Archive for May, 2010

Grantlee in use

May 20, 2010

The first release of Grantee is only 6 weeks old, but already third party developers are investigating the features it offers and the possibilities templating brings to their applications.

Ronny Yabar is using Grantlee for theming of KMail and broader KDEPIM as part of his Google Summer of Code project and has already made promising progress and uncovered a bug (fixed in Grantlee 0.1.1).

GSOC also brought an opportunity for Yiannis Belias to use Grantlee for code generation. Yiannis is doing a project this year for OpenICC, a color management platform. The project involves refactoring a lot of existing code, some of which includes a lot of repetition. Templating is being used to simplify the process of generating refactored code, generating new classes and possibly become a more long-term solution to the maintenance needs of the codebase.

Ryan Paul of ArsTechnica showed me a prototype of a twitter client using Grantlee. A simple template is used to generate html which is then shown using a QWebView.

Twitter client written in Qt using Grantlee to render the html

The template itself is mostly just a simple loop to generate the table.

<div class="messages">
     {% for m in messages %}
        <div id="{{ }}" class="message" style="border: 2px solid {{ m.color }}; border-left: 7px solid {{ m.color }};">
               <a href="{{ m.profile_url }}">
                 <div class="imgbox" title="{{ m.sender_nick }}" style="background-image: url({{ m.image }});"></div>
               <p class="content">
                 <span class="title">{{ m.sender }}</span>
                 <span class="time"> (<a href="{{ m.url }}">{{ m.time|timesince }}</a>)</span><br />
                 <span class="text">{{ m.html|safe }}</span>
     {% endfor %}

Ryan has moved on to using Qt Quick for his twitter client. However, this has given me some ideas on how I can make it easier to use Grantlee for these kinds of tasks.

Arduide is also using Grantlee for html generation, such as the built in documentation and examples browser. A simple map is easily expanded with some loops into a summary page of all examples.

The themed browser content in Arduide is generated using Grantlee

These are just some of the things made possible by an accessible templating system. I have many more ideas of how it can be used, and I’m sure many other people will too.

KBiHash brings simple API for bi-directional hash.

May 16, 2010

While refactoring KSelectionProxyModel I’ve been trying to address the problem that it’s really hard to implement QAbstractProxyModel.

There’s just so much API to implement. The entire QAbstractItemModel API needs to be implemented along with listener API for the source model (eg, sourceRowsAboutToBeInserted/sourceRowsInserted) along with mapToSource and mapFromSource for the proxy model and the internal mapping structures necessary for that.

The requirement of an internal mapping structure is that it must be possible to map objects representing QModelIndexes in the sourceModel to QModelIndexes in the proxyModel itself and vice-versa. In the refactor-in-progress KSelectionProxyModel I was until recently using a QHash to map parent indexes in the source model to parent indexes in the proxy model. The QHash gives O(1) time complexity for lookups, so mapping from the source model to the proxy is fast.

However, mapping from the proxy model to the source model required a call to QHash::key() to get the key given a particular value. That is a O(N) call. Initially I considered adding another mapping in the other direction to the private class, and maintaining both within the proxy implementation. That would be error prone however and not reusable.

The reason for this refactoring work is to make reusable components to use to implement proxy models with. So I needed a class to implement an efficient mapping in both directions. I implemented KBiHash which provided an opportunity to try out the massif-visualiser Milian has been writing and the QTestLib-Tools.

KBiHash maintains two symmetric QHash objects

KBiHash maintains internally a QHash<T, U> and a QHash<U, T> and provides iterators for both “sides” of the mapping along with API for inserting, removing, updating and querying from both sides. The fact that it is also quite similar in structure to a QSet<QPair<T, U> > is not lost on me, so it also provides some set-like API such as intersect(), subtract() and union(). Because the implementation is a bit na├»ve though (it’s a quick hack) a few nice-to-haves are a bit restricted, such as operator[] returning an always const reference. Allowing the return value there to be modified would make the internal QHashes out of sync. I suspect though that a real proper implementation might be able to solve that, and be a lot faster, but for now the main benefit of this class is the convenient API for managing the two way mapping. It should be useful in QAbstractItemModel implementations too where you need to map from a void * pointer to something else and vice-versa.

Benchmark results comparing KBiHash with QHash are almost entirely unsurprising. All benchmarks were executed ten times and the results averaged. The results before averaging are here. In the plots below N refers to number of instructions executed as reported by callgrind and size is the size of the container under test. Note also that the x axis is logarithmic.

Insert grows linearly, but is usually 100% larger in the KBiHash case. This is because both the left and right side of the mapping need to be hashed on insert. It could be larger by a different percentage depending on the complexity of the hash function for each type if two different types are in the KBiHash.

Key lookup is comparable as expected. The small relative difference may be caused by the fact the the hash is nested in another class.

Reverse lookup cost grows linearly for calls to QHash::key(value). Reverse lookup for KBiHash is still O(1) as it is still just a hash lookup.

Cost for removing items by key is also as expected. The KBiHash case is more expensive because the item must be removed from both internal hashes

Results for removing values from the KBiHash are also comparable to removal of keys in the KBiHash. Removing values from the QHash is slower for the same reason as reverse lookup.

Updating a key is constant for both QHash and KBiHash.

Changes to values are constant in both QHash and KBiHash

The memory usage of KBiHash is also greater than QHash, as expected when maintaining two hashes. The peak and average memory consumption in the KBiHash case is almost twice as large as in the QHash case.

Memory profile of KBiHash

Memory profile of QHash

The case against boost::bimap

An important part of being a software developer is reinventing what already exists in the standard template library or boost. We all do it I think.

boost already has a class, boost::bimap, which implements a forward and backward mapping based on std::map API. There are a few reasons I didn’t use it here.

Firstly, writing KBiHash was a good learning experience. It’s the sort of thing which has lots of hidden corners that you don’t expect. For example, when inserting a new pair into the mapping, it is necessary to explicitly remove entries in the opposite map. I probably would not have remembered to do that each time if I was simply maintaining both mappings manually, but it’s good to learn.

Secondly, boost::bimap is semantically slightly different to what I need. When inserting into the bimap and the left or right value is already there, it is not overwritten, but the operation is ignored. If using boost::bimap I’d end up using a lot of remove followed by insert anyway to work around that.

Thirdly, as std::map maintains sort order of keys, it may be slower than QHash. The average for key lookup and insertion in a map is O(log n), whereas for QHash it is O(1). It would be nice to include it in the benchmarks here, which brings me to the last point.

The API of KBiHash is more Qt-like. I couldn’t figure out how to use boost::bimap. Even though there’s a long tutorial for it, I couldn’t figure out how to compile the benchmarks. My attempt is ifdef’d out in the benchmarks file though, so if anyone else can figure it out I’ll add it to the benchmark plots.

Grantlee v0.1.1 now available

May 9, 2010

I’ve just made a new version of Grantlee available for download. This release contains two minor fixes and one workaround for a bug (or feature?) in WebKit.

I noticed when running Grantlee unit tests against Qt4.7 that they were segfaulting on exit if they used scriptable tags. After a debugging session I’d narrowed it down to just creating a QScriptEngine in a plugin will cause a crash. Qt4.6 didn’t show the same behavior, so I thought there would be no more for me to do.

Unfortunately the segfault was caused by the fact that JavaScriptCore in WebKit was not designed to be loaded (and unloaded) in a plugin. Interesting place for a Grantlee bug to end up, I thought. That meant that it would not be directly resolved in Qt4.7.

The workaround is to build in support for QtScript template libraries directly into the grantlee_core library instead of loading it in a plugin, which is the behavior as of this release. Hopefully that’s a temporary workaround.

Navigating a QAbstractItemModel tree in a QML view

May 5, 2010

QML in Qt 4.7.0 will feature elements for using QAbstractItemModels which are really lists. It is not possible to directly display a treeview on a hierarchical model. There are several good reasons for this.

  • It is difficult to define an API that will stand the test of time. NQDF don’t want to get it wrong early and have to maintain something broken.
  • It is difficult technically. There are other important things to do before release, and this would be a time-stealer.
  • It is not yet certain from a user interaction point-of-view where trees will be relevant in mobile UIs, including how to navigate one and how to visually represent it.

For those of us already prototyping though, some solution is needed. As a first iteration of a user interaction design, we’ve been experimenting with the use of breadcrumbs to navigate the view.

[OGG link]

Unfortunately the video capture is not very smooth, but there is an animation when selecting a breadcrumb. For illustration purposes, the selection made in the qml environment in mirrored in a QTreeView on the left.

Implementing this concept was actually the motivation behind developing a ui independent breadcrumbs list and a method of proxying selections through complex systems.

As this is very new, we would really like feedback about navigating the tree this way. This could be part of your next mobile email client, so now is your chance to help us make it more intuitive. We might consider user feedback on this stuff in a more formal way later.

  • Is your understanding of the current position in the tree clear?
  • Is it clear to you how to move “up” the tree?
  • Is it clear to you how to move “down” the tree?
  • Do the animations help your understanding of navigating the tree?

If you can’t compile code and don’t have a N900, feedback from watching the video is welcome. To compile the example on your computer (requires unreleased version of Qt 4.7):

svn co svn://
mkdir build && cd build
cmake ..

If you already have a N900 with Qt4.7, you can try out the demo by running the example from the tarball here.

Let us know what you think!