out of memory or dimension too large for Octave's index type

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

out of memory or dimension too large for Octave's index type

dkeck
I am using glpk to solve an optimization problem of the form 'Ax<=b'.
A submatrix of 'A' with size 5280 x 4608 fails to be built with "out of memory or dimension too large for Octave's index type"-error. These are 24,330,240 elements which are far below the 2e9 element border (http://octave.1599824.n4.nabble.com/error-memory-exhausted-or-requested-size-too-large-for-range-of-Octave-s-index-type-td3357172.html).

The complete size of A will be 7398 x 4608 in the current scenario. And should also work fine:
http://www.gnu.org/software/octave/doc/interpreter/Compiling-Octave-with-64_002dbit-Indexing.html

But I could not test it yet.

Does anybody have an idea what could cause the "out of memory"-error here?

Regards,
Daniel
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

nrjank
On Tue, Jun 17, 2014 at 9:43 AM, dkeck <[hidden email]> wrote:

> I am using glpk to solve an optimization problem of the form 'Ax<=b'.
> A submatrix of 'A' with size 5280 x 4608 fails to be built with "out of
> memory or dimension too large for Octave's index type"-error. These are
> 24,330,240 elements which are far below the 2e9 element border
> (http://octave.1599824.n4.nabble.com/error-memory-exhausted-or-requested-size-too-large-for-range-of-Octave-s-index-type-td3357172.html).
>
> The complete size of A will be 7398 x 4608 in the current scenario. And
> should also work fine:
> http://www.gnu.org/software/octave/doc/interpreter/Compiling-Octave-with-64_002dbit-Indexing.html
>
> But I could not test it yet.
>
> Does anybody have an idea what could cause the "out of memory"-error here?
>
> Regards,
> Daniel

Physical limits: what version of Octave? 32 or 64bit? what are your
machine's memory specs?

Operation limits: what else is in memory when you're building A? how
are you building A? have you preallocated for the final array size, or
are you forcing duplicate copies? Safe to assume that A is an double
precision array?

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

dkeck
Octave 3.8.0 32-bit.
4GB RAM of which 3,25 are visible to the OS (WinXP 32bit) of which are 60% in use before building A. So 1.3 GB of free space for A.

There are only temporary variables in the workspace visible while building A.
A_final=[A_1;A_2;...] where A_INT are preallocated with zeros but A_final is not preallocated but simply build as shown here.
What does "are you forcing duplicate copies" mean in this respect?

Yes, 'A' should be a double precision array since I did not modify any A_INT while preallocating.
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

nrjank
On Tue, Jun 17, 2014 at 10:22 AM, dkeck <[hidden email]> wrote:

> Octave 3.8.0 32-bit.
> 4GB RAM of which 3,25 are visible to the OS (WinXP 32bit) of which are 60%
> in use before building A. So 1.3 GB of free space for A.
>
> There are only temporary variables in the workspace visible while building
> A.
> A_final=[A_1;A_2;...] where A_INT are preallocated with zeros but A_final is
> not preallocated but simply build as shown here.
> What does "are you forcing duplicate copies" mean in this respect?
>
> Yes, 'A' should be a double precision array since I did not modify any A_INT
> while preallocating.

maybe not the correct terminology, but by duplicate copies I mean that
certain methods of building an array can require Octave to hold two
copies of the array at the same time. This I believe is usually the
case when you force a resizing of an array. Someone else can chime in
if I butcher this but something like:
----------
a = [1 2 3];
A=[];
for i= 1:5
  A = [A;a]
endfor
-----------

each time you append onto A, I believe Octave has to hold both the old
and new A in memory to complete the operation. Hence, for large arrays
with small additions, you effectively double the amount of memory
required for the operation. Not 100% sure that's your problem here,
but it comes up often when people are manipulating large arrays.

Checking: if you're using double precision, each element is 8 bytes,
and you have 5280 x 4608 = 24,330,240 elements, that's only
194,641,920 bytes. So, after all of that, unless you're doing
something to keep 7 of those in memory simultaneously, or have
something else sitting there occupying space, that alone shouldn't be
the problem.

sharing the relevant code, especially if you can simplify to the
error, may allow someone to spot the problem.

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

dkeck
Thanks for explaining the insights!
At the moment I can't release the code or parts of it, since its part of a scientific work which has yet no been published. For the moment I will rewrite the necessary parts to be able to use Matlab. And where still applicable I will continues with Octave.
If I find the time I will look at what Ocatve is exactly doing in the background. Maybe you're right with your assumption that I created some kind of nightmare-memory-leak.
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

nrjank
On Tue, Jun 17, 2014 at 12:13 PM, dkeck <[hidden email]> wrote:
> Thanks for explaining the insights!
> At the moment I can't release the code or parts of it, since its part of a
> scientific work which has yet no been published. For the moment I will
> rewrite the necessary parts to be able to use Matlab. And where still
> applicable I will continues with Octave.
> If I find the time I will look at what Ocatve is exactly doing in the
> background. Maybe you're right with your assumption that I created some kind
> of nightmare-memory-leak.

i understand the sensitivity. but perhaps a simplified version of the
relevant part of the algorithm? something simplified that still
generates the problem but doesn't reveal the core of what you're
publishing?

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

dkeck
I will post a minimum working example here when I find the time to write it or the cause of the problem which I might find during this process. But this will not happen during the next three weeks.
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

dkeck
I simply assumed that there might be a copy of 'A' somewhere in the background. A naive approach is:
>> A1=ones(5280,4608);
>> A2=ones(5280,4608);
error: out of memory or dimension too large for Octave's index type

Which already brings up the error. Yet I can't say what causes this.
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

Dmitri A. Sergatskov



On Thu, Jun 26, 2014 at 7:00 PM, dkeck <[hidden email]> wrote:
I simply assumed that there might be a copy of 'A' somewhere in the
background. A naive approach is:
>> A1=ones(5280,4608);
>> A2=ones(5280,4608);
error: out of memory or dimension too large for Octave's index type

Which already brings up the error. Yet I can't say what causes this.


​Memory fragmentation.​
 
​Dmitri.
--


_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

tmacchant
----- Original Message -----
From: Dmitri A. Sergatskov 
To: dkeck 
Cc: Octave users list
Date: 2014/6/27, Fri 09:52
Subject: Re: out of memory or dimension too large for Octave's index type




On Thu, Jun 26, 2014 at 7:00 PM, dkeck <[hidden email]> wrote:
I simply assumed that there might be a copy of 'A' somewhere in the
background. A naive approach is:
>> A1=ones(5280,4608);
>> A2=ones(5280,4608);
error: out of memory or dimension too large for Octave's index type

Which already brings up the error. Yet I can't say what causes this.


​Memory fragmentation.​
 
​Dmitri.
**************************************************************
Windows 7 64bit 4GB RAM, octave-3.8.1-4.

octave:1>  A1=ones(5280,4608);
octave:2>  A2=ones(5280,4608);
octave:3>  A3=ones(5280,4608);
octave:4>  A4=ones(5280,4608);
octave:5>  A5=ones(5280,4608);
octave:6>  A6=ones(5280,4608);
octave:7>  A7=ones(5280,4608);
octave:8>  A8=ones(5280,4608);
error: out of memory or dimension too large for Octave's index type

Perhaps the phenomena depends also on OS.

Tatsuro

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

dkeck
tmacchant wrote
​Memory fragmentation.​
No matter of scenario (how many processes started, when restarted Octave, when restarted OS) I am not able to create a matrix with more than 39,160,800 elements (e.g. A1=ones(6300,6217); will not work but A2=ones(6300,6216); will work).
So it seems that it is more than memory fragmentation because such a high degree of fragmentation in all scenarios is questionable.
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

marco atzeri-2
In reply to this post by dkeck
On 17/06/2014 16:22, dkeck wrote:
> Octave 3.8.0 32-bit.
> 4GB RAM of which 3,25 are visible to the OS (WinXP 32bit) of which are 60%
> in use before building A. So 1.3 GB of free space for A.

  60% in use by whom ?
  A single process can not use more than 2 Gb on WinXP 32bit

Regards
Marco



_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

dkeck
marco atzeri-2 wrote
60% in use by whom ?
60% are in use by all other running processes. The process count at 60% is 65. The minimum process count I've tested is 19 with 10% in use.
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

Philip Nienhuis
In reply to this post by dkeck
dkeck wrote
tmacchant wrote
​Memory fragmentation.​
No matter of scenario (how many processes started, when restarted Octave, when restarted OS) I am not able to create a matrix with more than 39,160,800 elements (e.g. A1=ones(6300,6217); will not work but A2=ones(6300,6216); will work).
So it seems that it is more than memory fragmentation because such a high degree of fragmentation in all scenarios is questionable.
You simply expect too much.
Memory fragmentation happens already when starting up your computer. Just have a look at the startup log in your C:\WINDOWS\Temp folder and glance through the loooong list of processes that were once or are still active (= in memory).

Only when you go to 64-bit systems (Linux, Mac, Windows alike) your programs get more room. But memory fragmentation does happen there as well. You'll only notice later.

On my WinXP SP3 box (32b) w. 4 GB RAM installed, and fairly regular SW (virus scanner, firewall, a Logitech mouse driver, but with all IMO unneeded services disabled), Matlab prerelease 2014b gives (when started as first user program after reboot):


>> [a, b] = memory
a =
    MaxPossibleArrayBytes: 291999744
    MemAvailableAllArrays: 1.3488e+09
            MemUsedMATLAB: 471793664
b =
    VirtualAddressSpace: [1x1 struct]
           SystemMemory: [1x1 struct]
         PhysicalMemory: [1x1 struct]

>> A2=ones(6300,6216)
Out of memory. Type HELP MEMORY for your options.
 
>>


This says that the largest contiguous chunk of free memory is less than 300 MB.

I think this is a fair indication that Octave's isn't to blame for OOM errors occurring for otherwise seemingly "reasonable" array sizes. Matlab doesn't perform any better on the same 32-bit platform.

You'd better say that Windows XP's memory management is particularly bad.
On my Mageia Linux 32b box, Octave-3.8.0 can create class double arrays of ~12500 X 12500, or ~4 times bigger than what you get on WinXP.


Philip
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

Dmitri A. Sergatskov
In reply to this post by tmacchant



On Fri, Jun 27, 2014 at 4:38 AM, Tatsuro MATSUOKA <[hidden email]> wrote:
----- Original Message -----
From: Dmitri A. Sergatskov 
To: dkeck 
Cc: Octave users list
Date: 2014/6/27, Fri 09:52
Subject: Re: out of memory or dimension too large for Octave's index type




On Thu, Jun 26, 2014 at 7:00 PM, dkeck <[hidden email]> wrote:
I simply assumed that there might be a copy of 'A' somewhere in the
background. A naive approach is:
>> A1=ones(5280,4608);
>> A2=ones(5280,4608);
error: out of memory or dimension too large for Octave's index type

Which already brings up the error. Yet I can't say what causes this.


​Memory fragmentation.​
 
​Dmitri.
**************************************************************
Windows 7 64bit 4GB RAM, octave-3.8.1-4.

octave:1>  A1=ones(5280,4608);
octave:2>  A2=ones(5280,4608);
octave:3>  A3=ones(5280,4608);
octave:4>  A4=ones(5280,4608);
octave:5>  A5=ones(5280,4608);
octave:6>  A6=ones(5280,4608);
octave:7>  A7=ones(5280,4608);
octave:8>  A8=ones(5280,4608);
error: out of memory or dimension too large for Octave's index type

Perhaps the phenomena depends also on OS.

Tatsuro

​Dmitri.
--


_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

dkeck
In reply to this post by Philip Nienhuis
Philip Nienhuis wrote
You simply expect too much. [...]
Thanks a lot for sharing your results! It gives a very good overview of what can be done together with tmacchants post.
So there are two options:
- get a 64bit OS and more RAM
- use sparse matrices (as suggested here http://octave.1599824.n4.nabble.com/help-on-Octave-td4630959.html)

I will go with the latter...
Test if LINPROG and GLPK support sparse input:
glpk(sparse([0 0]'),[-1 1; 1 1],sparse([0 5]'),[],[],"SS")
linprog(sparse([0 0]'),[],[],[-1 1; 1 1],sparse([0 5]'))
=> works (non trivial: test if result is correct)

Test with multiple matrices (with size near to out of memory):
m=6256; %my limit for a square matrix of size (m x m)
A1=sparse(diag(ones(1,m)));
A2=sparse(diag(ones(1,m)));

A_final=[A1; A2; …]; %indeed my real A_final will have more non-zero elements but I hope it works
X=sparse(linprog(sparse(zeros(size(A,2),1)),[],[],A,sparse(zeros(size(A,1),1))));
=> works (trivial: test if build of A_final works)
Reply | Threaded
Open this post in threaded view
|

Re: out of memory or dimension too large for Octave's index type

calaba@gmail.com
To address the 'error: out of memory or dimension too large for Octave's index type' in Ubuntu Linux check this BLOG (http://calaba.tumblr.com/post/107087607479/octave-64) or this GitHub (https://github.com/calaba/octave-3.8.2-enable-64-ubuntu-14.04)