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

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

In my case, I know most of the keys have long common
prefixes. The algorithm can exploit that to go faster:
but obviously a standard library routine can't know
that and take advantage of it. That's what I mean -
merely being able to redefine the comparison operator
doesn't get you far.

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

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

It's more likely to happen in homebrew code. But when
it does happen, it's a lot easier to debug and fix in
your own code than in third-party code.

And I've been skeptical of the "stricter testing regime"
ever since I picked up a new release of gdb back around
2002 and found that all the C++ support was fatally
broken ... QA is terrific for some open-source projects,
utterly lousy for others.

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

Investigate how ? If you read 500 lines an hour, then
merely reading a 1M-line codebase would take 2000 hours,
or 50 weeks of 40 hours. It can't be done.

It's another game altogether if your codebase is around
50Klines.

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

Well, there's something lacking in your profiling tools
if they don't *show* those routines taking significant
time, and yet removing them makes a significant difference.
>
>The prevalence of many cheap cores and the relative >stagnation of single threaded
>performance make that a really obvious target, however.

Of course. But one with many horrible pitfalls.

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

The issue is that you go 64bit because your data structures
are too big for 4GB. But going 64bit makes all your
Foo* pointers occupy 8 bytes (with 8byte alignment)
instead of 4bytes (with 4byte alignment). If roughly
half your data is pointers, then that means instead of
needing 4GB you now need about 6GB. Yeuch!

So you look for ways to compress the pointers into less
than 8 bytes, based on knowledge about the actual
virtual address regions used for allocation,

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

Sure, so you can write a program which checks the return
value and thus write a orogram which is conformant ...
but useless! Because it craps out with an error message
as soon as it tries to allocate anything. Did that help ?
>
>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

Sure they do, but so what ? If someone knocks the plug
out of the wall your process is going to get killed as
well, whether it's Windows or Linux.

I don't care what's "conformant". I care about what's
useful.

>The point is that it doesn't matter if and when malloc() returns NULL if
>you are checking for it, as you must.

Of course it matters! For most programs, if they can't
allocate memory dynamically then they can't do anything
useful.

I guess we have very different problems to deal with:
in my app, if you can't dynamically allocate tens of GB
of memory, then you're screwed. YMMV.

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

Of course. Using separate processes isn't a way to make
it faster; it's a way to make it *safer*. A lightweight
thread can read and write everything; a separate process
can only read and write what you explicitly copy in and
out of it.

>* In at least one of our cases you don't know which data should be moved

Doesn't sound particularly hard: there just needs to be
a local task queue manager which then passes tasks
(and their associated data) off to the worker processes.

>* If your structure includes pointers then you'll have to >figure out how to remap

Sure, we know how to serialize/deserialize data
structures with pointers. And since your app can dump
and reload its whole state, presumably you do too.

>optimal one, as well as
>copy across a whole bunch of other data that the data you >wish to process relies
>on.

There's some design work needed to precisely specify
the data to be moved in and out, and to keep it as small
as possible. But I actually think it may be good to
force people to think about that explicitly (just as it's
good for people to write procedures with arguments,
rather than access everything through global variables).