[racket] translate from Racket to Common Lisp

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4373 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20121105/849de94a/attachment-0001.p7s>