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

As I keep repeating, my observation was not related to where you ended up but rather the path you took to get there. I have no problem with you eventually deciding to use a different algorithm after exhausting the options I outlined; my observations related to a reluctance to even try standard library routines before reinventing the wheel, particularly when those standard library routines have well documented behaviour, unlike the undocumented behaviour of the memory allocator that you did come to rely on and that cost you a "nasty few weeks" to track down as the cause of the weird behaviour you were seeing.

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

Sure, that's a valid point, especially when the third-party code (or second party, in this case) is using templates. And while the sort() routine itself is pretty damn robust, it will be potentially relying on your own key comparison and element swapping code, which can also be buggy -- although since the required behaviour is so simple it shouldn't be too hard to get them right. (If you need to write your own iterators as well then it gets hairier.)

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

Heh -- we use very little open-source code in our software. We use some libraries from Boost, but I still rank that as "well tested" and even then we only use the "safer" parts of it.

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

Hmm... Our codebase is about half the size of yours, and if you were to ask me where to start looking for stuff that could be profitably threaded it wouldn't take me long. Heck, I did exactly that as soon as I got a dual-core and I certainly didn't do it by reading through the source code at 500 lines an hour.

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

Or 500K?

Of course, I'm one of only three developers so I may have far more intimate knowledge of the code than someone in a much larger team, especially since performance tuning has largely been up to me for the past decade.

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

I said "measurable", not "significant". It's faster with the simpler code so I'm taking it out.

Furthermore, the conversion routines are a few assembler instructions that get inlined in thousands of places. It's been a while since I checked but I didn't think the profiler could pick those up once the code had been optimised.

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

Which gets back to my original observation -- it's odd that you are so against using a standard routine rather than rolling-your-own when it comes to sorting, but you would rather rely on the unspecified behaviour of the standard memory allocation routine than roll-your-own.

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

What, precisely, do you think the alternative is?

This is not a choice between a conformant program that doesn't perform the operation when the resource cannot be obtained and a non-conformant program that ignores the fact that the resource cannot be obtained and magically manages to complete the task anyway. It's a choice between a conformant program that detects the problem, tries to work around it if possible, perhaps giving the user the option to do something about the problem (e.g. clearing up some disk space, shutting down other programs, etc.) or at the least giving the user the option of saving their work, and a non-conformant program that has a segmentation fault and dumps core.

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

What are you suggesting? That you can write a program that can survive having the plug knocked out of the wall, or that because no program could survive that there's no point writing code that can handle all of the myriad other problems that could occur that could be handled properly?

I certainly care about what's useful. It isn't a choice between writing "Code that handles errors gracefully" and "Code that is 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.

You said that anybody who tries to use malloc() at all is "relying on undefined behavior". "Undefined behaviour" in this context, first raised by Michael, has a very specific meaning, defined in the C and C++ standards.

If you do not make assumptions about malloc() other than:

1. It either returns NULL or the address of the start of a block of memory at least as large as requested.

2. If the return value is not NULL then it is an address that is suitably aligned that it can be assigned to a pointer to any type of object.

3. If the return value is not NULL then it can be used to access such an object or an array of such objects in the space allocated.

4. If the return value is not NULL then it is disjoint from all other objects.

Then you will not be relying on undefined behaviour at all.

You may or may not be able to get much work done if malloc() keeps returning NULL (and I certainly wouldn't pay money for the one you proposed), but that is orthogonal to the question of whether you are relying on undefined behaviour.

In your case you experienced first-hand exactly why relying on undefined behaviour is risky -- using multithreaded code caused the compiler to switch to a different allocator causing "weird behaviour".

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

So what -- you don't bother checking to see whether you were able to allocate tens of GB of data because if the user's screwed anyway, you may as well liven it up by not even attempting to deal with the problem?

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

Right, so to repeat the point I made:

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

You responded "Maybe it does, maybe it doesn't.". Well, if you agree that using separate processes is slower than using threads, and if you agree with the proposition that there's no point parallelising the algorithm if it doesn't deliver a performance improvement, we can only conclude that not using threads therefore rules out those operations that would be faster if parallelised using threads but not faster if parallelised using processes.

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

Which I stated at the end, yes.

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

Now who's trying to second-guess decisions without being aware of the context? :-)

In this case the work-per-item is too small to justify the overheads of IPC.

In the case where the work-per-item is sufficiently large that the IPC overheads are lost in the noise then it's a perfectly valid option. This isn't one of them.

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

Yes -- and the time required is fine when you're loading or saving a project, but again, it rules out a whole class of worthwhile operations that could be profitably threaded if this is the only option.

Since the motive for parallelising the code is to gain performance, the overheads are critical in determining what can and what cannot be parallelised.

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

We hardly use global variables at all as a matter of good coding style, but we still have a whole bunch of heavily interlinked data structures, and most of the suboperations that can be parallelised are so small that IPC overheads would make them not worthwhile using separate processess. Sad but true.