Good point. Here's the code_llvm for getindex: https://gist.github.com/yurivish/a0af9042137173fa8d55
It's rather long, but I don't have enough experience to tell whether it's within the bounds you'd expect. There are some checks in there for undefined references, which I initially thought are because the constructor for empty TreapNodes leaves some fields undefined, but I tested out a version of TreapNode with self-referential empty nodes and the generated code seems to look the same. On Monday, May 12, 2014 10:17:12 AM UTC-4, Iain Dunning wrote: > > For access and remove, that is like 30 bytes per op so its probably not > actually allocating memory in the malloc() sense. > And the memory usage when you are growing it seems proportional too. > How does code_llvm look? > > On Monday, May 12, 2014 10:12:47 AM UTC-4, Yuri Vishnevsky wrote: >> >> 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>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 >>>>>>>> >>>>>>>> >>>
