A generic hash table [LWN.net]

A generic hash table

Posted Aug 13, 2012 23:55 UTC (Mon) by liljencrantz (guest, #28458)
In reply to: A generic hash table by HelloWorld
Parent article: A generic hash table

The part where you say that it is impossible to write type-safe, generic and fast containers in C is demonstratably false. All of the above can be had with macros. I look forward to you arguing that such implementations aren't good while ignoring that most of the problems with macros also exist with templates.

Whenever the many deficiencies of STL is pointed out, you defensively say that "they fixed that in boost::XXX", but ignore that any missing containers, string types and other omissions from the standard C library can be easily rectified through the use of a small set of additional libraries.

to post comments

A generic hash table

Posted Aug 14, 2012 19:56 UTC (Tue) by HelloWorld (guest, #56129) [Link] (3 responses)

> I look forward to you arguing that such implementations aren't good while ignoring that most of the problems with macros also exist with templates.
Nonsense, there are numerous problems with macros. Here's a simple example:
template<typename T> bool max(T x, T y) { return x > y ? x : y; }
#define max(x, y) x > y ? x : y

The macro version will evaluate one argument twice. Bad things happen when you do max(a, max(b, c)). Yes, that can be fixed by parenthesizing each macro argument, but I shouldn't need to deal with that kind of crap. The template version will complain when the types don't match, the macro won't.
Other people have tried to make it suck less by using macros to generate functions:
http://www.canonware.com/rb/
That sucks too, because I really don't feel that I should be responsible for the bookkeeping that approach requires. It also doesn't work if you need to deal with complex types like int(*)(void) or whatever. Yes, one can use a typedef in that case. No, that's not how it should be. Generic algorithms and data structures are important enough to warrant language features to support them.

> Whenever the many deficiencies of STL is pointed out, you defensively say that "they fixed that in boost::XXX",
Boost doesn't usually "fix" the STL, it simply provides solutions to other problems than the STL does. std::list (de)allocates memory for you but works with arbitrary types. boost.intrusive don't work with all types (because they need the pointers to be embedded within the type), but it's more flexible with regards to memory management.

> but ignore that any missing containers, string types and other omissions from the standard C library can be easily rectified through the use of a small set of additional libraries.
It can't, generic data structures suck when the language doesn't support them. And besides, it's not like one always needs boost. Often enough, STL containers and algorithms do the job just fine.

A generic hash table

Posted Aug 17, 2012 8:18 UTC (Fri) by jzbiciak (guest, #5246) [Link] (2 responses)

template<typename T> bool max(T x, T y) { return x > y ? x : y; }

Erm... I don't think that's the right return type, unless you want max(a, max(b, c)) to have rather unusual semantics.

A generic hash table

Posted Aug 17, 2012 9:02 UTC (Fri) by jzbiciak (guest, #5246) [Link]

Actually... any use of that max that returns bool would have rather unusual semantics with that return type. Almost reminds me of PHP. ;-)

As far as the whole C / C++ debate goes: Up until a few years ago I was an ardent C proponent and avoided C++. Since then, I've really given C++ a chance, and I now tend to prefer it for new projects. I still use C for quick one-offs, but for anything larger I use C++.

For one thing, C++ compilers are much better now than when I first looked at them ~15 years ago. You can throw some seriously complicated template messes at a modern compiler and it'll sort it out and give you rather tight code more often than not. 5 to 10 years ago, good code in that circumstance was more the exception than the rule. Bringing STL into the language in the 90s, plus the rise of Boost and template metaprogramming really forced compilers to up their game here.

I remember around 10 years ago playing with the "Stepanov" benchmark. It's a benchmark that measures a compiler's ability to deal with abstraction in a C++ program by wrapping a simple addition with a double in increasing amounts of C++ abstraction. G++ performed rather poorly at the time (incurring a 10x - 15x slowdown at the worst, IIRC) and our own compiler at work showing a 50x slowdown. Now I believe both compilers show no slowdown. They are able to flatten away the abstractions. It's beautiful.

For the problems I'm tackling in my day job, I really appreciate the compositional style templates offer me. Too often I find myself needing "an X with detail Y". In C, I'd have to code up a separate function that combined the two, or a macro that instantiated X subbing in a Y where necessary. In C++, it's just X<Y>, if X is a suitable template. I get type safety and an awful lot of compile-time computation and help.

This can be really wild but useful at the limit. I have a truly compelling example I'd love to share, but since it's my day job and it's proprietary technology, I don't know just how much I can share. I will say that the code I generate relies on a ton of compile-time computation to generate code that's sufficiently efficient that I don't mind running on design simulations of our chips that run at speeds on the order of 100Hz, plus/minus an order of magnitude. You read that right: anywhere from 10 to 1000 CPU cycles per second.

(Note: I've completely ignored error messages. C error messages are rarely obtuse and usually easily grokked. C++ with multiple nested templates is another ball of yarn altogether... They generally suck, and I'm with you if you think they're an abomination.)

A generic hash table

Posted Aug 17, 2012 9:49 UTC (Fri) by HelloWorld (guest, #56129) [Link]

You're right of course :). Oops.