So I just implemented a version that eliminates the EmptyNode type It's much faster:
Timing 1000000 insert operations: elapsed time: 2.760959719 seconds (176035376 bytes allocated) Timing 1000000 random access operations. elapsed time: 1.424487301 seconds (31994776 bytes allocated) Timing 1000000 remove operations. elapsed time: 2.251920056 seconds (16007744 bytes allocated) With the other improvements – FloatingPoint -> Float64 and explicit type annotations inside the getindex method –, I've gotten the times down to 1.5s, 1.5s, and 1.10s, respectively. Still allocating memory everywhere, though. I've updated the code in the gist to the new version: https://gist.github.com/yurivish/aff46c190c1ac538c46f Cheers, Yuri On Sunday, May 11, 2014 8:59:58 PM UTC-4, Isaiah wrote: > > 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 <iaind...@gmail.com<javascript:> > > 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 <yuri...@gmail.com> >>>>>> 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 >>>>>> >>>>>> >
