Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Benchmarks

Reply
Thread Tools

Benchmarks

 
 
s0suk3@gmail.com
Guest
Posts: n/a
 
      11-06-2008
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;
};

// 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;
}
}

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?

Sebastian

 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      11-06-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) 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
 
Reply With Quote
 
 
 
 
Keith Thompson
Guest
Posts: n/a
 
      11-06-2008
(E-Mail Removed) writes:
> 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:
>

[snip]
> // 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;
> }
> }


You represent your set of words as a linked list. You compare each
new word to every word already in the set. The C++ solution uses a
std::set which, if I recall correctly, can do searches and insertions
in O(n log n).

If you re-write this to use a balanced binary tree, such as an AVL
tree, you should get performance similar to the C++ version.

> node = (struct SetNode *) malloc(sizeof(struct SetNode));


Not incorrect, but
node = malloc(sizeof *node);
would be better.

> if (!node) {
> free(aWord);
> return;
> }


And if malloc fails, you quietly return without doing anything to
handle the error or report it to the user.

[...]

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Longjun
Guest
Posts: n/a
 
      11-06-2008
On Nov 6, 11:53*pm, (E-Mail Removed) 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;
>
> };
>
> // 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;
> * * * * }
> * * }
>
> * * 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?
>
> Sebastian


Noticed that you've implemented your own mechanism of scanning words
from standard input and insert a new elements in your "sets". I don't
know why you implement it by yourself. Are you clear the principle of
the class cin/cout and set? Are you sure that your own function have a
better performance to the standard one?
I'm interested with how to test your application performance. Can you
tell me? I suggest you compare the performance difference between your
function between the standard one step by step.

Thanks
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      11-06-2008
Keith Thompson wrote:
> You represent your set of words as a linked list. You compare each
> new word to every word already in the set. The C++ solution uses a
> std::set which, if I recall correctly, can do searches and insertions
> in O(n log n).


That would be worse than linear-time, and is of course false.

You meant: O(lg n).
 
Reply With Quote
 
Juha Nieminen
Guest
Posts: n/a
 
      11-06-2008
(E-Mail Removed) wrote:
> Any ideas as to what causes the big slowdown?


Why do you expect that searching a linked list could be even close to
the speed of searching a balanced binary tree?
 
Reply With Quote
 
s0suk3@gmail.com
Guest
Posts: n/a
 
      11-06-2008
On Nov 6, 11:22*am, Obnoxious User <OU@127.0.0.1> wrote:
> On Thu, 06 Nov 2008 07:53:18 -0800, s0suk3 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:

>
> [snip]
>
> So, since your version uses "lower-level constructs" you assume
> it would be automatically faster?


Well, in this case it did seem to have a couple of advantages, like
for example, InsertWord() is given a pointer directly to the malloc()-
allocated string, which it simply copies into the .word member of the
struct; it doesn't need to allocate new memory and copy the string
from one place to the other, whereas std::set::insert() does need to
do make a copy.

Also, I'm not sure, but is the set's destructor invoked when main()
goes out of scope (causing memory cleanup)? (Currently the other
version has the DeleteSet() call commented-out.)

But, as others have pointed out, it's clear that the reason for the
difference in performance is the searching mechanism.

Sebastian

 
Reply With Quote
 
Pawel Dziepak
Guest
Posts: n/a
 
      11-06-2008
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

(E-Mail Removed) wrote:
> Well, in this case it did seem to have a couple of advantages, like
> for example, InsertWord() is given a pointer directly to the malloc()-
> allocated string, which it simply copies into the .word member of the
> struct; it doesn't need to allocate new memory and copy the string
> from one place to the other, whereas std::set::insert() does need to
> do make a copy.
>
> Also, I'm not sure, but is the set's destructor invoked when main()
> goes out of scope (causing memory cleanup)? (Currently the other
> version has the DeleteSet() call commented-out.)
>
> But, as others have pointed out, it's clear that the reason for the
> difference in performance is the searching mechanism.


Indeed it is. All that low-level stuff is faster, but it means nothing
when the problem is an algorithm and/or used data structure.

Pawel Dziepak
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org

iEYEARECAAYFAkkTNCAACgkQPFW+cUiIHNo9IQCgr6NC76/yXnouBhUYLn3fx3Rn
2HQAn3h19yS62OZqMv+jo0wSsr6M576O
=WTrr
-----END PGP SIGNATURE-----
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      11-06-2008
Juha Nieminen <(E-Mail Removed)> writes:
> Keith Thompson wrote:
>> You represent your set of words as a linked list. You compare each
>> new word to every word already in the set. The C++ solution uses a
>> std::set which, if I recall correctly, can do searches and insertions
>> in O(n log n).

>
> That would be worse than linear-time, and is of course false.
>
> You meant: O(lg n).


Oops, you're correct of course; thanks for the correction.

Actually I meant O(log n), but it's the same thing.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      11-06-2008
Longjun <(E-Mail Removed)> writes:
> On Nov 6, 11:53*pm, (E-Mail Removed) 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>

[...]
>>
>> 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>

[...]
>>
>> Any ideas as to what causes the big slowdown?

>
> Noticed that you've implemented your own mechanism of scanning words
> from standard input and insert a new elements in your "sets". I don't
> know why you implement it by yourself. Are you clear the principle of
> the class cin/cout and set? Are you sure that your own function have a
> better performance to the standard one?


This discussion is cross-posted to comp.lang.c and comp.lang.c++. His
solution is written in C, which doesn't have sets built into the
standard library.

But certainly the equivalent functionality could be written in C.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Benchmarks, you know ya wanna post em ;) RObErT_RaTh Hardware 115 11-26-2009 03:14 PM
FEAR - real world gameplay benchmarks at bit-tech Silverstrand Front Page News 1 11-01-2005 02:22 PM
First hands-on benchmarks of notebook using GeForce 7800 Go Silverstrand Front Page News 5 09-29-2005 01:39 PM
Third Party Benchmarks for Web Server abhi Java 1 09-28-2005 03:28 PM
porting spec benchmarks to Java Vasanth Venkatachalam Java 1 11-29-2004 06:57 PM



Advertisments