Look in src/objects.c, around line 80. This function looks up a vtable method
in a namespace. It has the name of the vtable method, as well as the number
of the vtable method.
Look how it reaches *inside* the namespace, grabs an iterator, and proceeds to
iterate through all of the keys of the namespace, trying to match the name or
the type number.
(One wonders why we bother with hashes, if O(n) is so much better for
something we do as often as looking up methods.)
For kicks, here's a slightly nicer version. There are potential improvements
there, but it's shorter, clearer, and O(1) instead of O(n). This makes a big
difference. Here's what callgrind thinks of parrot perl6.pbc
t/01-sanity/01-tap.t before the change:
Ir sysCount sysTime
--------------------------------------------------------------------------------
2,859,808,451 452 591 PROGRAM TOTALS
--------------------------------------------------------------------------------
Ir sysCount sysTime file:function
--------------------------------------------------------------------------------
370,031,493 . . hash.c:parrot_hash_get_idx
296,162,666 . . ascii.c:ascii_compare
216,535,642 . . hash.c:parrot_hash_get_bucket
205,389,756 . . string.c:string_compare
188,198,076 . . objects.c:find_vtable_meth_ns
132,994,291 . . dod.c:Parrot_dod_sweep
116,631,596 . .
namespace.pmc:Parrot_NameSpace_get_pmc_keyed_str
... and after:
Ir sysCount sysTime
--------------------------------------------------------------------------------
880,046,504 495 22,527 PROGRAM TOTALS
--------------------------------------------------------------------------------
Ir sysCount sysTime file:function
--------------------------------------------------------------------------------
98,680,680 . . dod.c:Parrot_dod_sweep
78,138,108 . . resources.c:compact_pool
70,556,241 . . ascii.c:ascii_compute_hash
49,233,260 . . string.c:string_make_direct
41,103,096 . . headers.c:get_free_buffer
30,652,923 . . resources.c:Parrot_allocate_string
30,365,471 . . strcmp.c:strcmp
The resulting work is 30% that of the previous. This is a huge amount of
execution time. (Note how even the functions in both lists do much less work
in the second one.)
Unfortunately, applying this patch fails some other tests, and I'm not sure
why. (My guess is that more PMCNULLs will help.)
I wonder if changing the Namespace PMC to store all vtable methods in such a
way that an indexed lookup will work is a benefit. It might simplify the
code even further.
-- c
=== src/objects.c
==================================================================
--- src/objects.c (revision 3994)
+++ src/objects.c (local)
@@ -81,27 +81,16 @@
static PMC*
find_vtable_meth_ns(Interp *interp, PMC *ns, INTVAL vtable_index)
{
- const INTVAL k = VTABLE_elements(interp, ns);
- PMC * const key = VTABLE_nextkey_keyed(interp, key_new(interp), ns,
- ITERATE_FROM_START);
+ const char * const meth = Parrot_vtable_slot_names[vtable_index];
+ UINTVAL const meth_len = strlen(meth);
+ STRING *key = string_from_cstring(interp, meth + 2,
+ meth_len - 2 );
+ PMC * const res = VTABLE_get_pmc_keyed_str(interp, ns, key);
- const char * const meth = Parrot_vtable_slot_names[vtable_index];
- STRING * const meth_str = string_from_cstring(interp, meth, strlen(meth));
+ if ( ! PMC_IS_NULL(res)
+ && VTABLE_isa(interp, res, CONST_STRING(interp, "Sub")))
+ return res;
- int j;
-
- for (j = 0; j < k; ++j) {
- STRING * const ns_key = (STRING *)parrot_hash_get_idx(interp,
- (Hash *)PMC_struct_val(ns), key);
- PMC * const res = VTABLE_get_pmc_keyed_str(interp, ns, ns_key);
-
- /* success if matching vtable index or double-underscored name */
- if (res->vtable->base_type == enum_class_Sub &&
- (PMC_sub(res)->vtable_index == vtable_index ||
- string_compare(interp, meth_str, ns_key) == 0))
- return res;
- }
-
return PMCNULL;
}
