Do you see how popular linked lists are?

I see. As it is impossible to overlook 🤪😎 And I’m aware of how important they are. Best regards, Karl.

«The Crux of the Biscuit is the Apostrophe»

> And I’m aware of how important they are

Actually, linked lists have recently become completely unimportant! :) ... due to the mind-bogglingly high cost of cache misses on modern memory architectures. Linked lists tend to maximize cache misses, at least compared to the much more compact vectors.

This is analysed in more detail in The 10**21 Problem (Part 3) where Stroustrup noted that on modern memory architectures, C++ linked lists are typically 50 to 100 times slower than vectors.

Update: Much later I remembered Re: Data structures in Perl. A C programmer's perspective. (vector vs linked list performance).

Greetings, karlgoethebier

How fortunate for the kids to have you as a tutor.

Many years ago before releasing MCE::Shared::Ordhash, I attempted a doubly-linked list, pure-Perl ordered hash implementation. It was based on Tie::Hash::Indexed. It lives in my gist repo Indhash.pm, but never released to CPAN. That's because it consumed more memory then I had wished for.

My goal at the time was making an ordered hash implementation that was as memory efficient as Hash::Ordered but wished for performance closer to Tie::Hash::Indexed, particularly deletions. Well, reached that goal and released MCE::Shared::Ordhash.

In the event the curriculum requires a doubly-linked list, see the TIEHASH, STORE, FETCH, and DELETE routines in Tie::Hash::Indexed and Indhash.pm (gist link above).

Tie::Hash::Indexed now works with recent Perl releases. Thank you, Slaven Rezić and @mhx. It has been a while and ran the bench script now that Tie::Hash::Indexed is working again. Look at Tie::Hash::Indexed go :). As mentioned in the prior post, MCE::Shared::Indhash lives in gist.

bench_oh.pl in gist

$ perl bench_oh.pl 1   # memory efficient and fast
Tie::Hash::Indexed
store  : 0.858 secs.
delete : 1.544 secs.
elapse : 2.401 secs.

$ perl bench_oh.pl 2   # not memory efficient, but fast for pure-Perl 
+impl.
MCE::Shared::Indhash
store  : 1.271 secs.
delete : 2.197 secs.
elapse : 3.468 secs.

$ perl bench_oh.pl 3   # memory efficient and fast for being pure-Perl
MCE::Shared::Ordhash
store  : 1.048 secs.
delete : 2.829 secs.
elapse : 3.877 secs.

$ perl bench_oh.pl 4   # memory efficient, but deletions taking longer
Hash::Ordered
store  : 1.076 secs.
delete : 4.037 secs.
elapse : 5.113 secs.
[download]

Sharing using the TIE interface.

Locking is necessary when performing FETCH followed by STORE; i.e. ++.

use strict; use warnings;

use MCE::Hobo;
use MCE::Shared;

use Tie::Hash::Indexed;
use Hash::Ordered;
use MCE::Shared::Ordhash;

tie my %hi, 'MCE::Shared', { module => 'Tie::Hash::Indexed' }, total =
+> 0;
tie my %ho, 'MCE::Shared', { module => 'Hash::Ordered' }, total => 0;
tie my %oh, 'MCE::Shared', { module => 'MCE::Shared::Ordhash' }, total
+ => 0;

sub task {
    my $id = shift;
    $hi{$id} = $id; tied(%hi)->lock; $hi{total}++; tied(%hi)->unlock;
    $ho{$id} = $id; tied(%ho)->lock; $ho{total}++; tied(%ho)->unlock;
    $oh{$id} = $id; tied(%oh)->lock; $oh{total}++; tied(%oh)->unlock;
}

MCE::Hobo->create('task', $_) for 1..4;
MCE::Hobo->wait_all();

my (@k, @v);
@k = keys %hi; print "hi keys: @k\n";
@k = keys %ho; print "ho keys: @k\n";
@k = keys %oh; print "oh keys: @k\n";
@v = values %hi; print "hi vals: @v\n";
@v = values %ho; print "ho vals: @v\n";
@v = values %oh; print "oh vals: @v\n";

__END__
hi keys: total 1 2 3 4
ho keys: total 1 2 3 4
oh keys: total 1 2 3 4
hi vals: 4 1 2 3 4
ho vals: 4 1 2 3 4
oh vals: 4 1 2 3 4
[download]

Sharing using the OO interface.

Locking isn't necessary when calling OO methods, further reducing latency.

use strict; use warnings;

use Tie::Hash::Indexed;
use Hash::Ordered;
use MCE::Shared::Ordhash;

use MCE::Hobo;
use MCE::Shared;

my $hi = MCE::Shared->share({ module => 'Tie::Hash::Indexed' }, total 
+=> 0);
my $ho = MCE::Shared->share({ module => 'Hash::Ordered' }, total => 0)
+;
my $oh = MCE::Shared->share({ module => 'MCE::Shared::Ordhash' }, tota
+l => 0);

sub task {
    my $id = shift;
    $hi->set($id => $id); $hi->preinc('total');
    $ho->set($id => $id); $ho->preinc('total');
    $oh->set($id => $id); $oh->incr('total');
}

MCE::Hobo->create('task', $_) for 1..4;
MCE::Hobo->wait_all();

my (@k, @v);
@k = $hi->keys; print "hi keys: @k\n";
@k = $ho->keys; print "ho keys: @k\n";
@k = $oh->keys; print "oh keys: @k\n";
@v = $hi->values; print "hi vals: @v\n";
@v = $ho->values; print "ho vals: @v\n";
@v = $oh->values; print "oh vals: @v\n";

__END__
hi keys: total 1 2 3 4
ho keys: total 1 2 3 4
oh keys: total 1 2 3 4
hi vals: 4 1 2 3 4
ho vals: 4 1 2 3 4
oh vals: 4 1 2 3 4
[download]

I'm delighted that Tie::Hash::Indexed is working again, plus includes complementary OO methods. The module may be shared and works great.

Update: I encountered a bug with Hash::Ordered. It's an old issue from 2016. Added a comment to issue #6.

«…very basic concept…using it internally…»

Exactly because of that I asked. Best regards, Karl

«The Crux of the Biscuit is the Apostrophe»

Yes, linked lists are important.
Some years ago, I did a C project which used a very dumbed down version of a Perl hash table. Not as sophisticated of data types, but the basic algorithm and structure are present including how Perl doubles a hash array when it needs to do so. Topics of interest: dynamic memory allocation, structures, array of pointer to linked lists, linked lists. If it would help this guy study, msg me with an email addr and I will find it and send it to you.

Update: Karl did take me up on the offer and I sent him my release version of MemTracker.h. I wrote this for a local CIS department in 2013. You include this .h file into your gcc, g++4 or MS dev 2008 and 2010 (C or C++) program and it uses pre-processor directives to "take over" and monitor memory allocation. Getting the preprocessor stuff right so that it worked with 4 compliers was non-trivial. It uses something very similar to a Perl hash table for its main data structure. Runs like a rocket (performance impact insignificant) and prints source code line numbers of say allocations which are not later freed before program exit. Plenty of dynamic stacks, lists, etc in this thing. It helps students monitor/debug creation of such things and of course uses such things itself! Current version only works with a single compilation unit, but that is all that was needed for beginning C++. Karl's student will understand some C if he understands this thing.