bs@faron.UUCP (Robert D. Silverman) (02/27/86)
Much of the work I (and others) do involves frequent computations of the form: int a,b,c,d; a = (b*c)/d; a = (b*c) % d; Even when I know (because of normalization or other conditions) that a will fit in a single machine word, C does not allow one to do such computations. The difficulty of course is that b*c frequently will overflow. However, many machines CAN multiply two full words together giving a double length product placed in two adjacent registers. Since there is no 'double register int a' or 'long long a' in C, one is forced however to write an assembler routine to do such arithmetic. However, if one does such computations frequently (e.g. millions of times) the cost of calling a routine to do it is prohibitive. e.g. A three argument call on the VAX takes 16+ usec. Does anyone have a good solution? Does C++ have long longs? Does anyone know of ANY language that does? (Bignums in Lisp don't qualify) Bob Silverman
chris@umcp-cs.UUCP (Chris Torek) (03/01/86)
In article <491@faron.UUCP> bs@faron.UUCP (Bob Silverman) writes: >Does anyone have a good solution [to getting (b*c)/d and (b*c)%d >done with double-length instructions]? and also mentions that one can >write an assembler routine to do such arithmetic. However, if one >does such computations frequently (e.g. millions of times) the cost >of calling a routine to do it is prohibitive. One method, used in the 4BSD kernel and in Franz Lisp, is to write a `sed' script, and run the output of the compiler through this. Thus what looks like a function call is actually expanded in-line: # foo.e - sed script to expand various routines in line # # Usage: /lib/cpp file.c | /lib/ccom | sed -f foo.e | /lib/c2 | \ # as -o file.o # (or use .s files if your `as' cannot read pipes). # # Change calls to `foo' to a `bar' instruction. # Foo takes two arguments and presents a return # value in r0. /calls $2,_foo/s//movl (sp)+,r0\ movl (sp)+,r1\ bar r1,r0/ This costs a few redundant stack operations; these can be avoided by using the 4.3BSD `inline' program---if you have it---in place of sed. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1415) UUCP: seismo!umcp-cs!chris CSNet: chris@umcp-cs ARPA: chris@mimsy.umd.edu
hosking@convexs.UUCP (03/03/86)
> Does anyone have a good solution? > > Does C++ have long longs? Does anyone know of ANY language that does? > > > > Bob Silverman We ran into exactly this sort of problem with the Convex C-1. It has 64 bit registers, but we didn't want to make "long" be 64 bits, for a number of reasons, including "portability" with existing code which assumed that sizeof(long) == sizeof(int) (Argh!!), and performance impact on typical applications. /* Danger, Will Robinson! Flames from hoptoad!laura approaching! */ We therefore support "short" "int" "long" and "long long" - where sizeof(long long) == 64 bits. You can argue that this is not portable, and I'd have to agree, but it seemed like the best solution at the time, given that we had to get a product to market in order to survive. Had we been doing the C compiler as a research project, we might very well have made different decisions. Doug Hosking Convex Computer Corp. Richardson, TX {allegra, ihnp4, uiucdcs}!convex!hosking
jon@cit-vax.ARPA (Jonathan P. Leech) (03/03/86)
> From: "Robert D. Silverman" <bs%faron.uucp@BRL.ARPA> > Subject: Long Longs > > ... Various reasons for wanting 'long longs' deleted > > Does C++ have long longs? Does anyone know of ANY language that does? > (Bignums in Lisp don't qualify) > > Bob Silverman Some C compilers have them, especially if the hardware supports it. I know that C on ELXSI Unix and UTS (Amdahl) Unix has them. Note that (even if they were added to the ANSI standard) there is nothing prohibiting the COMPILER from generating function calls just as you would - many compilers already do this for floating point operations if there is no hardware f.p. - so there's no guaranteed speedup. You could define a class in C++ containg 64-bit longs and overload the normal arithmetic operations to work on them; getting it to generate the 'proper' code for int b, c, d; longlong result; result = (b * c) / d; would be more difficult. My limited experience with C++ makes me think that you would have to define a new class equivalent to int except that result of '*' is a longlong (or whatever you want to call it). C++ could generate such code inline. Final cautionary note: [ from K&R Appendix A Sec. 7 (pg 185) Expressions ]: "... Expressions involving a commutative and associative operator (*, +, &, |, ^) may be rearranged arbitrarily, even in the presence of parentheses; to force a particular order of evaluation an explicit temporary must be used." I believe the ANSI draft lets you specify order of evaluation with the unary '+' operator, so you would want a = +(b * c) / d; whenever ANSI compilers finally arrive. -- Jon Leech (jon@csvax.caltech.edu) __@/
kwh@bentley.UUCP (KW Heuer) (03/04/86)
In article <491@faron.UUCP> faron!bs (Bob Silverman) writes: >[How do I calculate without intermediate overflow] >a = (b*c)/d; >a = (b*c) % d; >... Many machines CAN multiply two full words together giving a double >length product placed in two adjacent registers. Many others can't. If the feature were built into the language, what code should it generate for "long long" arithmetic on a more limited machine? >Does C++ have long longs? C++ cannot do anything that C cannot, since it produces C output. >Does anyone have a good solution? My prefered method (to maximize portability) is to have library functions int muldiv(int, int, int) int mulrem(int, int, int) which are written in assembly language; for specific applications in tight loops I hand-optimize the .s file as described in article <3408@umcp-cs.UUCP> by umcp-cs!chris (Chris Torek) (not quoted here). It seems to me that best solution for the future is for "int" to be 32 bits wide, while "long" is 64. I expect the compilers will start doing this once there is a little more support for 64-bit arithmetic in the hardware. (Like when 32-bit addresses aren't big enough.) No smiley on this paragraph, I'm serious. Incidentally, does anyone have a muldiv routine (in C or as) for a 32-bit machine without emul/ediv instructions? Currently I'm using (int)((double)x*(double)y/(double)z) which is quite slow on a 3b2 without floating-point hardware. Karl W. Z. Heuer (ihnp4!bentley!kwh), The Walking Lint
rich@rexago1.UUCP (K. Richard Magill) (03/04/86)
in reference to functions vs inline code... In article <3408@umcp-cs.UUCP> chris@umcp-cs.UUCP (Chris Torek) writes: >One method, used in the 4BSD kernel and in Franz Lisp, is to write >a `sed' script, and run the output of the compiler through this. >Thus what looks like a function call is actually expanded in-line: > > # foo.e - sed script to expand various routines in line > # > # Usage: /lib/cpp file.c | /lib/ccom | sed -f foo.e | /lib/c2 | \ > # as -o file.o > # (or use .s files if your `as' cannot read pipes). > # > # Change calls to `foo' to a `bar' instruction. > # Foo takes two arguments and presents a return > # value in r0. > /calls $2,_foo/s//movl (sp)+,r0\ > movl (sp)+,r1\ > bar r1,r0/ Paraphrased from "Maxicomputing in Microspace", (WE32100 info manual select code 451-000): Under the -O option the compiler expands functions inline providing, 1) the function has no local variables 2) no registers are saved 3) the function appears in the same file. ... K. Richard Magill
kwh@bentley.UUCP (KW Heuer) (03/04/86)
In article <1434@brl-smoke.ARPA> jon@cit-vax.ARPA (Jon Leech) writes: >Getting [ a C++ "class longlong" ] to generate the 'proper' code for > int b, c, d; > longlong result; > result = (b * c) / d; >would be more difficult. If you're willing to write it result = ((longlong)b * c) / d; it will work, but it will invoke a more powerful function than it needs. >Final cautionary note: [ from K&R ] "... Expressions ... may be >rearranged arbitrarily ..." That doesn't apply here; the only way b*c/d can be rearranged by the compiler is to write it c*b/d (using commutativity of "*"). It can't be written b*(c/d), for example, because that is not mathematically correct (since x/y means floor(x/y)). It could only do the division first if it were a floating-point expression. Besides, if you're talking about an overloaded C++ operator, none of the mathematical identities are assumed: b*c/d means exactly operator/(operator*(b,c),d); the compiler makes no assumptions about the semantics. Karl W. Z. Heuer (ihnp4!bentley!kwh), The Walking Lint
franka@mmintl.UUCP (Frank Adams) (03/05/86)
In article <1434@brl-smoke.ARPA> jon@cit-vax.ARPA (Jonathan P. Leech) writes: > Final cautionary note: [ from K&R Appendix A Sec. 7 (pg 185) >Expressions ]: > > "... Expressions involving a commutative and associative operator > (*, +, &, |, ^) may be rearranged arbitrarily, even in the > presence of parentheses; to force a particular order of evaluation > an explicit temporary must be used." This would let the compiler rearrange a = (b * c) * d; to a = b * (c * d); but it does not permit a = (b * c) / d; to be rearranged to a = b * (c / d); at least if b, c, and d are of integral type. Frank Adams ihnp4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
nolan@mimsy.umd.edu (03/06/86)
Who ever said that sizeof(long) must equal sizeof(int). It is precisely because they don't need to be the same size that we have ints and longs. True, many programmers make that assumption.....that doesn't make it right. I apologise for the above flame but it cheeses me off. john nolan@maryland American Air Force Express....Don't be deposed without it....F.E.Marcos
gwyn@BRL.ARPA (03/06/86)
We like short shorts.
laura@hoptoad.uucp (Laura Creighton) (03/10/86)
In article <7000005@convexs> hosking@convexs.UUCP writes: >We ran into exactly this sort of problem with the Convex C-1. It has 64 bit >registers, but we didn't want to make "long" be 64 bits, for a number of >reasons, including "portability" with existing code which assumed that >sizeof(long) == sizeof(int) (Argh!!), and performance impact on typical >applications. >/* Danger, Will Robinson! Flames from hoptoad!laura approaching! */ >We therefore support "short" "int" "long" and "long long" - where >sizeof(long long) == 64 bits. Nope -- the flame from hoptoad!laura comes right after yours -- beside the (Arghh!!). I think that you did the right thing, given your constraints. It is the fact that one of your constraints was ``we can hire someone for a year to take the (sizeof int == sizeof long)s out of 4.2, and delay shipping for a year, or we can work around it.'' -- Laura Creighton ihnp4!hoptoad!laura utzoo!hoptoad!laura sun!hoptoad!laura toad@lll-crg.arpa