Is there a way to write this with a single node type? One method that has been previously suggested is to indicate an "empty" node type by self-reference. This could improve type stability.
On Sun, May 11, 2014 at 8:52 PM, Iain Dunning <[email protected]> wrote: > Wow, yeah! It sure looks like that. Can you file an issue with this > information? > > > On Sunday, May 11, 2014 8:38:37 PM UTC-4, Yuri Vishnevsky wrote: >> >> I don't know if I'm interpreting the output correctly, but if you look at >> at the output from the following it seems that both t and index are >> interpreted to be of type Any. >> >> > t = MinTreap{Int}(); add!(t, 50) >> > @code_typed t.root[1] >> >> >> On Sunday, May 11, 2014 8:27:46 PM UTC-4, Iain Dunning wrote: >>> >>> So the FloatingPoint -> Float64 is probably a good idea, but isn't the >>> bottleneck. >>> >>> I profiled the random access section: >>> t[1] >>> @profile for i in 1:n >>> t[rand(1:n)] >>> end >>> Profile.print() >>> >>> and all the work is going on in lines 84,87, and 88, as you'd expect. >>> What I can't figure out is why it is allocating any memory... >>> >>> On Sunday, May 11, 2014 7:59:42 PM UTC-4, Yuri Vishnevsky wrote: >>>> >>>> Oddly, that makes it *slower*... >>>> >>>> julia> benchmark(1000000) >>>> Timing 1000000 insert operations. >>>> elapsed time: 11.637004929 seconds (1324768744 bytes allocated) >>>> Timing 1000000 random access operations. >>>> elapsed time: 15.640938079 seconds (1047763544 bytes allocated) >>>> Timing 1000000 remove operations. >>>> elapsed time: 9.440363056 seconds (1138842368 bytes allocated) >>>> >>>> (vs. 7s, 16s, and 5s with FloatingPoint priorities, respectively.) >>>> >>>> – Yuri >>>> >>>> On Sunday, May 11, 2014 7:39:17 PM UTC-4, John Myles White wrote: >>>>> >>>>> Try changing FloatingPoint to Float64 and you may seem a substantial >>>>> performance boost. >>>>> >>>>> — John >>>>> >>>>> On May 11, 2014, at 4:32 PM, Yuri Vishnevsky <[email protected]> >>>>> wrote: >>>>> >>>>> > I'm working on a Julia implementation of a Treap, a data structure >>>>> that maintains a sorted collection of elements and allows insertion, >>>>> deletion, and random access in O(log n) time ( >>>>> http://en.wikipedia.org/wiki/Treap). >>>>> > >>>>> > So far I've implemented the basic functions, but performance is far >>>>> slower than I'd like and I am having trouble understanding why. >>>>> > >>>>> > Here's the gist: https://gist.github.com/ >>>>> yurivish/aff46c190c1ac538c46f >>>>> > >>>>> > I've written a small benchmark script to try and diagnose the >>>>> problem. It reports lots of memory use for larger collections, even during >>>>> calls to getindex(). Here's the output for several runs; the function, >>>>> which is included in the gist, creates and queries a list of Int64s. >>>>> > >>>>> > julia> benchmark(100) >>>>> > Timing 100 insert operations. >>>>> > elapsed time: 0.000188415 seconds (11200 bytes allocated) >>>>> > Timing 100 random access operations. >>>>> > elapsed time: 0.000294615 seconds (0 bytes allocated) >>>>> > Timing 100 remove operations. >>>>> > elapsed time: 6.6692e-5 seconds (0 bytes allocated) >>>>> > >>>>> > julia> benchmark(1000) >>>>> > Timing 1000 insert operations. >>>>> > elapsed time: 0.0024881 seconds (208080 bytes allocated) >>>>> > Timing 1000 random access operations. >>>>> > elapsed time: 0.003553674 seconds (95776 bytes allocated) >>>>> > Timing 1000 remove operations. >>>>> > elapsed time: 0.001143906 seconds (74496 bytes allocated) >>>>> > >>>>> > julia> benchmark(1000000) >>>>> > Timing 1000000 insert operations. >>>>> > elapsed time: 6.920983574 seconds (521837776 bytes allocated) >>>>> > Timing 1000000 random access operations. >>>>> > elapsed time: 16.232631535 seconds (1010908560 bytes allocated) >>>>> > Timing 1000000 remove operations. >>>>> > elapsed time: 5.399104537 seconds (387715296 bytes allocated) >>>>> > >>>>> > Any insight into potential improvements to (or problems with) the >>>>> code would be appreciated. >>>>> > >>>>> > Cheers, >>>>> > Yuri >>>>> >>>>>
