Mailman 3 September 2003 - pypy-dev

OT: abs(x) with 4 assembly insns
by Damien Morton 30 Sep '03

30 Sep '03

>From http://www.hackersdelight.org/basics.pdf If your machine does not have an instruction for computing the absolute value, this computation can usually be done in three or four branch-free instructions. First, compute: signed int x signed int y = x >> 31 and then one of the following: abs = (x ^ y) - y abs = (x + y) ^ y abs = x - ((x<<1) & y)

1 0

OT: abs(x) with 4 assembly insns
by Christian Tismer 29 Sep '03

29 Sep '03

Hi friends, today, Armin presented me a simple brain-teaser: You have X86 assembly, you have only 4 insns, and you don't want to use a jump. You have a register, loaded with a value, and you should produce its abs, in another register, while preserving the argument register. Hmm. 4 insns. Here is the standard C solution for doing abs without a jump, whioch you can find on the internet: int int_abs(int a) { return a - ((a+a) & (a>>31)); } This clearly computes the bas, quite nicely. The resulting assembly code looks like so: ; 2 : return a - ((a+a) & (a>>31)); 00000 8b 44 24 04 mov eax, DWORD PTR _a$[esp-4] 00004 8b c8 mov ecx, eax 00006 c1 f9 1f sar ecx, 31 ; 0000001fH 00009 8d 14 00 lea edx, DWORD PTR [eax+eax] 0000c 23 ca and ecx, edx 0000e 2b c1 sub eax, ecx ; 3 : } This is clearly some solution. But, ignoring the first insn, which is just moving the argument, this really takes five instructions, one too much of course. Actually, there is a much better solution. X86 has the cdq insn, which does a sign extension from 32 bit signed eax to 64 bit signed edx/eax. This in fact puts a -1 into edx, whenever the eax is negative, or a 0, if eax is >= 0. Now, what is taking the abs() of a value? Right, it is a two's complement, if the argument is negative, or a do-nothing if it is not negative. And the name 'two's complement' comes from the fact that you need to do two operations for the complement: First, take the NOT of the value, then add one. So, here comes the trick: NOT is equivalent to XORing with -1. ADD 1 is the same as SUB -1. Fortunately, this can all be carried out with the result of the CDQ sign extension, since we got the -1 from it: Do the CDQ. Load eax into another register XOR it with edx (which is either 0 or -1) SUB edx from it (which is either adding one or zero) So, here the solution(TM): int other_abs(int a) { __asm { mov eax, a; /* from here... */ cdq; mov ebx, eax; xor ebx, edx; sub ebx, edx; /*... to here*/ xchg eax, ebx; } } The meat of the program is exactly four insns, the rest is just needed to make the C calling conventions happy. Here the full program, you can step through it with a debugger, to see that it really works: int int_abs(int a) { return a - ((a+a) & (a>>31)); } int other_abs(int a) { __asm { mov eax, a; /* C: load arg */ /* from here... */ cdq; /* 1: edx has either 0 or -1 */ mov ebx, eax; /* 2: get a copy */ xor ebx, edx; /* 3: either identity, or NOT */ sub ebx, edx; /* 4: either add 0, or 1 */ /* ... to here */ xchg eax, ebx; /* C: store result */ } } int main(int argc, char **argv) { int a; a = int_abs(5); a = int_abs(-5); a = other_abs(5); a = other_abs(-5); return 0; } Hoping-that-everybody-trusts-me-now-that-I-can-write-a-small-OS -- ly y'rs - chris -- Christian Tismer :^) <mailto:tismer@tismer.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/

4 9

Re: [pypy-dev] Re: OT: abs(x) with 4 assembly insns
by Laura Creighton 29 Sep '03

29 Sep '03

In a message of Mon, 29 Sep 2003 09:19:58 EDT, Bob Ippolito writes: > >On Monday, Sep 29, 2003, at 08:23 America/New_York, Michael Hudson >wrote: > >> Bob Ippolito <bob(a)redivi.com> writes: >> >>>> I've been reading the PPC architecture manual, though, so I can tell >>>> you that Bob's 3 instructions are all single cycle instructions on a >>>> G3... >>> >>> You should also check out IBM's PowerPC Compiler Writer's Guide, if >>> you haven't already: >>> http://www-3.ibm.com/chips/techlib/techlib.nsf/techdocs/ >>> 852569B20050FF7785256996007558C6 >>> >>> Hard copies of this document can be obtained by calling IBM at (800) >>> 879-2755 and requesting document number SA14-2094, I hear that they >>> used to (maybe still do) charge $1.00 for the book :) >> >> Our Apologies >> >> You have attempted to enter a controlled access area that you are not >> currently entitled to view. IBM Microelectronics uses a entitlement >> process to protect potentially sensitive data. >> >> ... oh well. I'll dig around for it, though. And I guess s&h might >> be more that $1 to the UK... > >Maybe it's restricted to US citizens only? That would be odd.. I >tried it in another browser just to make sure it wasn't a baked cookie >from when I downloaded IBM's PowerPC compilers, and it worked just fine. I can read it just fine as well. How very odd. Laura

1 0

Re: [pypy-dev] Re: OT: abs(x) with 4 assembly insns
by Laura Creighton 29 Sep '03

29 Sep '03

In a message of Mon, 29 Sep 2003 07:33:56 EDT, Bob Ippolito writes: > > >You should also check out IBM's PowerPC Compiler Writer's Guide, if you >haven't already: >http://www-3.ibm.com/chips/techlib/techlib.nsf/techdocs/ >852569B20050FF7785256996007558C6 > >Hard copies of this document can be obtained by calling IBM at (800) >879-2755 and requesting document number SA14-2094, I hear that they >used to (maybe still do) charge $1.00 for the book :) > >-bob 800 numbers don't work outside of the US, or maybe outside of the US and Canada. Do you have a regular number? Laura

1 0

Re: [pypy-dev] Fwd: Lightweight Languages 2003 (LL3) CFP
by Laura Creighton 27 Sep '03

27 Sep '03

In a message of Fri, 26 Sep 2003 20:40:11 +0200, Dinu Gherman writes: >Sounds like this could be of interest for PyPy development (and/or >funding?), especially since the program committee is highly aware >of Python, already! ;-) > >Dinu If we only had teleporters .... Wonder if Jonathan wants to give a talk. Where in the USA is he from anyhow? Laura

2 1

Fwd: Lightweight Languages 2003 (LL3) CFP
by Dinu Gherman 26 Sep '03

26 Sep '03

Sounds like this could be of interest for PyPy development (and/or funding?), especially since the program committee is highly aware of Python, already! ;-) Dinu > Von: Jeremy Hylton <jeremy(a)alum.mit.edu> > Datum: Fr, 26. Sep 2003 16:14:18 Europe/Berlin > An: python-announce-list(a)python.org > Betreff: Lightweight Languages 2003 (LL3) CFP > Antwort an: jeremy(a)alum.mit.edu > > Lightweight Languages Workshop 2003 (LL3) > ---------------------------------- > > Saturday, November 8, 2003, MIT, Cambridge, MA > http://ll3.ai.mit.edu/ mailto:ll3@ai.mit.edu > > CALL FOR PRESENTATIONS > > LL3 will be an intense, exciting, one-day forum bringing together the > best programming language implementors and researchers, from both > academia and industry, to exchange ideas and information, to challenge > one another, and to learn from one another. > > The workshop series focuses on programming languages, tools, and > processes that are usable and useful. Lightweight languages have been > an effective vehicle for introducing new features to mainstream > programmers. > > We encourage presentations on topics of interest to the community of > lightweight language users and designers. We prefer topics that will > interest a broad audience. We do not require the presentation of > novel research ideas. > > Proposal Abstracts > ------------------ > Due Friday Oct. 17 > > We seek two to five page abstracts of talks to be given at the > workshop. Talks will be 30 minutes long, including time for > questions and answers. Presenters are not expected to submit > papers, but slides will be published on the workshop web site. > We will also consider proposals for talks of different lengths. > > Some suggested topics are: > > * Language design: New language features, type systems and other > reasoning tools, critiques of existing languages. > > * Implementation techniques: Interpreters and virtual machines, > optimizations, cross-language interactions. > > * From scripts to programs: Software engineering with > lightweight and/or a mix of languages. How to (or not to!) > scale from little scripts to large, complex applications. > Application war stories. > > * From ivory tower to cubicle -- what language implementors need > to know from academic programming languages research -- and > back. > > * Lightweight pearls: Elegant and instructive examples of > programs in lightweight languages. > > * Programming tools and development processes. > > Send submissions to: ll3-submit(a)ai.mit.edu > > We want presentations that will inspire, motivate, and educate. We > want language implementors and researchers to leave the workshop fired > up with ideas for future languages, features, and implementation > tricks. We want language users to leave the workshop fired up with > new ideas and new tools. > > In addition to submitted presentations, there will be two invited > talks. After the workshop, there will be an evening social event and > dinner. > > Dates: Tuesday, Oct. 17 -- submissions due by end of day. > Tuesday, Oct. 24 -- notification of acceptance or rejection > Saturday, Nov. 8 -- 9am-7pm, LL3! > > Program Committee: > > Ken Anderson, BBN (co-chair) > Jeremy Hylton, Python Software Foundation (co-chair) > Geoffrey Knauth, BAE Systems > Shriram Krishnamurthi, Brown University > Erik Meijer, Microsoft Research > Dan Sugalski, Perl Foundation > Greg Sullivan, MIT CSAIL

1 0

Pyrex back-end
by Armin Rigo 25 Sep '03

25 Sep '03

Hello everybody, Concensus seems to araise that we should try during the sprint to obtain a basic translator-to-low-level-code, and that Pyrex would be a nice try. Remember that AnnObjSpace is supposed to do a complete type analysis of all the RPython code. With Pyrex we can seriously work on the different problem of actually emiting low-level code, before we have a really complete analysis. The idea is to simulate bytecode-by-bytecode the execution of the RPython source code, and instead of actually executing the instructions, we write a line in a .pyx (Pyrex) file. Whenever we are unsure about the type of a specific variable we can always fall back to generic Python objects. Pyrex don't have gotos -- they are essential for the low-level kind of code we can emit by blindly recording operation in an object space, because the object space doesn't see the control structures at all (only the operations). So Holger implemented (in 29 minutes!) a new Pyrex statement: cinline "anything" which causes Pyrex to emit the given string literally in the C code it produces. So we can say cinline "Label1:" ... if condition: cinline "goto Label1;" which is probably nicer than explicit "label" and "goto" statements because it denotes clearly that it is a hack :-) It also let us emit any other C code that we couldn't easily express in the Pyrex language. http://codespeak.net/svn/user/hpk/pyrex-0.8.2-hacked A bientot, Armin

1 0

Re: [pypy-dev] Extended goals
by Laura Creighton 25 Sep '03

25 Sep '03

In a message of Tue, 16 Sep 2003 13:46:26 +0200, holger krekel writes: >[Dinu Gherman Tue, Sep 16, 2003 at 01:24:12PM +0200] >> I forgot to mention: if you really want EU money, you should, under >> all circumstances, find a good explanation for how PyPy only can >> fuel the world's most sophisticated future E-Government platforms! >> >> No joke! Combine this with the mobile devices I mentioned before! ;-) > >And here we should mention Zope (and it's speed problems :-). Maybe >we/i can get some prominent Zope-developers to state that PyPy >could help Zope etc. At least in germany government agencies >are using Zope a lot ... What do you think? > >cheers, > > holger Good idea. I will ask Paul Everitt as well. Laura

8 11

My first try: dir()
by Seo Sanghyeon 23 Sep '03

23 Sep '03

Hello, everybody, I followed the mailing list for some time, but haven't touched the code yet. Here's my first try, dir(), from your confused newbie. For now, everything from Objectspace to Gateway is just incomprehensible for me, but I will try... I'm requesting for some comments. My try seems to work, but I want to know how would you write the following, and how to implement the rest of dir(), etc. Index: builtin.py =================================================================== --- builtin.py (revision 1415) +++ builtin.py (working copy) @@ -383,6 +383,20 @@ except AttributeError: return False + def dir(self, w_object=None): + space = self.space + ob = space.unwrap(w_object) + if ob is None: + dic = self.locals() + elif type(ob) is Module: + dic = ob.w_dict + else: + w_exc = space.w_ValueError("Not implemented yet") + raise OperationError(space.w_ValueError, w_exc) + result = space.call_method(dic, 'keys') + space.call_method(result, 'sort') + return result + # source code for the builtin xrange-class xrange_appsource = """if 1: class xrange:

1 0

Re: [pypy-dev] Re: fixeol
by Laura Creighton 22 Sep '03

22 Sep '03

In a message of Mon, 22 Sep 2003 15:15:10 +0200, holger krekel writes: >[Armin Rigo Mon, Sep 22, 2003 at 02:08:45PM +0100] >> Hello Christian, >> >> > >Argh ! The files look completely broken now !! Warning ! >> >> I hopefully fixed the script now. You might try it (carefully!) on some > new >> text files. >> >> I'm still a bit worried that if fixeol actually changes content, as wou >ld be >> the case if it is run by someone on another platform than the one used >to >> create it, then svn will record it as completely changed (ideal source >for >> conflicts). The only solution I could imagine would be to make sure tha >t >> people specify files to be text when they first add it to the repositor >y. >> Somehow the default "files-are-binary" of SVN creates different, new ki >nd of >> problems than the default "files-are-text" of CVS. Maybe a no-default >> you-must-specify-it-explicitely wouldn't have been such a bad idea. > >we could enforce this on a pre-commit hook and maybe other things >like e.g. that REST-files compile without errors. The latter would make >a checkin of documents slower but i think it's worth it IMO. > >cheers, > > holger I want to be able to stick broken ReST into the depository at any time. When your sysadmin is about to take your machine at work down for the weekend, is the time you need to stuff your half done work into the repository so you can go home and keep working, not discover that your work is marooned on a disk that is running a weekend long memory error diagnostic. Now BITCHING at me that it is broken, at commit time, preferably with a reminder of how to run the tool that tells you whats not working, that is a fine idea, I think. Laura

1 0