[perl #37003] [PATCH] Change GCD and LCM opcode to use Binary GCD algorithm
# New Ticket Created by Imran Ghory
# Please include the string: [perl #37003]
# in the subject line of all future correspondence about this issue.
# URL: https://rt.perl.org/rt3/Ticket/Display.html?id=37003
Presently GCD/LCM use the Euclidlean algorithm to calculate the GCD,
the attached path replaces it with the Binary GCD algorithm. The
primary advantage of the Binary GCD algorithm is that it doesn't use
division like the Euclidlean algorithm (it uses bitwise shifts
instead) and so is more efficient. On a PC it is roughly 25% faster,
on embedded platforms which don't have processor based division
support it can be around 80% faster.
The following code can be used to test both timings and correctness by
running against pre-patch and post-patch code and comparing the
results:
.sub _main
.local int i,j
i = 0
j = 0
loop:
loop2:
gcd $I3, i, j
lcm $I4, i, j
print i
print ,
print j
print -(
print $I3
print ,
print $I4
print )\n
inc j
if j = 1000 goto loop2
j = 0
inc i
if i = 1000 goto loop
end
.end
--- clean/parrot/ops/math.ops 2005-08-25 00:30:16.0 +0100
+++ parrot/ops/math.ops 2005-08-25 00:37:13.786736920 +0100
@@ -974,20 +974,30 @@
=cut
inline op gcd(out INT, in INT, in INT) :advanced_math {
-
- UINTVAL q = 0;
- UINTVAL c = 0;
- INTVAL temp2 = $2 0 ? -$2 : $2;
- INTVAL temp3 = $3 0 ? -$3 : $3;
- while (temp3 != 0) {
-q = (UINTVAL)floor( (FLOATVAL)temp2/temp3 );
-c = temp2 - temp3*q;
-temp2 = temp3;
-temp3 = c;
- }
- $1 = temp2;
- goto NEXT();
+ INTVAL p = 0;
+ INTVAL a = $2 0 ? -$2 : $2;
+ INTVAL b = $3 0 ? -$3 : $3;
+
+ if(a==0) { $1=b; goto NEXT(); }
+ if(b==0) { $1=a; goto NEXT(); }
+
+ while( !((a | b) 1) ) {
+ a=1;
+ b=1;
+ p++;
+ }
+
+ while(a0) {
+ if (!(a 1)) a=1;
+ else if (!(b 1)) b=1;
+ else if (ab) b = (b-a)1;
+ else a = (a-b)1;
+ }
+
+ $1 = bp;
+ goto NEXT();
}
+
@@ -998,26 +1008,31 @@
=cut
inline op lcm(out INT, in INT, in INT) :advanced_math {
- UINTVAL q = 0;
- UINTVAL c = 0;
- INTVAL temp2 = $2;
- INTVAL temp3 = $3;
- INTVAL saved_var2 = temp2;
- INTVAL saved_var3 = temp3;
- while (temp3 != 0) {
-q = (UINTVAL)floor( (FLOATVAL)temp2/temp3 );
-c = temp2 - temp3*q;
-temp2 = temp3;
-temp3 = c;
- }
- if (saved_var2 == 0) {
-$1 = 0;
- }
- else {
-saved_var2 = saved_var2 / temp2;
-$1 = saved_var2*saved_var3;
- }
- goto NEXT();
+ INTVAL gcd = 0;
+ INTVAL p = 0;
+ INTVAL a = $2 0 ? -$2 : $2;
+ INTVAL b = $3 0 ? -$3 : $3;
+ INTVAL saved_var1 = a, saved_var2 = b;
+
+ if(a==0 || b==0) { $1=0; goto NEXT(); }
+
+ while( !((a | b) 1) ) {
+ a=1;
+ b=1;
+ p++;
+ }
+
+ while(a0) {
+ if (!(a 1)) a=1;
+ else if (!(b 1)) b=1;
+ else if (ab) b = (b-a)1;
+ else a = (a-b)1;
+ }
+
+ gcd = bp;
+ saved_var1 /= gcd;
+ $1 = saved_var1*saved_var2;
+ goto NEXT();
}
pirate refactoring update
Hello! Here's an update on pirate (the python to parrot compiler) from the trenches. Pirate started as an example that fit in one small file and it stayed in that single file over the years while it grew into a *huge* mess: one monolithic object performing a variety of transformations on python's syntax tree, all in one single pass. Thanks to a Summer of Code grant from Google and the Perl Foundation, Curtis Hall and I have been working to refactor that mess. Our long term goal is to allow pirate to support multiple language front ends (for example, PyPy and Pugs) but our immediate goal was to make the refactoring easier to handle. So far, we've created a generic transformation module that greatly simplifies the work done by Visitors in the compiler module (it's called transform.py in the pirate repository - see below) With the generic Transformer in place, we were able to separate out a simplification pass, so that list comprehensions (eg: [x for x in range(10) if x 5] which evaluates to [6, 7, 8, 9]) are converted into their corresponding for and if blocks up front, before PirateVisitor ever sees the tree. Curt is currently working to use this same principle to separate out function definitions from generator definitions, another chunk of the single-pass system that would work much better as a separate pass through the tree. The big questions we'v been dealing with, though, is what will pirate look like after the refactoring? Well, we think we have a good answer, and we'd like your feedback. We recognize that there are very few people out there that understand how pirate works *today* so what we've done is create a much simplified toy version of pirate and shown, though actual code, how that toy version can be refactored, all in one easy to read narrative python script. Hopefully, you'll be able to understand what's going on even if you're not a python developer. So... Without further ado, here is the plan: http://pirate.versionhost.com/viewcvs.cgi/pirate/toys/refactor.py?rev=HEADcontent-type=text/vnd.viewcvs-markup Or, if that's probably mangled: http://tinyurl.com/d92f3 It's short, contains test cases, and you can actually run it from python, or step through it with a debugger. It does *not* take us all the way to a language-neutral compiler, but it will make that step much easier. Anyway, Curt will be using this plan as a guide to actually implement as much of the refactoring as possible in the time he has left for the Summer of Code, so if you've got feedback, please share it on the pirate list: http://www.cornerhost.com/mailman/listinfo/pirate Other links: The priate home page is here: http://pirate.tangentcode.com/ The code for pirate is available for browsing here: http://pirate.versionhost.com/viewcvs.cgi/pirate/ Thanks for reading! Sincerely, Michal J Wallace Sabren Enterprises, Inc. - contact: [EMAIL PROTECTED] hosting: http://www.cornerhost.com/ my site: http://www.withoutane.com/ -
Re: [perl #37003] [PATCH] Change GCD and LCM opcode to use Binary GCD algorithm
the attached path replaces it with the Binary GCD algorithm. The Thanks, applied. leo
[PATCH] PIR Syntax: (end)namespace id
hi, In the current docs of PIR, the .namespace id .endnamespace id directives are not mentioned. This patch adds a short description of both to syntax.pod. Regards, klaas-jan --- syntax.pod 2005-08-08 19:44:47.0 +0200 +++ syntax_patched.pod 2005-08-25 16:02:33.0 +0200 @@ -1,4 +1,4 @@ -# Copyright: 2001-2005 The Perl Foundation. All Rights Reserved. +# Copyright: 2001-2005 The Perl Foundation. All Rights Reserved. # $Id: syntax.pod 8745 2005-07-30 17:35:35Z chromatic $ =head1 NAME @@ -176,6 +176,29 @@ Define a named constant of style Itype and value Iconst. +=item .namespace identifier + +Open a new scope block. This namespace is not the same as the +.namespace [ identifier ] syntax, which is used for storing subroutines +in a particular namespace in the global symboltable. +This directive is useful in cases such as (pseudocode): + + local x = 1; + print(x); # prints 1 + do # open a new namespace/scope block + local x = 2;# this x hides the previous x + print(x); # prints 2 + end # close the current namespace + print(x); # prints 1 again + +All types of common language constructs such as if, for, while, repeat and such +that have nested scopes, can use this directive. + +=item .endnamespace identifier + +Closes the scope block that was opened with .namespace identifier. + + =item .namespace [ identifier ] =item .namespace [ identifier ; identifier ]
Re: [PATCH] PIR Syntax: (end)namespace id
woops, I used tabs to indent, that gives ugly layout. Here's a NEW version with spaces. regards, klaas-jan Klaas-Jan Stol wrote: hi, In the current docs of PIR, the .namespace id .endnamespace id directives are not mentioned. This patch adds a short description of both to syntax.pod. Regards, klaas-jan --- syntax.pod 2005-08-08 19:44:47.0 +0200 +++ syntax_patched.pod 2005-08-25 16:02:33.0 +0200 @@ -1,4 +1,4 @@ -# Copyright: 2001-2005 The Perl Foundation. All Rights Reserved. +# Copyright: 2001-2005 The Perl Foundation. All Rights Reserved. # $Id: syntax.pod 8745 2005-07-30 17:35:35Z chromatic $ =head1 NAME @@ -176,6 +176,29 @@ Define a named constant of style Itype and value Iconst. +=item .namespace identifier + +Open a new scope block. This namespace is not the same as the +.namespace [ identifier ] syntax, which is used for storing subroutines +in a particular namespace in the global symboltable. +This directive is useful in cases such as (pseudocode): + + local x = 1; + print(x); # prints 1 + do # open a new namespace/scope block + local x = 2;# this x hides the previous x + print(x); # prints 2 + end # close the current namespace + print(x); # prints 1 again + +All types of common language constructs such as if, for, while, repeat and such +that have nested scopes, can use this directive. + +=item .endnamespace identifier + +Closes the scope block that was opened with .namespace identifier. + + =item .namespace [ identifier ] =item .namespace [ identifier ; identifier ] --- syntax.pod 2005-08-25 16:13:16.0 +0200 +++ syntax_patched.pod 2005-08-25 16:13:59.0 +0200 @@ -176,6 +176,29 @@ Define a named constant of style Itype and value Iconst. +=item .namespace identifier + +Open a new scope block. This namespace is not the same as the +.namespace [ identifier ] syntax, which is used for storing subroutines +in a particular namespace in the global symboltable. +This directive is useful in cases such as (pseudocode): + + local x = 1; + print(x); # prints 1 + do # open a new namespace/scope block +local x = 2; # this x hides the previous x +print(x); # prints 2 + end # close the current namespace + print(x); # prints 1 again + +All types of common language constructs such as if, for, while, repeat and such +that have nested scopes, can use this directive. + +=item .endnamespace identifier + +Closes the scope block that was opened with .namespace identifier. + + =item .namespace [ identifier ] =item .namespace [ identifier ; identifier ]
Re: [PATCH] PIR Syntax: (end)namespace id
On 8/25/05, Klaas-Jan Stol [EMAIL PROTECTED] wrote: woops, I used tabs to indent, that gives ugly layout. Here's a NEW version with spaces. [snip] --- syntax.pod 2005-08-25 16:13:16.0 +0200 +++ syntax_patched.pod 2005-08-25 16:13:59.0 +0200 @@ -176,6 +176,29 @@ Define a named constant of style Itype and value Iconst. +=item .namespace identifier + +Open a new scope block. This namespace is not the same as the +.namespace [ identifier ] syntax, which is used for storing subroutines +in a particular namespace in the global symboltable. +This directive is useful in cases such as (pseudocode): + + local x = 1; + print(x); # prints 1 + do # open a new namespace/scope block +local x = 2; # this x hides the previous x +print(x); # prints 2 + end # close the current namespace + print(x); # prints 1 again + +All types of common language constructs such as if, for, while, repeat and such +that have nested scopes, can use this directive. + +=item .endnamespace identifier + +Closes the scope block that was opened with .namespace identifier. + + =item .namespace [ identifier ] =item .namespace [ identifier ; identifier ] thanks, applied. in the future, please provide diffs relative to the parrot base directory, it makes it easier to find the files to patch. also, this patch brings up an interesting point. .namespace identifier means something totally different than .namespace [ identifier ] or .namespace [ identifier, identifier ] this is a Bad Thing. i propose we rename .namespace identifier to something more appropriate like .scope identifier and change the matching .endnamespace identifier to .endscope identifier to better describe their function, and to prevent developer confusion. thoughts? ~jerry
Re: [PATCH] PIR Syntax: (end)namespace id
thanks, applied. in the future, please provide diffs relative to the parrot base directory, it makes it easier to find the files to patch. that is, I should do (for instance) $ diff -u imcc/docs/file.pod imcc/docs/newfile.pod patchfile ? also, this patch brings up an interesting point. .namespace identifier means something totally different than .namespace [ identifier ] or .namespace [ identifier, identifier ] this is a Bad Thing. I think this is confusing for new people yes. (well, I would have been confused, if I had not known about this) i propose we rename .namespace identifier to something more appropriate like .scope identifier and change the matching .endnamespace identifier to .endscope identifier to better describe their function, and to prevent developer confusion. thoughts? sounds good to me! ~jerry klaas-jan
Re: [PATCH] PIR Syntax: (end)namespace id
On 8/25/05, Klaas-Jan Stol [EMAIL PROTECTED] wrote: thanks, applied. in the future, please provide diffs relative to the parrot base directory, it makes it easier to find the files to patch. that is, I should do (for instance) $ diff -u imcc/docs/file.pod imcc/docs/newfile.pod patchfile ? yes, that's perfect, thanks. ~jerry
(r9051) leo-ctx5 test failures on win32--msvc-7.1--perl-5.8.6
Failed Test Stat Wstat Total Fail Failed List of Failed --- t\dynclass\gdbmhash.t 13 332813 13 100.00% 1-13 t\library\streams.t 2 512202 10.00% 18 20 t\op\gc.t1 256221 4.55% 13 t\src\manifest.t 2 512 52 40.00% 4-5 t\src\opcode-doc.t 1 256 11 100.00% 1 4 tests and 88 subtests skipped. Failed 5/158 test scripts, 96.84% okay. 19/2685 subtests failed, 99.29% okay. gdbmhash and streams failures are expected. here's the details on the rest: t\op\gcNOK 13# Failed test (t\op\gc.t at line 279) # got: '3 * 5 == 15! # Can't spawn .\parrot.exe --gc-debug D:\usr\local\parrot-HEAD\branches\leo-c tx5\t\op\gc_13.pir: Bad file descriptor at lib/Parrot/Test.pm line 238. # ' # expected: '3 * 5 == 15! # ' # '.\parrot.exe --gc-debug D:\usr\local\parrot-HEAD\branches\leo-ctx5\t\op\gc_ 13.pir' failed with exit code 255 t\src\manifest.NOK 4# Failed test (t\src\manifest.t at line 69) # Files ignored by SVN but not in MANIFEST.SKIP: # ^languages/Zcode/Makefile$ # ^languages/Zcode/Makefile/ t\src\manifest.NOK 5# Failed test (t\src\manifest.t at line 75) # Missing files: # languages/tcl/lib/tclcommandlist.pir # Looks like you failed 2 tests of 5. t\src\manifest.dubious Test returned status 2 (wstat 512, 0x200) t\src\opcode-doc...NOK 1# Failed test (t\src\opcode-doc.t at lin e 80) # Opcode documentation errors: # ops/core.ops:407: no documentation for DELETED_invoke() # ops/core.ops:448: no documentation for DELETED_updatecc() # Looks like you failed 1 test of 1. t\src\opcode-doc...dubious Test returned status 1 (wstat 256, 0x100) ~jerry
Native object execution and shared libraries
The Native Object Execution Subsystem section of the parrot documentation provides instructions for how to generate a native executable. I was wondering if it's possible (or planned) to create native shared libraries (so, dll) and have the executable link to it dynamically. Coming from a java background, this would really be a breath of fresh air!
