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 <[email protected]> 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 >> <[email protected]> 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 <[email protected]> >> >> 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 >> >> <[email protected]> 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 [email protected]. >> >> 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 [email protected]. >> > 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 [email protected]. >> 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 [email protected]. > 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 [email protected]. For more options, visit https://groups.google.com/d/optout.
