[Perl6-internals] keyed vtables and mmd

Only one question. What's the performance hit likely to be and is there
any way around that performance hit for code that doesn't want to take
it?

I'm not sure of the hit--an MMD version of the perl base scalar PMCs
is faster than the non-mmd version in some tests. I fully expect that
can't hold, though. And no, there's no way around it--if we do this
everyone pays. (OTOH, all perl PMCs are supposed to check anyway,
though this is a cost we weren't necessarily paying)

(On the other hand, if we do this the JIT may be able to play some
inlining games, which is worth thinking about before we set the
interface in stone)

Since we're specifically talking about Perl here (and probably not Perl
5, since its overloading model is baroque and probably has to be managed
by the compiler, not Parrot), I was under the impression that for types
that are non-objecty, they would NOT check. Specifically:

my int $x = 1;
my int $y = 2;
my int $z = $x + $y;

would be guaranteed to perform integer addition in the fastest possible
form (though it might store $x and $y in a PMC or an INT, that's not the
programmer's concern, only that his addition is going to be addition and
no one's going to rip that out from under him).

Certainly in Java that's going to be the case. I don't know Ruby or
Python well enough to comment.

Actually perl 5's overloading gets handled this way too. Overloaded
operations *can't* be handled by the compiler in dynamic languages,
and none of then do so.
Types that are non-PMC won't check. PMC types will.

Hmmm, I thought we were on the same page here, but I'll back up and
define terms if needed.

When I talk about a runtime construct being "handled by the compiler" vs
"handled by parrot", I mean that the compiler will have to generate code
that knows how to deal with the construct, rather than relying on
Parrot's native constructs. That might be (as is the case with Perl 5
right now) that the construct is built into a runtime library, or it
might be that the compiler generates special code inline.

You seem to be replying to a point I would not make, e.g., that the
compiler would have to somehow determine at compile-time what would
happen. Clearly that's impossible.
Ok, so in Boston you suggested that every variable declared by a high
level language would have to be a PMC and that INT registers for example
were only for the compilers and Parrot libraries to use... would that
not be the case for a "Java int" or a "Perl 6 int" and/or has it changed
since then?

I'm not arguing anything here, just trying to wrap my head around the
scope of this change's impact.

Right. That can't, and doesn't, work.

Take a look at pp.c (I think--might be pp_hot.c) in perl 5's source
distribution to see how perl 5 handles it now. Basically every
function that can be overloaded must first check to see if either
side does and, if so, does the dispatch. That's what parrot has to
do, only we skip the checks and just go dispatch. (Which is faster,
generally. Go figure)

We lose a bit of speed over the current parrot scheme of leaving it
to the vtable function to check, but given that all the major
languages would have to check anyway, it's not any loss, really. And
saves a dispatch as we don't have to do the vtable func dispatch.
Right, but you're assuming you can put this in the RTL. You can't,
and it isn't there in any of the other dynamic languages that do
overloading. (Which is what this is, essentially)
Nope. If it's in a namespace or pad it's got a backing PMC, otherwise
the introspective namespace walking stuff won't work right. The only
difference there is that the compiler will be able to emit shortcut
code and skip the whole PMC thing in operations in those cases where
it's not needed.

Ok, nuff said. I think there are slightly too many definitions that
we're not agreeing on (though, I suspect if we ironed those out, we'd be
in violent agreement).

As for INT/PMC thing.... I'm pretty sure all of my concerns come down
to: compilers can really screw each other over, but then we knew that,
and there will have to be conventions to prevent it.

As Dan already said there is no performance hit (at least if the MMD
tables don't blow the caches).

Doing 5 M divide vtables[1] on Athon 800, -O3 build:

$ parrot -j mmdp.imc # 10 / 2
PerlInt 1.048340
Integer 1.097163 # left arg MMD, right is VTABLE_get_integer [2]

Integer 1.039819 # left+right MMD, both use PMC_int_val(pmc) [3]

$ parrot -j mmdp.imc # 10 / 3
PerlInt 1.503322 # LHS type morph to PerlNum
Integer 1.039199

The relevant function in integer.pmc has one of the follwing lines inside:

static void
integer_divide(Parrot_Interp interp, PMC* self, PMC* value, PMC* destination){
INTVAL result;
// result = PMC_int_val(self) / VTABLE_get_integer(interp, value); //[2]
result = PMC_int_val(self) / PMC_int_val(value); //[3]
VTABLE_set_integer_native(interp, destination, result);
}

leo

[1]
$ cat mmdp.imc
.pcc_sub _main prototyped
.const int max = 5000000
.const int val = 3 # or 2
$P0 = new PerlInt
$P1 = new PerlInt
$P2 = new PerlInt
$P1 = 10
$P2 = val
.local float start
start = time
.local int i
i = 0
lp1:
$P0 = $P1 / $P2
inc i
if i < max goto lp1
$N0 = time
$N0 -= start
print "PerlInt "
print $N0
print "\n"


$P0 = new Integer
$P1 = new Integer
$P2 = new Integer
$P1 = 10
$P2 = val
.local float start
start = time
.local int i
i = 0
lp2:
$P0 = $P1 / $P2
inc i
if i < max goto lp2
$N0 = time
$N0 -= start
print "Integer "
print $N0
print "\n"
end
.end

Good stuff! One thing leaps to mind when you mention the cache though...
keep in mind that blowing L2 cache (which we might be in no danger of
doing at all, but I'm just bringing it up) might be WORSE than you would
think on P4 and beyond because of hyperthreading.

Well, turn off ARENA_DOD_FLAGS and force a few DOD runs with one million
PMCs in some array. Run valgrind [1] on that. Then turn on
ARENA_DOD_FLAGS again and watch the difference :)

I know that cache misses have worse impact on either faster CPUs or with
HT. Valgrind docs state that a L2 miss is worth around 200 CPU cycles, where
you can do something meaningful - e.g. avoid that miss.

leo

[1]
$ cat vgcp
valgrind --skin=cachegrind parrot "$@"

Leopold Toetsch wrote:

[ another MMD performance compare ]

Just an update. Last benchmark still called MMD via the vtable. Here is
now a compare of calling MMD from the run loop:

$ parrot -C mmd-bench.imc
vtbl add PerlInt PerlInt 1.072931
vtbl add PerlInt Integer 1.085116
MMD bxor PerlInt PerlInt 0.849723
MMD bxor PerlInt Integer 0.989387

$ parrot -j mmd-bench.imc
vtbl add PerlInt PerlInt 0.685505
vtbl add PerlInt Integer 0.692237
MMD bxor PerlInt PerlInt 0.628078
MMD bxor PerlInt Integer 0.790955

JITed vtable add calls directly into the vtable, while the MMD <bxor> is
still a function that calls mmd_dispatch.

Compiled with -O3, 5 Meg operations on Athlon 800.

leo

Sounds good. C<add_p_p_p> and friends isn't really fast now due to some
type checks. And that's only for Perl types. Would be much more for
multiple HLL. Putting in specialized MMD functions for each type
combination is better, but can cause huge tables for too much
[types*vtable_entries]**2.

But anyway I think it's the right thing todo.

But we have to consider "utility" PMCs like C<Env> or C<*struct> that
don't really match the concept of MMD.

leo

For those we can either lie about their type, or ignore them and use
fallback behaviour for them.

Another long running discussion: do we need duplicate mmd tables.
Here is a proof of concept to avoid it:

#v+
--- parrot/src/mmd.c Thu Apr 29 07:49:31 2004
+++ parrot-leo/src/mmd.c Thu Apr 29 15:40:58 2004
@@ -81,14 +81,21 @@
right_type + left_type;
real_function = (pmc_mmd_f)*(interpreter->binop_mmd_funcs->mmd_funcs[function] + offset);
}
- if (real_function) {
+ if ((UINTVAL)real_function & 1) {
+ sub = (PMC*)((UINTVAL)real_function & ~1);
+ Parrot_runops_fromc_args_save(interpreter, sub, "vPPP",
+ left, right, dest);
+ }
+ else
(*real_function)(interpreter, left, right, dest);
+#if 0
} else {
/* Didn't find it. Go look for a bytecode version */
offset = interpreter->binop_mmd_funcs->x[function] *
right_type + left_type;
sub = (void*)((pmc_mmd_f)*(interpreter->bytecode_binop_mmd_funcs->mmd_funcs[function] + offset));
}
+#endif
}

/*
@@ -473,6 +480,16 @@

offset = interpreter->binop_mmd_funcs->x[type] * right_type + left_type;
*(interpreter->binop_mmd_funcs->mmd_funcs[type] + offset) = funcptr;
+}
+
+void
+mmd_register_sub(Interp *interpreter,
+ INTVAL type,
+ INTVAL left_type, INTVAL right_type,
+ PMC *sub)
+{
+ PMC *fake = (PMC*)((UINTVAL) sub | 1);
+ mmd_register(interpreter, type, left_type, right_type, D2FPTR(fake));
}

/*

#v-

This wouldn't really slow down MMD in C. The current if(func) isn't
really necessary as empty slots are filled with the default function ptr.

I don't think that we need a (23 * 56 * 56 * 4 + some bytes) table
duplication (this is for current types only ...).

.sub _main
.include "pmctypes.pasm"
.include "vtable_constants.pasm"

# fake mmd_vtregister / mmdfunc opcode
.local pmc NULL
null NULL
.local pmc mmd_register
mmd_register = dlfunc NULL, "mmd_register_sub", "vIiiiP"
.local pmc divide
divide = global "Integer_divide_PerlInt"
.pcc_begin prototyped
.arg .VTABLE_DIVIDE
.arg .Integer
.arg .PerlInt
.arg divide
.nci_call mmd_register
.pcc_end
# done

$P0 = new PerlInt
$P1 = new Integer
$P2 = new PerlInt
$P1 = 10
$P2 = 3
$P0 = $P1 / $P2
print $P0
print "\n"
end
.end

.sub Integer_divide_PerlInt
.param pmc left
.param pmc right
.param pmc lhs
$P0 = new PerlInt
$I0 = left
$P0 = $I0
lhs = $P0/right # don't call divide Integer/PerlInt here
$N0 = lhs
floor $N0
lhs = $N0
.end

leo

Dunno. Don't care, really--I was throwing in two tables as
proof-of-concept just to get things going. We also don't need full
tables either--there are a number of games we can play to compact the
tables a lot.

FWIW, here's a pointer to a paper on it:

http://www.cs.dartmouth.edu/reports/abstracts/TR2001-404/

As there can be just one entry for a (func, left, right) triple we don't
need two tables. This all simplifies ...
... such compression too. Only one table to work on. The table lookup is
simpler too.

BTW: which of these opcodes:

ops/object.ops:=item B<makemmd>(in PMC, in INT)
ops/object.ops:=item B<mmdfunc>(in INT, in PMC, in PMC, in PMC)
ops/object.ops:=item B<mmddispatch>(out PMC, in INT, in PMC, in PMC)
ops/pmc.ops:=item B<mmdvtregister>(in INT, in INT, in INT, in PMC)
ops/pmc.ops:=item B<mmdvtfind>(out PMC, in INT, in INT, in INT)

should actually be implemented? Seems to exist some redundancy ;)

leo

Yep. We can look at it later as we need to. The bit test, twiddle,
and branch is going to be faster than the dual-table option. Faster
still when we can hoist the checking into the op body itself.
Yeah. Now that this is working I'll thump it into shape.

Oh, right, and... this is really, really evil. Which is why I just
put it in. :)

And just to add extra evil, now it works. Seems that gcc does *not*
align function pointers by default. (Though it does with -O2 or
higher) Well... now it does, at least on linux.

I think we may need to add compiler-specific hints as well as
platform-specific ones.

Almost:
$ perl Configure.pl --maintainer --floatval=double --verbose-step=Determ
...
cc1: Invalid option `-falign-functions=8'

This one want -malign-functions=3

Please also check, if it's a power of 2 thingy.

leo

The manpage made it sound like it was an absolute thing, but I can
see it being a power-of-two number. GCC 3.3.3 likes the 8, so I
hadn't noticed. I've a =3 build going now--if it tests OK I'll commit
the change.

It's still the issue the -falign-some doesn't exist on 2.95.x. Also
config/auto/gcc.pl is the place to mangle such flags.

leo

I've now created a new config key:

HAS_aligned_funcptr => 1

which creates

#define PARROT_HAS_ALIGNED_FUNCPTR 1

This key is already set for GCC. So, if you are using another compiler
please check the docs, if functions are aligned at least at an even byte
boundary and if yes, set this config var (see config/auto/gcc.pl).

If this define isn't set, we have to use "plan B", which is a compare of
the function pointer address against the PMC arenas low and high
addresses - not too costly but still some slow-down.

I really don't know how to probe for it: you could test 100 functions
find them all aligned and the 101th isn't. We could create a check
in the function registering routines, though.

leo

*g*

Should I cleanup and implement the rest? And which opcode of the
(duplicated? mm* ops?

leo

I'll go patch this up. I'm halfway through as it is, so I might as
well finish it. (This is all prompted by the work project, so they
might as well spring for the time to fix it :)

This *all* includes vtable functions like add_int() or add_float() too,
I presume. For these we have left argument dispatch only. But what is
the right argument? A PerlInt, TclInt, PyInt (or ..Float)? Or is it
assumed to be the same as the left argument type?

leo

leo

The three options are promotion to PMC, leaving these in the vtable,
or having a mmd-variant for them.

I'm up for the mmd-variant version. We just have a one-dimensional
table for PMC/int, PMC/float, and PMC/string functions and have the
ops directly dispatch to it. Seems simpler than stuffing the
functions into the base MMD table too.

We currently have left type only dispatch as a default for a
non-existent right type, this is in type slot 0.

What about this:
- assign fix class enums (we need that anyway for PBC consistency)
- assign class enums 1..3 to utility PMCs like Env that don't do MMD
- use these 3 type slots in the one and only MMD table for int, float,
string

leo

I'm mildly hesitant to have three special columns in the table (and
I'm not 100% sure someone won't do something really bizarre with Env)
but this seems OK. The one downside to it is that it potentially
anchors the rows a bit more than we might otherwise want--it's
possible to save a lot of space if each row in the MMD table has a
starting number and length prepended, so that the row for type 87
would be 5 words long if it only had entries for types 66, 67, and
68. (That paper I posted a link to a while back describes some of
this stuff)

OTOH that's all implementation detail, so lets go ahead and do it.

Leopold Toetsch wrote:

[rubbish:]
We have to extend the function range of the table. Using
type slots for functions is just nonsense.

leo

I've now implemented MMD for PerlInt's bitwise_xor as a test case. Syntax
looks like this:

void bitwise_xor (PMC* value, PMC* dest) {
MMD_PerlInt: {
VTABLE_set_integer_native(INTERP, dest,
PMC_int_val(SELF) ^ PMC_int_val(value));
}
MMD_DEFAULT: {
VTABLE_set_integer_native(INTERP, dest,
PMC_int_val(SELF) ^
VTABLE_get_integer(INTERP, value));
}
}

This creates two functions:

Parrot_PerlInt_bitwise_xor()
Parrot_PerlInt_bitwise_xor_PerlInt()

with the body parts from above and these initializer code snippet:

{ MMD_BXOR, enum_class_PerlInt, 0,
(funcptr_t) Parrot_PerlInt_bitwise_xor },
{ MMD_BXOR, enum_class_PerlInt, enum_class_PerlInt,
(funcptr_t) Parrot_PerlInt_bitwise_xor_PerlInt }


leo