order ops beeing based on a ternary MMD?
HaloO,
this sort of follows up on the
'Re: Junctions again (was Re: binding arguments)'
thread. The point I tried to make there is that
the optimizer needs the permission to change boolean
checks in the prime boolean block controller 'if'
and its friends like unless, while etc.
Of course certain contstraints must hold. These
are IMHO the axioms of a group with the six compare
ops <, ==, >, >=, !=, <= and negation in general.
And of course the string equivalents lt, eq, gt,
ge, ne, le.
These ops are not fundamental, though. I see them more
as syntactic sugar for an underlying framework build
around <=> and cmp which return one(-1,0,+1). In the
numeric case the minus function might suffice. Well
and there is the fourth return type undef that somehow
must be digested by if and unless. For if the undef right
away prevents the entry to the controlled block, but
should unless allow entry? I see an undef boolean more
like none(true,false) which might nicely prevent entry
in both cases, or so.
Here is the lattice defining the join and meet replacement
operations that the optimizer might use to cut away branches
in a truth check. For junctions this has to be deferred
until runtime:
( ) # undef, none(-1,0,+1)
/ | \
/ | \
/\ / | \
meet/|\
(-1) (0) (+1) # one(-1,0,+1) "element belt"
join |\ / \ /|
\/| \/ \/ |# no intersection of diagonals
| /\ /\ |
|/ \ / \|
(-1,0) (-1,+1) (0,+1)# one( any(-1,0), any(-1,+1), any(0,+1) )
\|/
\ | /
\ | /
\ | /
(-1,0,+1) # any(-1,0,+1)
The underlying idea is that the Int type arises similarly
Void
/ | \
/ | \
/ | \
/|\
Neg Zero Pos
|\ / \ /|
| \/ \/ |
| /\ /\ |
|/ \ / \|
NonPos NonZero NonNeg
\|/
\ | /
\ | /
\ | /
Int
NonPos ::= Neg | Zero # (-1, 0)
NonZero ::= Neg | Pos# (-1, +1)
NonNeg ::= Zero | Pos# (0,+1)
The full glory of Num arises when the void between
the int values is filled with remainders. Doubling
then gives the Complex type which drops out of Order ;)
Not to mention Quaternions and Octonions!
The ternary compare MMD method then has the default
entries
&compare:(Str,Str,Str)
&compare:(Str,Any,Any)
&compare:(Num,Num,Num)
&compare:(Num,Any,Any)
and perhaps and optimized version for
&compare:(Int,Int,Int)
The first parameter is just used to constrain the
choice of MMD. It is usually provided syntactically.
The interesting question is how a *heterogenous* list
of things is sorted! Because there this first parameter
needs to be determined upfront from the other two.
In other words the above compare methods might actually
look like
&compare:( ::X, ::Y : ::Z where { Z does meet(X,Y): }
--> one(-1,0,+1) )
with the syntactic parameter last for syntactic reasons.
Note the two colons to indicate a two step dispatch!
BTW, I would welcome the addition of meet and join lattice
operations to the set of Perl6's ops. With the nice operator
spelling /\ and \/ respectively:
\/ join,
supremum,
least upper bound,
|, any(), .kind, max, union
/\ meet,
infimum,
greatest lower bound,
&, all(), .meta, min, intersection
Comments?
--
$TSa.greeting := "HaloO"; # mind the echo!
Re: integer divide overflow
On Feb 10, 2006, at 3:15, Joshua Isom wrote: [ quoting rearranged - please don't toppost ] On Feb 9, 2006, at 6:20 PM, Leopold Toetsch wrote: $ cat div.pasm set I0, 0x8000 div I1, I0, -1 print I1 print "\n" end Why not case it to switch it to 0x7fff? In any case, if the code's added in to check for it an to throw an exception, then wouldn't it be more friendly to return as close to what's expected, and just call it "magical rounding"? 2^31-1 is close but of course wrong. Given that other native int operations just wrap around, 0 is as valid but OTOH far away from the correct result ;) But out of curiosity, why would integer division be a floating point exception? Lack of interrupt slots on x86? And why doesn't it set the overflow bit? Oh, and on my iBook g3, I get -1. Wow. leo
Re: integer divide overflow
"Leopold Toetsch" <[EMAIL PROTECTED]> wrote: Strange, but it exists for just on case (well not strange, there are just more negative numbers ...): $ cat div.pasm set I0, 0x8000 Which is the largest negative number we can represent in 32 bit integers (-2147483648). div I1, I0, -1 print I1 print "\n" end Which I'd kinda expect to give back -(-2147483648) = 2147483648, apart from that's one beyond the biggest positive number and thus overflows to what we had before, 0x8000, the largest negative number. Eww. Running it on PPC gives: $ ./parrot div.pasm 0 Ugh. And on x86: $ ./parrot div.pasm Floating point exception Looks kinda...broken. Oh, wait, it's x86... :-) What shall we do? Go to the pub. It won't fix the problem, but we'll feel better about it. Abstract it like division by zero and throw an exception? I guess the Right Exception to throw would be an integer overflow exception if we did that. Just ignore it? It's kinda worth asking "what is an I register" here. They're native size already, so we could just say "they have native overflow/wrap-around behaviour" too and then we can ignore it. It really depends how far we want to hide away the underlying hardware. There are always PMCs available to put in specific behaviour and checking of cases like this, and it may well be that certain languages we support want to give one promise with regard to questions like this while others want to give another. On the other hand, if we catch and throw an exception on overflow already with I registers then it may make sense to be consistent and handle this too. Jonathan
Re: integer divide overflow
On Fri, Feb 10, 2006 at 10:52:42AM +0100, Leopold Toetsch wrote: > > On Feb 10, 2006, at 3:15, Joshua Isom wrote: > > [ quoting rearranged - please don't toppost ] > > >On Feb 9, 2006, at 6:20 PM, Leopold Toetsch wrote: > > >>$ cat div.pasm > >>set I0, 0x8000 > >>div I1, I0, -1 > >>print I1 > >>print "\n" > >>end > > But out of curiosity, why would integer division be a floating point > >exception? > > Lack of interrupt slots on x86? > > And why doesn't it set the overflow bit? > > > > >Oh, and on my iBook g3, I get -1. > > Wow. Now I think I see why the C standard has overflowing signed integer arithmetic as undefined behaviour... Perl 5 on x86-FreeBSD coredumps: $ ./perl -Ilib -wle 'use integer; $a = 0x8000; print $a / -1' Floating point exception (core dumped) which I never knew. Beware of assuming anything about signed integer arithmetic overflow - the vendor compiler on 64 bit Irix produces the arithmetic results that you'd expect from 2's complement, but subsequent comparisons with the result don't always "work" (eg you end up down the "wrong" side of if statements) and on Ahmdal mainframes (IIRC) MAX_INT + 1 is 0, not MIN_INT. Nicholas Clark
Re: Heureka - from the -Ofun department
On Wed, 8 Feb 2006, Leopold Toetsch wrote: > Parrot runs the ackermann benchmark faster than C. > > $ time ./parrot -Oc -C ack.pir 11 > Ack(3, 11) = 16381 > > real0m0.567s > user0m0.559s > sys 0m0.008s > > $ time ./ack 11 > Ack(3,11): 16381 > > real0m0.980s > user0m0.978s > sys 0m0.002s This looked like fun, so I tried it on Solaris/SPARC. Alas, I didn't have such great luck. First, though the -C runcore made about a factor of 2 difference in timings (gcc/SPARC), it's only only available (as far as I can tell) with gcc. Still, you might as well use it if you can. On SPARC, I found Parrot took 12 times as long: C: time ./ack 11 Ack(3,11): 16381 real1m7.62s user1m7.36s sys 0m0.05s Parrot: time ./parrot -Oc -C ack.pir 11 Ack(3, 11) = 16381 real11m56.24s user11m52.12s sys 0m0.14s Thinking it might have something to do with the SPARC architecture, I tried it on x86, where Parrot took 80 times as long: C: time ./ack 11 Ack(3,11): 16381 real0m0.759s user0m0.758s sys 0m0.002s Parrot: time ./parrot -Oc -C ../tmp/ack.pir 11 Ack(3, 11) = 16381 real1m1.211s user1m1.087s sys 0m0.021s Something's obviously very goofy there, but I don't know what. -- Andy Dougherty [EMAIL PROTECTED]
Re: [perl #38406] [BUG] PGE - truncating PIR code generated by p6rule
On Sat, 4 Feb 2006, Allison Randal wrote: > On Feb 3, 2006, at 17:33, Joshua Isom via RT wrote: > > > > But, I've encountered two major problems. On darwin, I can't finish > > past_node.t, first parrot takes over 100 megs of ram, then perl(5.8.7) > > wants 180 megs. On freebsd, it's actually worse, but more confusing. > > It fails with past_*.t and post_*.t. But past.t is fine. It's > > essentially a lot of out of memory errors(yet swap space isn't touched, > > and there's free ram at that moment). Darwin essentially starts > > "stalling" when freebsd just gives up on allocating more memory. Line > > numbers aren't given in the print out, except for src/memory.c line 92. > > This is a known bug. As far as we can tell so far, it's not the Punie code, > but Parrot::Test causing the problem. On both platforms, try running the > generated .pir files in languages/punie/t directly (e.g. t/past_node_2.pir). > Everyone who's tried it so far has reported that they have no memory errors > running the test code directly, and only get errors running the code through > the test harness. I too had seen this memory problem before on Solaris/SPARC, but I'm pretty sure I saw it even when running t/past_node_5.pir directly. However, trying again today, I'm happy to report that that particular problem seems to be gone. Of course an awful lot of the tests still fail, but I don't know if that's expected or not. Failed 6/15 test scripts, 60.00% okay. 16/41 subtests failed, 60.98% okay. Failed Test Stat Wstat Total Fail Failed List of Failed --- t/past.t6 1536 76 85.71% 2-7 t/past_op.t 2 512 22 100.00% 1-2 t/past_val.t2 512 22 100.00% 1-2 t/post.t2 512 32 66.67% 2-3 t/post_op.t 2 512 22 100.00% 1-2 t/post_val.t2 512 22 100.00% 1-2 *** Error code 2 make: Fatal error: Command failed for target `test' -- Andy Dougherty [EMAIL PROTECTED]
Re: [perl #38468] [TODO] modify copyright info in parrot repo
On 2/8/06, via RT jerry gay <[EMAIL PROTECTED]> wrote: > ~ the official text will be associated to each file in the parrot > repository via a new svn keyword, 'Copyright' now DONE, r11501. still TODO: > ~ copyright text in each text file will be replaced with the new > keyword for expansion > ~ committers will be instructed on setting their environments to > understand this custom keyword > ~ tests will be designed to detect differences between the official > copyright text (README) and text files in the repository, with an > exception list for files that do not contain the copyright message > ~ these tests will be run before every release > ~ a script will be made available to add or otherwise maintain the > copyright info in all files > ~jerry
Re: Heureka - from the -Ofun department
On Feb 10, 2006, at 18:34, Andy Dougherty wrote: On Wed, 8 Feb 2006, Leopold Toetsch wrote: Parrot runs the ackermann benchmark faster than C. This looked like fun, so I tried it on Solaris/SPARC. Solaris/SPARC doesn't have a working JIT runcore rurrently and I can't test it - no chance yet. The mentioned optimizations are currently ok for x86 and ppc. I tried it on x86, where Parrot took 80 times as long: Rafl was also reporting it not to be working, which is really strange, because he could see (and trace) genereated optimized JIT code. It's still unclear what's going on here. Anyway, with the official (and a bit slower shootout code): $ time ./parrot -Oc -Cj examples/shootout/ack.pir 11 Ack(3, 11) = 16381 real0m0.748s $ time ./parrot -Oc -Sj examples/shootout/ack.pir 11 Ack(3, 11) = 16381 real0m0.800s The optimized PIR from the email is 0.5 sec, the C code takes 0.9 secs, all with AMD [EMAIL PROTECTED] Parrot Revision: 11505 leo
Re: [perl #38406] [BUG] PGE - truncating PIR code generated by p6rule
On Feb 10, 2006, at 9:56, Andy Dougherty via RT wrote: I too had seen this memory problem before on Solaris/SPARC, but I'm pretty sure I saw it even when running t/past_node_5.pir directly. However, trying again today, I'm happy to report that that particular problem seems to be gone. Excellent. Of course an awful lot of the tests still fail, but I don't know if that's expected or not. All of the test should be passing (at least, they are on other platforms). Could you send me more details on the failing tests? Some of the generated .out and .pir files would be a good start (running with POSTMORTEM=1). Thanks! Allison
Re: Heureka - from the -Ofun department
Andy Dougherty <[EMAIL PROTECTED]> wrote: > Thinking it might have something to do with the SPARC architecture, > I tried it on x86, where Parrot took 80 times as long: > > C: time ./ack 11 > Ack(3,11): 16381 > > real0m0.759s > user0m0.758s > sys 0m0.002s > > Parrot: time ./parrot -Oc -C ../tmp/ack.pir 11 > Ack(3, 11) = 16381 > > real1m1.211s > user1m1.087s > sys 0m0.021s > > Something's obviously very goofy there, but I don't know what. Leo forgot the -j flag, which enables JIT, in his post. It makes quite a difference: Parrot w/o JIT: time ./parrot -C -Oc examples/shootout/ack.pir 11 Ack(3, 11) = 16381 real7m11.365s user7m11.066s sys 0m0.168s Parrot w/ JIT: time ./parrot -Cj -Oc examples/shootout/ack.pir 11 Ack(3, 11) = 16381 real0m3.502s user0m3.477s sys 0m0.021s GCC 4.0: time ./ack 11 Ack(3,11): 16381 real0m1.960s user0m1.948s sys 0m0.003s I didn't use the custom PIR he posted (which is faster), so Parrot didn't beat the GCC code. -- matt diephouse http://matt.diephouse.com
