bugGNU Octave - Bugs: bug #61300, integer range might exceed upper...

 
 

bug #61300: integer range might exceed upper limit

Submitted by:  Arun Giridhar <arungiridhar>
Submitted on:  Wed 06 Oct 2021 03:13:19 PM UTC  
 
Category:  Interpreter Severity:  4 - Important
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  Open
Release:  dev Operating System:  Any

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Wed 06 Oct 2021 07:10:44 PM UTC, comment #8: 

Thanks for this report.  I'll take another look at integer ranges soon, definitely before version 7 is released.

John W. Eaton <jwe>
Project Administrator
Wed 06 Oct 2021 06:16:11 PM UTC, comment #7: 

It can also underflow, which can cause negative indices like here:

>> double(10) : double(-6) : int32(1)
ans =
   10    4   -2

>> double(10) : int32(-6) : int32(1)
ans =
   10    4   -2

>> int32(10) : int32(-6) : int32(1)
ans =
   10    4   -2

Arun Giridhar <arungiridhar>
Wed 06 Oct 2021 05:42:09 PM UTC, comment #6: 

I can confirm on Windows with Octave 7.

Re-titling to the better describe the underlying issue and raising severity.

Markus M├╝tzel <mmuetzel>
Project Member
Wed 06 Oct 2021 05:37:33 PM UTC, comment #5: 

Note: depending on input value n, sometimes the output of primes(n) can exceed n because of the range violation:

>> n = double(1.5e9); p = primes(n); p(end-5:end)
ans =
     1499999909     1499999927     1499999929     1499999933     1499999951     1499999957

>> n = uint64(1.5e9); p = primes(n); p(end-5:end)
ans =
  1499999927  1499999929  1499999933  1499999951  1499999957  1500000001

That last value 1500000001 is more than n.

Arun Giridhar <arungiridhar>
Wed 06 Oct 2021 05:17:35 PM UTC, comment #4: 

Yes, this is a regression, on version 6.0.1 (via octave-online.net) I have

format long;n = uint64(1.5e9), lenp = floor((n+1)/6), a=(8:7:lenp)(end-4:end)
n = 1500000000
lenp = 250000000
a =

   249999968   249999975   249999982   249999989   249999996

Michael Leitner <mleitner>
Wed 06 Oct 2021 05:10:10 PM UTC, comment #3: 

I know now exactly why this slowdown happens. It's because for some reason the integer range is violated, causing the upper bound to exceed lenp, then the array is resized and rewritten with all that overhead. For i = 1, the range inside sievep becomes 8:7:lenp. Look at this experiment for that range:

>> n = double(1.5e9), lenp = floor((n+1)/6), (8:7:lenp)(end-4:end)
n =       1500000000
lenp =        250000000
ans =
               249999968               249999975               249999982               249999989               249999996

>> n = uint64(1.5e9), lenp = floor((n+1)/6), (8:7:lenp)(end-4:end)
n = 1500000000
lenp = 250000000
ans =
  249999975  249999982  249999989  249999996  250000003

That last value 250000003 should not be there. Somehow the mixed range with doubles and integers is causing inappropriate rounding, therefore the whole array is being resized and rewritten. And this can happen for both sievem and sievep, therefore twice the overhead.

One more experiment. Stick one or both these statements inside the sieve calculation, just before sievem and sievep are created:

lenp = double(lenp);
lenm = double(lenm);

You will see that using only one causes 50% of the slowdown, using both causes no slowdown at all, and using neither causes the full slowdown.

So this is an integer range bug, not necessarily a bug in primes.

Copying jwe for his input.

Arun Giridhar <arungiridhar>
Wed 06 Oct 2021 04:07:03 PM UTC, comment #2: 

Wasn't there some recent work by jwe on integer ranges? Because without the patch, if you call primes with an integer class input, this ends up as the upper end of a range that is used for indexing, which perhaps is slow. But why it would be so very slow I do not see.

Michael Leitner <mleitner>
Wed 06 Oct 2021 04:02:49 PM UTC, comment #1: 

It looks like a regression. In 6.3.1 the difference is smaller.

octave:1> n = 1.5e9; tic; p1 = primes(n); toc, tic; p2 = primes(uint64(n)); toc
Elapsed time is 4.6902 seconds.
Elapsed time is 5.02894 seconds.

Dmitri.
--

Dmitri A. Sergatskov <dasergatskov>
Wed 06 Oct 2021 03:13:19 PM UTC, original submission:  

The primes() function is slow for integer types by a factor of 4 to 5 times for large values of n:

>> n = 1.5e9; tic; p1 = primes(n); toc, tic; p2 = primes(uint64(n)); toc
Elapsed time is 5.46344 seconds.
Elapsed time is 25.0824 seconds.

The slowdown is entirely inside the sieve calculation loop, likely because lenm and lenp are integers like n but the loop counter i is double, and the mixed types are somehow causing a slowdown.

The attached patch fixes the slowdown:

diff -r 39a4ab124fd0 scripts/specfun/primes.m
--- a/scripts/specfun/primes.m        Wed Oct 06 10:09:48 2021 +0900
+++ b/scripts/specfun/primes.m        Wed Oct 06 10:54:29 2021 -0400
@@ -57,6 +57,10 @@
   if (ischar (n))
     n = double (n);
   endif
+
+  cls = class (n);     # if n is not double, store its class
+  n = double (n);      # and use only double for internal use
+
   if (! isfinite (n) && n != -Inf)
     error ("primes: N must be finite (not +Inf or NaN)");
   endif
@@ -102,9 +106,7 @@
     p = sort ([2, 3, 6*find(sievem)-1, 6*find(sievep)+1]);
   endif

-  if (! isa (n, "double"))
-    p = cast (p, class (n));
-  endif
+  p = feval (cls, p);            # cast back to the type of the input

endfunction

New performance with the patch is much closer to parity:

>> n = 1.5e9; tic; p1 = primes(n); toc, tic; p2 = primes(uint64(n)); toc
Elapsed time is 5.52101 seconds.
Elapsed time is 5.84542 seconds.

Thanks to mleitner for the discussions in bug #61129 in locating this performance bug in primes().

Arun Giridhar <arungiridhar>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #52056:  primes_patch1.patch added by arungiridhar (717B - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by arungiridhar (Integer range bug, paging jwe)
  • -email is unavailable- added by mleitner (Posted a comment)
  • -email is unavailable- added by dasergatskov (Posted a comment)
  • -email is unavailable- added by nrjank (Updated the item)
  • -email is unavailable- added by arungiridhar (Submitted the item)
  • -email is unavailable- added by arungiridhar
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

     

     

    Follow 10 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-10-06 mmuetzel CategoryOctave Function => Interpreter
        Severity3 - Normal => 4 - Important
        Item GroupPerformance => Incorrect Result
        StatusPatch Submitted => Confirmed
        Operating SystemGNU/Linux => Any
        Summaryprimes() is 4 times slower for integer types than for double, patch attached => integer range might exceed upper limit
    2021-10-06 arungiridhar Carbon-Copy- => Added jwe
    2021-10-06 nrjank StatusNone => Patch Submitted
    2021-10-06 arungiridhar Attached File- => Added primes_patch1.patch, #52056
        Carbon-Copy- => Added mleitner

    Back to the top


    Powered by Savane 3.7