Rainer Weikusat
2024-02-14 22:37:07 UTC
Recently, I had to implement support for cancellable timers in
Perl. As maximum number of these was going to be small, I wanted to use
a sorted list as priority queue implementation. Originally, this used an
array to store the list. Unfortunately, a situation this needed to be
dealt with was that a timer supposed to fire before all others would
repeatedly be created and cancelled again with a high frequency (a HTTP
request timeout). When implemented naively, this caused the array to
grow by one element for each such timer and considering that the
complexity of the algorithm was already quadratic, this seemed like a
very undesirable property. I then implemented a bunch of algorithms for
compacting this array but these were all hideously complicated, negating
the original idea that doing something simple should be sufficient.
Then, I came up with the following idea: Anonymous arrays of size 2 make
perfect cons cells in Perl and can thus be used to implement LISP-style
linked lists. This led to a much simpler implementation of a priority
queue represented as sorted list which doesn't keep growing when
handling the situation created above.
Here's a bit of Perl code to illustrate the principle:
----
sub cons { [@_] }
sub car : lvalue
{
$_[0][0]
}
sub cdr : lvalue
{
$_[0][1]
}
sub printl
{
my ($what, $l) = @_;
print($what, "\n--\n");
while ($l) {
print(car($l), "\n");
$l = cdr($l);
}
print("\n");
}
sub do_revl
{
my $l = $_[0];
my ($first, $last);
for (cdr($l)) {
return ($l, $l) unless defined;
($first, $last) = do_revl($_);
}
$l = cdr($last) = cons(car($l));
return ($first, $l);
}
sub revl
{
(do_revl($_[0]))[0]
}
my $l = cons(1, cons(2, cons(3, cons(4))));
printl('forward', $l);
printl('reverse', revl($l));
Perl. As maximum number of these was going to be small, I wanted to use
a sorted list as priority queue implementation. Originally, this used an
array to store the list. Unfortunately, a situation this needed to be
dealt with was that a timer supposed to fire before all others would
repeatedly be created and cancelled again with a high frequency (a HTTP
request timeout). When implemented naively, this caused the array to
grow by one element for each such timer and considering that the
complexity of the algorithm was already quadratic, this seemed like a
very undesirable property. I then implemented a bunch of algorithms for
compacting this array but these were all hideously complicated, negating
the original idea that doing something simple should be sufficient.
Then, I came up with the following idea: Anonymous arrays of size 2 make
perfect cons cells in Perl and can thus be used to implement LISP-style
linked lists. This led to a much simpler implementation of a priority
queue represented as sorted list which doesn't keep growing when
handling the situation created above.
Here's a bit of Perl code to illustrate the principle:
----
sub cons { [@_] }
sub car : lvalue
{
$_[0][0]
}
sub cdr : lvalue
{
$_[0][1]
}
sub printl
{
my ($what, $l) = @_;
print($what, "\n--\n");
while ($l) {
print(car($l), "\n");
$l = cdr($l);
}
print("\n");
}
sub do_revl
{
my $l = $_[0];
my ($first, $last);
for (cdr($l)) {
return ($l, $l) unless defined;
($first, $last) = do_revl($_);
}
$l = cdr($last) = cons(car($l));
return ($first, $l);
}
sub revl
{
(do_revl($_[0]))[0]
}
my $l = cons(1, cons(2, cons(3, cons(4))));
printl('forward', $l);
printl('reverse', revl($l));