Questions about getting ready for multicore programming.

[bob]

OK, for the record, what is the beef with qsort()???

1. It is the fastest known sorting algorithm, an O(N log N) algorithm.

(This isn't why they are harping on qsort, but I thought it worth mentioning...)

Actually Prof. Hyatt, you've made a slight error there...

The C standard does *NOT* require the qsort routine to be implemented with any particular method.

(edited. Used 'algorithm' when I meant 'routine')

Because of the name, you expect it to be the quick-sort algorithm, but it doesn't have to be. It could be bubble sort.

I know, it sounds stupid. But the C standard simply doesn't require it to be any particular method but still calls itself 'qsort'. You'd think they'd either require it to be quick-sort or have changed it to just 'sort' but they didn't.

True, most compilers will do quick-sort. But they don't have to.


Also, the quick-sort method, while being usually efficient, can have some degenerate cases where the performance really degrades. The exact sequence depends on the implementation and the choice of the pivot point.

That's why the currently prefered methods are to use a hybrid sort method. It starts out as quick-sort but if monitoring code thinks it's taking too long, it'll switch to a different algorithm, such as a heap-sort.

Ironically enough, I think it was one of the original designers of C++'s STL that came up with this aproach. He called it the 'Intro sort'.


Writing a good sort routine can be surprisingly difficult. I remember reading an article by P. J. Plauger (he was on both the C & C++ standards commitees) about all the errors he made over the years while writing supposedly simple sort routines.

I used to thoroughly enjoy his articles back when he wrote in Embedded Systems Programming magazine.



To get this back onto chess....

I used to use the C library qsort routine back in my early chess programs. This was with a K&R C compiler.

It had so much overhead that it was actually faster for me to just do a little selection sort. The n^2 growth was still faster than what the C library offered.

I've never been much of a fan of the ANSI C committee. The standard leaves too many vaguely define features, some of which are basic, essential things. But in any case, the only C library I use (gcc's version) is clearly a classic quicksort/heapsort algorithm. I don't use it myself because for sorting very small numbers of items, quicksort is worse than bubblesort. But the idea of "generic" algorithms leaves me cold, because "generic" is almost always a synonym for "slow"...

[Bo Persson]

OK, for the record, what is the beef with qsort()???

1. It is the fastest known sorting algorithm, an O(N log N) algorithm.

2. It has the rather clunky comparison facility where you write a procedure to compare two values and return <, = or >. But a _generalized_ sort is going to have to do the same thing, and I'll bet I can _always_ write a better comparison algorithm than a general-purpose one supplied for a more general sort algorithm.

The thing was actually that the interface *is* clunky, and that you cannot do much about that in C. In C++, std::sort can just use < for the comparisons, possibly picking up an overloaded operator for the specific type, and inline everything.

With a good optimizer, that runs circles around qsort.

All this is just in response to the statment "C++ can never be faster than C."

Software development cost is a different issue, but for a chess engine, I consider that irrelevant, since it is a "one-off" type algorithm where reusability is of little importance when compared to raw speed.

C is still completely viable for high-performance algorithms...

Sure, but sometimes you have to work harder than in C++.

Also, I remember the times you had to defend the use of Bubblesort in Crafty. Had it been written in C++, nobody would have questioned the use of std::sort.


Bo Persson

[Tord Romstad]

Hello Andreas,

Thanks for the compliments! I'm glad you like my code. But why do you think it shows how to do things "in a better way in C++"? As far as I can see, I don't make use of a lot of C++ features except stronger typing.

But this is a main feature of C++ and one that is beneficial for a chess engine, while others like subclassing are probably not so useful in a chess engine. But I'm a C++ beginner, thus I can learn also from very simple constructs.

Me too. I learnt most of what I needed along the way. One of my main motivations for writing Glaurung 2 in a more C++-like style was to learn more about the language, and to find out if my distaste of it was just caused by lack of knowledge. It turned out that on the contrary, I dislike it more and more.

I only say in contrary to Fruit, Glaurung looks like a C++ programm. You use the C++ I/O functions,

Yes. They are sometimes a bit more convenient than the C I/O functions, although I find the oveloading of the '<<' and '>>' operators a phenomenally ugly hack.

classes, namespaces, enums etc.

I only use anonymous namespaces. I read somewhere that using the 'static' keyword for making a file-local variable or function was considered deprecated in C++, and that I was supposed to use anonymous namespaces instead. I am not sure I like it; the extra level of indentation is a bit annoying (especially because I adhere religiously to a maximum of 80 characters per line).

Mine is much less C++. I planned to write mainly C but use some useful features of C++, but I'm often to conservative and concerned to much about speed. E.g. I currently don't type everything in enums, like you do in glaurung, but use typedefs. I was worried enums would be slower.

They probably are a tiny bit slower, at least in a few cases. As far as I know, there is no way to specify the type of integer used for an enumerated type in C++ (I think I've read that this will be added in the next version of the C++ standard, but I could be wrong). In general, it is probably implementation-dependent. This might also make your code less portable unless you are careful.

I think using enums the way I do in Glaurung is probably highly non-idiomatic C++ style. Enums are not meant to be used this way. If you have a definition like

Code: Select all

enum Foo {BAR, BAZ, BAX, GAZONK};

you are really only supposed to use the type 'Foo' for variables which can only hold one of the four values BAR, BAZ, BAX and GAZONK. Using a cast like Foo(256) is probably considered very poor style. There is even a small risk that it won't work the way you expect: If your compiler decides to store the type Foo as 8-bit numbers, Foo(256) will equal 0 (or BAR), which is probably not what you intended.

Using enums the way I do is basically just a hack intended to make C++ a slightly more similar the languages I like. For me, the ease of catching bugs and the improved readability of the code (this is subjective, of course) is worth the risk of reduced portability, but you probably shouldn't blindly imitate this technique without being aware of the possible problems.

In general, Glaurung 2 is probably a very poor guide to good C++ programming style, although I would like to think that it is a decent guide to solid chess programming style.

Tord

[Tord Romstad]

I think many people get bored with the "state of the art" chess. I think I will not mistake if you expressed a similar personal opinion in forums.

Yes, you are right.

It is very difficult to succeed in innovation at established field of algorithms and data structures, but I believe current chess programming fashion is not the final solution.

I think you are right in the sense that the current techniques are very far from optimal. On the other hand, I think they are sufficiently close to optimal (from a human perspective) that further improvements are no longer very interesting. I also think that future improvements in computer chess are more likely to come as a side-effect of research in more difficult games. Even now, there seems to be much more interesting research going on in the computer go and shogi communities.

Some innovative and important things like Magic Attacks Bitboards and material evaluation tables was relatively late additions to chess community.

Sure, but these are only relatively unimportant low-level implementation details, and don't really qualify as new algorithms or data structures.

Tord

[wgarvin]

OK, for the record, what is the beef with qsort()???

1. It is the fastest known sorting algorithm, an O(N log N) algorithm.

2. It has the rather clunky comparison facility where you write a procedure to compare two values and return <, = or >. But a _generalized_ sort is going to have to do the same thing, and I'll bet I can _always_ write a better comparison algorithm than a general-purpose one supplied for a more general sort algorithm.

The thing was actually that the interface *is* clunky, and that you cannot do much about that in C. In C++, std::sort can just use < for the comparisons, possibly picking up an overloaded operator for the specific type, and inline everything.

With a good optimizer, that runs circles around qsort.

All this is just in response to the statment "C++ can never be faster than C."

Anecdotally, on my last project I replaced a qsort() of a smallish structure (I think it was 8 bytes per entry?) with a fully inlined one and the result was approximately 8 times faster. qsort() is handy for miscellaneous tasks, but don't use it in an inner loop, especially on machines where function calls are costly.

[To clarify: it was sorting an array of the 8-byte structures, maybe 10K elements or something like that]