system out of memory

[Jon]

Hello,

I am running an algorithm that requires O(n^2) space. The comp has 8
GB of RAM, but I'm seeing the program cap out at around 1.7 GB, and
then I get an out-of-memory error. (The algorithm essentially
constructs a complete graph, where each node has an edge to every
other node in the graph.) Now, given the n^2 requirement there will
always be some limit, so in the end I should find a better algorithm,
but for now it would be nice to somehow increase the allocated space
for the program. Is there something I can do in C# to increase its
memory cap?

Thanks,
Jon

 

[Alun Harford]

Hello,

I am running an algorithm that requires O(n^2) space. The comp has 8
GB of RAM, but I'm seeing the program cap out at around 1.7 GB, and
then I get an out-of-memory error. (The algorithm essentially
constructs a complete graph, where each node has an edge to every
other node in the graph.) Now, given the n^2 requirement there will
always be some limit, so in the end I should find a better algorithm,
but for now it would be nice to somehow increase the allocated space
for the program. Is there something I can do in C# to increase its
memory cap?

Looks like you're running out of paged memory. That's a limitation of
Windows on a 32-bit architecture - no process can use more than 2GB of
paged memory.

You'd need to switch your operating system to Windows x64 (and you might
have to change your processor to one that supports 64-bit).

(Although I'm not 100% sure that the x64 version of .NET supports >2GB,
I suspect it does)

Alun Harford

 

[Willy Denoyette [MVP]]

Hello,

I am running an algorithm that requires O(n^2) space. The comp has 8
GB of RAM, but I'm seeing the program cap out at around 1.7 GB, and
then I get an out-of-memory error. (The algorithm essentially
constructs a complete graph, where each node has an edge to every
other node in the graph.) Now, given the n^2 requirement there will
always be some limit, so in the end I should find a better algorithm,
but for now it would be nice to somehow increase the allocated space
for the program. Is there something I can do in C# to increase its
memory cap?

Thanks,
Jon

Process Memory space is limited to ~2GB (or 3GB on 4GT enabled systems) on
32-bit Windows systems.
64-bit Windows has a much higher limit (~8TB) for process space, however,
the CLR currently restricts the size of an object to ~2GB, so even on 64-bit
windows you will probably run into the same issue if you don't change your
algorithm.

Willy.

 

[Jon Skeet [C# MVP]]

On Jun 18, 9:21 am, "Willy Denoyette [MVP]"

Process Memory space is limited to ~2GB (or 3GB on 4GT enabled systems) on
32-bit Windows systems.
64-bit Windows has a much higher limit (~8TB) for process space, however,
the CLR currently restricts the size of an object to ~2GB, so even on 64-bit
windows you will probably run into the same issue if you don't change your
algorithm.

Either I've mistaken the OP's problem, or your reply, or he probably
won't need to change the algorithm: if the limit is on a per *object*
basis, then most algorithms I've used wouldn't run into the issue, as
they scale up by having more small objects, and possibly a bigger
"referencing" object which still doesn't end up being very big. For
instance, a 1,000x1,000 array of references would only be 8MB in
itself but could be part of a system taking up many gigabytes if each
referenced object is "reasonably" large without being huge.

It *could* be a problem, of course, if there's a huge value type
array, but otherwise I'd expect the overall memory to be a problem
before the per-object constraint to kick in. I could be very wrong, of
course

Jon

 

[Marc Gravell]

Likewise, if it was implemented as a jagged array (that happens to be
regular) rather than a single rectangular array, the theoretical cap
would presumably increase further - which might be an option for "fat"
value-types. Of course, value-types should be lean to start with,
otherwise there are other issues (copy performance, stack size,
etc)...

Marc

 

[Willy Denoyette [MVP]]

On Jun 18, 9:21 am, "Willy Denoyette [MVP]"



Either I've mistaken the OP's problem, or your reply, or he probably
won't need to change the algorithm: if the limit is on a per *object*
basis, then most algorithms I've used wouldn't run into the issue, as
they scale up by having more small objects, and possibly a bigger
"referencing" object which still doesn't end up being very big. For
instance, a 1,000x1,000 array of references would only be 8MB in
itself but could be part of a system taking up many gigabytes if each
referenced object is "reasonably" large without being huge.

It *could* be a problem, of course, if there's a huge value type
array, but otherwise I'd expect the overall memory to be a problem
before the per-object constraint to kick in. I could be very wrong, of
course

Jon

Sure, You are right, all depends on the size of the largest object in his
object graph, so, I should have said that even Windows 64-bit wouldn't be of
any help "if the largest object in his object hierarchy was larger than
2GB".

Willy.

 

[Jon]

Thank you for all of your responses.

An excerpt of the complete graph class:

class UndirectedCompleteGraph<N, E> : IUndirectedGraph<N, E>
where N : Node
where E : Edge<N>
{
private List<N> m_lNodes = new List<N>();
private List<E> m_lEdges = new List<E>();
}

So even though it's a dynamic list, the underlying implementation is a
reference array.

if m_lNodes.Count is O(N), m_lEdges.Count would be O(N^2) (N*(N-1)/2
to be exact). So in the end are you suggesting I switch the edges
representation to something like SortedList<N,List<E>> so that the
size of the edge list stays within O(N)? This would get past the CLR
limit no? Then the last barrier would be the process limit.

The computer has a Core 2 Quad CPU (with 4 GB of RAM, not 8 as I
mentioned before). We have XP 32-bit installed on the machine. I
tried installing a 64-bit edition of Windows before (I forget which
version it was) but during development on VS C# I've gotten the blue
screen a couple times (on another machine on an AMD64 chip), so I was
hesitant to install a 64-bit version because of stability concerns.
What is the status of the stability of XP 64-bit? And which version
of the 64-bit should I be using (I think I remember reading there are
2 versions)?

Thanks again.

Jon