New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Overflow on reshape #207

Closed
isweaver opened this Issue Nov 12, 2018 · 10 comments

Comments

Projects
None yet
3 participants
@isweaver
Copy link

isweaver commented Nov 12, 2018

Hey. Sorry if this is trivial: the array shape appears to be stored as a tuple of int values, not long, and so the reshaping function (and presumably others) encounters problems for even relatively small arrays:

import sparse
sparse.COO([], shape = (10,1000000,1000000)).sum(0)

Yields an error, originating from

# TODO: this self.size enforces a 2**64 limit to array size
linear_loc = self.linear_loc()

coords = np.empty((len(shape), self.nnz), dtype=np.intp)
strides = 1
for i, d in enumerate(shape[::-1]):
	coords[-(i + 1), :] = (linear_loc // strides) % d
	strides *= d

where strides overflows. You can simply cast this as strides = 1L instead but it's hard to imagine there isn't other errors introduced by this. Other reshapes may only raise a warning, as the overflow gives a positive. A comment in the offending function reads # TODO: this self.size enforces a 2**64 limit to array size, but the size is currently limited to 2**32. In the above case

2**32 < 1,000,000**2 < 2**64

I should add this happens on Windows 10 with Python versions 2.7 and 3.7.

@hameerabbasi

This comment has been minimized.

Copy link
Collaborator

hameerabbasi commented Nov 12, 2018

Hello! Personally, I only use Python 3... Which may be the issue here, are you using Python 2 on a 32-bit operating system?

@isweaver

This comment has been minimized.

Copy link

isweaver commented Nov 12, 2018

64-bit Python 2.7 and 3.7 are giving identical messages. I've been reading that Python 3 did away with int and long as distinct types, so I'm actually confused what is happened here.

Adding a print statement shows that in the above case, the "shape" argument sent to reshape is (-727379968, 1). So it is actually butchered elsewhere.

Can you quickly verify the above snipped works for you?

@hameerabbasi

This comment has been minimized.

Copy link
Collaborator

hameerabbasi commented Nov 12, 2018

64-bit Python 2.7 and 3.7 are giving identical messages. I've been reading that Python 3 did away with int and long as distinct types, so I'm actually confused what is happened here.

Python 3 uses what are called big-ints. It grows the size of the integer, so it has no limit practically, so realistically this issue shouldn't happen at all on Python 3.

Adding a print statement shows that in the above case, the "shape" argument sent to reshape is (-727379968, 1). So it is actually butchered elsewhere.

So you're overflowing in Python itself. That's a hint, could you add this line to sparse/sparse_array.py?

from .compatibility import int

Can you quickly verify the above snipped works for you?

I tried it on macOS 10.14.1 and it works just fine. I have installations of Linux and Windows laying around as well, which one are you on? I can test there.

Are you completely sure you're using the 64-bit version, not invoking the 32-bit version by mistake?

@isweaver

This comment has been minimized.

Copy link

isweaver commented Nov 12, 2018

The top line reads:

Python 3.7.1 (v3.7.1:260ec2c36a, Oct 20 2018, 14:57:15) [MSC v.1915 64 bit (AMD64)] on win32

win32 gave me pause for a moment, but I understand this is simply a moniker for windows. The OS itself is certainly 64-bit Windows.

Adding this line to sparse/sparse_array.py did not affect the issue.

I should add that I do have Python 2.7 installed alongside 3.7 - I added 3.7 just now to verify the problem still exists but it's possible that there's something messy going on with my installation.

EDIT: To make absolutely sure!

import platform, struct
platform.architecture()
struct.calcsize('P') * 8

yields

('64bit', 'WindowsPE')
64
@hameerabbasi

This comment has been minimized.

Copy link
Collaborator

hameerabbasi commented Nov 12, 2018

I was able to reproduce the error and fix it on Windows. If it's not too much trouble, could you test against #208?

@isweaver

This comment has been minimized.

Copy link

isweaver commented Nov 12, 2018

Certainly, travelling for the next few hours, but will check when I can.

@isweaver

This comment has been minimized.

Copy link

isweaver commented Nov 13, 2018

Brilliant. This fix works both for the example above, and the project I'm working on. Thank you so much.

If you have a moment to describe, what do those lines you tweaked do? You load the Python 3 version of int from compatibility and just be sure to cast a few bits with it? Any idea why this was still an issue for Python 3 on Windows?

@hameerabbasi

This comment has been minimized.

Copy link
Collaborator

hameerabbasi commented Nov 13, 2018

You can ignore almost every line except the one that adds dtype=np.intp to np.prod. Essentially, for some reason, on Windows, it was converting the input Python integer arrays to np.int32 instead of np.int64. I forced it to use np.intp which is np.int64 on 64-bit machines.

@hameerabbasi

This comment has been minimized.

Copy link
Collaborator

hameerabbasi commented Nov 13, 2018

A word of caution. You shouldn't be on Python 2.7 for too long, a lot of projects will drop support for it soon, including this one.

@ewmoore

This comment has been minimized.

Copy link

ewmoore commented Nov 13, 2018

Windows is different because the default integer dtype is always 32 bit, even for 64 bit python. This is different from linux/mac/anything else.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment