By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,804 Members | 1,666 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,804 IT Pros & Developers. It's quick & easy.

Allocating large blocks

P: n/a
I'm experimenting with a program that manipulates a large matrix, i.e.
a 2-deep array. I started by just allocating this in one go, but later
it occurred to me that, as there are still some very old systems
around where such a large allocation might fail, perhaps it would be
better to split the allocation into many allocations, one for each
row, to increase portability to legacy systems.

The advantage I see is that the memory allocator or operating system
might not be able to find a contiguous block, but several smaller
blocks might be OK. The downside would be that there is likely to be
more overhead in the allocator, and my program itself needs to store
an extra thousand pointers to keep track of the individual rows.

What do people think is best?

Here's some example code in case what I say isn't clear.

#include <stdlib.h>

#define ROWS (1<<10)
#define COLS (1<<20)

/* approach 1 */

static int *M;

void init()
{
if(!M=malloc(ROWS*COLS*sizeof(int)))
abort();
}
/* approach 2 */

static int *r[ROWS];

void init()
{
int i;
for(i=0; i<ROWS; (r[i++]=malloc(COLS*sizeof(int))) || (abort(),0));
}

Mar 10 '07 #1
Share this Question
Share on Google+
8 Replies


P: n/a
Fr************@googlemail.com wrote:
I'm experimenting with a program that manipulates a large matrix, i.e.
a 2-deep array. I started by just allocating this in one go, but later
it occurred to me that, as there are still some very old systems
around where such a large allocation might fail, perhaps it would be
better to split the allocation into many allocations, one for each
row, to increase portability to legacy systems.

The advantage I see is that the memory allocator or operating system
might not be able to find a contiguous block, but several smaller
blocks might be OK. The downside would be that there is likely to be
more overhead in the allocator, and my program itself needs to store
an extra thousand pointers to keep track of the individual rows.

What do people think is best?
You'll have to try it on your implementation to see which works best for
you.

--
Ian Collins.
Mar 10 '07 #2

P: n/a
<Fr************@googlemail.comwrote in message
news:11**********************@p10g2000cwp.googlegr oups.com...
I'm experimenting with a program that manipulates a large matrix,
i.e. a 2-deep array. I started by just allocating this in one go, but
later it occurred to me that, as there are still some very old
systems around where such a large allocation might fail, perhaps
it would be better to split the allocation into many allocations, one
for each row, to increase portability to legacy systems.

The advantage I see is that the memory allocator or operating
system might not be able to find a contiguous block, but several
smaller blocks might be OK. The downside would be that there
is likely to be more overhead in the allocator, and my program
itself needs to store an extra thousand pointers to keep track of
the individual rows.

What do people think is best?
....
#define ROWS (1<<10)
#define COLS (1<<20)
With these sizes, both approaches will almost certainly fail on all existing
32-bit and smaller systems. OTOH, both will likely work on 64-bit systems.

If you were exaggerating the dimensions, there is a window where the per-row
method will succeed where the single-chunk one will fail, but will depend on
the implementation and it's typically fairly narrow.

The biggest advantage of doing it all at once is that you'll find out if
your program will get what it wants in one call to malloc() instead of after
(worst case) ROWS-1 calls.

S

--
Stephen Sprunk "Those people who think they know everything
CCIE #3723 are a great annoyance to those of us who do."
K5SSS --Isaac Asimov
--
Posted via a free Usenet account from http://www.teranews.com

Mar 11 '07 #3

P: n/a

"Stephen Sprunk" <st*****@sprunk.orgwrote in message
>#define ROWS (1<<10)
#define COLS (1<<20)

With these sizes, both approaches will almost certainly fail on all
existing 32-bit and smaller systems. OTOH, both will likely work on
64-bit systems.

If you were exaggerating the dimensions, there is a window where the
per-row method will succeed where the single-chunk one will fail, but will
depend on the implementation and it's typically fairly narrow.
If you want to allocate about 1GB on a machine with around 2GB installed you
are in that window. That's 1000 * 1 million chars, and correspondingly fewer
ints.

Mar 11 '07 #4

P: n/a
Fr************@googlemail.com wrote:
# I'm experimenting with a program that manipulates a large matrix, i.e.
# a 2-deep array. I started by just allocating this in one go, but later
# it occurred to me that, as there are still some very old systems
# around where such a large allocation might fail, perhaps it would be
# better to split the allocation into many allocations, one for each
# row, to increase portability to legacy systems.

Perhaps if you're talking about 8086 or 80286 processors.
At some point you can decide some hardware is too old for
you to support and not worry about. Like I doubt your code
will run on mercury delay lines or ferrite core memories.

Otherwise the fewest stable blocks regardless of size is
most likely to make the memory allocator happy.

# #define ROWS (1<<10)
# #define COLS (1<<20)
#
# /* approach 1 */
#
# static int *M;
#
# void init()
# {
# if(!M=malloc(ROWS*COLS*sizeof(int)))

On some machines, this will become a single operating request
to memory map 4 or 8 gigabytes into your program. Efficient,
low overhead. And then with all the array elements contiguous
you can more predictably page the array by how you index it.

# int i;
# for(i=0; i<ROWS; (r[i++]=malloc(COLS*sizeof(int))) || (abort(),0));

This requires 500 times as many calls, perhaps each a separate
operating system request. Also the rows will have no predictable
relation to each other, so the paging will be more unpredictable.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
TEMPORARILY CLOSED
BE OPENED AFTER FIRST PERIOD
Mar 11 '07 #5

P: n/a
"Malcolm McLean" <re*******@btinternet.comwrote in message
news:VY******************************@bt.com...
"Stephen Sprunk" <st*****@sprunk.orgwrote in message
>>#define ROWS (1<<10)
#define COLS (1<<20)

With these sizes, both approaches will almost certainly fail on all
existing 32-bit and smaller systems. OTOH, both will likely work on
64-bit systems.

If you were exaggerating the dimensions, there is a window where
the per-row method will succeed where the single-chunk one will
fail, but will depend on the implementation and it's typically fairly
narrow.
If you want to allocate about 1GB on a machine with around 2GB
installed ...
While I grant it's possible to have that much RAM installed without virtual
memory, it's unlikely, so the physical RAM size is usually irrelevant.
... you are in that window.
Not necessarily. A 1GB single-chunk allocation may work on some 32-bit
machines -- and 1GB broken down into multiple chunks may fail on others.
(Then you get into fun issues like Linux's infamous tendency to
"successfully" return a large block from malloc() and then segfault when you
try to use it...)

But, yes, you are generally correct that 1-2GB is much more likely to
succeed if it's done in chunks; most implementations have "holes" at various
memory locations that make extremely large allocations difficult to
impossible. That's roughly the window I was talking about, though it
varies. However, I've found that folks tend to either be well below that
window, or their data will soon grow to exceed it significantly, making the
optimal behavior in that window mostly irrelevant. If you need to work with
>1GB of data at a time -- or will within a couple years -- you need to give
in and move to a 64-bit system. They're cheap enough these days it's not
worth the time to figure out how to make memory-hungry apps work on 32-bit
boxes.

S

--
Stephen Sprunk "Those people who think they know everything
CCIE #3723 are a great annoyance to those of us who do."
K5SSS --Isaac Asimov
--
Posted via a free Usenet account from http://www.teranews.com

Mar 11 '07 #6

P: n/a
On Mar 10, 10:25 pm, Francine.Ne...@googlemail.com wrote:
#define ROWS (1<<10)
#define COLS (1<<20)

/* approach 1 */

static int *M;

void init()
{
if(!M=malloc(ROWS*COLS*sizeof(int)))
abort();

}
Try to print the value of (size_t) (ROWS*COLS*sizeof(int)). You may be
surprised.

Mar 11 '07 #7

P: n/a
On Mar 11, 8:29 pm, "christian.bau" <christian....@cbau.wanadoo.co.uk>
wrote:
On Mar 10, 10:25 pm, Francine.Ne...@googlemail.com wrote:
#define ROWS (1<<10)
#define COLS (1<<20)
/* approach 1 */
static int *M;
void init()
{
if(!M=malloc(ROWS*COLS*sizeof(int)))
abort();
}

Try to print the value of (size_t) (ROWS*COLS*sizeof(int)). You may be
surprised.
peachy@sam:~$ echo '#include <stdio.h>
#include <stddef.h>
main() { return printf("%llu\n", (size_t)
((1<<10)*(1<<20)*sizeof(int))); }' | gcc -x c -
peachy@sam:~$ ./a.out
4294967296

Doesn't seem all that surprising?

Mar 12 '07 #8

P: n/a
Fr************@googlemail.com writes:
On Mar 11, 8:29 pm, "christian.bau" <christian....@cbau.wanadoo.co.uk>
wrote:
>On Mar 10, 10:25 pm, Francine.Ne...@googlemail.com wrote:
#define ROWS (1<<10)
#define COLS (1<<20)
/* approach 1 */
static int *M;
void init()
{
if(!M=malloc(ROWS*COLS*sizeof(int)))
abort();
}

Try to print the value of (size_t) (ROWS*COLS*sizeof(int)). You may be
surprised.

peachy@sam:~$ echo '#include <stdio.h>
#include <stddef.h>
main() { return printf("%llu\n", (size_t)
((1<<10)*(1<<20)*sizeof(int))); }' | gcc -x c -
peachy@sam:~$ ./a.out
4294967296

Doesn't seem all that surprising?
You're probably using a 64-bit implementation. On a 32-bit
implementation, you most likely would have gotten a result of 0.

There's no clear definition of "64-bit implementation" or "32-bit
implementation". It typically refers to the width of the CPU
registers. In this case, what's relevant is the width of size_t (and
the value of sizeof(int)).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Mar 12 '07 #9

This discussion thread is closed

Replies have been disabled for this discussion.