[PATCH] reduce kjs hash table bloat

[Darin Adler]

On Dec 28, 2003, at 6:58 AM, Dirk Mueller wrote:

> Please review.

This does look like a good improvement.

> +  # first, build the string table
> +  # TODO: implement tail-string optimisation
> +  my %soffset = ();
> +  my $l = 1;
> +  print "\nstatic const char $nameStringTable\[\] = {\n";
> +  foreach my $k (@keys) {
> +    print "    \"\\000$k\"\n";
> +    $soffset{$k} = $l;
> +    $l += length($k)+1;
> +  }
> +  print "    \"\\000\"\n";
> +  print "};\n\n";

Here's a version of the above that implements the tail-string 
optimization.

my %soffset = ();
print "\nstatic const char $nameStringTable\[\] = {\n";
my $s = "\0";
print "    \"\\0\"\n";
for my $k (sort { length $b <=> length $a || $a cmp $b } @keys) {
   if ($s =~ /^(.*)\Q$k\E\0/) {
     $soffset{$k} = length $1;
   } else {
     $soffset{$k} = length $s;
     print "    \"$k\\0\"\n";
     $s .= $k;
     $s .= "\0";
   }
}
print "};\n\n";

To make the table "stable", I also made it sort keys within each 
same-length group.

     -- Darin