On Mon, Jun 9, 2014 at 9:46 PM, Eric Dobson <eric.n.dob...@gmail.com> wrote: > Splitting this out because this is actually a different issue. This is > about us generating slow contracts. > > There are two things in play here. > > One is that TR doesn't use the new lazy parts of struct/dc. This would > require changing struct contracts from flat contracts to > chaperone-contracts. Given that I think we are going to need to change > struct contracts to sometimes be chaperone contracts anyways for > soundness that might not be a huge loss. I did performance measurements and it is about a factor of 60 slower for lazy chaperone contracts. I see a couple of ways to improve these numbers, so they could be better in the future with a bit more work on optimizing. Given that strict contracts actually change the big O notation I think that this is a reasonable performance price to pay, given that data structures with more than 60 elements are fairly common.
> > #lang racket > > > (struct my-cons (fst snd)) > > (define (list->my-list xs) > (if (empty? xs) xs (my-cons (first xs) (list->my-list (rest xs))))) > > (define (my-first xs) > (if (empty? xs) (error 'bad) (my-cons-fst xs))) > > > > (define c1 > (recursive-contract > (struct/dc my-cons [fst () #:flat any/c] [snd () #:flat (or/c null c1)]) > #:flat)) > (define c2 > (recursive-contract > (struct/dc my-cons [fst () #:flat any/c] [snd () #:chaperone #:lazy > (or/c null c2)]) > #:chaperone)) > > > > (define/contract (f1 xs) > (-> c1 any) (my-first xs)) > (define/contract (f2 xs) > (-> c2 any) (my-first xs)) > > > (define lst1 (list->my-list '(1 2))) > > (for ([_ (in-range 5)]) > (time (for ([_ (in-range 10000)]) > (my-first lst1)))) > > (for ([_ (in-range 5)]) > (time (for ([_ (in-range 10000)]) > (f1 lst1)))) > > (for ([_ (in-range 5)]) > (time (for ([_ (in-range 10000)]) > (f2 lst1)))) > > (define lst2 (list->my-list '(1 2 3 4 5 6 7 8 9))) > > (for ([_ (in-range 5)]) > (time (for ([_ (in-range 10000)]) > (my-first lst2)))) > > (for ([_ (in-range 5)]) > (time (for ([_ (in-range 10000)]) > (f1 lst2)))) > > (for ([_ (in-range 5)]) > (time (for ([_ (in-range 10000)]) > (f2 lst2)))) > > f2 is constant where f1 grows. > > And the other is that TR cannot follow the logic that you use to show > that just running my-cons? is as strong as checking the entire list. > If we could do that reduction we would get a large speedup. > > > On Mon, Jun 9, 2014 at 10:01 AM, Neil Toronto <neil.toro...@gmail.com> wrote: >> On 06/09/2014 10:25 AM, Neil Toronto wrote: >>> >>> On 06/09/2014 01:19 AM, Eric Dobson wrote: >>>> >>>> >>>> Does this seem like a reasonable thing to support/do people see issues >>>> with it? >>> >>> >>> I can only speak on reasonableness, and my answer is emphatically YES. >>> >>> Typed Racket is a great language in which to define and use data >>> structures: access is very fast, and many properties are checked >>> statically. But accessor performance suffers badly when the data types >>> are used in untyped Racket. If access uses higher-order functions (e.g. >>> math/array), wrapping the functions slows access by a very high constant >>> factor. If the data structures are first-order, every O(1) access >>> becomes O(n). >>> >>> I recently had to work around this in Plot when I needed an untyped >>> module to be able to operate on typed BSP trees. I ended up making a >>> typed weak hash map from "BSP tree handles" (gensyms) to BSP trees, and >>> writing a new untyped API for operating on trees using handles. It was >>> ugly. If the untyped and typed modules had been too tightly coupled, it >>> would have been impossible. >>> >>> IIUC, your proposal would make untyped use of typed data structures >>> actually feasible for real-world use. So again, YES. >> >> >> Here's a concrete example, using Typed Racket to define a new list type. >> >> >> #lang racket >> >> (module typed-defs typed/racket >> (provide list->my-list >> my-first) >> >> (define-type (My-Listof A) (U Null (my-cons A))) >> (struct (A) my-cons ([fst : A] [snd : (My-Listof A)]) #:transparent) >> >> (: list->my-list (All (A) (-> (Listof A) (My-Listof A)))) >> (define (list->my-list xs) >> (if (empty? xs) xs (my-cons (first xs) (list->my-list (rest xs))))) >> >> (: my-first (All (A) (-> (My-Listof A) A))) >> (define (my-first xs) >> (if (empty? xs) (error 'bad) (my-cons-fst xs))) >> >> ;; Timing loop speed is very fast and O(1) >> (define lst (list->my-list '(1))) >> (for ([_ (in-range 5)]) >> (time (for ([_ (in-range 1000000)]) >> (my-first lst)))) >> ) >> >> (require 'typed-defs) >> >> ;; Timing loop speed is very slow and O(n) >> (define lst (list->my-list '(1))) >> (for ([_ (in-range 5)]) >> (time (for ([_ (in-range 1000000)]) >> (my-first lst)))) >> >> >> I get 4ms for the timing loop in the typed module, and 620ms for the timing >> loop in the untyped module, so the constant factor is about 150. >> >> When I change the test data from '(1) to '(1 2), the untyped module's timing >> loop takes about 1010ms. The contract boundary has changed the asymptotic >> complexity of `my-first' from O(1) to O(n). >> >> >> Neil ⊥ >> >> _________________________ >> Racket Developers list: >> http://lists.racket-lang.org/dev _________________________ Racket Developers list: http://lists.racket-lang.org/dev