[...]

Also, having Set::IntSpan (and Set::IntSpan::Fast, as per the

documentation) implemented on top of an ordered list seems to imply

the insertion and deletion times of O (N), while for a red-black tree

they're both O (log N). Though ::XS may still outperform a pure-Perl

tree-based implementation on reasonable use cases.

So, I've ran a simplistic benchmark over the three, which is,

roughly (the exact code is as shown below):

# my ($size, $iter) = (4194304, 5);

my @vec

= (map { int (rand ($size)); } (1 .. $size));

my $set

= Set::IntSpan::Fast->new ();

$set->add ($_)

foreach (@vec);

It took awhile to complete, but the results seem to suggest that

Tree::Range::RB is indeed faster than both Set::IntSpan::Fast

and Set::IntSpan, should the problem size be sufficiently large.

Size: 4194304 Iterations: 5 (negative is time in seconds)

Tree::Range::RB: 8003 wallclock secs (7944.34 usr 5.88 sys + 0.00 cusr 0.00 csys = 7950.22 CPU) @ 0.00/s (n=5)

Set::IntSpan: 17759 wallclock secs (17556.78 usr 10.12 sys + 0.00 cusr 0.00 csys = 17566.90 CPU) @ 0.00/s (n=5)

Set::IntSpan::Fast: 19318 wallclock secs (19060.33 usr 9.25 sys + 0.00 cusr 0.00 csys = 19069.58 CPU) @ 0.00/s (n=5)

s/iter Set::IntSpan::Fast Set::IntSpan Tree::Range::RB

Set::IntSpan::Fast 3814 -- -8% -58%

Set::IntSpan 3513 9% -- -55%

Tree::Range::RB 1590 140% 121% --

44565.74user 26.12system 12:31:28elapsed 98%CPU (0avgtext+0avgdata 972212maxresident)k

224inputs+0outputs (1major+316600minor)pagefaults 0swaps

Or did I make some silly mistake with that?

TIA.

### Code:

use common::sense;

use Benchmark qw (cmpthese timethis);

use Scalar::Util qw (looks_like_number);

require Set::IntSpan;

require Set::IntSpan::Fast;

require Tree::Range::RB;

my ($size, $iter)

= (map { (/^0/ ? oct ($_) : $_); } (@ARGV));

$size

//= 0x100000;

$iter

//= -521;

looks_like_number ($size)

or die ($size, ": Size given is not a number\n");

looks_like_number ($iter)

or die ($iter, ": Iterations count given is not a number\n");

warn ("Size: ", 0 + $size, " Iterations: ", 0 + $iter,

" (negative is time in seconds)\n");

my @vec

= (map { int (rand ($size)); } (1 .. $size));

sub xcmp {

## .

$_[0] <=> $_[1];

}

sub xeq {

## .

$_[0] eq $_[1];

}

my $trr

= timethis ($iter,

sub {

my $rat_opt = {

"cmp" => \&xcmp,

"equal-p" => \&xeq

};

my $value

= [ "*value*" ];

my $rat

= Tree::Range::RB->new ($rat_opt);

$rat->range_set ($_, 1 + $_, $value)

foreach (@vec);

},

"Tree::Range::RB", "all");

my $sis

= timethis ($iter,

sub {

my $set

= Set::IntSpan->new ();

$set->insert ($_)

foreach (@vec);

},

"Set::IntSpan", "all");

my $sisf

= timethis ($iter,

sub {

my $set

= Set::IntSpan::Fast->new ();

$set->add ($_)

foreach (@vec);

},

"Set::IntSpan::Fast", "all");

cmpthese ({

"Set::IntSpan" => $sis,

"Set::IntSpan::Fast" => $sisf,

"Tree::Range::RB" => $trr

},

"all");