even faster heaps

[Sven R. Kunze]

On 08.03.2016 08:12, srinivas devaki wrote:
> Hi,
> sorry i didn't get to your last mail as i'm having exams at that time.

No problem. :) I hope they went all well for you.

> Everything is good so far.
>
> but if at all the purpose is to add features to the stdlib heap and
> keeping the speed offered by the stdlib, why aren't you allowing the
> duplicate elements which is possible with stdlib heap.

Don't let the old boy have time to rest, he? ;-)

But that's good. We all need a kick in the ass from time to time in 
order to get thing running. :-)

> to be able to add duplicate elements you just have to make the set as
> a dict with counter as the value. afterall it is highly common to have
> priority task scheduling with equal priorities to the tasks.
>
> as far as the benchmarks are concerned it didn't change much with the
> current dataset. but it is not valid to compare them as the current
> dataset is intended for unique elements. but with the dict the dataset
> can contain elements which have equal keys.

So, my initial design idea was to wrap these items up in their own 
wrapper and thus avoiding the duplicate issue. I discussed this with Cem 
here http://code.activestate.com/lists/python-list/697567/  :)

> on my machine with 10 repetitions in the test_xheap_time.py
> ** results for the code which supports duplicate elements
> HEAD at github.com/eightnoteight/xheap **
>
> (u'init', u'heapq      ', u' 0.45 ( 1.00x)  4.59 ( 1.00x) 52.24 (
> 1.00x) 553.80 ( 1.00x)')
> (u'    ', u'Heap       ', u' 0.48 ( 1.07x)  5.41 ( 1.18x) 75.89 (
> 1.45x) 786.46 ( 1.42x)')
> (u'    ', u'RemovalHeap', u' 0.86 ( 1.93x)  9.98 ( 2.18x) 131.28 (
> 2.51x) 1364.14 ( 2.46x)')
> --------------------------------------------------------------------
> (u'pop ', u'heapq      ', u' 0.09 ( 1.00x)  1.27 ( 1.00x) 15.64 (
> 1.00x) 184.76 ( 1.00x)')
> (u'    ', u'Heap       ', u' 0.10 ( 1.07x)  1.33 ( 1.05x) 16.30 (
> 1.04x) 191.43 ( 1.04x)')
> (u'    ', u'RemovalHeap', u' 0.15 ( 1.64x)  1.87 ( 1.47x) 21.33 (
> 1.36x) 242.31 ( 1.31x)')
> --------------------------------------------------------------------
> (u'push', u'heapq      ', u' 0.04 ( 1.00x)  0.33 ( 1.00x)  3.53 (
> 1.00x) 32.99 ( 1.00x)')
> (u'    ', u'Heap       ', u' 0.05 ( 1.20x)  0.41 ( 1.25x)  4.37 (
> 1.24x) 44.14 ( 1.34x)')
> (u'    ', u'RemovalHeap', u' 0.06 ( 1.58x)  0.56 ( 1.70x)  5.85 (
> 1.66x) 59.59 ( 1.81x)')
> --------------------------------------------------------------------
> --------------------------------------------------------------------
> (u'init', u'heapq    ', u' 0.45 ( 1.00x)  8.00 ( 1.00x) 109.50 (
> 1.00x) 898.50 ( 1.00x)')
> (u'    ', u'OrderHeap', u' 0.50 ( 1.10x)  8.75 ( 1.09x) 112.63 (
> 1.03x) 1108.26 ( 1.23x)')
> (u'    ', u'XHeap    ', u' 0.93 ( 2.06x) 13.88 ( 1.74x) 170.97 (
> 1.56x) 1709.94 ( 1.90x)')
> --------------------------------------------------------------------
> (u'pop ', u'heapq    ', u' 0.04 ( 1.00x)  0.54 ( 1.00x)  6.50 ( 1.00x)
> 76.64 ( 1.00x)')
> (u'    ', u'OrderHeap', u' 0.06 ( 1.73x)  0.80 ( 1.49x)  9.16 ( 1.41x)
> 101.68 ( 1.33x)')
> (u'    ', u'XHeap    ', u' 0.10 ( 2.65x)  1.14 ( 2.13x) 12.60 ( 1.94x)
> 137.73 ( 1.80x)')
> --------------------------------------------------------------------
> (u'push', u'heapq    ', u' 0.01 ( 1.00x)  0.17 ( 1.00x)  1.86 ( 1.00x)
> 14.85 ( 1.00x)')
> (u'    ', u'OrderHeap', u' 0.04 ( 3.88x)  0.47 ( 2.86x)  4.80 ( 2.58x)
> 42.98 ( 2.89x)')
> (u'    ', u'XHeap    ', u' 0.04 ( 3.79x)  0.47 ( 2.85x)  4.85 ( 2.61x)
> 43.94 ( 2.96x)')
> --------------------------------------------------------------------
> --------------------------------------------------------------------
> (u'remove', u'RemovalHeap', u' 0.07 ( 1.00x)  0.73 ( 1.00x)  7.38 (
> 1.00x) 75.18 ( 1.00x)')
> (u'      ', u'XHeap      ', u' 0.05 ( 0.79x)  0.55 ( 0.75x)  5.52 (
> 0.75x) 55.08 ( 0.73x)')
> --------------------------------------------------------------------
> --------------------------------------------------------------------
>
>
> ** benchmark for current git HEAD d0707fba2401a3cef8aed54028fe6d7e9497faa5 **
>
>
> (u'init', u'heapq      ', u' 0.49 ( 1.00x)  5.03 ( 1.00x) 58.71 (
> 1.00x) 600.91 ( 1.00x)')
> (u'    ', u'Heap       ', u' 0.51 ( 1.05x)  5.83 ( 1.16x) 82.88 (
> 1.41x) 886.22 ( 1.47x)')
> (u'    ', u'RemovalHeap', u' 0.58 ( 1.19x)  7.19 ( 1.43x) 106.80 (
> 1.82x) 1108.52 ( 1.84x)')
> --------------------------------------------------------------------
> (u'pop ', u'heapq      ', u' 0.10 ( 1.00x)  1.41 ( 1.00x) 17.64 (
> 1.00x) 209.82 ( 1.00x)')
> (u'    ', u'Heap       ', u' 0.11 ( 1.07x)  1.47 ( 1.04x) 18.27 (
> 1.04x) 215.14 ( 1.03x)')
> (u'    ', u'RemovalHeap', u' 0.15 ( 1.52x)  1.91 ( 1.35x) 22.64 (
> 1.28x) 258.68 ( 1.23x)')
> --------------------------------------------------------------------
> (u'push', u'heapq      ', u' 0.04 ( 1.00x)  0.32 ( 1.00x)  3.49 (
> 1.00x) 33.92 ( 1.00x)')
> (u'    ', u'Heap       ', u' 0.05 ( 1.18x)  0.39 ( 1.22x)  4.21 (
> 1.20x) 42.03 ( 1.24x)')
> (u'    ', u'RemovalHeap', u' 0.06 ( 1.52x)  0.52 ( 1.62x)  5.60 (
> 1.60x) 56.54 ( 1.67x)')
> --------------------------------------------------------------------
> --------------------------------------------------------------------
> (u'init', u'heapq    ', u' 0.44 ( 1.00x)  7.92 ( 1.00x) 106.52 (
> 1.00x) 915.20 ( 1.00x)')
> (u'    ', u'OrderHeap', u' 0.50 ( 1.14x)  8.67 ( 1.10x) 111.99 (
> 1.05x) 1129.89 ( 1.23x)')
> (u'    ', u'XHeap    ', u' 0.61 ( 1.38x) 10.75 ( 1.36x) 140.86 (
> 1.32x) 1417.84 ( 1.55x)')
> --------------------------------------------------------------------
> (u'pop ', u'heapq    ', u' 0.04 ( 1.00x)  0.55 ( 1.00x)  6.59 ( 1.00x)
> 76.81 ( 1.00x)')
> (u'    ', u'OrderHeap', u' 0.06 ( 1.68x)  0.79 ( 1.43x)  9.04 ( 1.37x)
> 101.72 ( 1.32x)')
> (u'    ', u'XHeap    ', u' 0.09 ( 2.43x)  1.03 ( 1.85x) 11.48 ( 1.74x)
> 125.94 ( 1.64x)')
> --------------------------------------------------------------------
> (u'push', u'heapq    ', u' 0.01 ( 1.00x)  0.16 ( 1.00x)  1.85 ( 1.00x)
> 14.65 ( 1.00x)')
> (u'    ', u'OrderHeap', u' 0.04 ( 4.32x)  0.46 ( 2.81x)  4.74 ( 2.56x)
> 42.25 ( 2.88x)')
> (u'    ', u'XHeap    ', u' 0.03 ( 3.73x)  0.42 ( 2.55x)  4.34 ( 2.35x)
> 38.37 ( 2.62x)')
> --------------------------------------------------------------------
> --------------------------------------------------------------------
> (u'remove', u'RemovalHeap', u' 0.05 ( 1.00x)  0.54 ( 1.00x)  5.62 (
> 1.00x) 57.04 ( 1.00x)')
> (u'      ', u'XHeap      ', u' 0.04 ( 0.88x)  0.44 ( 0.80x)  4.41 (
> 0.78x) 43.86 ( 0.77x)')
> --------------------------------------------------------------------
> --------------------------------------------------------------------
>
>
> So as the results are not much effected apart of __init__, i think you
> should consider this.

Looks promising. I will look into it.

> Note: i'm not using collections.Counter because it is written in
> python, and from my previous experience it is slower than using
> defaultdict for this kind of purposes.

That's exactly why the __setitem__ implemenation was so slow. It did not 
use the C implemention. I think I could reduce the overhead even further 
by having my own global/thread-local integer counter. Stay tuned. ;-)

> ps: there are two error's when i ran tests with test_xheap.

Damn. I see this is Python 2 and Python 3 related. Thanks for bringing 
this to my attention. I am going to fix this soon.

> OMG why
> did you keep repititions = 10000, at first i though my pentium laptop
> is too slow that it is not printing a single line even after 20
> minutes. then i saw the number of computations are in the order of
> 10**10, how many days did it took to completely run the tests?

I don't know. I let it run overnight since I wasn't at home. :)

But you are right. I re-executed the benchmark and compared 100, 1000 
and 10000 with each other. Almost no difference at all.

I am going to reduce it to 100. So, it takes ca. 8 minutes on my machine.

Thanks for your feedback,
Sven

>
>
> On Sun, Mar 6, 2016 at 7:29 PM, Sven R. Kunze <srkunze at mail.de> wrote:
>> Hi python-list, hi Srinivas,
>>
>> I managed to implement the mark&sweep approach for fast removal from heaps.
>> This way, I got three pleasant results:
>>
>> 1) a substantial speed up!
>> 2) an improved testsuite
>> 3) discovery and fixing of several bugs
>>
>> @Srinivas I would be honored if you could have a look at the implementation:
>> https://github.com/srkunze/xheap . After all, it was your idea. I only
>> perform the sweeping step during pop and remove with the condition of yours.
>> :)
>>
>> Using the original xheap benchmark, I could see huge speedups: from 50x/25x
>> down to 3x/2x compared to heapq. That's a massive improvement. I will
>> publish an update soon.
>>
>> Best,
>> Sven
>
>