C linked lists in Perl

[Ted Zlatanov]

TZ> Lisp pretty much is all about linked lists, they are built into
TZ> everything.

UG> sure but other than car and cdr (great names! and i know why) and dotted
UG> pair, it doesn't have any builtin support for linked lists. you still
UG> need to work at making them with primitives.


s> In lisp a list can be built from cons cells. It is not a data type in
s> lisp any more than in C.

I really don't know how much more "built-in" linked lists can be than
what you find in Lisp, considering that code and data both are lists and
treated as such by the language, and you can construct either
dynamically. At this point you're arguing that with Lisp you have an
assembled band saw (vs. Perl's Swiss Army knife or Java's diesel-powered
hammer-screwdriver) but you can't use it until you plug it in. Well,
yeah, but that is not an argument worth having.

Ted

 

[Uri Guttman]

TZ> Lisp pretty much is all about linked lists, they are built into
TZ> everything.

UG> sure but other than car and cdr (great names! and i know why) and dotted
UG> pair, it doesn't have any builtin support for linked lists. you still
UG> need to work at making them with primitives.


s> In lisp a list can be built from cons cells. It is not a data type in
s> lisp any more than in C.

TZ> I really don't know how much more "built-in" linked lists can be than
TZ> what you find in Lisp, considering that code and data both are lists and
TZ> treated as such by the language, and you can construct either
TZ> dynamically. At this point you're arguing that with Lisp you have an
TZ> assembled band saw (vs. Perl's Swiss Army knife or Java's diesel-powered
TZ> hammer-screwdriver) but you can't use it until you plug it in. Well,
TZ> yeah, but that is not an argument worth having.

yeah, like arguing with brick walls over PERL vs Perl.

what i meant about builtin was stuff that does insert/delete/lookup
stuff. any linked list thing needs those and related funcs to be
useful. even lisp doesn't do that directly. but no matter.

uri

 

[Joost Diepenmaat]

what i meant about builtin was stuff that does insert/delete/lookup
stuff. any linked list thing needs those and related funcs to be
useful. even lisp doesn't do that directly. but no matter.

But (common) lisp *does* provide functions that do just that.

 

[szr]

i wouldn't call that part of the lang. but some would.

I would call it a library or an extension (not like a Perl Module that
comes bundled with Perl), which, IIRC, uses a process not unlike C to
create linked lists from primitives; it just gives you a pre-made
interface.

 

[Gordon Corbin Etly]

....

yeah, like arguing with brick walls over PERL vs Perl.

My thoughts exactly. But you don't see me going around random threads
attempting to incite a flame war, when the very problem you complain
about stems from your own inability to be reaonable when it comes to
things you have a hard view on.

 

[szr]

[...]
I really don't know how much more "built-in" linked lists can be than
what you find in Lisp, considering that code and data both are lists
and treated as such by the language, and you can construct either
dynamically. At this point you're arguing that with Lisp you have an
assembled band saw (vs. Perl's Swiss Army knife or Java's
diesel-powered hammer-screwdriver) but you can't use it until you
plug it in. Well, yeah, but that is not an argument worth having.

You forgot PHP's nuclear-powered 10,000 piece rachet set.

 

[Uri Guttman]

GCE> ...

GCE> My thoughts exactly. But you don't see me going around random threads
GCE> attempting to incite a flame war, when the very problem you complain
GCE> about stems from your own inability to be reaonable when it comes to
GCE> things you have a hard view on.

brickhead ignored. especially since you never talk perl.

uri

 

[szr]

I guess like almost everybody, I like to discuss (argue) the merits
of different technologies. In my world, the big two are Java and
ColdFusion. Recently, we had someone with a background in embedded
systems who has been advocating C. The conversation goes something
like this:

him - Does Perl have linked lists?
me - No.

Perl does have linked lists at least as much as C does.

my $ll = [ 'bla', [ 'blie', [ 'bloe' ]]];

etc.

But expect perl's garbage collector to get in your face if you create
giant linked lists. Not that you'd want to do that, anyway.

Why would the GC get in the way? In a nutshell, it doesn't free
something until no one is referring to it anymore (the ref-count is
zero), so I'd imagine there would be no problem, or have you run into
issue in certain circumstances?

 

[Gordon Corbin Etly]

brickhead ignored. especially since you never talk perl.

Once again spilling falsehoods. Clearly you are egging this on, not only
by refusing to see any reason but by baiting in random threads. You, one
who enjoys dictating "netiquette" to others, then you turn around and
blatantly flame bait. Wonderful example you're making for others...

 

[Martijn Lievaart]

and i want to kill the cow-orker who said perl has no linked lists. or
better, make him code in cobol for 10 years!

Better yet, make him implement linked lists in COBOL!

M4

 

[Martijn Lievaart]

The main reason for C++ was to hide pointers from your friend.
Programmers cannot be trusted doing their own memory allocation or
linked lists. Tell him to do what everyone else does, which is to
attack perl on performance.

That reminds me of an old truism:

C programmers know that memory management is to important to leave it to
the OS. Perl programmers know that memory management is to important to
leave to to the programmer.

As usual, the truth is somewhere in the middle, but I would say
definitely somewhere the perl side[1].

M4

[1] In the past 5 years I had one (1!) program that did not perform well
enough in Perl. It did a lot of pack/unpack, which could be replaced by
direct member access in C. Obviously, we solved the problem by throwing
faster hardware at it.

 

[sln]

I guess like almost everybody, I like to discuss (argue) the merits of
different technologies. In my world, the big two are Java and
ColdFusion. Recently, we had someone with a background in embedded
systems who has been advocating C. The conversation goes something
like this:

him - Does Perl have linked lists?
me - No.
him - Therefore, C is better than Perl because it has linked lists.
me - But Perl has other data structures that are easier to use than
linked lists.
him - So what? Perl still doesn't have linked lists.

I've never studied linked lists and certainly never coded one (in C or
anything else) but it aroused my curiosity. So after searching on
c.l.p.m. and online, I decided to see if I couldn't do a linked list
in Perl. My first thought is to do something like this:

%linked_list{$key} = { prev => $linked_list{$prev_key}{prev},
value => $value,
next => $linked_list{$next_key}
{next} };

I know that most people will think I'm an absolute moron for thinking
about this (and they likely would be right), but CAN you do a linked
list in Perl (never mind that you would never want to), and if so, how
would you go about it?

My motive is to say to my C friend, "Nya, nya, nya."

Thanks, CC.

A linked list element is a Node, commonly containing a Header, that
points to the previous and next header. Within the node, below the
header, contains data.

What on earth could that be used for, and why on earth would you
need to code that?

Why would you need a linked list at all, in any language?

sln

 

[Jürgen Exner]

A linked list element is a Node, commonly containing a Header, that
points to the previous and next header.

For a double-linked list, yes. But there are also single-linked list
which are missing the 'previous' link.

Within the node, below the header, contains data.

What on earth could that be used for, and why on earth would you
need to code that?
Why would you need a linked list at all, in any language?

Whenever you need a sequence of data elements a linked list is one
possible implementation. As others have pointed out in Perl you would
usually prefer an array.
However if your programming language does not support dynamically
growing and shrinking arrays as well as efficient insertion and deletion
in the middle of an array then those are out of the question and you
have no choice but to use a linked list.

Not to mention that a single-linked list is the most simple dynamic data
type and therefore is often used as the first step to introduce more
complex data types like trees and graphs.

jue

 

[Dr.Ruud]

Martijn Lievaart schreef:

Uri Guttman:

Better yet, make him implement linked lists in COBOL!

Here is an "over-the-heap" implementation:
http://www.ibmmainframes.com/about20758.html
(150+ lines, incl. alloc and free and such)


Some articles:
http://home.swbell.net/mck9/cobol/tech/linklist.html

 

[Joost Diepenmaat]

Why would the GC get in the way? In a nutshell, it doesn't free
something until no one is referring to it anymore (the ref-count is
zero), so I'd imagine there would be no problem, or have you run into
issue in certain circumstances?

The problem is that perl's CG is buggy and relatively slow for large
linked lists (or any kind of deeply nested structure):

#!/usr/local/bin/perl -w
use strict;
$|=1;

sub test {
print "Building list\n";
my $head = [];
my $tail = $head;
for (0 .. 1000000) {
$tail = ($tail->[1] = [$_]);
}
print "Exiting sub\n";
}

test();
print "Exiting program\n";

ouput:

Building list
Exiting sub
Segmentation fault

This is perl, v5.10.0 built for i686-linux-thread-multi

 

[Martijn Lievaart]

Martijn Lievaart schreef:

Here is an "over-the-heap" implementation:
http://www.ibmmainframes.com/about20758.html
(150+ lines, incl. alloc and free and such)

OH! MY! GOD! Even sendmail.cf is readable compared to that.

M4

 

[Martijn Lievaart]

The problem is that perl's CG is buggy and relatively slow for large
linked lists (or any kind of deeply nested structure):
(snip)

This is perl, v5.10.0 built for i686-linux-thread-multi

[martijn@cow ~]$ perl -e '#!/usr/local/bin/perl -w

use strict;
$|=1;

sub test {
print "Building list\n";
my $head = [];
my $tail = $head;
for (0 .. 1000000) {
$tail = ($tail->[1] = [$_]);
}
print "Exiting sub\n";
}

test();
print "Exiting program\n";
'

Building list
Exiting sub
Segmentation fault
[martijn@cow ~]$ perl -v

This is perl, v5.8.8 built for x86_64-linux-thread-multi

Same on v5.8.8 built for i386-linux-thread-multi

M4

 

[Ted Zlatanov]

s> [...]
I really don't know how much more "built-in" linked lists can be than
what you find in Lisp, considering that code and data both are lists
and treated as such by the language, and you can construct either
dynamically. At this point you're arguing that with Lisp you have an
assembled band saw (vs. Perl's Swiss Army knife or Java's
diesel-powered hammer-screwdriver) but you can't use it until you
plug it in. Well, yeah, but that is not an argument worth having.

s> You forgot PHP's nuclear-powered 10,000 piece rachet set.

I tried to resist but you made me do it...

Emacs Lisp = the band saw everyone has lost a fingertip to
C = a club dotted with razor blades dipped in iodine "for better lubrication"
C++ = machine gun that shoots dandellions
Python = a Swedish Army knife
COBOL = enough rubber bands WILL shoot you to the moon, apparently
Fortran = a calculator embedded in a rock
HTML/CSS/Javascript = a flail that keeps flinging back at you
APL = a unicorn horn
Ruby = Lisp's band saw and Perl's army knife used to decorate a princess
birthday cake ("so cute!")

Ted

 

[sln]

For a double-linked list, yes. But there are also single-linked list
which are missing the 'previous' link.


Whenever you need a sequence of data elements a linked list is one
possible implementation. As others have pointed out in Perl you would
usually prefer an array.
However if your programming language does not support dynamically
growing and shrinking arrays as well as efficient insertion and deletion
in the middle of an array then those are out of the question and you
have no choice but to use a linked list.

Not to mention that a single-linked list is the most simple dynamic data
type and therefore is often used as the first step to introduce more
complex data types like trees and graphs.

jue

Yes indeed. In fact all OS's incorporate linked lists for dynamic memory manangement.
A series of discontinuous blocks of data all linked together in lists.

Languages are built upon these OS intrinsics. By all accounts, the only way
to grow and shrink "array's". Deallocating memory is as simple as destroying a list,
giving up/returning chunks of address space back to the free pool, another list.

Most languages have collection layers that negate the need for linked lists.
At higher levels, lists are common and are supported by API that do add/insert/remove
management (node manipulation).

Scripting languages built on C/C++, like Perl, would invoke tremendous overhead doing
linked lists.

To me, unless your doing system programming, doing linked lists is just an educational
experience.

sln

 

[Peter J. Holzer]

The problem is that perl's CG is buggy

Define "buggy".

and relatively slow for large linked lists (or any kind of deeply
nested structure):

That program doesn't demonstrate that it is "relatively slow". You would
have to compare it to something else relative to which it is slow.

#!/usr/local/bin/perl -w
use strict;
$|=1;

sub test {
print "Building list\n";
my $head = [];
my $tail = $head;
for (0 .. 1000000) {
$tail = ($tail->[1] = [$_]);
}
print "Exiting sub\n";
}

test();
print "Exiting program\n";

ouput:

Building list
Exiting sub
Segmentation fault

That seems to be related to the stack size (if I reduce the stack size
the crash occurs with smaller lists). So without looking at the code I'd
guess that the GC calls itself recursively on all referenced objects
after freeing an object. Since on most OSs the stack is relatively small
(e.g., 8 MB on Linux/x86), you run out of stack space after a few 10000
nesting levels. Should be relatively simple to fix, but who in his right
mind builds datastructures with 100000 nesting levels?

hp