Among the three operations I measured (add!, remove!, and getindex), there's one place in the code where the inferred type of a variable is a type union. This is in the first if-branch of remove!, which deletes the root node by returning the merge of the left and right subtrees, both of which may be empty.
Perhaps some measurements are in order to test whether the way I've set up the node types has a strong negative impact on performance, but because all three functions seem slower than they should be I suspect there are other factors at play as well. I did consider indicating empty nodes by self-reference but decided that the current approach allows the code to be much more elegant – giving empty nodes their own priority (Inf) and size (0) simplifies a lot of the logic. Unless it's a large performance slowdown, I'd like to continue to leverage the type system for dispatching operations on empty and non-empty nodes. 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 <[email protected]<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 <[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 >>>>>> >>>>>> >
