Done: https://github.com/JuliaLang/julia/issues/6813
On Sunday, May 11, 2014 8:52:09 PM UTC-4, Iain Dunning 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
>>>>>
>>>>>
