[racket] translate from Racket to Common Lisp

On Sun, Nov 4, 2012 at 8:48 PM, Robby Findler
<robby at 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 <matthias at 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 <mflatt at 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
samth at ccs.neu.edu