Richard Cownie (tich@pobox.com) on 8/20/09 wrote:
---------------------------
>Oh, I daresay the STL sort() was *correct* from the
>beginning. But when it's a) mixed in with a lot of
>other flaky stuff, and b) not particularly fast in
>some cases, then the decision to use it is not so obvious.

Well, as I said, if sort() was defined correctly but the compiler couldn't turn that into correct code then I wouldn't trust it with any code, including my own sorting algorithm.

Note that the cases where it was "not particularly fast" are exactly those where the Quicksort algorithm is not particularly fast. If you're willing to sacrifice average performance to get better worst-case performance then stable_sort() is a better option, however now that all implementations are using Introsort for sort() the worst-case behaviour is the same.

You shouldn't rely on it being the same, of course, because the current standard doesn't guarantee that.

>And that's a good argument for the *correctness* of such code.
>But for uses which are performance-critical, I'm much
>more skeptical about picking up "standard" stuff which
>necessarily has to cater to the lowest common denominator,
>rather than being optimized to the characteristics of your
>own particular problem.

One of the things I like about C++ is that there is no reason for the standard stuff to cater for the lowest common denominator. It should already have partial specialisations for all the built-in types where it makes sense to do so, and you can supply your own specialisations for e.g. key comparison and element swapping on your own data structures and the algorithm will seamlessly take advantage of them without incurring any unnecessary function call overhead (as qsort() does).

>Yeah, that's one way a sort() can go wrong. The other way
>is a bus error or segmentation violation ... or maybe a
>pathological case that takes hours to run, or even an infinite loop. And if any of those happen,
>you can bet it will be at the site of your largest
>customer, right while you're negotiating a big order :-(

I don't see how they can be any more likely (and I would posit less likely, given the stricter testing regime that standard library code has to pass) than code you have written yourself.

If you're worried you can always simply inspect the header file to verify the implementation. None of the standard algorithms are terribly complicated.

>Trouble is that "revisiting assumptions" in 1M+ lines of
>code could take years. If something shows up in profiling
>or other performance analysis, then you look at it, for
>sure. But otherwise it's all going to stay just the way
>it is.

The issue in this case is that the world has changed, and if you only ever revisit assumptions when something shows up in profiling then you miss out on taking advantage of those changes.

For example, in the past ten years it's entirely possible that nothing much has changed when profiling your code, yet portions of that code could be much slower than they otherwise would be if they were threaded. Similarly, when first written it may have been using x87 code and may now profit greatly from using SSE[n], but because the profiling results haven't changed there's nothing to indicate that you should investigate.

In my case, the float-to-int conversion routines that we wrote ten years ago to address VC6's braindead casting implementation are now slower than VC2k8's casting implementation, and taking them out has a measurable impact on overall performance even though they've never shown up in profiling as suddenly being a problem.

The prevalence of many cheap cores and the relative stagnation of single threaded performance make that a really obvious target, however.

>As for the "single-threaded" issue, I'm actively working
>on ways to exploit more parallelism. But my own opinion
>is that a scheme based on multiple processes (each
>with their own protected address space) is likely to
>yield a product-quality solution much earlier than an
>approach based on multiple threads in a single address
>space (which is the more conventional approach). YMMV.

MMDV, yes. I use both; if I restricted our parallelism to only those cases where multiple processes were the solution we would lose most of the current speedups that we have gained and we would lose some of the premium we can therefore charge for the higher-performance versions.

>Most of our code is 64bit these days - and the core code
>has been 64bit since around 2000 (first on SPARC/Solaris,
>then on x86_64 as soon as that became available).
>I don't think it made much difference to any of the
>design decisions though.

So even with a 64 bit virtual address space to play with you still find you rely on the memory allocator returning addresses in a particular way?

>>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.
>
>Yes you are. You're relying on the undefined behavior of
>how much memory malloc() will give you, on a particular
>platform, with other processes running, before it craps
>out and returns NULL.

No, at several different levels.

Firstly, unless you are not bothering to check the return value because you "know" it will always succeed, then you are not relying on anything other than the guarantees in the standard, which, by definition, you are allowed to rely on. If you rely only on the guarantees I listed above, then you can use your very uncooperative malloc() (which I don't agree is consistent with the standard's specification for malloc()'s behaviour but it doesn't matter), or a malloc() that randomly returns NULL for no good reason, or a malloc() that behaves in the way described by the standard, and the code will still be perfectly valid and conformant.

Secondly, there are platforms for which you can't rely on the above guarantees (e.g. Linux and apparently MacOS X), because they return a non-NULL value for malloc() even when there isn't sufficient memory available and therefore can run out of memory and kill your process or even somebody else's process when you actually try to use that memory. As I said, that makes those platforms non-conformant by definition. It doesn't make your program non-conformant and it doesn't mean you are relying on undefined behaviour, and the existence of non-conformant environments certainly doesn't mean that you can't write non-trivial programs using dynamic memory allocation that don't rely on undefined behaviour -- Windows, for example, is perfectly happy to oblige, and Linux offers settings that you can use to make it conformant.

>Which depends on the allocation
>algorithm, the pattern of allocations, how much swap space
>the machine is configured with, and what other processes
>are running. In my trivial example, the answer is
>that malloc() is going to crap out right away. But *no*
>implementation actually defines the behavior in detail -
>fragmentation is too complex, the OS environment is too
>complex.

The point is that it doesn't matter if and when malloc() returns NULL if you are checking for it, as you must. If you check for NULL and do whatever you need to do to cope with it (which could be anything from calling exit() to attempting to free up some memory being used elsewhere and/or being less ambitious in the size requested, which sometimes you can do with some performance loss) then you haven't assumed anything. (In our code we use set_new_handler to install a routine that will try to free up some memory in low memory situations.)

It's only when you don't check for NULL and assume you always got the memory you asked for that you are relying on undefined behaviour. Or when you assume something about the memory you will be allocated other than what I listed above (which could range from undefined -- e.g. assuming that you can use a certain range beyond that which you actually allocated -- to merely unspecified -- e.g. assuming a certain order or contiguity to the storage allocated by successive calls).

>>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.
>
>There you go, that's just the kind of "undefined behavior"
>of malloc that I'm talking about.

But we weren't relying on it. Our software didn't crash and nothing was lost, it just stopped and reported that it was unable to proceed. So instead of stopping, it now takes steps to see if it can jump-start the memory allocation process again. In this case it works (the first attempt didn't so we had to get more drastic and dump everything from memory to start from a completely clean slate) but even if it didn't and the program had to give up and say "Sorry" we still wouldn't be relying on undefined behaviour.

If, OTOH, we had assumed that malloc() (or new in this case) would never fail, then you could say that we were relying on undefined behaviour. (It's harder in the case of new because it will throw an exception; you have to go out of your way to try and use the pointer under those circumstances. We normally wrap the user-level operation itself with an exception handler and, where possible, do the work "off to the side". If the operation succeeds the results are incorporated into the project, and if it fails we simply report that it was unable to perform the requested operation. If bad_alloc was thrown and we are unable to do anything to free up some memory ourselves we advise the user to either be less ambitious or take steps to free up memory themselves.)

The simple fact that a program may not be able to perform a particular operation it was designed to on a particular system due to insufficient resources does not mean it is relying on undefined behaviour unless it erroneously assumed it would be able to access those resources. An inability to acquire necessary resources is a fact of life and it is in no way relying on undefined behaviour to refuse to do something unless those resources are available.

>>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.
>
>Maybe it does, maybe it doesn't. The dirty secret about
>multi-core and multi-socket machines with caches is that
>your threaded program is going to spend a whole lot of
>time moving cache lines between the different caches.
>It's not completely obvious that moving data explicitly
>and in advance will end up costing you a lot more than
>having it happen implicitly on demand. And the implicit
>case is *definitely* going to be harder to understand
>(because the data movement operations that take the time
>are not apparent in the source code).

However:

* Simply using processes instead of threads doesn't remove those additional copy operations, so you still have to move the data explicitly and in advance in addition.

* You can also set processor affinity for a thread exactly as easily as you can for a process.

* In at least one of our cases you don't know which data should be moved in advance (threads remove work items off the head of a queue) so you would either have to copy all of it, once for each process, and then have the communications overhead of telling each process when one of the items has been removed from the head, or you would have to try to partition it in some way that would be a serious problem in this case because one of the things the threads do is add stuff to the queue as well, i.e. only some of the data is there at the beginning.

* If your structure includes pointers then you'll have to figure out how to remap those on transfer to a different address space, possibly forcing you to use a different structure just to make that easier even if it was not the optimal one, as well as copy across a whole bunch of other data that the data you wish to process relies on. In the general case this could involve an entire serialisation/de-serialisation operation.

* With modern prefetching implementations, a low frequency of non-local memory accesses could be completely hidden in a way that a bulk copy up-front could not be, and if the data is sufficiently large the copy operation could trash your caches anyway. (If the frequency of memory access is so high that the code is actually bandwidth limited then there's probably not much point threading it in the first place.)

One option is to use shared memory. This isn't all that different to threading except data is not shared by default so you have better control over the portion you need to be careful about, whereas with threading everything is shared by default and you have to explicitly request thread-local storage.