Re: Time-efficient memory-allocation

Anders Christensen wrote:
Hi NG,

I'm doing a C-program that might use a whole lot of memory (possibly
several GB). Basically the program will be doing Gaussian elimination
on a large matrix; the dimension of the matrix will increase in a
number og repeated steps.

The number of steps is unknown from the beginning: maybe it won't need
more than one iteration to succeed but possibly it'll take more
iterations. For each iteration the number of rows and the number of
columns will grow exponentially. In an iteration each row is extended
s.t. the original row's content should be in the beginning of the
extended row. And extra rows are added. The question is how I should
allocate the huge matrix in an efficient manner?

My approach is to malloc() each row seperately. When increasing the
demension of the matrix, I realloc() the existing rows and malloc()
some extra.

I'd like as little cache-misses as possibly (faster runningtime). And
the process of extending the row's lengths should be as time-efficent
as possible (faster preparing for the next iteration).

I'd appreciate any sugestions or comments.

Kind regards,
Anders


Rather than allocate and reallocate memory, how about just allocating a very big matirx to start with. You need not use all of the space!

Dynamic memory allocation does not make as much sense on today's machines with large virtual memory as it did when you were working with a PDP-11 with 32K of memory!
.

Relevant Pages

  • Re: Im missing something here with range vs. xrange
    ... the cost of creating the ... Allocate a big chunk of memory ... iteration is a separate step, ... The creation of the xrange object is massively faster - at least an ...
    (comp.lang.python)
  • Re: Time-efficient memory-allocation
    ... more than one iteration to succeed but possibly it'll take more ... I would try and allocate in the largest chunks you can manage. ... So rather than allocate rows at a time, I'd be tempted to allocate a whole array, copy from the old structure to the new one, then drop the old one. ... This means you use a lot of memory when you have both arrays in existence, but assuming you have the physical memory, it's likely to be more efficient. ...
    (comp.unix.solaris)
  • Re: Time-efficient memory-allocation
    ... I'm doing a C-program that might use a whole lot of memory (possibly ... more than one iteration to succeed but possibly it'll take more ... allocate the huge matrix in an efficient manner? ... My approach is to malloc() each row seperately. ...
    (comp.unix.solaris)
  • Re: Fearsome Parsing challenge, round 2.
    ... On all the platform's I've encountered, the behaviour when you change a long sting into a shorter one is to re-use the memory associated with the long string to contain the shorter string, leaving some unused, but not forgotten memory. ... The first iteration is fast, the second iteration is really slow, the third is fast, but not as fast as the first. ...
    (comp.lang.rexx)
  • [PATCH 0/5] PM: Drop shrink_all_memory (rev. 3)
    ... inefficient: it takes 7-9s to free up 1.4G memory: ... basically two major problems: ... iteration on my 64-bit test box), so we can improve that by limiting the number ... Although it doesn't seem to improve the speed of memory shrinking, ...
    (Linux-Kernel)