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 ____________________ Racket Users list: http://lists.racket-lang.org/users