[RFC] some doubtable MMDs?
I'm not quite sure, but it seems that some of the MMD functions may better be vtable methods: - bitwise_sh[rl]*shift by anything other then int? - bitwise_lsris missing generally or even just a plain opcode only: - logical_{or,and,xor} return a PMC depending on the boolean value What are HLLs expecting of these infix operations? OTOH it might be useful that the current get__keyed operations (postcircumfix:[]) become MMD subroutines: Px = Py[Pz]Pz = String, Int, Key, Slice, ... Comments welcome, leo
Re: [RFC] some doubtable MMDs?
On Fri, Apr 15, 2005 at 02:38:36PM +0200, Leopold Toetsch wrote: : I'm not quite sure, but it seems that some of the MMD functions may : better be vtable methods: : : - bitwise_sh[rl]*shift by anything other then int? : - bitwise_lsris missing generally : : or even just a plain opcode only: : : - logical_{or,and,xor} return a PMC depending on the boolean value : : What are HLLs expecting of these infix operations? Perl 6 tends to distinguish these as different operators, though Perl 5 did overload the bitwise ops on both strings and numbers, which newbies found confusing in ambiguous cases, which is why we changed it. : OTOH it might be useful that the current get__keyed operations : (postcircumfix:[]) become MMD subroutines: : : Px = Py[Pz]Pz = String, Int, Key, Slice, ... At the moment, the Perl 6 optimizer is explicitly allowed to optimize array indices with the assumption that the subscript is a scalar (or slice) of integer, or something that converts to integer. I'd be interested to know if that policy will actually buy us any performance. If it always has to go through MMD anyway, maybe it doesn't. But array indexing code tends to be pretty hot, so if we can keep it somewhat optimizable and/or jittable, that'd be nice. Larry
Re: [RFC] some doubtable MMDs?
From: Larry Wall <[EMAIL PROTECTED]> Date: Fri, 15 Apr 2005 12:52:53 -0700 On Fri, Apr 15, 2005 at 02:38:36PM +0200, Leopold Toetsch wrote: : I'm not quite sure, but it seems that some of the MMD functions may : better be vtable methods: : : - bitwise_sh[rl]*shift by anything other then int? Shifting right by a positive BigInt (or left by a negative BigInt) can be optimized to -1 or 0. Shifting the other way could still produce a valid result for some values, even on a machine with 32-bit addresses. : - bitwise_lsris missing generally : : or even just a plain opcode only: : : - logical_{or,and,xor} return a PMC depending on the boolean value : : What are HLLs expecting of these infix operations? Perl 6 tends to distinguish these as different operators, though Perl 5 did overload the bitwise ops on both strings and numbers, which newbies found confusing in ambiguous cases, which is why we changed it. [FWIW, Common Lisp can't use these ops, as it has a different idea of logical truth. And that's the honest (not nil). ;-} ] : OTOH it might be useful that the current get__keyed operations : (postcircumfix:[]) become MMD subroutines: : : Px = Py[Pz]Pz = String, Int, Key, Slice, ... At the moment, the Perl 6 optimizer is explicitly allowed to optimize array indices with the assumption that the subscript is a scalar (or slice) of integer, or something that converts to integer . . . Larry By the same token, couldn't one reasonably ask for a boolean array that required BigInt subscripts, even on said 32-bit machine? (Once boolean arrays actually store one element per bit, that is.) Or are subscripts this large ruled out? Or are you using "integer" conceptually to include both Integer and BigInt? -- Bob Rogers http://rgrjr.dyndns.org/
Re: [RFC] some doubtable MMDs?
Larry Wall <[EMAIL PROTECTED]> wrote: > On Fri, Apr 15, 2005 at 02:38:36PM +0200, Leopold Toetsch wrote: >: I'm not quite sure, but it seems that some of the MMD functions may >: better be vtable methods: >: >: - bitwise_sh[rl]*shift by anything other then int? >: - bitwise_lsris missing generally >: >: or even just a plain opcode only: >: >: - logical_{or,and,xor} return a PMC depending on the boolean value >: >: What are HLLs expecting of these infix operations? > Perl 6 tends to distinguish these as different operators, though Perl 5 > did overload the bitwise ops on both strings and numbers, which newbies > found confusing in ambiguous cases, which is why we changed it. We have distinct functions for bitwise shift int and string. That's no prblem. But can the right operand be anything different then a plain integer? >: OTOH it might be useful that the current get__keyed operations >: (postcircumfix:[]) become MMD subroutines: >: >: Px = Py[Pz]Pz = String, Int, Key, Slice, ... > At the moment, the Perl 6 optimizer is explicitly allowed to optimize > array indices with the assumption that the subscript is a scalar > (or slice) of integer, or something that converts to integer. I'd be > interested to know if that policy will actually buy us any performance. > If it always has to go through MMD anyway, maybe it doesn't. But > array indexing code tends to be pretty hot, so if we can keep it > somewhat optimizable and/or jittable, that'd be nice. Above are only the PMC variants. There are optimized forms for array and hash lookup by native types: Px = Py[Iz] Px = Py[Sz] But with PMCs we seem to have a bunch of different key-ish PMCs, including a BigInt PMC for bitarrays. With MMD we'd have one function per key. Without the usual cascaded if statements: if key.type == Int ... elsif key.type == Slice ... >From a performance POV, MMD is faster with optimizing run cores that can rewrite the opcode and about the same speed with a plain MMD function cache. > Larry leo
Re: [RFC] some doubtable MMDs?
On Fri, Apr 15, 2005 at 11:11:00PM -0400, Bob Rogers wrote: : By the same token, couldn't one reasonably ask for a boolean array that : required BigInt subscripts, even on said 32-bit machine? (Once boolean : arrays actually store one element per bit, that is.) Or are subscripts : this large ruled out? It's certainly reasonable to have some way of allocating a bit array that big. If you have to turn you're entire memory into a bit array, that's fine by me. I've never been much into arbitrary limits. But my question as a language designer then has to be: What do you mean by "ask for", and is merely asking for any bit array the same thing as asking for one that big? :Or are you using "integer" conceptually to include both Integer and : BigInt? Whether I am or not depends on whether I take a big speed hit for the generality. I like generality, but I also want Perl 6 to be fast in the common case, as long as it is not too difficult for the compiler to figure out which cases are not the common ones. Syntactically speaking, Perl 6 can easily distinguish my bit @array is shape(int);# native int subscript from my bit @array is shape(Int);# big int subscript but I'm just wondering which I should be thinking of as the default for my bit @array; It seems to me that assuming shape(int) is not generally going to be a hardship on people, especially once 64-bit machines get to be the norm. And if it means that the optimizer can do tricks and eek some more speed out, then I'm willing to force the occasional user to declare shape(Int) when they want the generality. Larry
Re: [RFC] some doubtable MMDs?
On Sat, Apr 16, 2005 at 10:36:37AM +0200, Leopold Toetsch wrote: : Larry Wall <[EMAIL PROTECTED]> wrote: : > Perl 6 tends to distinguish these as different operators, though Perl 5 : > did overload the bitwise ops on both strings and numbers, which newbies : > found confusing in ambiguous cases, which is why we changed it. : : We have distinct functions for bitwise shift int and string. That's no : prblem. But can the right operand be anything different then a plain : integer? I don't think Perl cares. (Can't speak for other languages.) I do think bit shifts tend to be in very hot code for crypto routines, so any hints we can give the optimizer would help those apps. : Above are only the PMC variants. There are optimized forms for array and : hash lookup by native types: : : Px = Py[Iz] : Px = Py[Sz] Is there a bitarray lookup by native int? : But with PMCs we seem to have a bunch of different key-ish PMCs, : including a BigInt PMC for bitarrays. I don't mind the general MMDish cases, as long as they don't get in the way of a writing a devilish fast LINPACK in Perl 6 without too many contortions. And we can certainly contort Perl 6 to our hearts' content, but I'm just trying to figure out whether ordinary arrays default to shape(int) or shape(Int). My gut feeling is that defaulting to shape(int) is going to buy the optimizer something, but it's just that, a gut feeling. (That, and the fact that plural slice subscripts are generally visible to the compiler, because we don't automatically interpolate $foo into a list even if it's a sublist. So we generally know when we're doing a singular subscripting op.) : With MMD we'd have one function per key. Without the usual cascaded if : statements: : : if key.type == Int : ... : elsif key.type == Slice : ... : : >From a performance POV, MMD is faster with optimizing run cores that can : rewrite the opcode and about the same speed with a plain MMD function cache. Yes, but there's still got to be some internal overhead in deciding whether the run-time Int object is representing the integer in some kind of extended bigint form. (Or are you meaning Int as Parrot's native integer there?) Plus if you're optimizing based on run-time typing, there has to be some check somewhere to see if you're assumptions are violated so you can pessimize. That sort of check can be factored out to some extent, but not to the same extent that a compiler can factor it out with sufficient advance type information, either direct or inferred. (At least, that's my assumption. I don't claim to up-to-date on the latest in optimizing run cores.) Basically, Perl[1-5] got a lot of performance out of assuming IEEE floats were available and sufficiently accurate, whereas earlier languages like REXX has to roll their own numerics to achieve accuracy. I'd like to think that native integers will (soon) always be big enough for most purposes, and am wondering how much it buys us to stay close to the metal here. (And whether the answer is different for 32-bit and 64-bit machines, but that feels like a hack.) Larry
Re: [RFC] some doubtable MMDs?
Larry Wall <[EMAIL PROTECTED]> wrote: > On Sat, Apr 16, 2005 at 10:36:37AM +0200, Leopold Toetsch wrote: >: Above are only the PMC variants. There are optimized forms for array and >: hash lookup by native types: >: >: Px = Py[Iz] >: Px = Py[Sz] > Is there a bitarray lookup by native int? Yes. All array lookups support a native int index. >: But with PMCs we seem to have a bunch of different key-ish PMCs, >: including a BigInt PMC for bitarrays. > I don't mind the general MMDish cases, as long as they don't get > in the way of a writing a devilish fast LINPACK in Perl 6 without > too many contortions. And we can certainly contort Perl 6 to our > hearts' content, but I'm just trying to figure out whether ordinary > arrays default to shape(int) or shape(Int). My gut feeling is that > defaulting to shape(int) is going to buy the optimizer something, but > it's just that, a gut feeling. A default of shape(int) sounds very reasonable. WRT speed: we'll have basically two different runoptions similar to -Os and -Ot. The former is useful in cases, where 300 users are running "parrot order.pbc" (Dan Sugalski). The bytecode is read-only and can be shared via e.g. mmap(2). The latter can rewrite the bytecode and even inline the array access for the native integer case. > Yes, but there's still got to be some internal overhead in deciding > whether the run-time Int object is representing the integer in some > kind of extended bigint form. (Or are you meaning Int as Parrot's > native integer there?) A Parrot Integer PMC (32bit for a 32bit sytem), which has a different type number then a BigInt PMC. > ... Plus if you're optimizing based on run-time > typing, there has to be some check somewhere to see if you're > assumptions are violated so you can pessimize. The check is rather cheap. Given the (hypothetical) opcode: circumfix .MMD_GET_KEYED, Par, Pidx, Pdest $1 $2 $3$4 it can be recompiled to: cache = $1 if ($2.type << 16 | $3.type) == cache.type $4 = (cache.function)(INTERP, $2, $3) else // consider some more cache slots else // MMD lookup There is one cache entry per bytecode location with this opcode (PIC, Polymorphic Inline Cache). The fast path is usually hit in more then 95% of the cases states the literature. With readonly-bytecode a slightly slower variant is the default, where the cache lookup involves some more indirections. > ... That sort of check > can be factored out to some extent, but not to the same extent that a > compiler can factor it out with sufficient advance type information, > either direct or inferred. (At least, that's my assumption. I don't > claim to up-to-date on the latest in optimizing run cores.) Type interference is a nice to have but difficult with dynamic languages. It needs support by the user (closed classes, no overloading) but yes, the compiler can emit a direct function call sometimes. > Larry leo
Re: [RFC] some doubtable MMDs?
On Sun, Apr 17, 2005 at 09:50:28AM +0200, Leopold Toetsch wrote: : Larry Wall <[EMAIL PROTECTED]> wrote: : > Is there a bitarray lookup by native int? : : Yes. All array lookups support a native int index. Good, good. Speaking of bitarrays (uint1 in the Perl panoply of types), is there any built-in support for arrays of tiny integers like uint2 or uint4? It'd be nice to have uint24 in there too. These can all be emulated from an array of bytes like vec() does in Perl 5, but we're making feeble attempts to treat the oddball types as standard types in Perl 6. 'Course, I'm not writing the compiler myself, so I'm only asking out of curiosity. :-) : > Yes, but there's still got to be some internal overhead in deciding : > whether the run-time Int object is representing the integer in some : > kind of extended bigint form. (Or are you meaning Int as Parrot's : > native integer there?) : : A Parrot Integer PMC (32bit for a 32bit sytem), which has a different : type number then a BigInt PMC. For simplicity Perl is probably just going to make a two-way distinction between int/Int, where the latter is assumed to have BigInt properties as necessary. We can probably use Parrot Integer PMCs for boxing native ints when we need to do that, but that's hopefully transparent to the user. Thanks for all the info. Nice to know we're pushing the state of the art in spots. We'll just keep on pushing it till it falls over. Larry
Re: [RFC] some doubtable MMDs?
Larry Wall <[EMAIL PROTECTED]> wrote: > On Sun, Apr 17, 2005 at 09:50:28AM +0200, Leopold Toetsch wrote: >: Larry Wall <[EMAIL PROTECTED]> wrote: >: > Is there a bitarray lookup by native int? >: >: Yes. All array lookups support a native int index. > Good, good. Speaking of bitarrays (uint1 in the Perl panoply of > types), is there any built-in support for arrays of tiny integers > like uint2 or uint4? It'd be nice to have uint24 in there too. I can see two ways to do it: a) a general n-bit array Px = new NBitArray, 2 # or 4, 24 or 128, ... which would mean that this is just one type, i.e. no MM dispatch difference between C<@a of int2> and C<@a of int4>. b) implement it as distinct array types. The former is probably slightly slower with the said dispatch problem, the latter uses more resources, more code, bigger type registry, bigger MMD caches and so on. An C<@a of uint8> is definitely such a distinct type RSN. c) a mixture of a) and some commonly used sizes for b) Ehem three ways. >: A Parrot Integer PMC (32bit for a 32bit sytem), which has a different >: type number then a BigInt PMC. > For simplicity Perl is probably just going to make a two-way > distinction between int/Int, where the latter is assumed to have > BigInt properties as necessary. Yep. The distinction between BigInt and Integer PMC is almost invisble to Perl6, except in something like: $i.isa # ["Int"] $i.__isa# ["Integer"] or ["BigInt"] > ... We can probably use Parrot Integer > PMCs for boxing native ints when we need to do that, but that's > hopefully transparent to the user. Should be, yes. > Thanks for all the info. Nice to know we're pushing the state of the > art in spots. We'll just keep on pushing it till it falls over. > Larry Welcome, leo
Re: [RFC] some doubtable MMDs?
At 2:38 PM +0200 4/15/05, Leopold Toetsch wrote: I'm not quite sure, but it seems that some of the MMD functions may better be vtable methods: - bitwise_sh[rl]*shift by anything other then int? - bitwise_lsris missing generally or even just a plain opcode only: - logical_{or,and,xor} return a PMC depending on the boolean value What are HLLs expecting of these infix operations? These were in because I fully expected people would want to override "<<", ">>" and their ilk. Basically any overridable operation got an entry in the MMD table. -- Dan --it's like this--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk