Re: ADT.Heap performance poorer than just sorting and slicing

On 02/22/16 20:33, Chris Angelico wrote:

> Is there a better way to use a heap? Or should I simply accept that
> the highly optimized sort() function is generally going to be better
> for anything less than billions of rows?

Well, theoretically the sorting solution should become slower
at some point. Your heap has constant size, so the insert/pop is
constant time. On the other hand, in pike most 'special' data structures
have a relatively high extra cost. This is because operations on arrays
(and mappings for that matter) usually use special opcodes and do not
need to make (pike) function calls. This is true for both data
structures implemented in C modules and all the more for those written
in pike.
For instance, in case of the bloom filters I wrote some time ago, the
overhead for doing the function calls for lookups or inserts is about
30% of the overall runtime.

The performance benefit of speacial data structures (like ADT.Heap,
etc.) usually only comes in when applied to very special use cases and
problem sizes. Of course there is another good reason to use them, which
is readability.

Arne