Re: [racket-users] `divides?` from math/number-theory slow?
The above is of course supposed to say that `divides?` needed a few seconds more than the modulo example even in Typed Racket. Both were of course typed when running with TR. On Mon, Aug 24, 2015 at 3:38 PM, Rickard Andersson rickard.m.anders...@gmail.com wrote: Yes, that indeed seems to be the problem. However, even after managing to wrap the types properly, using `divides?` still ended up being a bit slower. Not dramatically slower, but still noticably and unexpectedly. As I'm not at all comfortable with Typed Racket I would appreciate if someone could show how one would annotate the example minimally to give the optimizer enough information to surpass Racket. As of this moment I haven't really managed to see any improvement from using Typed Racket. It cut down the time `divides?` needed to a few seconds more than Racket. Otherwise, it had no effect (on the other example either). As a point of curiosity; I had to work around the fact that apparently there were not enough type annotations by wrapping the `for`s in functions and typing them accordingly. Is there a better way to do this? I'm currently trying to compare some performance between OCaml, C and Racket and I'm currently using the aforementioned example. Here are some timings: | time racket divides.rkt; time ./divides_c; time ./divides_ocaml 416658333 racket divides.rkt 7.32s user 0.02s system 100% cpu 7.336 total 416658333 ./divides_c 0.49s user 0.00s system 99% cpu 0.488 total 416658333 ./divides_ocaml 0.75s user 0.00s system 99% cpu The idea is to see how fast one can make the following: #lang racket/base (define (divisible-by? x d) (= (modulo x d) 0)) (module+ main (for/sum ([x (in-range 3 5)]) (if (x . divisible-by? . 3) x 0)) ) On Mon, 24 Aug 2015, Pierpaolo Bernardi wrote: On Mon, Aug 24, 2015 at 1:25 PM, Jens Axel Søgaard jensa...@soegaard.net wrote: It looks very odd to me. Maybe this is due to calling TR functions from plain Racket? -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] `divides?` from math/number-theory slow?
It looks to me like the slowdown isn't entirely explained by contract checking, or perhaps TR isn't generating the contracts I would have guessed. With the program below, I see this output cpu time: 1228 real time: 1228 gc time: 133 cpu time: 658 real time: 658 gc time: 18 cpu time: 80 real time: 81 gc time: 0 but would have expected the first two lines to be nearly the same. Robby #lang racket (require (only-in math/number-theory divides?)) (define (divisible-by? x d) (= (modulo x d) 0)) (module d racket/base (require racket/contract/base) (define (divisible-by? x d) (= (modulo x d) 0)) (provide (contract-out [divisible-by? (- exact-integer? exact-integer? boolean?)]))) (require (prefix-in c: (submod . d))) (module+ main (time (for ([x (in-range 3 500)]) (if (3 . divides? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (3 . c:divisible-by? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (x . divisible-by? . 3) x 0 -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] `divides?` from math/number-theory slow?
The difference in performance between the two functions when there are no contracts (ie, when there are no types anywhere, or when everything is typed) seems to be just from the extra `zero?` check in `divides?`. Adding that to your program produced something that runs in about the same time as your `divisible-by?` (I ran them all in both untyped and typed Racket). Sam On Mon, Aug 24, 2015 at 8:40 AM Rickard Andersson rickard.m.anders...@gmail.com wrote: Yes, that indeed seems to be the problem. However, even after managing to wrap the types properly, using `divides?` still ended up being a bit slower. Not dramatically slower, but still noticably and unexpectedly. As I'm not at all comfortable with Typed Racket I would appreciate if someone could show how one would annotate the example minimally to give the optimizer enough information to surpass Racket. As of this moment I haven't really managed to see any improvement from using Typed Racket. It cut down the time `divides?` needed to a few seconds more than Racket. Otherwise, it had no effect (on the other example either). As a point of curiosity; I had to work around the fact that apparently there were not enough type annotations by wrapping the `for`s in functions and typing them accordingly. Is there a better way to do this? I'm currently trying to compare some performance between OCaml, C and Racket and I'm currently using the aforementioned example. Here are some timings: | time racket divides.rkt; time ./divides_c; time ./divides_ocaml 416658333 racket divides.rkt 7.32s user 0.02s system 100% cpu 7.336 total 416658333 ./divides_c 0.49s user 0.00s system 99% cpu 0.488 total 416658333 ./divides_ocaml 0.75s user 0.00s system 99% cpu The idea is to see how fast one can make the following: #lang racket/base (define (divisible-by? x d) (= (modulo x d) 0)) (module+ main (for/sum ([x (in-range 3 5)]) (if (x . divisible-by? . 3) x 0)) ) On Mon, 24 Aug 2015, Pierpaolo Bernardi wrote: On Mon, Aug 24, 2015 at 1:25 PM, Jens Axel Søgaard jensa...@soegaard.net wrote: It looks very odd to me. Maybe this is due to calling TR functions from plain Racket? -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] `divides?` from math/number-theory slow?
My message below is not doing the right test. This is the right test and it produces the expected result, namely that the TR version runs a bit faster (presumably because of type-based optimizations that TR does). Robby #lang racket (module t typed/racket/base (: divides? : Integer Integer - Boolean) (define (divides? a b) (cond [(zero? a) #f] [else (= (remainder b a) 0)])) (provide divides?)) (module c racket/base (require racket/contract/base) (define (divides? a b) (cond [(zero? a) #f] [else (= (remainder b a) 0)])) (provide (contract-out [divides? (- exact-integer? exact-integer? boolean?)]))) (require (prefix-in c: (submod . c))) (require (prefix-in t: (submod . t))) (time (for ([x (in-range 3 500)]) (if (3 . c:divides? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (3 . t:divides? . x) x 0))) On Mon, Aug 24, 2015 at 8:18 AM, Robby Findler ro...@eecs.northwestern.edu wrote: It looks to me like the slowdown isn't entirely explained by contract checking, or perhaps TR isn't generating the contracts I would have guessed. With the program below, I see this output cpu time: 1228 real time: 1228 gc time: 133 cpu time: 658 real time: 658 gc time: 18 cpu time: 80 real time: 81 gc time: 0 but would have expected the first two lines to be nearly the same. Robby #lang racket (require (only-in math/number-theory divides?)) (define (divisible-by? x d) (= (modulo x d) 0)) (module d racket/base (require racket/contract/base) (define (divisible-by? x d) (= (modulo x d) 0)) (provide (contract-out [divisible-by? (- exact-integer? exact-integer? boolean?)]))) (require (prefix-in c: (submod . d))) (module+ main (time (for ([x (in-range 3 500)]) (if (3 . divides? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (3 . c:divisible-by? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (x . divisible-by? . 3) x 0 -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] `divides?` from math/number-theory slow?
With regards to the measurements; as is obvious from this mailchain, I know about and use the `time` form. It hasn't skewed the results. Using the optimizing coach in DrRacket has yielded no results, really. I tried using it and there wasn't any advice on what to do for speedups (unless that advice isn't very discoverable, I don't know.). The only meaningful difference I discovered for TR was using 6.1.1, as apparently there was an optimization that'd been borked for 6.2.0 and onwards. I'm still curious about speed-ups with TR. I had expected it to perform better than Racket, but I guess the big win is that you get contracts with better performance instead of much faster, brittle code? On Mon, 24 Aug 2015, Vincent St-Amour wrote: On Mon, 24 Aug 2015 08:38:46 -0400, Rickard Andersson wrote: Yes, that indeed seems to be the problem. However, even after managing to wrap the types properly, using `divides?` still ended up being a bit slower. Not dramatically slower, but still noticably and unexpectedly. As I'm not at all comfortable with Typed Racket I would appreciate if someone could show how one would annotate the example minimally to give the optimizer enough information to surpass Racket. As of this moment I haven't really managed to see any improvement from using Typed Racket. It cut down the time `divides?` needed to a few seconds more than Racket. Otherwise, it had no effect (on the other example either). In general, if you want to ensure that your code plays nice with the Typed Racket optimizer, I recommend you try the optimization coach, in DrRacket. There should be a button in the toolbar when you're working in Typed Racket. The coach points out portions of your programs where additional optimizations could apply if you were to change your program a bit, and give you advice on how to change it. The Typed Racket guide also has some general performance advice: http://docs.racket-lang.org/ts-guide/optimization.html As a point of curiosity; I had to work around the fact that apparently there were not enough type annotations by wrapping the `for`s in functions and typing them accordingly. Is there a better way to do this? Have you tried adding annotations to the `for` forms directly? The docs show the syntax: http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._for%29%29 I'm currently trying to compare some performance between OCaml, C and Racket and I'm currently using the aforementioned example. Here are some timings: | time racket divides.rkt; time ./divides_c; time ./divides_ocaml 416658333 racket divides.rkt 7.32s user 0.02s system 100% cpu 7.336 total 416658333 ./divides_c 0.49s user 0.00s system 99% cpu 0.488 total 416658333 ./divides_ocaml 0.75s user 0.00s system 99% cpu The idea is to see how fast one can make the following: #lang racket/base (define (divisible-by? x d) (= (modulo x d) 0)) (module+ main (for/sum ([x (in-range 3 5)]) (if (x . divisible-by? . 3) x 0)) ) In this particular example, you may get speedups by using Typed Racket's sub-`Integer` types, such as `Index` or `Fixnum`. These can guarantee to the typechecker that your code will not generate bignums, which will allow TR to optimize accordingly. A note on your particular measurement methodology. When you use unix's `time` command on `racket x.rkt`, this measures not only the actual execution time, but also compilation to bytecode and, in the case of Typed Racket programs, typechecking time as well (which can be significant). If you run `raco make x.rkt` before measuring, you avoid measuring that extra overhead. If you also want to avoid measuring the startup overhead of the Racket VM (which only really matters for short scripts), you should use the `time` form in Racket, instead of the unix `time` command. Vincent -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] `divides?` from math/number-theory slow?
On Mon, 24 Aug 2015 08:38:46 -0400, Rickard Andersson wrote: Yes, that indeed seems to be the problem. However, even after managing to wrap the types properly, using `divides?` still ended up being a bit slower. Not dramatically slower, but still noticably and unexpectedly. As I'm not at all comfortable with Typed Racket I would appreciate if someone could show how one would annotate the example minimally to give the optimizer enough information to surpass Racket. As of this moment I haven't really managed to see any improvement from using Typed Racket. It cut down the time `divides?` needed to a few seconds more than Racket. Otherwise, it had no effect (on the other example either). In general, if you want to ensure that your code plays nice with the Typed Racket optimizer, I recommend you try the optimization coach, in DrRacket. There should be a button in the toolbar when you're working in Typed Racket. The coach points out portions of your programs where additional optimizations could apply if you were to change your program a bit, and give you advice on how to change it. The Typed Racket guide also has some general performance advice: http://docs.racket-lang.org/ts-guide/optimization.html As a point of curiosity; I had to work around the fact that apparently there were not enough type annotations by wrapping the `for`s in functions and typing them accordingly. Is there a better way to do this? Have you tried adding annotations to the `for` forms directly? The docs show the syntax: http://docs.racket-lang.org/ts-reference/special-forms.html#%28form._%28%28lib._typed-racket%2Fbase-env%2Fprims..rkt%29._for%29%29 I'm currently trying to compare some performance between OCaml, C and Racket and I'm currently using the aforementioned example. Here are some timings: | time racket divides.rkt; time ./divides_c; time ./divides_ocaml 416658333 racket divides.rkt 7.32s user 0.02s system 100% cpu 7.336 total 416658333 ./divides_c 0.49s user 0.00s system 99% cpu 0.488 total 416658333 ./divides_ocaml 0.75s user 0.00s system 99% cpu The idea is to see how fast one can make the following: #lang racket/base (define (divisible-by? x d) (= (modulo x d) 0)) (module+ main (for/sum ([x (in-range 3 5)]) (if (x . divisible-by? . 3) x 0)) ) In this particular example, you may get speedups by using Typed Racket's sub-`Integer` types, such as `Index` or `Fixnum`. These can guarantee to the typechecker that your code will not generate bignums, which will allow TR to optimize accordingly. A note on your particular measurement methodology. When you use unix's `time` command on `racket x.rkt`, this measures not only the actual execution time, but also compilation to bytecode and, in the case of Typed Racket programs, typechecking time as well (which can be significant). If you run `raco make x.rkt` before measuring, you avoid measuring that extra overhead. If you also want to avoid measuring the startup overhead of the Racket VM (which only really matters for short scripts), you should use the `time` form in Racket, instead of the unix `time` command. Vincent -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] `divides?` from math/number-theory slow?
I was very curious about what you were talking about, as I saw wildly different numbers (in line with what I'd seen before). However, I did the following test: | ~/tools/racket/6.1.1/bin/racket typed_divide.rkt cpu time: 536 real time: 537 gc time: 27 cpu time: 347 real time: 347 gc time: 4 cpu time: 87 real time: 84 gc time: 0 | ~/tools/racket/6.2.0/bin/racket typed_divide.rkt cpu time: 567 real time: 565 gc time: 10 cpu time: 960 real time: 958 gc time: 13 cpu time: 83 real time: 84 gc time: 0 | ~/tools/racket/6.2.1/bin/racket typed_divide.rkt cpu time: 600 real time: 601 gc time: 70 cpu time: 970 real time: 974 gc time: 23 cpu time: 86 real time: 85 gc time: 0 The below program is what's being run: #lang racket/base (module t typed/racket/base (: divides? : Integer Integer - Boolean) (define (divides? a b) (cond [(zero? a) #f] [else (= (remainder b a) 0)])) (provide divides?)) (module c racket/base (require racket/contract/base) (define (divides? a b) (cond [(zero? a) #f] [else (= (remainder b a) 0)])) (provide (contract-out [divides? (- exact-integer? exact-integer? boolean?)]))) (module no-contract racket/base (define (divides? a b) (cond [(zero? a) #f] [else (= (remainder b a) 0)])) (provide divides?)) (require (prefix-in with-contract: (submod . c))) (require (prefix-in typed: (submod . t))) (require (prefix-in no-contract: (submod . no-contract))) (time (for ([x (in-range 3 500)]) (if (3 . with-contract:divides? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (3 . typed:divides? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (3 . no-contract:divides? . x) x 0))) On Mon, 24 Aug 2015, Robby Findler wrote: My message below is not doing the right test. This is the right test and it produces the expected result, namely that the TR version runs a bit faster (presumably because of type-based optimizations that TR does). Robby #lang racket (module t typed/racket/base (: divides? : Integer Integer - Boolean) (define (divides? a b) (cond [(zero? a) #f] [else (= (remainder b a) 0)])) (provide divides?)) (module c racket/base (require racket/contract/base) (define (divides? a b) (cond [(zero? a) #f] [else (= (remainder b a) 0)])) (provide (contract-out [divides? (- exact-integer? exact-integer? boolean?)]))) (require (prefix-in c: (submod . c))) (require (prefix-in t: (submod . t))) (time (for ([x (in-range 3 500)]) (if (3 . c:divides? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (3 . t:divides? . x) x 0))) On Mon, Aug 24, 2015 at 8:18 AM, Robby Findler ro...@eecs.northwestern.edu wrote: It looks to me like the slowdown isn't entirely explained by contract checking, or perhaps TR isn't generating the contracts I would have guessed. With the program below, I see this output cpu time: 1228 real time: 1228 gc time: 133 cpu time: 658 real time: 658 gc time: 18 cpu time: 80 real time: 81 gc time: 0 but would have expected the first two lines to be nearly the same. Robby #lang racket (require (only-in math/number-theory divides?)) (define (divisible-by? x d) (= (modulo x d) 0)) (module d racket/base (require racket/contract/base) (define (divisible-by? x d) (= (modulo x d) 0)) (provide (contract-out [divisible-by? (- exact-integer? exact-integer? boolean?)]))) (require (prefix-in c: (submod . d))) (module+ main (time (for ([x (in-range 3 500)]) (if (3 . divides? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (3 . c:divisible-by? . x) x 0))) (time (for ([x (in-range 3 500)]) (if (x . divisible-by? . 3) x 0 -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] `divides?` from math/number-theory slow?
On Mon, 24 Aug 2015 11:24:33 -0400, Rickard Andersson wrote: With regards to the measurements; as is obvious from this mailchain, I know about and use the `time` form. It hasn't skewed the results. Using the optimizing coach in DrRacket has yielded no results, really. I tried using it and there wasn't any advice on what to do for speedups (unless that advice isn't very discoverable, I don't know.). The only meaningful difference I discovered for TR was using 6.1.1, as apparently there was an optimization that'd been borked for 6.2.0 and onwards. I'm still curious about speed-ups with TR. I had expected it to perform better than Racket, but I guess the big win is that you get contracts with better performance instead of much faster, brittle code? TR can perform better than plain Racket, but not always. TR mostly performs local optimizations that remove dispatch / checks in various operations, so only programs using these operations will see any improvements. Areas where you can expect wins are float- and complex-number-intensive computations, as well as some data structure accesses. Vincent -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[racket-users] `divides?` from math/number-theory slow?
Hi, I noticed that the `divides?` function from math/number-theory seems to be a huge bottleneck for whatever reason. This seems strange to me, but I figured I'd write to the list to see if maybe there are trade-offs made that make sense mostly for big integers or something. Example with (time): #lang racket/base (require (only-in math/number-theory divides?)) (define (divisible-by? x d) (= (modulo x d) 0)) (module+ main (time (for/sum ([x (in-range 3 5)]) (if (3 . divides? . x) x 0))) ; cpu time: 96257 real time: 96166 gc time: 128 (time (for/sum ([x (in-range 3 5)]) (if (x . divisible-by? . 3) x 0))) ; cpu time: 7277 real time: 7266 gc time: 0 ) -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] `divides?` from math/number-theory slow?
I hope someone has solution. It looks very odd to me. The function divides? is defined in https://raw.githubusercontent.com/racket/math/master/math-lib/math/private/number-theory/divisibility.rkt #lang typed/racket/base (provide divides? coprime? pairwise-coprime? bezout) ;;; ;;; DIVISIBILITY ;;; (: divides? : Integer Integer - Boolean) ; a divides b = exists unique k s.t. a*k=b (define (divides? a b) (cond [(zero? a) #f] [else (= (remainder b a) 0)])) 2015-08-24 12:41 GMT+02:00 Rickard Andersson rickard.m.anders...@gmail.com : Hi, I noticed that the `divides?` function from math/number-theory seems to be a huge bottleneck for whatever reason. This seems strange to me, but I figured I'd write to the list to see if maybe there are trade-offs made that make sense mostly for big integers or something. Example with (time): #lang racket/base (require (only-in math/number-theory divides?)) (define (divisible-by? x d) (= (modulo x d) 0)) (module+ main (time (for/sum ([x (in-range 3 5)]) (if (3 . divides? . x) x 0))) ; cpu time: 96257 real time: 96166 gc time: 128 (time (for/sum ([x (in-range 3 5)]) (if (x . divisible-by? . 3) x 0))) ; cpu time: 7277 real time: 7266 gc time: 0 ) -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- -- Jens Axel Søgaard -- You received this message because you are subscribed to the Google Groups Racket Users group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
