Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

Benchmarks

 
 
James Kanze
Guest
Posts: n/a
 
      11-11-2008
On Nov 11, 11:27*pm, CBFalconer <(E-Mail Removed)> wrote:
> James Kanze wrote:
> > Paul Hsieh <(E-Mail Removed)> wrote:


> ... snip ...


> >> Outside of crypto-hashes, Bob Jenkin's function and my
> >> function, the quality of everything else out there is truly
> >> pathetic.


> > As I said, I'm interested, because I've been collecting
> > benchmarks of various hashing functions. *Post a link to the
> > algorithm, and I'll add it in.


> One of the original purposes of hashlib was to make testing hash
> functions easy. *It is much more than just that now, but still
> fills the purpose. *hashlib includes a couple of very simple, and
> fast, hashes for text strings as a convenience for users. *All
> available on my site.


If they're already widely known hashing algorithms, I've
probably already gotten them. But it might be interesting to
compare our results---I'll just make a guess () that your
library is written in C, so it will definitely have a different
implementation from mine.

(Just curious about one thing: how do you benchmark. I use
virtual functions to impose a firewall on optimization; do you
use pointers to functions, or some other technique?)

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
 
 
 
robertwessel2@yahoo.com
Guest
Posts: n/a
 
      11-11-2008
On Nov 11, 8:15*am, James Kanze <(E-Mail Removed)> wrote:
> On Nov 11, 11:54*am, Pete Becker <(E-Mail Removed)> wrote:
>
> > It's well understood what sort of input causes O(n^2) behavior.

>
> Really? *If I post a quicksort implementation here, could you
> give me an algorithm which would generate the worst case?
> (I guess there should a smiley here, because I don't think that
> that's really what you meant. *But just a half of one, because
> I'd really like to find such. *There are times where you do want
> to test worst case.)



David Musser's original paper on Introsort ("Introspective Sorting and
Selection Algorithms") provides a surprisingly simple algorithm that
produces worst case (or at least quadratic) behavior in median-of-
three Quicksort. The paper is worth reading just for that.

http://www.cs.rpi.edu/~musser/gp/introsort.ps
 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      11-12-2008
James Kanze wrote:
>

.... snip ...
>
> If they're already widely known hashing algorithms, I've
> probably already gotten them. But it might be interesting to
> compare our results---I'll just make a guess () that your
> library is written in C, so it will definitely have a different
> implementation from mine.
>
> (Just curious about one thing: how do you benchmark. I use
> virtual functions to impose a firewall on optimization; do you
> use pointers to functions, or some other technique?)


I suspect you do have them. However, the installation is dead
simple. Just open the hashtable with pointers to the hash
functions (and a few other things). The documentation explains
all.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
 
Reply With Quote
 
Keith H Duggar
Guest
Posts: n/a
 
      11-12-2008
Juha Nieminen wrote:
> However, apparently the "in average" in this particular context means
> something slightly different. More precisely, the function f(n) is
> defined as:
>
> f(n) = the average amount of steps the algorithm performs for an input
> of size n (with all possible different inputs of that size)
>
> In this case the f(n) function can indeed have a smaller upper bound
> than the worst case for the algorithm in question.
>
> I think the "in average" is a bit confusing.


That is one purpose of education: to formalize and normalize
vocabulary
and understanding. It exposes students to common conventions that
enable
them to communicate on a common ground. Unfortunately many internet
folk
mistakenly believe wikipeducation is a substitute for education and
that
vociferous noise is a substitute for listening and critical thinking.

They defend their misinformed ignorant view ad nauseam. They claim
vast
experience when in truth they have none. In the end if some modicum of
intelligence finally motivates them to capitulate, their pride does
not
allow them to admit "I was wrong. I learned something. Thank you!".
No.
Instead they attribute their "arguments" to a language barrier or to
"confusing" conventions, etc.

KHD

 
Reply With Quote
 
Old Wolf
Guest
Posts: n/a
 
      11-12-2008
On Nov 7, 7:00*am, (E-Mail Removed) wrote:
> But, as others have pointed out, it's clear that the reason for the
> difference in performance is the searching mechanism.


Another reason for slowdown may be that you
malloc for every single word read. If the C++
program is using the small string optimization
then it won't need to malloc anything except
the new set node, for short words.

I suspect you could improve performance
(and memory consumption!) a lot with improved
allocation strategies too. Two mallocs per word
is a lot of work.
 
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