[Beowulf] Stroustrup regarding multicore

[Perry E. Metzger]

"Robert G. Brown" <rgb at phy.duke.edu> writes:
> On Tue, 26 Aug 2008, Perry E. Metzger wrote:
>
>>> Perhaps, but don't most C programmers allocate such an array as a single
>>> vector and then repack the indices?
>>
>> I've never seen anyone allocate "as a single vector and repack the
>> indices", though I'm sure that a counterexample exists in someone's
>> code out there somewhere. In any case, one has no need to do such a
>> thing.
>
> I find that hard to believe, in both cases.  I and plenty of others do
> it all the time, and of course there is need.  Just (perhaps) not in
> your code.  Although maybe I shouldn't have said "most C programmers" --
> I meant "in the context of C programmers who are writing fortran-like
> numerical code for e.g. physics".  In systems code or text processing
> code I could easily believe that it is quite rare.
>
> In physics it is not.
>
> As a single example, if one is writing physics code summing matrices
> with angular momentum indices, the natural range is l = 0,1,2,3...; m =
> -l,-l+1,-l+2...0,...l-2,l-1,l.  The array is triangular and the indices
> don't start at 0.

Ah. You're not talking about using a C array as a C array any
more. You're talking about using it as a data structure to represent an
arbitrary matrix structure. In that case you will find C programmers
doing all sorts of games, of course, and I don't disagree with you.

>    a) Allocate a vector large enough to exactly hold the whole thing and
> use complicated pointer arithmetic to compute the displacements of each
> element (incorporated into a macro or whatever).

Games are better played inline functions these days -- much cleaner in
terms of semantics and similar performance to open coded stuff.

> Then there is the general problem of dynamic allocation of arrays, which
> I thought was nearly always done according to either c) a loop of
> mallocs, but malloc is expensive and there IS no guarantee that
> successive mallocs in a program will return contiguous blocks so if you
> want to ensure that a dynamic matrix is a single block of continuous
> memory internally you have to allocate it all at once and put the
> appropriate addresses in a suitable **pointer.

Multiple mallocs are guaranteed not to return contiguous memory,
because of the malloc headers.

Generally, if one is allocating and deallocating enough arrays and
they're big, I'd probably write a custom allocator that operated in
its own mmapped arena, but I'm a macho systems programmer. Normal
people are best off figuring out how large the whole thing has to be
and mallocing the chunk.

> And finally there is the convolution of this problem with structs,
> especially dynamically allocated structs with unusual index ranges.

Not sure what you mean by that.

> Sure, these tricks aren't needed in all C programs -- plenty of them can
> do fine with just:
>
>   double x[10],y[10][10],z[10]
>
> and C programmers quickly grow used to messing with the fact that maybe
> half of all loops they might want to program "naturally" run from 1 to N
> and not 0 to N-1.  But a lot of numerical C programmers simply write a
> matrix allocate subprogram (not unlike the one(s) in Numerical Recipes)
> that lets them dynamically allocate *x,**y,***z and run the loop indices
> from whatever to whatever for rectilinear allocation, or (in my case)
> write a somewhat more complex allocator for non-rectilinear allocation.

One can also play games with incrementing the pointers because believe
it or not, C will let you do that, at which point indexing 0 is an
error. You can also use negative indexes that way. NOT NOT NOT a
recommended idea. Much better to use an inline function and a wee bit
of imagination, or (in C++) to overload the [] operator.

-- 
Perry E. Metzger		perry at piermont.com