Something like:

category|count
--------|-----
a       |22
a.b     |10
a.b.a   |2
a.b.a.a |1
a.b.a.b |1
a.b.b   |8
a.b.b.a |6
a.b.b.b |2
a.c     |12
a.c.a   |4
a.c.a.a |2
a.c.a.b |2
a.c.b   |8
a.c.b.a |6
a.c.b.b |2
[download]

.. I just typed this, it is not real data.. Hopefully I got all the math right and things add up correctly.

One way I thought about doing this was to have a separate process/server running that when fed a list of IDs would look up each of them in its cache, requerying the database for any which have grown stale/etc.

The first order of business was to determine if this mountain can be moved. My test script is:

use strict;
use Data::Dumper;
use Time::HiRes qw(time);
print STDERR "Building cats\n";
my %cats = ();
foreach my $one ('a'..'d')
{
  $cats{"a.$one"} = "a.$one";
  foreach my $two ('a'..'z')
  {
    $cats{"a.$one.$two"} = "a.$one.$two";
    foreach my $three ('a'..'z')
    {
      $cats{"a.$one.$two.$three"} = "a.$one.$two.$three";
    }
  }
}
my @keys = sort keys %cats;
my $cnt = scalar @keys;
print STDERR "Building array from $cnt possibilities\n";
my $n = 100000;
my %ids = ();
foreach my $id (0..$n)
{
  my $rand = int(rand($cnt));
  $ids{$id} = $cats{$keys[$rand]};
}
@keys = keys %ids;
$cnt = scalar @keys;
my %ret = ();
my $x = 100000;
my $start_time = time();
print STDERR "Returning mapped categories for values from a pool of $c
+nt\n";
foreach my $id (0..$x)
{
  my $cat = $ids{$id};
  if(!$ret{$ids{$id}}{'count'})
  {
    $ret{$ids{$id}}{'count'} = 0;
    $ret{$ids{$id}}{'head_count'} = 'head_count';
    $ret{$ids{$id}}{'cat_count'} = 'cat_count';
    $ret{$ids{$id}}{'subcat_count'} = 'subcat_count';
  }
  $ret{$ids{$id}}{'count'}++;
}
@keys = keys %ret;
$cnt = scalar @keys;
my $end_time = time();
my $total_time = $end_time - $start_time;
print STDERR "Built $cnt entries to start with, $total_time seconds\n"
+;
while(my($key,$val) = each(%ret))
{
  my @parts = split(/\./, $key);
  my $id = '';
  foreach my $add (@parts)
  {
    $id .= $add;
    if($id eq $key)
    {
      next;
    }
    if(!$ret{$id}{'count'})
    {
      $ret{$id}{'count'} = 0;
      $ret{$id}{'head_count'} = 'head_count';
      $ret{$id}{'cat_count'} = 'cat_count';
      $ret{$id}{'subcat_count'} = 'subcat_count';
    }
    $ret{$id}{'count'} += $ret{$key}{'count'};
    $id .= '.';
  }

}
$end_time = time();
$total_time = $end_time - $start_time;
my @sorted_keys = sort keys(%ret);
my $tot = $ret{'a'}{'count'};
print STDERR "Completed in $total_time seconds ($tot)\n";
foreach my $key (@sorted_keys)
{
  my $cnt = $ret{$key}{'count'};
    #print "KEY: $key $cnt\n";
}
print STDERR "Sleeping...\n";
sleep(1000);
[download]

Most of this script is just being used to setup the data/cache for later use. The real work I am trying to measure begins with the "Returning mapped categories for values..." and ends at the "Completed in $total_time" message.

As you can probably tell from the code I am setting up 2812 categories and testing how quickly I can map 100,001 of them.

The last sleep is just so I can look at the process and guage how much memory it is using.

So with all this being said, I get a run time of about 2.1 seconds on my development system. Do you see any obvious ways that this section of the code could be improved, considering the importance of raw performance here?

My second question is... The recipient of what this server would output would actually be a PHP script. I wrote a PHP version of this same test script, but the performance was much worse (3.6 seconds). What might be a quick and efficient means to connect this up to PHP/Apache?