This is related to a thought I've had, tho. It seems like it is hard for TR or for the contract system to know if a lazy or a strict check is the most useful, but the programmer may have some good information. So maybe there could be a way for the TR programmer to say "make things with this type, when doing contract generation, have eager semantics" and then maybe even give the same things two different types if it would be used in two different situations that would have different performance characteristics.
In this particular case, however, the pdfs programmer could just say "make it eager" and be done with it. Robby On Tue, Jan 5, 2016 at 4:08 PM, Sam Tobin-Hochstadt <sa...@cs.indiana.edu> wrote: > It's possible; I'm not sure. The essence of the issue is here: > https://gist.github.com/38f4ef694d1df822b3e2 with this contract: > > (recursive-contract (struct/c Trie number? (or/c #f (hash/c any/c Trie/c))) > #:chaperone) > > The similar contract: > > (recursive-contract (struct/c Trie number? (or/c #f (hash/c any/c > Trie/c-flat #:flat? #t))) > #:flat) > > Is at least 100x faster when traversing the tree after the contract is > applied. > > It seems like it would be tricky for the contract system to figure out that > one can be used for the other. > > Sam > > > On Tue, Jan 5, 2016 at 4:53 PM Robby Findler <ro...@eecs.northwestern.edu> > wrote: >> >> Could the contract do something helpful here, or is this really a fix >> that needs to happen in TR and/or the pfds library? >> >> Robby >> >> >> On Tue, Jan 5, 2016 at 3:21 PM, Sam Tobin-Hochstadt >> <sa...@cs.indiana.edu> wrote: >> > The actual problem (in addition to the slowness of chaperones that >> > exist at every level of a structure) is that TR doesn't distinguish >> > between mutable and immutable hash tables. Therefore, a contract that >> > uses `hash/c` has to be a chaperone contract, thus causing the >> > slowdown John reported. >> > >> > Sam >> > >> > On Tue, Jan 5, 2016 at 3:33 PM, Sam Tobin-Hochstadt >> > <sa...@cs.indiana.edu> wrote: >> >> The overhead appears to be a combination of the following: >> >> >> >> - Typed Racket should see that checking whether something is a Trie >> >> is a flat contract, but it doesn't. >> >> - Typed Racket should be able to drop the result contract check >> >> entirely, but it can't (I don't think this is expensive, though). >> >> - Applying chaperones to a recursive data structure, and then >> >> traversing that data structure, is quite slow. >> >> >> >> Note that there's 2 passes over the data structure implied by the >> >> contract, but they aren't expensive -- if you just write them yourself >> >> with Racket code, they're basically instant. Everything is about the >> >> cost of chaperoning the data. >> >> >> >> Sam >> >> >> >> On Tue, Jan 5, 2016 at 3:19 PM, Vincent St-Amour >> >> <stamo...@eecs.northwestern.edu> wrote: >> >>> (add1 Jay) >> >>> >> >>> That kind of overhead has to be a bug somewhere, or a bad way to write >> >>> something. I hope. >> >>> >> >>> Vincent >> >>> >> >>> >> >>> >> >>> On Tue, 05 Jan 2016 13:40:33 -0600, >> >>> Jay McCarthy wrote: >> >>>> >> >>>> I would prefer taking this useful library and making it actually >> >>>> useful to all Racket users. >> >>>> >> >>>> Jay >> >>>> >> >>>> On Tue, Jan 5, 2016 at 2:39 PM, 'John Clements' via Racket Users >> >>>> <racket-users@googlegroups.com> wrote: >> >>>> > Asumu, does this make sense to you? Note that in particular, I >> >>>> > think that a warning at the top of the pfds package wouldn’t have >> >>>> > helped me; >> >>>> > I think a warning at the top of each pfds page would make a lot more >> >>>> > sense. >> >>>> > >> >>>> > John >> >>>> > >> >>>> >> On Jan 5, 2016, at 11:00 AM, Sam Tobin-Hochstadt >> >>>> >> <sa...@cs.indiana.edu> wrote: >> >>>> >> >> >>>> >> Yes, I think a warning at the top of the documentation for the >> >>>> >> `pfds` package would make sense, and probably Asumu would accept >> >>>> >> such a pull >> >>>> >> request. You might follow the phrasing in the math/array library. >> >>>> >> >> >>>> >> Sam >> >>>> >> >> >>>> >> On Tue, Jan 5, 2016 at 1:49 PM 'John Clements' via Racket Users >> >>>> >> <racket-users@googlegroups.com> wrote: >> >>>> >> This program constructs a trie containing exactly two keys; each >> >>>> >> is a list of 256 integers. On my machine, it takes *twelve seconds*. >> >>>> >> The >> >>>> >> time taken appears to be n^2 in the length of the key, so doubling >> >>>> >> it to 256 >> >>>> >> means it’ll take about a minute to add a key. >> >>>> >> >> >>>> >> #lang racket >> >>>> >> >> >>>> >> (require pfds/trie) >> >>>> >> >> >>>> >> (define (rand-list) >> >>>> >> (for/list ([i (in-range 128)]) >> >>>> >> (random 256))) >> >>>> >> >> >>>> >> (define t (trie (list (rand-list)))) >> >>>> >> (define u (time (bind (rand-list) 0 t))) >> >>>> >> >> >>>> >> When I translate this to typed racket, the time taken is 0 ms. >> >>>> >> >> >>>> >> I feel like I got a bit burned here, and an ordinary user might >> >>>> >> simply conclude that Racket libraries are teh suck. >> >>>> >> >> >>>> >> Can we add a warning to the beginning of the documentation page >> >>>> >> for Tries (and perhaps for the other data structures as well) >> >>>> >> indicating >> >>>> >> that these functions are likely to be unusably slow in #lang racket? >> >>>> >> >> >>>> >> I propose the following, at the top of the documentation. Possibly >> >>>> >> in boldface. >> >>>> >> >> >>>> >> “NB: these data structures are written in Typed Racket. While they >> >>>> >> may be nominally usable in the (untyped) Racket language, the >> >>>> >> resulting >> >>>> >> dynamic checks will probably cause them to be unacceptably slow” >> >>>> >> >> >>>> >> Suggestions? May I make a pull request here? >> >>>> >> >> >>>> >> John >> >>>> >> >> >>>> >> >> >>>> >> >> >>>> >> -- >> >>>> >> 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. >> >>>> >> >>>> >> >>>> >> >>>> -- >> >>>> Jay McCarthy >> >>>> Associate Professor >> >>>> PLT @ CS @ UMass Lowell >> >>>> http://jeapostrophe.github.io >> >>>> >> >>>> "Wherefore, be not weary in well-doing, >> >>>> for ye are laying the foundation of a great work. >> >>>> And out of small things proceedeth that which is great." >> >>>> - D&C 64:33 >> >>>> >> >>>> -- >> >>>> 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. >> > >> > -- >> > 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. -- 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.
