Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > The SETT Programming Contest: The fastest set<T> implementation

Reply
Thread Tools

The SETT Programming Contest: The fastest set<T> implementation

 
 
SETT Programming Contest
Guest
Posts: n/a
 
      06-03-2008
The SETT Programming Contest: The fastest set<T> implementation

Write the fastest set<T> implementation using only standard C++/C.
Ideally it should have the same interface like std::set.
At least the following methods must be implemented:
insert(), find(), begin(), end(), erase(), size(), operator<(),
and at least the forward iterator.

Here, speed and correctness are the 2 most important factors.
Functionally it should behave similar to std::set,
have practically no limitation on the number of items,
and be significantly faster, either always or under specified
conditions (for example for random items etc.).

The class should be placed in an own namespace.
Supply also a benchmark routine which compares your
implementation with that of std::set, and briefly document
and comment these results.

Hint: Since items in a set are always in an ordered sequence
(as determined by operator<()) you need to use some tree
routines (AVL, red-black, splay, etc.) or use your own tree
method in the heart of your implementation.

See also this paper:
Ben Pfaff, "Performance Analysis of BST in System Software", Stanford University
http://www.stanford.edu/~blp/papers/libavl.pdf

Publish your finished project somewhere on the Web
(for example at your own homepage or at http://sourceforge.net/ )
and announce it in comp.lang.c++ .

There is no deadline on this contest. The fastest method
will be the winner of the SETT Programming Contest,
until someone comes up with a faster method.

Good Luck!

 
Reply With Quote
 
 
 
 
SETT Programming Contest
Guest
Posts: n/a
 
      06-03-2008
"Chris Thomasson" <(E-Mail Removed)> wrote:
> "SETT Programming Contest" wrote:
> >
> > The SETT Programming Contest: The fastest set<T> implementation

>
> What's the prize?


The winner will get the title "Winner of the SETT Programming Contest".
Also a wiki page will be created and the winner presented there.
Sponsors from the industry, academic institutions, and individuals
can decide on their own to honor the winner with additional prizes.

 
Reply With Quote
 
 
 
 
Juha Nieminen
Guest
Posts: n/a
 
      06-03-2008
SETT Programming Contest wrote:
> The SETT Programming Contest: The fastest set<T> implementation


Considerable speedups can be achieved by simply using the default
std::set with a custom memory allocator. I have done exactly that here:

http://warp.povusers.org/FSBAllocator/

I suppose that could be my entry.
 
Reply With Quote
 
Lars Uffmann
Guest
Posts: n/a
 
      06-03-2008
SETT Programming Contest wrote:
> The winner will get the title "Winner of the SETT Programming Contest".
> Also a wiki page will be created and the winner presented there.
> Sponsors from the industry, academic institutions, and individuals
> can decide on their own to honor the winner with additional prizes.


[x] Do your own homework
 
Reply With Quote
 
shablool
Guest
Posts: n/a
 
      06-03-2008
On Jun 3, 4:55 pm, "SETT Programming Contest"
<(E-Mail Removed)> wrote:
> The SETT Programming Contest: The fastest set<T> implementation
>
> Write the fastest set<T> implementation using only standard C++/C.
> Ideally it should have the same interface like std::set.
> At least the following methods must be implemented:
> insert(), find(), begin(), end(), erase(), size(), operator<(),
> and at least the forward iterator.
>
> Here, speed and correctness are the 2 most important factors.
> Functionally it should behave similar to std::set,
> have practically no limitation on the number of items,
> and be significantly faster, either always or under specified
> conditions (for example for random items etc.).
>
> The class should be placed in an own namespace.
> Supply also a benchmark routine which compares your
> implementation with that of std::set, and briefly document
> and comment these results.
>
> Hint: Since items in a set are always in an ordered sequence
> (as determined by operator<()) you need to use some tree
> routines (AVL, red-black, splay, etc.) or use your own tree
> method in the heart of your implementation.
>
> See also this paper:
> Ben Pfaff, "Performance Analysis of BST in System Software", Stanford Universityhttp://www.stanford.edu/~blp/papers/libavl.pdf
>
> Publish your finished project somewhere on the Web
> (for example at your own homepage or athttp://sourceforge.net/)
> and announce it in comp.lang.c++ .
>
> There is no deadline on this contest. The fastest method
> will be the winner of the SETT Programming Contest,
> until someone comes up with a faster method.
>
> Good Luck!


Interesting contest. However, the assumption that there should be no
limitation on the number of items implies that the underlying memory
management model will be similar to the one used by std::set. It
appears that a change to this memory model (particularly within modern
multi-threaded environments) may have a more dramatic affect on
performance benchmarks, then the selection of the underlying data
structure, as demonstrated by the String library
(see: http://strinx.sourceforge.net/docs/strinx.html).

ShacharS.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      06-03-2008
"SETT Programming Contest" <(E-Mail Removed)> writes:
> The SETT Programming Contest: The fastest set<T> implementation
>
> Write the fastest set<T> implementation using only standard C++/C.
> Ideally it should have the same interface like std::set.

[snip]

What is "C++/C"?

Since C doesn't have C++-style templates or namespaces, the problem as
stated cannot be solved in C (though you could probably do the
equivalent).

Why not just say "standard C++" and leave C out of it?

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(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
 
Christopher
Guest
Posts: n/a
 
      06-03-2008
On Jun 3, 8:55 am, "SETT Programming Contest"
<(E-Mail Removed)> wrote:
> The SETT Programming Contest: The fastest set<T> implementation
>

[snip drabble]

I am running a SCTMM contest: Send Chris the most money contest.
The contest has no deadline.
The person who sends the most money will be the winner.
Sponsors will decide on prizes.
I'll create a wiki page and be sure to thank you.
Send entries to:

SCTMM Contest
P.O box 50001
Austin TX 78735
 
Reply With Quote
 
SETT Programming Contest
Guest
Posts: n/a
 
      06-03-2008
"Keith Thompson" <(E-Mail Removed)> wrote:
> "SETT Programming Contest" writes:
> >
> > The SETT Programming Contest: The fastest set<T> implementation
> >
> > Write the fastest set<T> implementation using only standard C++/C.
> > Ideally it should have the same interface like std::set.

> [snip]
>
> What is "C++/C"?
>
> Since C doesn't have C++-style templates or namespaces, the problem as
> stated cannot be solved in C (though you could probably do the
> equivalent).
>
> Why not just say "standard C++" and leave C out of it?


It means that you can also use pure C for the underlying methods,
ie. by using the 'extern "C"' interface mechanism of the C++ compiler.
Only the public interface must be in C++, the rest can also be
in portable standard C. For example if you already have some
working C code (for example the tree routines) for re-use here...

 
Reply With Quote
 
SETT Programming Contest
Guest
Posts: n/a
 
      06-03-2008
"Richard Harter" <(E-Mail Removed)> wrote:
> "SETT Programming Contest" wrote:
> >
> >The SETT Programming Contest: The fastest set<T> implementation
> >
> >Write the fastest set<T> implementation using only standard C++/C.
> >Ideally it should have the same interface like std::set.
> >At least the following methods must be implemented:
> >insert(), find(), begin(), end(), erase(), size(), operator<(),
> >and at least the forward iterator.
> >
> >Here, speed and correctness are the 2 most important factors.
> >Functionally it should behave similar to std::set,
> >have practically no limitation on the number of items,
> >and be significantly faster, either always or under specified
> >conditions (for example for random items etc.).
> >
> >The class should be placed in an own namespace.
> >Supply also a benchmark routine which compares your
> >implementation with that of std::set, and briefly document
> >and comment these results.
> >
> >Hint: Since items in a set are always in an ordered sequence
> >(as determined by operator<()) you need to use some tree
> >routines (AVL, red-black, splay, etc.) or use your own tree
> >method in the heart of your implementation.
> >
> >See also this paper:
> >Ben Pfaff, "Performance Analysis of BST in System Software", Stanford University
> >http://www.stanford.edu/~blp/papers/libavl.pdf
> >
> >Publish your finished project somewhere on the Web
> >(for example at your own homepage or at http://sourceforge.net/ )
> >and announce it in comp.lang.c++ .
> >
> >There is no deadline on this contest. The fastest method
> >will be the winner of the SETT Programming Contest,
> >until someone comes up with a faster method.
> >
> >The winner will get the title "Winner of the SETT Programming Contest".
> >Also a wiki page will be created and the winner presented there.
> >Sponsors from the industry, academic institutions, and individuals
> >can decide on their own to honor the winner with additional prizes.
> >
> >Good Luck!

>
> I take it that you really mean C++ and not C.


It means that you can also use pure C for the underlying methods,
ie. by using the 'extern "C"' interface mechanism of the C++ compiler.
Only the public interface must be in C++, the rest can also be
in portable standard C. For example if you already have some
working C code (for example the tree routines) for re-use here...

> Must entries use binary trees? What about T trees or radix trees?


You are free to use any tree mechanism you like. It's your choice.

> Are we talking about in-memory methods here or
> do we have to account for disk based methods too?


In-memory methods only; much like std::set .

 
Reply With Quote
 
James Dow Allen
Guest
Posts: n/a
 
      06-04-2008
On Jun 4, 4:37*am, "SETT Programming Contest"
<(E-Mail Removed)> wrote:
> "Richard Harter" <(E-Mail Removed)> wrote:
> > "SETT Programming Contest" wrote:
> > >Write the fastest set<T> implementation using only standard C++/C.

>
> > >Here, speed and correctness are the 2 most important factors.

>
> In-memory methods only; much like std::set


Too bad the contest doesn't include memory needs as a
criterion; I've a method with the same compaction as
Cleary's Compact Tree, but faster -- though not as fast as
non-compact methods.

Obviously, a compact method will be faster than a "fast"
method, if the former fits in core and the latter doesn't.

James Dow Allen
 
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
Knowing the implementation, are all undefined behaviours become implementation-defined behaviours? Michael Tsang C++ 32 03-01-2010 09:15 PM
Current Fastest Python Implementation? samuraisam Python 4 02-20-2008 10:11 AM
Sett absolute path problem Pumkin ASP .Net 9 10-12-2006 12:33 PM
Fastest 5 mp Digital Camera ? Fastest 4 mp Digital Camera? photoguysept102004@yahoo.com Digital Photography 6 10-28-2004 11:33 AM
Fastest ip address searching method/implementation Jonathan C++ 6 11-29-2003 06:19 AM



Advertisments