You should look at maintaining the %uid2msg mapping as you go along. This shouldn't be too hard since $self appears to be an object. It just means you'll have to add some code to your insert and delete methods to keep $self->{uid2msg} up to date. This is exactly what a database does when you mark a column as indexed.

In the benchmark below, this resulted in a speedup of about 9x. Of course you do have to pay a little for maintaining the %uid2msg index but I'm assuming in your case you do a lot more reading than inserting and deleting.

Once you've done that, you can further speed things up with hash slice in the return, changing 

return [ map { $uid2msg{$_} } @$uids ];

[download]
to 
return [ @uid2msg{ @$uids } ];

[download]
This doesn't make much of difference in the original version but it more than doubles performance when %uid2msg uses a precomputed index.

Here's the results of a benchmark for 1000 msg objects 

Benchmark: running hashslice, hashslice_pre, original, original_pre fo
+r at least 5 CPU seconds...
 hashslice:  5 wallclock secs ( 5.29 usr +  0.00 sys =  5.29 CPU) @ 97
+.35/s (n=515)
hashslice_pre:  5 wallclock secs ( 5.30 usr +  0.01 sys =  5.31 CPU) @
+ 1757.63/s (n=9333)
  original:  5 wallclock secs ( 5.30 usr +  0.00 sys =  5.30 CPU) @ 91
+.51/s (n=485)
original_pre:  5 wallclock secs ( 5.33 usr +  0.00 sys =  5.33 CPU) @ 
+817.07/s (n=4355)

[download]
and 10000 msg objects 
Benchmark: running hashslice, hashslice_pre, original, original_pre fo
+r at least 5 CPU seconds...
 hashslice:  5 wallclock secs ( 5.04 usr +  0.04 sys =  5.08 CPU) @  7
+.28/s (n=37)
hashslice_pre:  5 wallclock secs ( 5.27 usr +  0.01 sys =  5.28 CPU) @
+ 93.56/s (n=494)
  original:  5 wallclock secs ( 5.08 usr +  0.01 sys =  5.09 CPU) @  6
+.68/s (n=34)
original_pre:  6 wallclock secs ( 5.37 usr +  0.00 sys =  5.37 CPU) @ 
+46.93/s (n=252)

[download]
the _pre versions are hugely faster. Code below 
use Benchmark;

my $UID = 0;

my $uids = [];
my $msgs = [];

for (1..10000)
{
  UO->new;
}

my %pre_uid2msg = map { $_->uid => $_ } @$msgs;
timethese(-5,
  {
    original => sub {
      my %uid2msg     = map { $_->uid => $_ } @$msgs;
      return [ map { $uid2msg{$_} } @$uids ];
    },
    hashslice => sub {
      my %uid2msg     = map { $_->uid => $_ } @$msgs;
      return [ @uid2msg{ @$uids }];
    },
    original_pre => sub {
      return [ map { $pre_uid2msg{$_} } @$uids ];
    },
    hashslice_pre => sub {
      return [ @pre_uid2msg{ @$uids }];
    } 
  }
);

package UO;

sub new
{
  $UID += rand(1000);
  my $self = bless {uid => $UID}, shift();
  push(@$uids, $UID);
  push(@$msgs, $self);

  return $self;
}
 
sub uid
{
  my $self = shift;
  return $self->{uid};
}

[download]

edit (broquaint): changed <pre> tags to <code> tags

In reply to Re: Ordering objects using external index by fergal
in thread Ordering objects using external index by kappa

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.