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<javascript:>> > 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 > >
