... which of course just means that the 'unsafe' implementation exposes a weakness in the programmer's reasoning while the Typed Racket implementation appears to achieve the same level of performance as UNSAFE SBCL *with a proof* that it is safe.
Thanks this is a nice confirmation of our work -- Matthias On Nov 4, 2012, at 9:00 PM, Sam Tobin-Hochstadt wrote: > On Sun, Nov 4, 2012 at 8:48 PM, Robby Findler > <ro...@eecs.northwestern.edu> wrote: >> I think it is difficult to see that those integers do not escape >> fixnum range. :) > > In particular, we can learn from the Online Encyclopedia of Integer > Sequences that they escape Racket's fixnum range on a 32 bit machine > like the one I'm typing on at 77671 [1]. Further, Matthew's unsafe > implementation (and the SBCL fixnum implementation) will give the > wrong answer starting at 8528817511 if not earlier. > > [1] http://oeis.org/A006884 and http://oeis.org/A006885 > >> >> On Sun, Nov 4, 2012 at 7:42 PM, Matthias Felleisen <matth...@ccs.neu.edu> >> wrote: >>> >>> Hmph. I would expect TR to perform as fast as 'unsafe'. >>> >>> >>> On Nov 4, 2012, at 7:40 PM, Matthew Flatt wrote: >>> >>>> 2668 msecs when I declare `cycle-length' as `(Integer -> Integer)' and >>>> change `(even? n)' to `else', or 2809 msecs if I add `[else 0]' instead >>>> of changing `(even? n)'. >>>> >>>> At Sun, 4 Nov 2012 18:30:21 -0600, Robby Findler wrote: >>>>> And just to complete the list, how does the TR version fare? >>>>> >>>>> Robby >>>>> >>>>> On Sun, Nov 4, 2012 at 6:26 PM, Matthew Flatt <mfl...@cs.utah.edu> wrote: >>>>>> Thanks! >>>>>> >>>>>> Sometimes, a x3 difference means that we're missing a straightforward >>>>>> opportunity in performance, and that was the case here. The Racket >>>>>> program spent most of its time in generic `/' by pessimistically >>>>>> expecting a non-integer result. >>>>>> >>>>>> I've adjusted the JIT to optimistically compute and check a fixnum >>>>>> result for a division of fixnums, and then the example runs about four >>>>>> times as fast on my machine: >>>>>> >>>>>> Old Racket: 12589 msec >>>>>> New Racket: 3850 msec >>>>>> Racket with `quotient': 3851 msec [old or new is the same] >>>>>> SBCL: 5553 msec >>>>>> SBCL, unsafe fixnum: 2692 msec >>>>>> New Racket, in module: 2823 msec >>>>>> Racket, unsafe fixnum: 2405 msec [uses `fxquotient'] >>>>>> >>>>>> At Sun, 4 Nov 2012 15:54:51 +0000 (UTC), daniel rupistraliz wrote: >>>>>>> >>>>>>> >>>>>>> racket: >>>>>>> Welcome to Racket v5.2.1. >>>>>>>> (define (cycle-length n) >>>>>>> (cond >>>>>>> [(= n 1) >>>>>>> 1] >>>>>>> [(odd? n) >>>>>>> (add1 (cycle-length (add1 (* 3 n))))] >>>>>>> [(even? n) >>>>>>> (add1 (cycle-length (/ n 2)))])) >>>>>>> >>>>>>> (time (for ([i (in-range 1 1000000)]) >>>>>>> (cycle-length i))) >>>>>>>> >>>>>>> cpu time: 15016 real time: 15018 gc time: 0 >>>>>>> >>>>>>> sbcl: >>>>>>> >>>>>>> (defun cycle-length(n) >>>>>>> (cond ((= n 1) 1) >>>>>>> ((oddp n) (1+ (cycle-length (1+ (* 3 n))))) >>>>>>> ((evenp n) (1+ (cycle-length (/ n 2)))))) >>>>>>> >>>>>>> >>>>>>> * (time (loop for i from 1 to 1000000 do (cycle-length i))) >>>>>>> >>>>>>> Evaluation took: >>>>>>> 6.192 seconds of real time >>>>>>> 6.192387 seconds of total run time (6.192387 user, 0.000000 system) >>>>>>> 100.00% CPU >>>>>>> 14,496,643,427 processor cycles >>>>>>> 0 bytes consed >>>>>>> >>>>>>> >>>>>>> With optimizations: >>>>>>> >>>>>>> (defun cycle-length(n) >>>>>>> (declare (fixnum n) >>>>>>> (ftype (function (fixnum) fixnum) cycle-length) >>>>>>> (optimize (speed 3) (safety 0) (compilation-speed 0))) >>>>>>> (cond ((= n 1) 1) >>>>>>> ((oddp n) (the fixnum (1+ (cycle-length >>>>>>> (the fixnum (1+ (the fixnum (* 3 >>>>>>> n)))))))) >>>>>>> ((evenp n) (cycle-length (the fixnum (/ n 2)))))) >>>>>>> >>>>>>> CL-USER> (time (loop for i from 1 to (expt 10 6) do (cycle-length i))) >>>>>>> Evaluation took: >>>>>>> 3.515 seconds of real time >>>>>>> 3.524220 seconds of total run time (3.524220 user, 0.000000 system) >>>>>>> 100.26% CPU >>>>>>> 8,228,949,701 processor cycles >>>>>>> 33,008 bytes consed >>>>>>> >>>>>>> So racket = 15 seconds >>>>>>> sbcl = 6 seconds >>>>>>> sbcl optimized = 3.5 seconds. >>>>>>> >>>>>>> >>>>>>> ____________________ >>>>>>> Racket Users list: >>>>>>> http://lists.racket-lang.org/users >>>>>> ____________________ >>>>>> Racket Users list: >>>>>> http://lists.racket-lang.org/users >>>> ____________________ >>>> Racket Users list: >>>> http://lists.racket-lang.org/users >>> >> ____________________ >> Racket Users list: >> http://lists.racket-lang.org/users > > > > -- > sam th > sa...@ccs.neu.edu
smime.p7s
Description: S/MIME cryptographic signature
____________________ Racket Users list: http://lists.racket-lang.org/users