Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | James Kuyper <jameskuyper@verizon.net> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: what is the right value about a = a++; |
| Date | 2012-02-08 22:25 -0500 |
| Organization | A noiseless patient Spider |
| Message-ID | <jgvean$8mm$1@dont-email.me> (permalink) |
| References | (4 earlier) <20120207090433.476@kylheku.com> <qdadndbp0NhHGKzSnZ2dnUVZ_uCdnZ2d@bestweb.net> <4f319955.234650417@text.giganews.com> <27WdnWl1SYYBQK_SnZ2dnUVZ_q2dnZ2d@bestweb.net> <93794fd7-14e9-4bef-b9bc-f027dd734ce7@o13g2000vbf.googlegroups.com> |
On 02/08/2012 08:41 PM, John Bode wrote: > Is this anything more than received wisdom? Does anyone have a > concrete example (read: generated machine code) showing *how* > rearranging evaluation order can make an operation more efficient? As a undergrad, I once had a summer job where I was responsible for writing some hand-optimized assembler to replace two C subroutines that had been found to be a bottleneck in a scientific calculation. I no longer remember the concrete details you're asking for, but I do remember the general strategies I used, and they all depended upon rearranging the evaluation order. On the machine I was writing for, there was one component that could handle either a division or a sqrt() operation in parallel with multiplications and additions. The main loop required one division, followed by a sqrt(), followed by another division. Division and sqrt() both took much longer than either a multiplication or an addition, so one of the first things I did was rearrange evaluation so the division started as early as possible, and was immediately followed by the sqrt(), which was then followed by the second division, and I rearranged things so that as many multiplications and additions as possible were done between the start of the division and the completion of the sqrt(). Another key aspect of this machine was a component that could carry out the register-based equivalent of fma() in three clock cycles, and could be working on three different fma() operations at the same time, if they were each started on a different clock cycle. Because the subroutine was carrying out matrix multiplications, I could easily arrange to keep that component busy almost full time, but doing so required rearranging the order of evaluation extensively. Finally, one of the key things I could do which the compiler was not able to do, was to treat three different registers as the elements of a 3-component array. This helped to drastically reduce the number of slow load and store operations, but it meant that a naive implementation of the subroutine would have required three times as many registers as were actually available. I dealt with this by rearranging the order of evaluation so that the each register could be used to represent the value of several different variables during the course of the subroutine, by making sure that the periods of time during which the register represented each variable didn't overlap. IIRC, if there had been even a single additional register, I could have completely avoided using RAM for any of the intermediate steps; as it was, I think there was only one load and one store per pass through the main loop. It was my first and last project writing in that assembly language. I documented as accurately as I could precisely how I had designed it, but I'm sure it was almost completely unmaintainable. My supervisor expected me to spend the entire summer on it. I completed it in a couple of weeks, and sped up the subroutine by a factor of 3.5, which disappointed me - I'd been expecting a factor of 5. But the relevant subroutine was going to be keeping hundreds of processors busy with a nearly 100% duty cycle for several years, so that speed-up easily paid for the cost of my salary. And most of it would have been impossible if I'd not been free to rearrange the order of evaluation. All of my rearrangements conformed to the as-if rule, however, so I'm not sure they're directly relevant to this discussion. The real issue is whether declaring certain kinds of behavior undefined makes it easier to optimize code by mechanisms that would violate the as-if rule if the behavior were defined. I believe this is the case, but I don't have any anecdotes that demonstrate that fact. -- James Kuyper
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
what is the right value about a = a++; lujnan <lujnan@gmail.com> - 2012-02-06 00:10 -0800
Re: what is the right value about a = a++; Ruben Mikkonen <camu.umac@gmail.com> - 2012-02-06 00:28 -0800
Re: what is the right value about a = a++; Keith Thompson <kst-u@mib.org> - 2012-02-06 21:27 -0800
Re: what is the right value about a = a++; Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2012-02-06 22:39 -0700
Re: what is the right value about a = a++; bert <bert.hutchings@btinternet.com> - 2012-02-06 01:45 -0800
Re: what is the right value about a = a++; lujnan <lujnan@gmail.com> - 2012-02-06 02:33 -0800
Re: what is the right value about a = a++; "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2012-02-06 14:57 -0800
Re: what is the right value about a = a++; Barry Schwarz <schwarzb@dqel.com> - 2012-02-06 22:50 -0800
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-07 08:15 +0000
Re: what is the right value about a = a++; lujnan <lujnan@gmail.com> - 2012-02-07 00:31 -0800
Re: what is the right value about a = a++; Keith Thompson <kst-u@mib.org> - 2012-02-07 09:07 -0800
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-07 17:31 +0000
Re: what is the right value about a = a++; Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-09 17:50 -0800
Re: what is the right value about a = a++; Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-21 23:42 +0200
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-22 04:28 +0000
Re: what is the right value about a = a++; Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-25 00:01 +0200
Re: what is the right value about a = a++; Shao Miller <sha0.miller@gmail.com> - 2012-02-25 02:25 -0500
Re: what is the right value about a = a++; Ike Naar <ike@iceland.freeshell.org> - 2012-02-25 09:00 +0000
Re: what is the right value about a = a++; Philip Lantz <prl@canterey.us> - 2012-02-25 11:13 -0800
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-25 19:34 +0000
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-25 16:51 -0500
Re: what is the right value about a = a++; lawrence.jones@siemens.com - 2012-02-27 16:12 -0500
Re: what is the right value about a = a++; Ike Naar <ike@iceland.freeshell.org> - 2012-02-27 22:42 +0000
Re: what is the right value about a = a++; Shao Miller <sha0.miller@gmail.com> - 2012-02-27 18:54 -0500
Re: what is the right value about a = a++; Barry Schwarz <schwarzb@dqel.com> - 2012-02-07 09:26 -0800
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-07 15:12 -0500
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-07 21:50 +0000
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-07 16:51 -0600
Re: what is the right value about a = a++; Robert Wessel <robertwessel2@yahoo.com> - 2012-02-07 22:49 -0600
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-08 14:08 -0600
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 00:18 +0000
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-09 13:06 -0500
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-09 13:58 -0600
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 23:52 +0000
Re: what is the right value about a = a++; jgk@panix.com (Joe keane) - 2012-02-10 21:45 +0000
Re: what is the right value about a = a++; Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-22 00:09 +0200
Re: what is the right value about a = a++; Robert Wessel <robertwessel2@yahoo.com> - 2012-02-08 22:35 -0600
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-08 15:42 -0500
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-08 14:47 +0000
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-08 14:29 -0600
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-10 02:27 +0000
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-09 23:10 -0500
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-10 09:11 +0000
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-10 07:26 -0500
Re: what is the right value about a = a++; Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-02-10 13:12 +0000
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-10 11:07 -0500
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-10 16:27 +0000
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-10 12:17 -0500
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-10 12:09 -0600
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-10 18:17 -0500
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-11 10:15 +0000
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-13 16:04 -0500
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-10 12:30 -0600
Re: what is the right value about a = a++; Shao Miller <sha0.miller@gmail.com> - 2012-02-09 21:30 -0500
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-10 02:48 +0000
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-10 09:49 +0000
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 00:15 +0000
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-09 12:49 -0500
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 23:51 +0000
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-08 15:39 -0500
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 01:05 +0000
Re: what is the right value about a = a++; Shao Miller <sha0.miller@gmail.com> - 2012-02-09 23:24 -0500
Re: what is the right value about a = a++; Jens Gustedt <jens.gustedt@loria.fr> - 2012-02-10 16:58 +0100
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-10 23:32 +0000
Re: what is the right value about a = a++; John Bode <jfbode1029@gmail.com> - 2012-02-08 17:41 -0800
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-08 22:25 -0500
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-09 13:15 -0500
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 23:57 +0000
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-10 11:15 -0500
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-10 11:58 -0600
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-10 18:14 -0500
Re: what is the right value about a = a++; Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-02-10 22:43 +0000
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-10 11:53 -0600
Re: what is the right value about a = a++; Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-10 15:19 -0800
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-10 02:32 +0000
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-09 23:13 -0500
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-10 09:34 +0000
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-10 07:32 -0500
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-10 22:24 +0000
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-10 11:35 -0500
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-10 12:23 -0500
Re: what is the right value about a = a++; falk@rahul.net (Edward A. Falk) - 2012-02-08 20:40 +0000
Re: what is the right value about a = a++; Keith Thompson <kst-u@mib.org> - 2012-02-08 15:00 -0800
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 01:10 +0000
Re: what is the right value about a = a++; 88888 Dihedral <dihedral88888@googlemail.com> - 2012-02-09 20:43 -0800
Re: what is the right value about a = a++; Robert Wessel <robertwessel2@yahoo.com> - 2012-02-09 23:36 -0600
Re: what is the right value about a = a++; cri@tiac.net (Richard Harter) - 2012-02-10 02:40 +0000
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-09 23:17 -0500
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-08 23:49 +0000
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-08 23:42 +0000
Re: what is the right value about a = a++; blp@cs.stanford.edu (Ben Pfaff) - 2012-02-07 12:09 -0800
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-07 07:42 -0500
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-07 17:21 +0000
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-07 15:24 -0600
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 01:27 +0000
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-10 21:57 -0600
Re: what is the right value about a = a++; "Joel C. Salomon" <joelcsalomon@gmail.com> - 2012-02-08 01:00 -0500
Re: what is the right value about a = a++; falk@rahul.net (Edward A. Falk) - 2012-02-08 20:33 +0000
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 02:05 +0000
Re: what is the right value about a = a++; Markus Wichmann <nullplan@gmx.net> - 2012-02-09 09:28 +0100
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 10:21 +0000
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-09 11:38 +0000
Re: what is the right value about a = a++; Shao Miller <sha0.miller@gmail.com> - 2012-02-10 00:03 -0500
Re: what is the right value about a = a++; Philip Lantz <prl@canterey.us> - 2012-02-10 01:15 -0800
Re: what is the right value about a = a++; Kenneth Brody <kenbrody@spamcop.net> - 2012-02-09 13:22 -0500
Re: what is the right value about a = a++; Slash QB <slashqb@gmail.com> - 2012-02-06 02:35 -0800
Re: what is the right value about a = a++; Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-02-07 03:07 -0800
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-07 15:19 -0600
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-07 17:00 -0500
Re: what is the right value about a = a++; Stephen Sprunk <stephen@sprunk.org> - 2012-02-10 12:05 -0600
Re: what is the right value about a = a++; James Kuyper <jameskuyper@verizon.net> - 2012-02-10 13:46 -0500
Re: what is the right value about a = a++; Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2012-02-06 22:37 -0700
Re: what is the right value about a = a++; Kaz Kylheku <kaz@kylheku.com> - 2012-02-07 07:22 +0000
Re: what is the right value about a = a++; Shao Miller <sha0.miller@gmail.com> - 2012-02-07 01:18 -0500
csiph-web