Re: [code-review] Tie::Array::Sorted

On Wed, Nov 12, 2003 at 02:54:47PM +0000, Simon Cozens wrote:
> It's time I practiced what I preached; here's my latest module, before it goes
> to CPAN.

Just for interest, I decided to replace your PUSH with the naive:

	sub PUSH {
		my ($self, @elems) = @_;
		$self->{array} = [ sort (@{ $self->{array} }, @elems) ];
	}

The benchmarking results were very interesting:

             Rate  tony_oaat simon_oaat  simon_all   tony_all
tony_oaat  1.54/s         --       -91%       -94%       -99%
simon_oaat 17.3/s      1019%         --       -34%       -94%
simon_all  26.3/s      1606%        52%         --       -91%
tony_all    278/s     17903%      1508%       956%         --


These are with pushing a randomised 1000 element list onto a tied array
all at once, and one at a time.

(I also tried adding a use sort '_mergesort' but that didn't make much
difference)

This implies there's probably some cut off point where if the user is
pushing more than X items on to the list at once, it's going to be
faster (potentially significantly faster) to just delegate it off to the
builtin sort, rather than repeatedly running your own binary search. 

I have no idea how to calculate that number however.

I also don't really think it's worth doing for the module - just
throwing it out as a random observation ...

Tony