IndexError: index out of range

[Kyle Hubert]

Hello,

I'm working on a problem with 67529 variables. When taking the modeling constraints and building the matrix form, CVXOPT errors with an IndexError. This is inside the __getitem__ method in the _lin class. In particular, this code:

                # create a sparse matrix with 1.0 element in 

                # position (k,l[k]) for k in range(len(l)) 

                f._coeff[v] = spmatrix([], [], [], (len(l),len(v)), 'd')

                f._coeff[v][[l[k]*len(l)+k for k in range(len(l))]] \

                    = c[0]

I believe this is either a 32bit error or an int versus unsigned int error in the sparse matrix C file. I noticed when I had more variables (~85k) it failed at 4.2GB of memory consumed. However, by dialing back to 67529 variables, I still get an error, but only consume 3.6GB of memory. 67529 x 67529 is greater than a 32bit integer, and that's what it looks like the sparse matrix's requested size is.

Has CVXOPT been proven to work on larger than 32bit problems? For most problems, it screams when compiled with MKL, so I really would like to continue using the package.

Cheers,

-Kyle

[Martin]

Hi Kyle,

CVXOPT should work with 64bit, but it is entirely possible that you have found a bug. Can you provide a bit more context or perhaps send me a small example?

Kind regards,

Martin

[Kyle Hubert]

Hello,

Sorry I dropped this message! My local copy of CVXOPT has this fix:

diff --git a/src/C/dense.c b/src/C/dense.c

index 3de2855..c6655e6 100644

--- a/src/C/dense.c

+++ b/src/C/dense.c

@@ -40,7 +40,7 @@ extern int (*convert_num[])(void *, void *, int, int_t) ;

 extern PyObject * (*num2PyObject[])(void *, int) ;

 int get_id(void *, int ) ;

 

-extern const int  E_SIZE[];

+extern const unsigned int  E_SIZE[];

 extern const char TC_CHAR[][2];

 extern number One[3], MinusOne[3], Zero[3];

 static char FMT_STR[][4] = {"l","d","Zd","i"};

This was enough for me to make forward progress. It looks like the following conditional in convert_mtx caused the memcpy to copy a negative buffer size, which was casted to a size_t, aka uint64_t, which sign extended the buffer size into a huge value.

   if (MAT_ID(src) == id) {

     memcpy(dest, src->buffer, E_SIZE[src->id]*MAT_LGT(src) );

     return 0;

   }

However, I didn't see if I could move that unsigned int to a size_t.. I just switched it to unsigned and it worked for me.

Cheers,

-Kyle

[Martin]

I'm not sure that I understand why it helps to change the type. The array E_SIZE is defined as follows (in base.c):

const int  E_SIZE[] = { sizeof(int_t), sizeof(double), sizeof(double complex) };

Moreover, src->id is equal to INT (defined as 0), DOUBLE (defined as 1), or COMPLEX (defined as 2), so E_SIZE[src->id] should be the size of one element.

[Kyle Hubert]

Hello,

See attached a.c and b.c. Please compile them. It should show the error succinctly in code, as my explanation wasn't clear.

Here is the output on my machine:

$ ./a.out 

Testing: x = 16384, y = 16384

Signed: 18446744071562067968

Unsigned: 2147483648

Cheers,

-Kyle

[Martin]

OK, I see the problem. It is because foo[1]*(x*y) overflows. You can get around the problem if you write the size_t cast as follows:

 printf("Signed: %lu\n", ((size_t)foo[1]*(x*y)));
 printf("Unsigned: %lu\n", ((size_t)bar[1]*(x*y)));

Now both results are the same. Note that changing declaration to unsigned int is not really a fix. If you change your example such that x = 1 << 15 and y = 1 << 15, you will get the correct result with the above cast, but the result still overflows if you use (size_t)(bar[1]*(x*y))).

[Martin]

Can I ask you to try if an explicit cast fixes the issue? 

memcpy(dest, src->buffer, (size_t)E_SIZE[src->id]*MAT_LGT(src) );

Out of curiosity, what operating system and which version of Python are you using?

[Kyle Hubert]

I am using Debian/Linux 3.16-0.bpo.2-amd64. Python 2.7.10 |Anaconda 2.3.0 (64-bit)| (default, Sep 15 2015, 14:50:01).

I'll try running the explicit cast tonight or tomorrow.

Thanks,

-Kyle

--
You received this message because you are subscribed to a topic in the Google Groups "CVXOPT" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/cvxopt/d8NJ9-yS5ZI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to cvxopt+un...@googlegroups.com.
To post to this group, send email to cvx...@googlegroups.com.
Visit this group at http://groups.google.com/group/cvxopt.
For more options, visit https://groups.google.com/d/optout.