Richard Cownie (tich@pobox.com) on 8/18/09 wrote:
---------------------------
>Michael S (already5chosen@yahoo.com) on 8/18/09 wrote:
>---------------------------
>
>>If the app is multiplatform it's another matter. Although by now standard compliance
>>of popular C++ compilers is MUCH better than it used to be just 5-6 years ago
>so I wouldn't expect correctness problems.
>
>Maybe. I'm a bit of a Luddite on much of this stuff: I'm
>not interested in using features until they've been around
>for a while (and from what you're saying, while templates
>and STL were kinda sorta around in 1995, it was a bit of a
>crapshoot until around 2004 ...)

The "crapshoot" was mostly on more esoteric things like member function templates defined outside of the class body (a problem in VS6, one of many fixed in VS.NET, which was released in 2002, but we still used templates quite a lot in VS6).

sort() is really simple and I doubt there has been a problem with that for a long time on any implementation.

At the very least I'd give it a test to see how it performs (and therefore whether it is worthwhile pursuing or not), since it shouldn't take more than a few minutes to implement.

>>Doesn't it mean that your original design was relying on >undefined behavior?
>
>Yes it was. Not a good idea in general. But we're up
>against the wall in terms of trying to build big data
>structures that need to fit in physical DRAM to go fast
>enough, so we play some tricks with squeezing virtual
>addresses into less than 64 bits.
>
>Playing it safe is good. But sometimes you can't get what
>you need without breaking a few rules.

Not using "sort" because it might break seems a bit incongruous in the circumstances. :-)

>Anyhow, the consequence for our app was that introducing
>even a minimal use of threads actually made things
>break. For apps which are less sensitive to memory
>address ranges, what you might see is that your program
>still runs, but behaves a little differently ... either
>way it's awkward.

I'm not familiar enough with Linux programming to know for sure, but I would have thought you could (and probably should) write your own custom allocators that could give you the desired behaviour in a portable and safe way, rather than depend on the implementation details of glibc?

>There's a good paper on "The Problem With Threads" which
>goes into considerable detail on the many ways this is
>a bad idea. Basically even for apparently trivial
>programs it's desperately hard to enumerate all the
>possible sequences of interactions and prove that all
>are correct. I suppose occasionally people manage to
>write correct threaded code, but mostly it has lurking
>bugs. And then the problem is aggravated by the fact that
>there's no good way to reproduce a bug because the
>the threaded program doesn't execute things in the same
>order each time.

It's certainly more work than serial code, but it's not that hard to safely parallelise subsets of code. Sometimes it's really easy and obviously correct, other times it's a lot more complicated. If you find that a hotspot is one of those really easy and obviously correct cases then leaving all that extra performance on the table and instead trying so hard to speed up serial code is probably a poor choice.

>So as for whether there are cases where threads are
>"easy to use and cause no problems at all", my personal
>view is that while in theory it's possible, in practice
>I've never seen any such case - and on the contrary, the
>few times I've encountered threads they've caused me big
>trouble (even though they weren't even in *my* code).
>YMMV.

In our own software there are a bunch of cases where it was easy to use and cause no problems at all. These were all cases where there was a lot of work to be done but each parcel was (or could be made) independent of the others, allowing a data-parallel approach. There was only one where I had to sacrifice determinism[*] to gain significant speedups, where the code transformation was a lot more complicated, and not surprisingly, it's also the only one to have turned up subtle threading errors. Other cases, where it would be even harder to thread, I have chosen not to so far because in my opinion the tradeoff isn't currently worth it (but as the number of cores increases, so does the tradeoff because more and more performance being left on the table shifts the balance towards more complicated algorithms that can take advantage of it).

[*] That is, determinism of the output, not of the behaviour. Of course the fine-grained behaviour of all the code is non-deterministic, but the output of all except that one case is deterministic and identical to the single-threaded version. The non-deterministic output case is one where the precise values in the output are unimportant and there is nothing particularly special about the set of values returned by the single-threaded algorithm, so it doesn't matter if you get a different set of values every time you run the program, other than making it harder to reproduce a bug.