Richard Cownie (tich@pobox.com) on 8/19/09 wrote:
---------------------------
>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 ?

I would really hope so in both cases. I certainly wouldn't have given it a second thought and I was using VC6 back in 2000. (Having said that, we may also have been using STLPort by then as well, which is excellent -- http://www.stlport.org/. We used that for many years.)

>Probably not, because back
>then the sort() was bad enough that someone thought it
>needed to be changed.

Just because someone at SGI thought to improve their particular implementation doesn't mean it was bad before. (I mention implementation specifically here because the C++ standard doesn't define what sorting algorithm is used, and although all of them seem to have switched now, I don't know when the other implementations chose to switch.)

Switching from Quicksort to Introsort after seeing publications showing better worst-case behaviour is perfectly reasonable, and one of the benefits of just using sort() yourself is that you would have received the benefit of those refinements automatically without having to keep up with the literature on sorting algorithms. Using it when it was "just" Quicksort would hardly have been a hanging offence. What algorithm is yours using currently?

>Was it true in 1995 ? Definitely
>not, because all the template stuff was pretty flaky
>back then.

Our current codebase started in 1995 using what was a particularly flaky and non-conformant compiler in those days (Visual C++) but even then sort() would have been a pretty safe portion to use. It's such a simple algorithm relying on such simple operations that if the compiler couldn't compile that right then you wouldn't trust it to compile anything.

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

I tend to favour standard libraries where-ever possible on the basis that they have been more widely deployed and more widely tested than anything I am ever likely to write. More importantly, the compiler would have been tested on the libraries it shipped with, but not on my own code -- and I have turned up a handful of compiler bugs over the years. Learning about new libraries that I can use is also one of the ways that I improve my productivity over time, justifying increases in salary.

Furthermore, with a sort routine it is obviously trivial to assert() a call to a simple function that does a single pass through the data to verify it is in the correct order. I wish all operations were that easy to check.

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

There always is, which is why I'm not judging you, merely making suggestions. There is code in our software as well that hasn't been touched in nearly 15 years and that could do with a serious overhaul taking into account modern practices and compiler support. I'm also only partway through removing special inline assembler routines we wrote years ago to convert floats and doubles to ints because that was a ridiculously slow operation in the VC6 days (ten years ago I profiled one of our applications and discovered that a massive 50% of its runtime was spent in this mysterious _something function that turned out to be the function VC6 called whenever you cast a float to an int!) but which is now slower than the code generated by the modern compiler because it was pre-SSE2.

So I know where you're coming from, and I fully understand how compilers ten+ years ago were pretty crappy, especially if you started poking around the darker recesses of the language. However, ten years is also a long time, and it probably wouldn't hurt you to revisit your assumptions to see if there are better ways of doing things now -- not just because your tools should have matured a lot during that time, but also because being forced to remain single-threaded due to design decisions made back then is leaving increasingly large amounts of performance on the table.

We actually use "the number of threads the software will use" as a differentiating feature between different levels of the software, because time really is worth money, so the investment can pay off financially as well in a way that it didn't when customers could make your software faster just by buying a new PC. Porting it to 64 bits is another option that could massively clean up the code and invalidate all the design decisions you made back then. (We haven't yet because 4 GB -- the amount available to 32 bit Windows apps under a 64 bit OS -- is enough most of the time and we'd still have to support a 32 bit version anyway, but it's a dream I have.)

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

No. On a conformant implementation you can build an entire program around the assumption that malloc() either returns NULL or the address of the start of a block of memory at least as large as requested, suitably aligned that it can be assigned to a pointer to any type of of object, and then used to access such an object or an array of such objects in the space allocated, and that is disjoint from all other objects, and you will not be relying on undefined behaviour at all.

There are non-conformant systems that don't actually guarantee that you can actually use the memory successfully allocated, and may kill you (or even some other process) with prejudice at any time if you try to, but that's besides the point because it doesn't invalidate the above, and doesn't affect me because Windows isn't one of them. :-)

>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'm a little bit confused. I thought you were relying on particular undefined behaviour, not that the behaviour was unsuitable?

Our software has to cope with up to 10 GB of data under 32-bit Windows (which generally means 2 GB virtual address space and memory allocations starting to fail around the 1.5-1.7 GB mark) and so we have had to handle memory management and paging of some of our data for a long time already, particularly because the paging algorithm is far from optimal for our workload.

>I don't see a lot of point in everyone trying to second-
>guess all the decisions without knowledge of the context.

As I keep saying, I'm not.

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

Fair enough.

We actually came across a problem in the last couple of months where some data types not using our own explicit memory management (because it never gets large enough to warrant our attention) started failing to allocate memory only after 24 hours of runtime or so, despite there being huge amounts of physical and virtual address space still available.

We ended up concluding that fragmentation of the virtual address space must have been responsible (even though the allocation was failing on a tiny allocation, less than 10 MB) because stepping through the code showed it failing on the underlying Windows call (MS provides the CRT sourcecode so you can see where it goes) and I couldn't think of any other explanation.

Our solution, after trying a few different things to reduce fragmentation, was to give up and simply unload the entire project, clean up all memory, and then reload it again and continue on. Not pretty, but it only takes a few seconds and it works.

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

In general, although some sharing can be managed reasonably and tricks like double-buffering can help if you can afford the memory.

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

The problem with that is the overhead of copying data into different processes rules out a whole class of worthwhile operations that could be profitably threaded.

That's why I specifically mentioned "operations" and "sub-operations". The operation can easily have many interleaved parallel and serial suboperations, and having to coalesce all that data for each serial portion then copy it back out again for each parallel portion simply wouldn't be worth it in many cases.

But if you can split it into separate processes then of course that's the ideal, simplest possible case. It's just that those cases aren't common enough that we can ignore the others, even if they do require more effort.

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

Fair enough.

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

Of course. But that particular operation is the only one with non-deterministic results in our code, and the reason it is non-deterministic is very closely related to the fact that the precise values don't matter. (I don't mean this in the trivial way -- i.e. that we allowed it to be non-deterministic because it was OK to do so -- but because even in the serial case the output is non-deterministic in a particular case, but it just happens to always give the same output on every run. There is nothing special about the particular output it gave on that run.) For all the other operations the results are repeatable, even if the runtime behaviour (i.e. the precise interleaving of operations) is not.