Exporting History from Konqueror

In my Konqueror settings I have had it retain my history sense August 2006. This has resulted in a history file that contains over eighteen thousand entries. As you can guess Konqueror has some trouble with a history of this size. A dataset of this size is a good way to test any history managers memory usage and performance. I was hoping to be able to export the data with dcop, but unfortunately the only function available is allUrls which doesn't make that much sense because the dates are just as important as the urls. To see your history urls with dcop use

dcop konqueror-11489 KonqHistoryManager allURLs

replacing 11489 with your Konqueror number of course. Reaching a dead end with dcop I whipped up a tool that uses libkonq to extract the history.

#include <kapplication.h>
#include <kcmdlineargs.h>
#include <konq_historymgr.h>

int main(int argc, char **argv)
{
    KCmdLineArgs::init(argc, argv, "konqueror", "konqueror", "I do stuff", "0.1");
    KApplication application(argc, argv);
    KonqHistoryManager manager(0, "manager");
    KonqHistoryList list = manager.entries();
    for (uint i = 0; i < list.count(); ++i) {
        printf("%s\n%s\n%s\n",
                list.at(i)->url.url().latin1(),
                list.at(i)->title.latin1(),
                list.at(i)->lastVisited.toString().latin1());
    }
    return 0;
}

Already this data has proved useful and helped me reduce my memory footprint by half and catch my performance bottlenecks so it can handle 20 entries or 20,000 just as fast. If you are interested in playing with the dataset send me an e-mail.

Valgrind callgrind tools Part 3: Code coverage

In the Valgrind manual they list some tools you could write for Valgrind. One of the suggestions is to write a coverage tool. So a few months ago I sat down and did exactly that. It was a nice little tool and I happily posted it to the Valgrind developer mailing list only to discover that I was not the first person to do this nor was any of our solutions that good in the end. The easy part of the project is obtaining a recored of what was executed. In fact Cachegrind does a fantastic job of that. The only thing my tool did (that I thought was new) was automatically collect data on all the jumps which discovered after I wrote my tool was already present in the callgrind tool if you pass in the argument "--collect-jumps=yes". So me and several others have all written bad versions of callgrind and the cg_annotate script. Code coverage with Valgrind is made up of two problems. The first is obtaining the code execution and the second is applying this over the source for the program. The first is easy by using "callgrind --collect-jump=yes". The second part isn't as easy a new problem for every language, but at least for C++ using Roberto's parser makes this task a lot easier.

Here is an older output for a test that I wrote for QColumnView that shows some missing coverage:

valgrind --tool=callgrind --collect-jumps=yes ./tst_qcolumnview

./callgrind_coverage ~/dev/qt/tests/auto/qcolumnview/callgrind.out.16089 ~/dev/qt/src/gui/itemviews/qcolumnview.cpp

Function coverage - Has each function in the program been executed?
        Not executed: 612 void QColumnViewPrivate::_q_clicked(const QModelIndex &index)
        Coverage: 39/40 97%

Condition coverage - Has each evaluation point (such as a true/false decision) been executed?
443    for (int i = 0; i < ranges; ++i) {
842    for (; (i < list.count() && i < d->columns.count()); ++i) {
212    if (d->columns.isEmpty() || dx == 0)
976    if (!model() || !selectionModel())
976    if (!model() || !selectionModel())
229    if (!index.isValid() || d->columns.isEmpty())
229    if (!index.isValid() || d->columns.isEmpty())
272    if (leftEdge > -horizontalOffset()
336    switch (cursorAction) {
338        if (current.parent().isValid() && current.parent() != rootIndex())
338        if (current.parent().isValid() && current.parent() != rootIndex())
557        for (int i = columns.size() - 1; i >= 0; --i) {
549    while (currentColumn == -1 && parentIndex.isValid()) {
572    if (currentColumn == -1 && parent.isValid())
577    if (build && columns.size() > currentColumn + 1) {
580                             && !columns.at(currentColumn + 1)->rootIndex().isValid());
689    if (!columns.isEmpty() && columns.last()->isHidden())
689    if (!columns.isEmpty() && columns.last()->isHidden())
695    if (show && view->isHidden())
394    if (horizontalLength < viewportSize.width() && q->horizontalScrollBar()->value() == 0) {
813        if (!columns.isEmpty() && columns.last() == previewColumn)
1024    if (!model || columns.isEmpty())
1035            if (x != view->x() || viewportHeight != view->height())
1042            if (x != view->x() || viewportHeight != view->height())
368        if (diff < 0 && horizontalScrollBar()->isVisible()
877    if (currentParent == previous.parent()
877    if (currentParent == previous.parent()
879        for (int i = 0; i < d->columns.size(); ++i) {
893        for (int i = 0; i < d->columns.size(); ++i) {
512        if (!found && columns.at(i)->cornerWidget() == grip) {
        Coverage: 566/598 377%

Statement coverage - Has each line of the source code been executed?
        Coverage: 475/523 90%
-------------
Key:
 c == compiled
 e == executed
 r == return
 j == jump
 s == skipped
 - == comment/whitespace/not compiled
-------------
94      [j]  f: }
273     [c]:         && rightEdge <= ( -horizontalOffset() + viewport()->size().width())) {
286     [c]:             newScrollbarValue = rightEdge + horizontalOffset();
336     [j] f:     switch (cursorAction) {
369     [c]:             && horizontalScrollBar()->value() == horizontalScrollBar()->maximum()) {
579     [c]:         bool viewingChild = (!model->hasChildren(parent)
612     [c]: void QColumnViewPrivate::_q_clicked(const QModelIndex &index)
614     [c]:     Q_Q(QColumnView);
615     [c]:     QModelIndex parent = index.parent();
616     [c]:     QAbstractItemView *columnClicked = 0;
617     [c]:     for (int column = 0; column < columns.count(); ++column) {
618     [c]:         if (columns.at(column)->rootIndex() == parent) {
619     [c]:             columnClicked = columns[column];
623     [c]:     if (q->selectionModel() && columnClicked) {
624     [c]:         QItemSelectionModel::SelectionFlags flags = QItemSelectionModel::Current;
625     [c]:         if (columnClicked->selectionModel()->isSelected(index))
626     [c]:             flags |= QItemSelectionModel::Select;
627     [c]:         q->selectionModel()->setCurrentIndex(index, flags);
690     [c]:         columns.last()->setVisible(true);
726     [c]:         model()->fetchMore(index);
824     [c]:     previewColumn->setMinimumWidth(qMax(previewColumn->verticalScrollBar()->width(),
861     [rc]:     return list;
878     [c]:             && model()->hasChildren(current) && model()->hasChildren(previous)) {
939     [c]:             QItemSelectionModel *replacementSelectionModel =
941     [c]:             replacementSelectionModel->setCurrentIndex(
943     [c]:             replacementSelectionModel->select(
993     [c]:     QModelIndex br = model()->index(model()->rowCount(parent) - 1,
994     [c]:                                     model()->columnCount(parent) - 1,
1081    [c]:         opt.rect = QRect(option.rect.x() + option.rect.width() - width, option.rect.y(),

Note that this tool is a bit of a hack and is a work in progress so you will no doubt find issues. But it is good enough to be useful so I figured it would be time to publish:

The source for callgrind_coverage can be found in my callgrind tools git repository.

Valgrind callgrind tools Part 2: accessing information inside a callgrind files

From Valgrind's callgrind manual:

Callgrind is a Valgrind tool for profiling programs. The collected data consists of the number of instructions executed on a run, their relationship to source lines, and call relationship among functions together with call counts. Optionally, a cache simulator (similar to cachegrind) can produce further information about the memory access behavior of the application.

The result is that the files that are produces contain a plethora of data just waiting to be mined. I have written a tool called callgrind_info to extract information out of a callgrind file.

When you want to watch a function for performance regressions callgrind excels at getting results that are similar one run to the next. Extracting the cost of a function in a nightly script would be a very useful thing to do to automatically determine if you are having performance regressions:

./callgrind_info callgrind.out.5511 -cost 'tst_QListView::cursorMove()'
158034263

The matching functionality for the "-cost" is the "-function" which will output every function that was used in some specific file:

./callgrind_info callgrind.out.5511 -functions tst_qlistview.cpp                              
tst_QListView::tst_QListView()
tst_QListView::~tst_QListView()
tst_QListView::cleanup()
tst_QListView::cursorMove()
...

callgrind_info also lets you extract a list of the different specification types.

If you want to know every object/library that was loaded during the run of the program:

./callgrind_info callgrind.out.5511 -spec ob
/lib/tls/i686/cmov/libm-2.6.1.so
/usr/lib/libstdc++.so.6.0.9
/home/ben/dev/qt/tests/auto/qlistview/tst_qlistview
/lib/tls/i686/cmov/libnss_nis-2.6.1.so
/lib/tls/i686/cmov/libc-2.6.1.so
...

Every file:

./callgrind_info callgrind.out.5511 -spec fl | more
???
qbasicatomic.h
qdatetime.h
qwidget.h
qlist.h
qabstractitemmodel.h
qsize.h
...

Every function:

./callgrind_info callgrind.out.5511 -spec fn | more
0x00003460
floor
QBasicAtomicInt::operator int() const
QBasicAtomicInt::operator!=(int) const
QBasicAtomicInt::operator!() const
QBasicAtomicInt::operator==(int) const
QBasicAtomicInt::operator=(int)
QTime::QTime()
QWidget::show()
QWidget::resize(int, int)
QWidget::height() const
...

The callgrind info tool just touches on some of the data that can be extracted, but already it has proved to be very useful.

The source for callgrind_info can be found in my callgrind tools git repository.

Valgrind callgrind tools Part 1: decompressing callgrind files

If you have ever used the Vallgrind tool callgrind you will find that it generates a file "callgrind.out.pid". Looking inside of this file you will find a compressed version of the execution of the program. Here is a snippet from a callgrind file I generated last night:

fn=(43726) tst_QListView::indexAt()
463 4
+2 4
cfn=(24288)
calls=1 148 
* 3399
+1 1
+1 1
+2 4
cob=(26)
cfi=(265)
cfn=(21860)
calls=1 150 
* 320655
+1 5
...

After reading the callgrind format specification you shouldn't have too much trouble being able to read it if you really want to. By default the callgrind files are compressed which make it harder to read then it has to be. So if you get a compressed callgrind file that you want to read I have written a tool to decompress the file into a more reasonable format. Here is the same code as before, but this time decompressed:

fn=tst_QListView::indexAt()
463 4
465 4
cfn=QtTestModel::QtTestModel(QObject*)
calls=1 148 
465 3399
466 1
467 1
469 4
cob=/home/ben/dev/qt/lib/libQtGui.so.4.4.0
cfi=qlistview.cpp
cfn=QListView::QListView(QWidget*)
calls=1 150 
469 320655
470 5
...

If you are going to be either extracting information out of a callgrind file or writing your own tool that generates a callgrind files like my QScript profiler having a decompresser comes in handy.

The source for callgrind decompress can be found in my callgrind tools git repository.