Richard Cownie (tich@pobox.com) on 8/24/09 wrote:
---------------------------
>It isn't global variables in the language sense, so much
>as the fact that the data structures are highly
>interlinked, so if you pass a pointer into a thread
>then the thread might call routines that call other
>routines that follow pointers to other objects that
>point to other objects that point anywhere ...

Well, we generally don't write our code as unencapsulated as that. A few objects contain methods that return pointers, but when those object are const, the const versions of those methods are called, and they return const pointers.

And one of the cool things about threading is that it's cheap enough that you don't need to do it at such a high level that you're talking about calling routines that call other routines that follow pointers to other objects that point to other objects that point anywhere. All of our threaded routines have a very shallow view of the data, generally working directly with the container that contains the objects to be processed.

>>What I did say was that it would need to be about a thousand times faster
>>to compete with not having to copy it at all.
>
>The data has to get into/through the L1 cache of the
>core that runs the task, whether you program any explicit
>data copying or not. And the *implicit* data movement
>takes time - time that is hard to measure, but it
>isn't a free lunch.

As I've said before:

1. That cost will be present in the parallel processing case as well, and will typically be worse if distinct copies of the data are being used rather than shared memory because of the additional cache pressure. Therefore the cost of the up-front copy is in addition to the normal copying of data into caches. The only downside I can see is that when there is a lot of writing to shared data it can cause a lot of cache flushes that wouldn't otherwise have been required, but if you can partition the output well enough that separate processes can write to independent partitions then you can certainly do exactly the same thing with the multithreaded version, while still gaining on not copying the read-only portions. (We have several routines that partition the problem by the output generated, and then each thread fills in its portion of the output array, while all reading the shared input.)

2. It can be a free lunch if there is enough computation between accesses and the predictors work well enough that the latency is completely hidden.

>>That's also a huge burden. You've stated many times how much effort is required
>>to revisit the assumptions of a large codebase stretching back 15 years while at
>>the same time advocating a sweeping change like this.
>
>It's a problem that tools can help with, a lot: the
>serialize code can follow pointers, and it can tell
>you where it's going and how much stuff it's moving.
>And if you fail to copy some stuff you really needed
>(e.g. access through global/static variable), then
>the separate process will get junk and crash. Dealing
>with those issues seems more tractable than dealing
>with unrepeatable thread interactions. YMMV.

That seems like a lot of work compared to analysing a single routine that's a hotspot amenable to parallelisation. YMMV.

>>Using threading I can look at a tiny part of the code, analyse it, and thread it
>>safely with minimal changes. I can do this bit-by-bit over time, finding the next
>>best operation to parallelise and implementing it.
>
>That aspect is the same.

Maybe in your case.

>>To do it your way I would have to be in a position to predict all the ways I might
>>want to slice and dice the data in future if I want to avoid having to go through
>>the whole process every time I wanted to parallelise a certain operation, which
>>would be tricky since different operations really want to partition the data in different ways.
>
>Well, good algorithms need suitable data structures.
>If different algorithms want to traverse the data in
>different ways, that's a design issue which may need
>to be addressed for serial code just as much as for
>parallel code. If my approach forces its users to
>think hard about the data structure for each particular
>algorithm, that may have some benefits as well as costs.

There's no issue with the data structures in the serial case. It's when you come to thinking about how to parallelise the operation that different views into the data can be required to maximise performance.

>>Consider the case I mentioned: the processor is accessing shared data at a rate
>>of no more than a few hundred MB/sec, and each access is surrounded by quite a few
>
>Yeah, that's all fine: if you have a detailed understanding
>of all the data access patterns and algorithms, then
>you're golden. But that isn't the kind of culture I'm
>working in (and frankly, I think the vast majority of
>programmers these days don't have a clue: a lot of ours
>have no clue about relative bandwidth and latency of
>disk and DRAM; some don't seem to know what a cache is,
>or why it matters).

I would suggest that trying to do anything remotely complicated with programmers that don't have a clue is a bad idea.

>>BTW, I did forget one feature of C++ that does help with threading, and
>>that's const,
>
>I find it mostly useless myself: you pass in a pointer
>to a const object, then you read some other pointer
>inside the object and follow it to something else,
>and modifying that second (or N'th) object is just as
>harmful. I suppose you could try to write all your
>classes with deep const'ness, i.e. a const method treats
>all pointers to other objects as const, But that's
>hard to do and perhaps not always what you want "const"
>to mean.

If you declare that a method is const then it's up to you to make sure it means what you want it to mean. If you can't do that, don't declare it const.

As I mentioned above, the handful of const methods that we have that return pointers to things only return const pointers, thereby ensuring constness is transitive. The logic behind it is that if you're asking an object for a pointer to something, chances are the "something" should be thought of as part of the state of that object, and therefore if the object is const, the pointer should be as well.

I would consider a whole mess of classes returning pointers to all sorts of other classes to be a sign of poor encapsulation, however, and good encapsulation certainly helps when it comes to threading because it allows you to focus on a manageable portion of the code.