[Octave-bug-tracker] [bug #61300] primes() is 4 times slower for integer types than for double, patch attached

[Arun Giridhar]

URL:
  <https://savannah.gnu.org/bugs/?61300>

                 Summary: primes() is 4 times slower for integer types than
for double, patch attached
                 Project: GNU Octave
            Submitted by: arungiridhar
            Submitted on: Wed 06 Oct 2021 11:13:19 AM EDT
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: dev
         Discussion Lock: Any
        Operating System: GNU/Linux

    _______________________________________________________

Details:

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().



    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Wed 06 Oct 2021 11:13:19 AM EDT  Name: primes_patch1.patch  Size: 717B  
By: arungiridhar

<http://savannah.gnu.org/bugs/download.php?file_id=52056>

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?61300>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/