Opened 6 years ago

Closed 6 years ago

#21746 closed defect (fixed)

overflow for vector mod2 dense

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-7.5
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Vincent Delecroix Reviewers: Jeroen Demeyer, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 428c88e (Commits, GitHub, GitLab) Commit: 428c88e3e6869f508308c7395037977b3cd9e115
Dependencies: Stopgaps:

Status badges

Description

sage: VS = VectorSpace(GF(2),1)
sage: VS([2**64])
Traceback (most recent call last):
...
OverflowError: Python int too large to convert to C long

Change History (17)

comment:1 Changed 6 years ago by vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/21746
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by git

  • Commit set to 9a5227206b6a75f36cca0a82299666e158061c18

Branch pushed to git repo; I updated commit sha1. New commits:

9a5227221746: fix overflow for dense vector mod 2

comment:3 Changed 6 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to positive_review

comment:4 Changed 6 years ago by git

  • Commit changed from 9a5227206b6a75f36cca0a82299666e158061c18 to d1c54b1679d9f60b6612a98d6b1386d5ddb1b347
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

d1c54b121746: fix doctest in coding/

comment:5 Changed 6 years ago by vdelecroix

Fixed doctest failure in coding/. Needs review again.

comment:6 Changed 6 years ago by tscrim

This branch does result in ~10% slowdown:

sage: V = VectorSpace(GF(2), 2^10)
sage: %timeit V([1]*(2^10))
The slowest run took 5.95 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 49.8 µs per loop

Before:

sage: V = VectorSpace(GF(2), 2^10)
sage: %timeit V([1]*(2^10))
The slowest run took 5.69 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 3: 45.8 µs per loop

However, changing the for loop over enumerate back to for i from 0 <= i < self._degree: and setting xi = x[i] doesn't have a noticeable impact. So I think we have to deal with this.

I do have one nitpick: change the ZeroDivisionError to start with a lowercase. Once that is done, you can put this back to a positive review.

comment:7 Changed 6 years ago by git

  • Commit changed from d1c54b1679d9f60b6612a98d6b1386d5ddb1b347 to 428c2cd96d640a939424865a85660cf0813b3e1d

Branch pushed to git repo; I updated commit sha1. New commits:

428c2cd21746: remove enumerate + cleaning

comment:8 Changed 6 years ago by git

  • Commit changed from 428c2cd96d640a939424865a85660cf0813b3e1d to 65894e56a7405309381db71dbe583d7b8f943388

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

65894e521746: remove enumerate + cleaning

comment:9 Changed 6 years ago by vdelecroix

Thanks for the timings!

I removed the enumerate and also did some cleaning in the case x = 0. This code is completely useless

for i from 0 <= i < self._degree:
    mzd_set_ui(self._entries, 0)

comment:10 Changed 6 years ago by jdemeyer

The enumerate is optimized by Cython, so no need to remove it!

comment:11 Changed 6 years ago by tscrim

  • Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Travis Scrimshaw
  • Status changed from needs_review to positive_review

I realize the phrasing in my comment was somewhat vague too; I meant we have to just live with the slowdown. I did come to the conclusion that enumerate was likely optimized by Cython, but it is good to know. Anyways, removing it is a net-zero change, so I'm setting this back to a positive review.

comment:12 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

segfault galore... see patchbot

comment:13 Changed 6 years ago by vdelecroix

Indeed. I am able to reproduce it with the shorter

sage: (GF(2)**0).zero_vector()

comment:14 Changed 6 years ago by git

  • Commit changed from 65894e56a7405309381db71dbe583d7b8f943388 to 428c88e3e6869f508308c7395037977b3cd9e115

Branch pushed to git repo; I updated commit sha1. New commits:

428c88e21746: fix segementation fault for 0-dim spaces

comment:15 Changed 6 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:16 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:17 Changed 6 years ago by vbraun

  • Branch changed from u/vdelecroix/21746 to 428c88e3e6869f508308c7395037977b3cd9e115
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.