All --
I've talked a few times on the list and on IRC about looking up ops
by name from their oplibs at load time. Last night I finally decided
to write some code to show what I've been talking about.
The attached patch adds a field to the oplib info structure for a
function that takes an op name and returns an integer opcode number
(or -1 if not found).
In addition, it adds some code to ops2c.pl to generate such a function
as a tree of nested switch statements that do a character-by-character
search for the name. I believe this is just about as efficient as we
can expect things to be. We find the op by name in at most one scan
over the op name (failures can fail in as few as one character compare).
On my Athlon 1.4 GHz, I've been measuring about 17 million op-by-name
lookups per second, which I believe is sufficiently fast for load-
time use. For comparison, the same machine gets about 25 mops.
Anyway, I'm attaching the patch for your amusement. This is one part
of the puzzle for building opcode tables at run time. This may go in
after some discussion with Dan, et al.
Regards,
-- Gregor
____________________________________________________________________
/ Inspiration >> Innovation >> Excellence (TM) \
Gregor N. Purdy [EMAIL PROTECTED]
Focus Research, Inc. http://www.focusresearch.com/
8080 Beckett Center Drive #203 513-860-3570 vox
West Chester, OH 45069 513-860-3579 fax
\____________________________________________________________________/
[[EMAIL PROTECTED]]$ ping osama.taliban.af
PING osama.taliban.af (68.69.65.68) from 20.1.9.11 : 56 bytes of data.
>From 85.83.77.67: Time to live exceeded
Index: ops2c.pl
===================================================================
RCS file: /home/perlcvs/parrot/ops2c.pl,v
retrieving revision 1.16
diff -a -u -r1.16 ops2c.pl
--- ops2c.pl 30 Jan 2002 04:20:37 -0000 1.16
+++ ops2c.pl 1 Feb 2002 13:36:36 -0000
@@ -46,6 +46,8 @@
my $header = "include/$include";
my $source = "${base}_ops${suffix}.c";
+my $remembered_ops = { };
+
#
# Read the input files:
@@ -76,6 +78,8 @@
my $cur_code = 0;
for(@{$ops->{OPS}}) {
$_->{CODE}=$cur_code++;
+
+ remember_op($_->full_name(), $_->{CODE});
}
my $num_ops = scalar $ops->ops;
@@ -233,6 +237,20 @@
};
/*
+** Op lookup function:
+*/
+
+static int find_op(const char * name) {
+END_C
+
+#print STDERR "Top level op chars: ", keys %$remembered_ops, "\n";
+
+generate_switch($remembered_ops);
+
+print SOURCE <<END_C;
+}
+
+/*
** op lib descriptor:
*/
@@ -243,7 +261,8 @@
$patch_version,
$num_ops,
op_info_table,
- op_func_table
+ op_func_table,
+ find_op
};
op_lib_t *
Parrot_DynOp_${base}${suffix}_${major_version}_${minor_version}_${patch_version}(void)
{
@@ -254,3 +273,70 @@
exit 0;
+
+#
+# remember_op()
+#
+
+sub remember_op
+{
+ my ($name, $code) = @_;
+ my $hash = $remembered_ops;
+
+# print STDERR "Remembering [$code] $name...";
+
+ my @chars = (split(//, $name), "\0");
+
+ while (@chars) {
+ my $char = shift @chars;
+
+# print "$char...";
+
+ if (@chars) {
+ if (!exists $hash->{$char}) {
+ $hash->{$char} = { };
+ }
+
+ $hash = $hash->{$char}
+ }
+ else {
+ $hash->{$char} = $code;
+# print "$code.\n";
+ }
+ }
+}
+
+
+#
+# generate_switch()
+#
+
+sub generate_switch {
+ my ($hash, @so_far) = @_;
+ my $index = scalar(@so_far);
+ my $indent = " " x $index;
+
+ print SOURCE <<END_C;
+${indent} switch (name[$index]) {
+END_C
+
+ foreach my $key (sort keys %$hash) {
+ print SOURCE "${indent} case '" . ($key eq "\0" ? "\\0" : $key) . "':\n";
+
+ if (ref $hash->{$key} eq 'HASH') {
+ generate_switch($hash->{$key}, @so_far, $key);
+ }
+ else {
+ print SOURCE "${indent} return " . $hash->{$key} . ";\n";
+ }
+
+ print SOURCE "${indent} break;\n";
+ }
+
+ print SOURCE <<END_C;
+${indent} default:
+${indent} return -1;
+${indent} break;
+${indent} }
+END_C
+}
Index: include/parrot/oplib.h
===================================================================
RCS file: /home/perlcvs/parrot/include/parrot/oplib.h,v
retrieving revision 1.3
diff -a -u -r1.3 oplib.h
--- include/parrot/oplib.h 1 Jan 2002 17:22:55 -0000 1.3
+++ include/parrot/oplib.h 1 Feb 2002 13:36:36 -0000
@@ -29,6 +29,7 @@
INTVAL op_count;
op_info_t * op_info_table;
void * op_func_table;
+ int (*op_code)(const char * name);
} op_lib_t;
typedef op_lib_t * (*oplib_init_f)(void);
