JasonB (no@spam.com) on 8/19/09 wrote:
---------------------------

>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().'

And that's probably true now, in 2009. Was it true in
2004 ? Was it true in 2000 ? Probably not, because back
then the sort() was bad enough that someone thought it
needed to be changed. Was it true in 1995 ? Definitely
not, because all the template stuff was pretty flaky
back then.

And that's the problem with "pick up something freely
available" approach: you don't know the quality of what
you're getting. You don't know - without considerable
research - whether you're picking up something flaky,
or something really really good. I suppose I'm just not
a very trusting person: I don't trust third-party code
as far as I can throw it. And I don't trust my own code
either (but when there *is* a problem, I find it easier
to debug in my own code). Again, YMMV.

>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.

Really I didn't use existing library code because
a) I knew I could do better than qsort() because I could
avoid the procedure call overhead, and b) I'm not
familiar with STL because we don't use it widely because
it was a pile of crap back around 1995. So there's
history and path-dependence in these decisions.

>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.

OK. Here's an implementation of malloc() that satisfies
the specification:

char* malloc(size_t n)
{ return NULL; }

So frankly, anybody who uses malloc() at all is "relying
on undefined behavior".

And back around 1999, when we were figuring out how to
get processes with up to 3.7GB of user-space heap on
32bit Solaris, the "undefined behavior" of malloc was
a real problem that we had to get round. It didn't
want to give you more than 2GB.

I don't see a lot of point in everyone trying to second-
guess all the decisions without knowledge of the context.
This is engineering: nothing is perfect, everything is a
compromise. And yes, sometimes you make mistakes. With
hindsight, it would have been better to write our own
complete allocator a long time ago. But I didn't have
hindsight, I had a big long to-do list, and many items
would help to generate revenue, and rewriting malloc()
never looked like enough of a short-term win to get to the
top of the list.

>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.

Been there, tried that: not a good idea when you're tight
on space. You can't afford the fragmentation of having
many different allocators each maintaining its own
separate pool.

>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.

Sure. Shared data that's read-only for the duration of
an operation is no problem. Shared data that gets written
is a big problem.

Anyway, my current opinion is that most of the operations
that could safely be parallelized with threads can
more easily be parallelized with an approach based on
copying data to separate heavyweight processes, which has
the great benefit of *guaranteeing* that nobody messes
around with shared data in ways that make it buggy or
unrepeatable. I realize that's not the dominant view:
I'm not afraid to be a little unconventional.

>Not in this case, no. In fact, I wouldn't have bothered with the trie-sort experiment
>for that very reason. :-)

Yes. I'm interested in the trie data structure for some
possible applications other than sorting, so this was
partly a way to get familiar with that.

>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.)

Yes. In this case it makes sense for you. As a general
rule, programs with non-repeatable behavior are a huge
pain in the ass. When the payoff is big enough to
justify the high cost of dealing with non-repeatable code,
it *can* be a good choice.

>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.

Fair enough.