Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Eric Sosman <esosman@ieee-dot-org.invalid> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: multidimensional heap arrays |
| Date | 2011-04-25 20:50 -0400 |
| Organization | A noiseless patient Spider |
| Message-ID | <ip54ts$20a$1@dont-email.me> (permalink) |
| References | <ip4if6$hhk$1@speranza.aioe.org> |
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
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web