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

[SETT Programming Contest]

The SETT Programming Contest: The fastest set<Timplementa tion

Write the fastest set<Timplementa tion 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, "Performanc e 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!

[Chris Thomasson]

"SETT Programming Contest" <se**@sett.prog ramming.contest .org.invalidwro te
in message news:g2******** **@aioe.org...

The SETT Programming Contest: The fastest set<Timplementa tion

What's the prize?

[...]

[Juha Nieminen]

SETT Programming Contest wrote:

The SETT Programming Contest: The fastest set<Timplementa tion

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.

[shablool]

On Jun 3, 4:55 pm, "SETT Programming Contest"
<[e-mail] ramming.contest .org.invalidwro te:

The SETT Programming Contest: The fastest set<Timplementa tion

Write the fastest set<Timplementa tion 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, "Performanc e Analysis of BST in System Software", Stanford Universityhttp://www.stanford.ed u/~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.

[Keith Thompson]

"SETT Programming Contest" <se**@sett.prog ramming.contest .org.invalidwri tes:

The SETT Programming Contest: The fastest set<Timplementa tion

Write the fastest set<Timplementa tion 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_Keit h) ks***@mib.org <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"

[Stephen Howe]

As others have observed, the conditions stop C being used.

The basic issue for most set implmentations is that insert/delete is slowest
as memory allocation/deallocation occurs per-node.
If you double this, the perforamance of set doubles.
So an allocator geared towards allocation of nodes the same size is where
time should be spent.

Stephen Howe

[SETT Programming Contest]

"Keith Thompson" <ks***@mib.orgw rote:

"SETT Programming Contest" writes:

The SETT Programming Contest: The fastest set<Timplementa tion

Write the fastest set<Timplementa tion 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...

[James Dow Allen]

On Jun 4, 4:37*am, "SETT Programming Contest"
<[e-mail] ramming.contest .org.invalidwro te:

"Richard Harter" <[e-mail] rote:

"SETT Programming Contest" wrote:

>Write the fastest set<Timplementa tion 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

[Jon Harrop]

SETT Programming Contest wrote:

The SETT Programming Contest: The fastest set<Timplementa tion

Write the fastest set<Timplementa tion using only standard C++/C...

That basically rules out persistence and efficient set theoretic operations.

The set implementations in languages like OCaml are up to a million times
faster in practice but to be competitively performant without missing
features you would need to Greenspun an efficient GC in C++ (and
assembler). So why restrict your competition to archaic languages like C++?

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com/products/?u

[James Kanze]

On Jun 3, 3:55 pm, "SETT Programming Contest"
<[e-mail] ramming.contest .org.invalidwro te:

The SETT Programming Contest: The fastest set<Timplementa tion

Write the fastest set<Timplementa tion using only standard
C++/C.

Fastest at what? On what machine? With which implementation of
C++?

[...]

See also this paper:
Ben Pfaff, "Performanc e Analysis of BST in System Software", Stanford Universityhttp://www.stanford.ed u/~blp/papers/libavl.pdf

Which more or less establishes that "fastest" is meaningless
unless you define at what?

--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]