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.
