Richard Cownie (tich@pobox.com) on 8/18/09 wrote:
---------------------------
>JasonB (no@spam.com) on 8/18/09 wrote:
>---------------------------
>
>>sort() is really simple and I doubt there has been a >problem with that for a long time on any implementation.
>
>I dunno. From a quick google it looks as though the
>algorithm changed from a QuickSort to an IntroSort
>(combination of MergeSort and QuickSort) around 2000.
>Which doesn't exactly make it sound either particularly
>simple, nor particularly stable (in terms of code not
>changing).

That's still pretty simple and stable compared to most code. :-) Also, by "simple" I was really referring to the implementation being fairly straightforward code rather than heavily relying on the murkier corners of the language where you are more likely to run into trouble with compilers. It would take a lot of testing for me to have more confidence in something I threw together than in sort().

>>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.
>
>I just tried the simplest case, and time to sort 2M
>integers was around 300msec in the same ballpark as my
>not-highly-tuned trie-sort code; but this wasn't really
>an apples-to-apples comparison, as the trie-sort has to
>get the keys out of a struct, whereas the STL sort was
>just handling a vector.

You could do an apples-to-apples comparison just by writing the appropriate functor or overloading the less-than operator to get the keys out of the struct, something like:

bool operator<(const MyStruct& x, const MyStruct& y)

{

    return x.Key < y.Key;

}

(That's assuming you don't already have that operator overloaded for your struct and you don't want to have to specify the functor in the call to sort(). Obviously x.Key can be replaced by whatever magic is required to obtain the necessary key.)

In this case, if there isn't really a performance difference and you've already written your own sort, then the only real advantage of using sort() would be in having less code to compile and maintenance. But another way of saying the above (assuming the conclusion holds for an apples-to-apples comparison) is that you could have saved yourself the time it took to implement and test your own sorting routine (and, done much earlier, the time spent maintaining the old sort routine) by simply using sort().

>>Not using "sort" because it might break seems a bit >incongruous in the circumstances. :-)
>
>Well, you pick your battles ... And if we don't meet
>our memory-size constraints, we can't run the program
>at all - whereas if we use a less-than-optimal sorting
>routine, it just costs a few extra minutes. Not such
>a show-stopper.

Not in this case, but it's more the general principle (being unwilling to use STL sort() because it might break while relying on undefined compiler behaviour that actually did turn out to break as soon as someone used some threading) that I was referring to.

>>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?
>
>Yes, I considered that option at several points. But
>it was always hard to justify the effort involved in
>writing and maintaining a complete general-purpose
>allocator, when what we had worked fine (until someone
>on another continent decided to use threads, and then
>it became an urgent problem that required a faster fix
>than writing a new allocator).

The problem is that as soon as you made the decision to rely on undefined behaviour rather than rolling your own the risk was always there. And if you're using C++ the allocator needn't be complete and general-purpose, it can be a special-case allocator just for a particular class, tuned to the actual usage patterns of that class.

Of course it could still be the right decision in your case, as can taking the opposite approach with your sorting, although I suspect you would always have been safer with a decision to use sort() despite your misgivings about doing so, even if the rewards would not have been as great.

>>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.
>
>For the kind of stuff I mostly work on - big complicated
>highly-interlinked data structures, with hundreds of
>different classes - attempting to retrofit threading
>would be a nightmare.

No doubt. I normally look at it on an operation-by-operation basis. Is it an expensive operation from the user's point of view? Can the operation be split into sub-operations, a worthwhile subset of which can view and operate on the data as independent sets? Will it make the operation significantly faster to do so? The first and third determine the benefits; the second determines the cost. A resounding "Yes" to the second means the answers to the first and third questions can be weaker. It also makes it much more likely that the transformation only needs to be done once and after that additional processors will simply mean more partitions. A "No" for the second means more effort required and therefore the benefits need to be correspondingly greater to be worth the effort.

The second one is worth thinking about, because for certain operations a big, complicated, high-interlinked set of data structures can look just like a set of completely independent and easily partitioned sets of data, while for other operations the exact same set of data structures cannot be partitioned.

>>If you find that a hotspot is one of those really
>>easy and obviously correct cases then leaving all that extra performance on the
>
>And in this case the sort'ing is very probably
>parallelizable - but in fact, since it's only about
>15 minutes in 20 hours, it hardly counts as a "hotspot".

Not in this case, no. In fact, I wouldn't have bothered with the trie-sort experiment for that very reason. :-) I would have compared sort() with the existing implementation for maintainability reasons, though.

>Yes. I'm aware that you can have programs which produce
>"correct" but non-deterministic and non-repeatable
>results. Our customers really don't like that though
>(and we don't like debugging non-repeatable bugs).

In this case the data is a set of points representing a surface, akin to what you get from a laser scanner. Since the particular points you get from any particular scan are arbitrary anyway, it doesn't really matter if you get a slightly different set of points from one time to the next. (In this case, "slightly different" is generally a few hundred points different out of a million; still on the same surface but at slightly different locations on the surface. Assuming the point cloud is dense with respect to the level of detail on the surface that is required, precise locations don't matter, and if it's not dense enough, then you've planned it wrong because you don't know where the points will be even in the deterministic, single-threaded case.)

It's potentially more of an issue for us in terms of debugging, but bugs in that part of the code are very rare and we can easily verify any non-threading-related change to the code simply by running it with a single thread (in which case the result is repeatable). Threading-related changes require very careful inspection of the code in that case (testing threaded code is nowhere near as valuable) because unlike the other operations, that one isn't obviously correct on inspection. However, the performance benefits justify the effort required.

>Again, YMMV: there's a wide range of choices in the
>design space.

That's why my comments are so heavily qualified; I'm not trying to critique your design choices, I'm simply making some general observations that may or may not be relevant in your case.