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

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

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.

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

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.

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

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 :-(

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

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.

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.

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

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.

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

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

Some aspects of the undefined behavior were a pain that
we had to work around; other aspects of the undefined
behavior were helpful, and we started to rely on them.

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

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