Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #2883 > unrolled thread

multidimensional heap arrays

Back to article view | Back to comp.lang.c

Contents

  multidimensional heap arrays Jack Boot <jackboot@mailinator.com> - 2011-04-25 19:36 +0000
    Re: multidimensional heap arrays Francois Grieu <fgrieu@gmail.com> - 2011-04-25 23:16 +0200
    Re: multidimensional heap arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-25 22:35 +0100
      Re: multidimensional heap arrays Anand Hariharan <mailto.anand.hariharan@gmail.com> - 2011-04-25 21:19 -0700
        Re: multidimensional heap arrays Francois Grieu <fgrieu@gmail.com> - 2011-04-26 08:19 +0200
          Re: multidimensional heap arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-26 12:19 +0100
            Re: multidimensional heap arrays Ian Collins <ian-news@hotmail.com> - 2011-04-26 23:25 +1200
              Re: multidimensional heap arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-26 21:06 +0100
                Re: multidimensional heap arrays Ian Collins <ian-news@hotmail.com> - 2011-04-27 08:59 +1200
                  Re: multidimensional heap arrays Keith Thompson <kst-u@mib.org> - 2011-04-26 14:39 -0700
                    Re: multidimensional heap arrays Ian Collins <ian-news@hotmail.com> - 2011-04-27 10:03 +1200
                    Re: multidimensional heap arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-26 23:41 +0100
                      Re: multidimensional heap arrays Keith Thompson <kst-u@mib.org> - 2011-04-26 16:33 -0700
                        Re: multidimensional heap arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-27 04:05 +0100
                  Re: multidimensional heap arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-26 22:49 +0100
                    Re: multidimensional heap arrays Ian Collins <ian-news@hotmail.com> - 2011-04-27 10:19 +1200
                      Re: multidimensional heap arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-27 00:38 +0100
                        Re: multidimensional heap arrays Ian Collins <ian-news@hotmail.com> - 2011-04-27 11:48 +1200
                          Re: multidimensional heap arrays Keith Thompson <kst-u@mib.org> - 2011-04-26 17:38 -0700
                            Re: multidimensional heap arrays Ian Collins <ian-news@hotmail.com> - 2011-04-27 13:08 +1200
                              Re: multidimensional heap arrays Tim Rentsch <txr@alumni.caltech.edu> - 2011-04-26 18:31 -0700
                                Re: multidimensional heap arrays Ian Collins <ian-news@hotmail.com> - 2011-04-27 14:01 +1200
                                  Re: multidimensional heap arrays Tim Rentsch <txr@alumni.caltech.edu> - 2011-04-27 00:04 -0700
                                    Re: multidimensional heap arrays Ian Collins <ian-news@hotmail.com> - 2011-04-27 19:58 +1200
                                      Re: multidimensional heap arrays Ian Collins <ian-news@hotmail.com> - 2011-04-27 20:03 +1200
                              Re: multidimensional heap arrays Keith Thompson <kst-u@mib.org> - 2011-04-27 00:03 -0700
                        Re: multidimensional heap arrays Tim Rentsch <txr@alumni.caltech.edu> - 2011-04-26 18:20 -0700
                          Re: multidimensional heap arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-04-27 03:59 +0100
                            Re: multidimensional heap arrays Tim Rentsch <txr@alumni.caltech.edu> - 2011-04-27 00:24 -0700
      Re: multidimensional heap arrays "io_x" <a@b.c.invalid> - 2011-04-26 09:42 +0200
    Re: multidimensional heap arrays Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-04-25 20:50 -0400
    Re: multidimensional heap arrays James Kuyper <jameskuyper@verizon.net> - 2011-04-25 22:57 -0400

Page 2 of 2 — ← Prev page 1 [2]

#2949

Ian Collins <ian-news@hotmail.com> writes:

> On 04/27/11 12:38 PM, Keith Thompson wrote:
>> Ian Collins<ian-news@hotmail.com>  writes:
>>> On 04/27/11 11:38 AM, Ben Bacarisse wrote:
>>>>
>>>> The standard can't mandate a type compatibility test that requires an
>>>> arbitrary non-constant expression to be evaluated, so in one way it is
>>>> not surprising that there is no error message.  Unfortunately I can't
>>>> square that with the requirement to issue a diagnostic when a pointer to
>>>> an incompatible type is passed to a function.
>>>
>>> I agree.  I tried the code with both gcc 4.5.1 (-ansi -Wall -pedantic
>>> -std=c99) and Sun c99.
>>>
>>> I thought a VLA would always have an incompatible type, given its size
>>> isn't known at compile time.  In cases like this, I miss C++'s typeid!
>>
>> C99 6.7.5.2p6:
>>
>>      For two array types to be compatible, both shall have compatible
>>      element types, and if both size specifiers are present, and are
>>      integer constant expressions, then both size specifiers shall
>>      have the same constant value. If the two array types are used in
>>      a context which requires them to be compatible, it is undefined
>>      behavior if the two size specifiers evaluate to unequal values.
>
> Ah, so they are incompatible, but no diagnostic was issued by either
> compiler.  I'd be interested in seeing if another C99 compiler issues
> one.

No, a VLA type is compatible with a non-VLA array type if they
have compatible element types.  The second sentence of 6.7.5.2p6
doesn't affect compatibility.

[toc] | [prev] | [next] | [standalone]

#2951

On 04/27/11 01:31 PM, Tim Rentsch wrote:
> Ian Collins<ian-news@hotmail.com>  writes:
>
>> On 04/27/11 12:38 PM, Keith Thompson wrote:
>>> Ian Collins<ian-news@hotmail.com>   writes:
>>>> On 04/27/11 11:38 AM, Ben Bacarisse wrote:
>>>>>
>>>>> The standard can't mandate a type compatibility test that requires an
>>>>> arbitrary non-constant expression to be evaluated, so in one way it is
>>>>> not surprising that there is no error message.  Unfortunately I can't
>>>>> square that with the requirement to issue a diagnostic when a pointer to
>>>>> an incompatible type is passed to a function.
>>>>
>>>> I agree.  I tried the code with both gcc 4.5.1 (-ansi -Wall -pedantic
>>>> -std=c99) and Sun c99.
>>>>
>>>> I thought a VLA would always have an incompatible type, given its size
>>>> isn't known at compile time.  In cases like this, I miss C++'s typeid!
>>>
>>> C99 6.7.5.2p6:
>>>
>>>       For two array types to be compatible, both shall have compatible
>>>       element types, and if both size specifiers are present, and are
>>>       integer constant expressions, then both size specifiers shall
>>>       have the same constant value. If the two array types are used in
>>>       a context which requires them to be compatible, it is undefined
>>>       behavior if the two size specifiers evaluate to unequal values.
>>
>> Ah, so they are incompatible, but no diagnostic was issued by either
>> compiler.  I'd be interested in seeing if another C99 compiler issues
>> one.
>
> No, a VLA type is compatible with a non-VLA array type if they
> have compatible element types.  The second sentence of 6.7.5.2p6
> doesn't affect compatibility.

It doesn't affect compatibility, but surly passing the address of one to 
a function expecting a pointer to a fixed size array is "used in a 
context which requires them to be compatible"?

Both compilers issue a diagnostic if the size specifier is not present, ie:

extern int x[];

f( &x );

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#2954

Ian Collins <ian-news@hotmail.com> writes:

> On 04/27/11 01:31 PM, Tim Rentsch wrote:
>> Ian Collins<ian-news@hotmail.com>  writes:
>>
>>> On 04/27/11 12:38 PM, Keith Thompson wrote:
>>>> Ian Collins<ian-news@hotmail.com>   writes:
>>>>> On 04/27/11 11:38 AM, Ben Bacarisse wrote:
>>>>>>
>>>>>> The standard can't mandate a type compatibility test that requires an
>>>>>> arbitrary non-constant expression to be evaluated, so in one way it is
>>>>>> not surprising that there is no error message.  Unfortunately I can't
>>>>>> square that with the requirement to issue a diagnostic when a pointer to
>>>>>> an incompatible type is passed to a function.
>>>>>
>>>>> I agree.  I tried the code with both gcc 4.5.1 (-ansi -Wall -pedantic
>>>>> -std=c99) and Sun c99.
>>>>>
>>>>> I thought a VLA would always have an incompatible type, given its size
>>>>> isn't known at compile time.  In cases like this, I miss C++'s typeid!
>>>>
>>>> C99 6.7.5.2p6:
>>>>
>>>>       For two array types to be compatible, both shall have compatible
>>>>       element types, and if both size specifiers are present, and are
>>>>       integer constant expressions, then both size specifiers shall
>>>>       have the same constant value. If the two array types are used in
>>>>       a context which requires them to be compatible, it is undefined
>>>>       behavior if the two size specifiers evaluate to unequal values.
>>>
>>> Ah, so they are incompatible, but no diagnostic was issued by either
>>> compiler.  I'd be interested in seeing if another C99 compiler issues
>>> one.
>>
>> No, a VLA type is compatible with a non-VLA array type if they
>> have compatible element types.  The second sentence of 6.7.5.2p6
>> doesn't affect compatibility.
>
> It doesn't affect compatibility, but surly passing the address of one
> to a function expecting a pointer to a fixed size array is "used in a
> context which requires them to be compatible"?

Yes, and that results in undefined behavior, but since compatibility
isn't affected there is no constraint violation, so no diagnostic
is required.


> Both compilers issue a diagnostic if the size specifier is not present, ie:
>
> extern int x[];
>
> f( &x );

This surprises me (at least for C).  The types 'int[]' and 'int[N]'
for any integer constant expression N are compatible types, so
pointers to them are compatible types.  Is the diagnostic a warning?
Might it have been provoked by use of -Wall, or something similar?

[toc] | [prev] | [next] | [standalone]

#2958

On 04/27/11 07:04 PM, Tim Rentsch wrote:
> Ian Collins<ian-news@hotmail.com>  writes:
>
>> On 04/27/11 01:31 PM, Tim Rentsch wrote:
>>>
>>> No, a VLA type is compatible with a non-VLA array type if they
>>> have compatible element types.  The second sentence of 6.7.5.2p6
>>> doesn't affect compatibility.
>>
>> It doesn't affect compatibility, but surly passing the address of one
>> to a function expecting a pointer to a fixed size array is "used in a
>> context which requires them to be compatible"?
>
> Yes, and that results in undefined behavior, but since compatibility
> isn't affected there is no constraint violation, so no diagnostic
> is required.

An interesting defect in the language.  Or have I become too used to the 
extra type safety in C++?

>> Both compilers issue a diagnostic if the size specifier is not present, ie:
>>
>> extern int x[];
>>
>> f(&x );
>
> This surprises me (at least for C).  The types 'int[]' and 'int[N]'
> for any integer constant expression N are compatible types, so
> pointers to them are compatible types.  Is the diagnostic a warning?
> Might it have been provoked by use of -Wall, or something similar?

A warning in both, Sun c99 with no options, gcc with -std=c99.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#2960

On 04/27/11 07:58 PM, Ian Collins wrote:
> On 04/27/11 07:04 PM, Tim Rentsch wrote:
>> Ian Collins<ian-news@hotmail.com>   writes:

>>> Both compilers issue a diagnostic if the size specifier is not present, ie:
>>>
>>> extern int x[];
>>>
>>> f(&x );
>>
>> This surprises me (at least for C).  The types 'int[]' and 'int[N]'
>> for any integer constant expression N are compatible types, so
>> pointers to them are compatible types.  Is the diagnostic a warning?
>> Might it have been provoked by use of -Wall, or something similar?
>
> A warning in both, Sun c99 with no options, gcc with -std=c99.

Silly me.  Notice I wrote extern int x[], not extern char x[].

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#2955

Ian Collins <ian-news@hotmail.com> writes:
> On 04/27/11 12:38 PM, Keith Thompson wrote:
>> Ian Collins<ian-news@hotmail.com>  writes:
>>> On 04/27/11 11:38 AM, Ben Bacarisse wrote:
>>>>
>>>> The standard can't mandate a type compatibility test that requires an
>>>> arbitrary non-constant expression to be evaluated, so in one way it is
>>>> not surprising that there is no error message.  Unfortunately I can't
>>>> square that with the requirement to issue a diagnostic when a pointer to
>>>> an incompatible type is passed to a function.
>>>
>>> I agree.  I tried the code with both gcc 4.5.1 (-ansi -Wall -pedantic
>>> -std=c99) and Sun c99.
>>>
>>> I thought a VLA would always have an incompatible type, given its size
>>> isn't known at compile time.  In cases like this, I miss C++'s typeid!
>>
>> C99 6.7.5.2p6:
>>
>>      For two array types to be compatible, both shall have compatible
>>      element types, and if both size specifiers are present, and are
>>      integer constant expressions, then both size specifiers shall
>>      have the same constant value. If the two array types are used in
>>      a context which requires them to be compatible, it is undefined
>>      behavior if the two size specifiers evaluate to unequal values.
>
> Ah, so they are incompatible, but no diagnostic was issued by either
> compiler.  I'd be interested in seeing if another C99 compiler issues
> one.

It's some rather odd wording.  The types are compatible, but using them
in a context that requires compatibility is undefined behavior.

It makes sense, or at least the consequences do.  Type compatibility is
purely a compile-time issue; VLAs introduce cases where compatible types
can't be used together, but in a way that the error can't (generally) be
detected at compile time.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#2948

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Ian Collins <ian-news@hotmail.com> writes:
>>
>> [snip] I was trying to come up [an example where the VLA-ness
>> changes the semantics]:
>>
>> typedef char C[16];
>>
>> void f( C* c ) {}
>>
>> int main(void)
>> {
>>   char c[16];
>>
>>   f( &c );
>>
>>   const unsigned n = 15;
>>
>>   char cc[n];
>>
>>   f( &cc );
>> }
>>
>> Compiles fine as c99 (which was the surprise),
>
> Hmm...  At first glance it looks like a diagnostic is required.  6.7.5.2
> p6 says:
>
>   "For two array types to be compatible, both shall have compatible
>   element types, and if both size specifiers are present, and are
>   integer constant expressions, then both size specifiers shall have the
>   same constant value. If the two array types are used in a context
>   which requires them to be compatible, it is undefined behavior if the
>   two size specifiers evaluate to unequal values."
>
> so are '&cc' and the parameter 'c' pointers to compatible types?  This
> paragraph does not say.  Maybe it is specified somewhere else, but I
> can't find it.
>
> I think the intent of the last sentence is to make the program's
> behaviour is undefined, but that would imply the need for a diagnostic.

No diagnostic is required because the last sentence isn't a
constraint.  That is, it isn't a restriction on the language
(does not have 'shall' or 'shall not').


>> but fails as C++ (type
>> mismatch).  What did surprise me was the VLA type matching even though
>> the size differed.  Changing the declaration of cc to cc[15] did
>> produce the expected compiler warnings.
>
> The standard can't mandate a type compatibility test that requires an
> arbitrary non-constant expression to be evaluated, so in one way it is
> not surprising that there is no error message.  Unfortunately I can't
> square that with the requirement to issue a diagnostic when a pointer to
> an incompatible type is passed to a function.

The VLA type is compatible with the non-VLA type, per the first
sentence of 6.7.5.2p6.  The second sentence doesn't affect
the compatibility relationship, just the defined-ness of
runtime behavior.

[toc] | [prev] | [next] | [standalone]

#2952

Tim Rentsch <txr@alumni.caltech.edu> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> Ian Collins <ian-news@hotmail.com> writes:
>>>
>>> [snip] I was trying to come up [an example where the VLA-ness
>>> changes the semantics]:
>>>
>>> typedef char C[16];
>>>
>>> void f( C* c ) {}
>>>
>>> int main(void)
>>> {
>>>   char c[16];
>>>
>>>   f( &c );
>>>
>>>   const unsigned n = 15;
>>>
>>>   char cc[n];
>>>
>>>   f( &cc );
>>> }
>>>
>>> Compiles fine as c99 (which was the surprise),
>>
>> Hmm...  At first glance it looks like a diagnostic is required.  6.7.5.2
>> p6 says:
>>
>>   "For two array types to be compatible, both shall have compatible
>>   element types, and if both size specifiers are present, and are
>>   integer constant expressions, then both size specifiers shall have the
>>   same constant value. If the two array types are used in a context
>>   which requires them to be compatible, it is undefined behavior if the
>>   two size specifiers evaluate to unequal values."
>>
>> so are '&cc' and the parameter 'c' pointers to compatible types?  This
>> paragraph does not say.  Maybe it is specified somewhere else, but I
>> can't find it.
>>
>> I think the intent of the last sentence is to make the program's
>> behaviour is undefined, but that would imply the need for a diagnostic.
>
> No diagnostic is required because the last sentence isn't a
> constraint.  That is, it isn't a restriction on the language
> (does not have 'shall' or 'shall not').

Yes, I know, but that was not my point.  I was saying that if the intent
was for the behaviour to be undefined (due to that last sentence) it
would be because the two types are incompatible and that incompatibility
would require a diagnostic form the call.  However, I can see that is
not what is written.  What it says is simply that unequal sizes gives
rise to UB, not to incompatibility.  So thank you for making me read it
again ore carefully.

>>> but fails as C++ (type
>>> mismatch).  What did surprise me was the VLA type matching even though
>>> the size differed.  Changing the declaration of cc to cc[15] did
>>> produce the expected compiler warnings.
>>
>> The standard can't mandate a type compatibility test that requires an
>> arbitrary non-constant expression to be evaluated, so in one way it is
>> not surprising that there is no error message.  Unfortunately I can't
>> square that with the requirement to issue a diagnostic when a pointer to
>> an incompatible type is passed to a function.
>
> The VLA type is compatible with the non-VLA type, per the first
> sentence of 6.7.5.2p6.

Oh, I see.  I am amazed at how differently I read it.  I think it would
be clearer as two sentences:

  "For two array types to be compatible, both shall have compatible
  element types.  If both size specifiers are present, and are integer
  constant expressions, then both size specifiers shall have the same
  constant value."

but it's late, and no doubt that carries some other unintended meaning.

>  The second sentence doesn't affect
> the compatibility relationship, just the defined-ness of
> runtime behavior.

Yes, I see that now.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#2957

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <txr@alumni.caltech.edu> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> Ian Collins <ian-news@hotmail.com> writes:
>>>>
>>>> [snip] I was trying to come up [an example where the VLA-ness
>>>> changes the semantics]:
>>>>
>>>> typedef char C[16];
>>>>
>>>> void f( C* c ) {}
>>>>
>>>> int main(void)
>>>> {
>>>>   char c[16];
>>>>
>>>>   f( &c );
>>>>
>>>>   const unsigned n = 15;
>>>>
>>>>   char cc[n];
>>>>
>>>>   f( &cc );
>>>> }
>>>>
>>>> Compiles fine as c99 (which was the surprise),
>>>
>>> Hmm...  At first glance it looks like a diagnostic is required.  6.7.5.2
>>> p6 says:
>>>
>>>   "For two array types to be compatible, both shall have compatible
>>>   element types, and if both size specifiers are present, and are
>>>   integer constant expressions, then both size specifiers shall have the
>>>   same constant value. If the two array types are used in a context
>>>   which requires them to be compatible, it is undefined behavior if the
>>>   two size specifiers evaluate to unequal values."
>>>
>>> so are '&cc' and the parameter 'c' pointers to compatible types?  This
>>> paragraph does not say.  Maybe it is specified somewhere else, but I
>>> can't find it.
>>>
>>> I think the intent of the last sentence is to make the program's
>>> behaviour is undefined, but that would imply the need for a diagnostic.
>>
>> No diagnostic is required because the last sentence isn't a
>> constraint.  That is, it isn't a restriction on the language
>> (does not have 'shall' or 'shall not').
>
> Yes, I know, but that was not my point.  I was saying that if the intent
> was for the behaviour to be undefined (due to that last sentence) it
> would be because the two types are incompatible and that incompatibility
> would require a diagnostic form the call.

Ahh, I see.  I misunderstood your intended implication there.

> However, I can see that is
> not what is written.  What it says is simply that unequal sizes gives
> rise to UB, not to incompatibility.  So thank you for making me read it
> again ore carefully.

You are most welcome, sir.


>>>> but fails as C++ (type
>>>> mismatch).  What did surprise me was the VLA type matching even though
>>>> the size differed.  Changing the declaration of cc to cc[15] did
>>>> produce the expected compiler warnings.
>>>
>>> The standard can't mandate a type compatibility test that requires an
>>> arbitrary non-constant expression to be evaluated, so in one way it is
>>> not surprising that there is no error message.  Unfortunately I can't
>>> square that with the requirement to issue a diagnostic when a pointer to
>>> an incompatible type is passed to a function.
>>
>> The VLA type is compatible with the non-VLA type, per the first
>> sentence of 6.7.5.2p6.
>
> Oh, I see.  I am amazed at how differently I read it.  I think it would
> be clearer as two sentences:
>
>   "For two array types to be compatible, both shall have compatible
>   element types.  If both size specifiers are present, and are integer
>   constant expressions, then both size specifiers shall have the same
>   constant value."
>
> but it's late, and no doubt that carries some other unintended meaning.

As written, one problem is the second sentence is (arguably)
decoupled from the definition of compatibility, so its 'shall'
again just causes UB on length mismatches rather than forcing
a diagnostic.  Writing Standard-suitable text is a lot harder
than it looks.

[toc] | [prev] | [next] | [standalone]

#2907

"Ben Bacarisse" <ben.usenet@bsb.me.uk> ha scritto nel messaggio
news:0.3b2fcc49ff70b692295a.20110425223547BST.87vcy2dnf0.fsf@bsb.me.uk...
> Jack Boot <jackboot@mailinator.com> writes:
>> 3: one big mallocated array, no separate row pointers but an accessor
>> macro instead, ie
>> int * Astorage = malloc(nrow * ncol * sizeof(int));
>> #define A(i,j) Astorage[i*ncol+j];
>
> You can avoid the macro by allocating (and thus pointing to) an array
> type:
>
>  int (*A)[ncol] = malloc(nrow * sizeof *A);
>
> The sizeof idiom really pays off here: there is no need to think about
> what the right type element type is.
>
> If ncol is not a constant expression, you will need a modern C compiler
> for this to work (by which I mean C99).  Use them while you can, since
> they will no longer be required in the next C standard.

good, i not thought until now how to do that [use with the malloc
the arr[i][j] way]
-----------------
#include  <stdio.h>
#include  <stdlib.h>

int main(void)
{unsigned  x, y, z;
 unsigned  *pc, arr[10][10], (*p10)[10];

 z=0;
 for(y=0; y<10; ++y)
   for(x=0; x<10; ++x)
          arr[y][x]=z++;

 x=rand()%10;  y=rand()%10;
 z=arr[0][0];
 arr[y][x]=9;
 pc=arr[1];

 p10=arr;
 x=p10[1][0];
 printf("[0][1]=%u\n", x);
 return 0;
}


>> what is your opinion of these methods? what situations is one is better
>> than another? should some of them never be used? what is standard/best
>> practice?
>
> Sorry, no idea.  It is sometimes possible to pick the "best" if enough is
> known about the problem being solved and the constraints on the solution
> but I don't think there is a "best" without any such information.
>
> -- 
> Ben.

[toc] | [prev] | [next] | [standalone]

#2891

On 4/25/2011 3:36 PM, Jack Boot wrote:
> hi
>
> we have been discussing methods for multidimensional heap arrays, between
> us we have 3 preferred approaches
>
> 1: array of pointers each mallocated, ie
> int ** A = malloc(nrow * sizeof(int*));
> for(i=0;i<nrow;i++) A[i]=malloc(ncol * sizeof(int));
>
> 2: array of pointers set into one big mallocated array, ie
> int ** A = malloc(nrow * sizeof(int*));
> int * Astorage = malloc(nrow * ncol * sizeof(int));
> for(i=0;i<nrow;i++) A[i]=Astorage+i*ncol;
>
> 3: one big mallocated array, no separate row pointers but an accessor
> macro instead, ie
> int * Astorage = malloc(nrow * ncol * sizeof(int));
> #define A(i,j) Astorage[i*ncol+j];
>
> what is your opinion of these methods? what situations is one is better
> than another? should some of them never be used? what is standard/best
> practice?

     All need some cleanup, of course: Error-checking on the malloc()
calls, extra parentheses in the macro, better sizeof operands, etc.

     (1) uses the most storage, (3) the least.  (2) is somewhere in
between: It uses the same nominal amount as (1), but by using fewer
allocations it uses less per-allocation overhead.

     (1) is least likely to run afoul of per-allocation size limits
(including limits caused by fragmentation).

     (1) is the most vulnerable to performance penalties, because of
the double indirection and the possible lack of locality among the
individual sub-allocations.  (2) suffers the indirection but not the
locality problems, and (3) suffers neither.  But this must be taken
ith a grain of salt, or maybe even a truckload, because access patterns
and cache characteristics and can interact in hard-to-foresee ways.

      Which would I choose?  Well, what day of the week is it, and
what's the phase of the Moon, and was my coffee bitter this morning?
More to the point, what fits most neatly into the rest of the program?
If the individual "rows" have a meaning of their own, I'd probably opt
for (1) or (2), but if it's just an "atomic" matrix I might use (3).
Or not.  Or, as a wise man once said: "When you cannot choose between
A and B, flip a coin.  As the coin starts descending from the height
of its arc, you'll realize which way you want it to fall."

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#2896

On 04/25/2011 03:36 PM, Jack Boot wrote:
> hi
> 
> we have been discussing methods for multidimensional heap arrays, between 
> us we have 3 preferred approaches
> 
> 1: array of pointers each mallocated, ie
> int ** A = malloc(nrow * sizeof(int*));
> for(i=0;i<nrow;i++) A[i]=malloc(ncol * sizeof(int));

I've used this approach before. It's particularly useful when the rows
of the array have different lengths, and in a triangular matrix. With
careful attention to how you access such a matrix, you can avoid storing
all of the useless zero elements.

> 2: array of pointers set into one big mallocated array, ie
> int ** A = malloc(nrow * sizeof(int*));
> int * Astorage = malloc(nrow * ncol * sizeof(int));
> for(i=0;i<nrow;i++) A[i]=Astorage+i*ncol;

I've used something like this approach before, but I don't like it. I
used it because I was trying to reverse-engineer some routines from a
commercial third-party library (I told my boss I wanted to get advice
from a corporate lawyer before I tackled this project - he told me to
just get on with it, and not worry about such issues. I filled the code
with comments documenting which library my code was emulating, as well
as exactly how I determine what the functions should do without
disassembling it or stealing the original source code. I hope that was
sufficient to avoid legal problems.)

One of these routines created a dynamically-allocated structure filled
with pointers to arrays of several different dimensions, whose length in
each dimension was variable, and stored in that structure. My black-box
testing determined that it was using something like the following
method: it allocated a single block of memory big enough to store the
structure and all of the arrays it contained pointers to. The arrays
were not merely of several different sizes, but even of several
different dimensions. The routine filled in the pointers in that
structure with values pointing at various parts of that single big
allocation.

I perforce followed the same approach in my own reverse-engineered code.
I can see the advantages of such an approach, but it strikes me as a
delicate system, easily broken if a single pointer gets set incorrectly
during an update.

> 3: one big mallocated array, no separate row pointers but an accessor 
> macro instead, ie
> int * Astorage = malloc(nrow * ncol * sizeof(int));
> #define A(i,j) Astorage[i*ncol+j];
> 
> what is your opinion of these methods? what situations is one is better 
> than another? should some of them never be used? what is standard/best 
> practice?

I'd replace the accessor macro with an inline function, if only for type
safety. Otherwise, this is another reasonable approach.
-- 
James Kuyper

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web