Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #106011 > unrolled thread
| Started by | BartC <bc@freeuk.com> |
|---|---|
| First post | 2017-03-14 13:01 +0000 |
| Last post | 2017-03-16 23:19 +0000 |
| Articles | 20 on this page of 115 — 22 participants |
Back to article view | Back to comp.lang.c
C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 13:01 +0000
Re: C Compilers QoI mark.bluemel@gmail.com - 2017-03-14 06:16 -0700
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 06:42 -0700
Re: C Compilers QoI "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-14 06:56 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 15:58 +0000
Re: C Compilers QoI "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-03-14 09:22 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-14 16:54 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 10:24 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-14 17:58 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 14:12 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-14 16:34 -0500
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-14 17:36 -0500
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 23:06 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 16:20 -0700
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-15 02:32 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-15 12:49 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-15 11:56 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-15 23:09 +0000
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-16 18:17 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 11:47 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 07:50 +1300
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 12:59 -0700
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-16 21:24 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 14:23 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:30 +1300
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:38 +1300
Re: C Compilers QoI Gareth Owen <gwowen@gmail.com> - 2017-03-17 05:07 +0000
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 20:26 +1300
Re: C Compilers QoI Gareth Owen <gwowen@gmail.com> - 2017-03-17 07:59 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 16:14 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-16 22:54 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-17 09:01 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-26 14:16 +1300
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-26 14:19 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-26 22:43 +0100
Re: C Compilers QoI GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-03-27 01:28 +0200
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-26 22:07 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 11:28 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 07:38 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 16:23 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 08:55 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-27 17:01 +0100
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 10:03 -0700
Re: C Compilers QoI GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-03-27 17:58 +0200
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-27 03:54 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 08:46 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-27 17:47 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 11:48 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 15:37 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 14:46 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 20:28 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-28 01:18 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-28 18:24 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-29 07:40 -0700
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-29 17:05 +0200
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-29 11:07 -0700
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-31 04:04 +0000
Re: C Compilers QoI bartc <bc@freeuk.com> - 2017-03-31 10:53 +0100
Re: C Compilers QoI Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-31 07:35 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 08:07 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 07:54 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-31 07:43 -0700
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:21 +1300
Re: C Compilers QoI Ian Collins <ian-news@hotmail.com> - 2017-03-17 11:24 +1300
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 22:15 +0000
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-17 12:31 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-16 15:24 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 16:03 -0700
Re: C Compilers QoI scott@slp53.sl.home (Scott Lurndal) - 2017-03-17 12:39 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-17 08:27 -0700
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-16 01:35 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 02:18 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-18 00:45 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-18 13:12 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-18 20:31 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-18 17:31 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-16 09:22 -0700
Re: C Compilers QoI Nick Bowler <nbowler@draconx.ca> - 2017-03-24 16:13 +0000
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-24 12:32 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-24 22:13 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-25 13:05 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 15:44 -0500
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-27 14:51 -0700
Re: C Compilers QoI Robert Wessel <robertwessel2@yahoo.com> - 2017-03-27 20:31 -0500
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:26 +0000
Re: C Compilers QoI Andrew Haley <andrew29@littlepinkcloud.invalid> - 2017-03-15 12:02 -0500
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 15:00 +0100
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 07:36 -0700
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 15:57 +0100
Re: C Compilers QoI Andrey Tarasevich <andreytarasevich@hotmail.com> - 2017-03-14 08:11 -0700
Re: C Compilers QoI BGB <cr88192@hotmail.com> - 2017-03-29 23:51 -0500
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 15:28 +0000
Re: C Compilers QoI David Brown <david.brown@hesbynett.no> - 2017-03-14 21:41 +0100
Re: C Compilers QoI Keith Thompson <kst-u@mib.org> - 2017-03-14 09:26 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 18:23 +0000
Re: C Compilers QoI Keith Thompson <kst-u@mib.org> - 2017-03-14 12:05 -0700
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 09:35 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:08 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 10:24 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 17:34 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 11:55 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:03 +0000
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:06 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 12:10 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 21:14 +0000
Re: C Compilers QoI already5chosen@yahoo.com - 2017-03-14 14:42 -0700
Re: C Compilers QoI supercat@casperkitty.com - 2017-03-14 14:53 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 23:20 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-15 02:43 +0000
Re: C Compilers QoI jacobnavia <jacob@jacob.remcomp.fr> - 2017-03-14 19:39 +0100
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-14 19:10 +0000
Re: C Compilers QoI antispam@math.uni.wroc.pl - 2017-03-14 19:29 +0000
Re: C Compilers QoI Noob <root@127.0.0.1> - 2017-03-15 09:27 +0100
Re: C Compilers QoI ed_davis2@yahoo.com - 2017-03-16 15:10 -0700
Re: C Compilers QoI BartC <bc@freeuk.com> - 2017-03-16 23:19 +0000
Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6 Next page →
| From | supercat@casperkitty.com |
|---|---|
| Date | 2017-03-31 07:54 -0700 |
| Message-ID | <25c0d3fa-6831-4b8f-a6ef-3dc170faca99@googlegroups.com> |
| In reply to | #107537 |
On Friday, March 31, 2017 at 4:53:38 AM UTC-5, Bart wrote: > Now you'd have to use (p-q)*sizeof(*p). In fact, what happens at the > moment is that (p-q), which has a natural byte offset at machine level, > has to be divided by sizeof (*p) to get the element offset, then you > have to multiply by sizeof(*p) to get back the byte offset! These ought > to be cancel out, but that optimisation has to be done. The divide and multiply can't be canceled out unless the offset is a multiple of the item size and the compiler knows that. If p is a long*, for example, and a platform doesn't require alignment for that type, then then the syntax p[ofs/sizeof(p*)] would be required to use an offset of (ofs & ~3).
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2017-03-31 07:43 -0700 |
| Message-ID | <29a5b0f7-1e55-49b3-90c6-88d98a3f6248@googlegroups.com> |
| In reply to | #107531 |
On Thursday, March 30, 2017 at 11:04:51 PM UTC-5, anti...@math.uni.wroc.pl wrote:
> supercat wrote:
> >
> > Further, my point was that I found it curious that C didn't include a set
> > of pointer arithmetic operators (e.g. ~+, ~-, and ~[]) that were byte-based
> > rather than object-based, since such operators would have made it possible
> > for programmers and compilers to perform strength reduction with the kinds
> > of compilers that were in use back then.
>
> For program writen in pointer style such operators would be
> almost of no use, after all normal case is to go to next
> element. And if needed programmer could define pointers
> as char * and use casts when dereferencing. AFAICS with naive
> compilers programmer was supposed to choose between array style
> and pointer style. So nonoptimizing compiler would have almost
> no opportunity to perform useful strength reduction. OTOH
> by not having such operators compiler can be smaller, which
> was important at that time.
On something like 16-bit x86 which typically allows two 16-bit register-
qualified variables, something like:
register int x=18;
do
arr1~[x]+=arr2~[x];
// or *(int*)((char*)arr1+x) += *(int*)((char*)arr2+x)
while((x-=2) >= 0);
could rather easily yield:
mov si,9
lp:
mov ax,[arr2+si]
add [arr1+si],ax
sub si,2
jp lp ; I think that's "jump positive"
The only part of that that would require any "optimization" beyond simple
code generation would be recognition that "sub" will set the flag needed
for a conditional jump without requiring a "cmp si,0".
Using marching pointers, the best code would probably be:
register int *near src=arr2;
register int *near dest=arr1;
do
{
*dest++ += *src++;
} while(dest < arr1+10);
which would yield:
mov si,offset arr2
mov di,offset arr1
lp:
mov ax,[si]
add si,2
add [di],ax
add di,2
cmp di,20+offset _arr2
jb lp
One of the goals of C is to allow things to be written concisely in source
code, and requiring lots of casts would seem to go against that goal.
> Take into account that in early C days people started looking
> at relative frequencies of various operations. And when
> something is rare enough it is not worth optimizing.
A major reason byte-based pointer arithmetic isn't common is that the
syntax is rather painful. Compatibility with B would require that
normal arithmetic operations on pointers to int or pointers to pointers
scale by the size of the pointer target, but supporting byte-based
operations in the language would be cheaper than adding the logic that
would be necessary to perform automatic strength reduction required to
yield decent code from:
register int x=9;
do
arr1[x]+=arr2[x];
while((x--) >= 0);
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2017-03-17 11:21 +1300 |
| Message-ID | <ej0hfsFhe9iU9@mid.individual.net> |
| In reply to | #106278 |
On 03/17/17 08:59 AM, supercat@casperkitty.com wrote: > On Thursday, March 16, 2017 at 1:50:51 PM UTC-5, Ian Collins wrote: >> On 03/17/17 07:47 AM, supercat wrote: >>> That's only really relevant if the person who is using the compiler knows >>> what kind of hardware will be used to run the generated code. Otherwise >>> code orderings which improve performance on one processor may make it worse >>> on another. >> >> Which is why compilers have extensive architecture related options... > > ...which are useful **in the case where the user of the compiler knows what > kind of hardware will be used to run the generated code.** Which is their intent! Hence names like "-xtarget=native". > If an executable is being built for the purpose of publication, the person > who built it may have no way of knowing everyone who might want to use it or > what kind of hardware they may have. As such, it may not make sense to > worry about the intricacies of particular processors' instruction scheduling > except possibly to avoid performance disasters. Quite, in that case use generic options, such as (for Sun cc) "-xchip=generic". -- Ian
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2017-03-17 11:24 +1300 |
| Message-ID | <ej0hl3Fhe9iU10@mid.individual.net> |
| In reply to | #106292 |
On 03/17/17 11:21 AM, Ian Collins wrote: > On 03/17/17 08:59 AM, supercat@casperkitty.com wrote: >> On Thursday, March 16, 2017 at 1:50:51 PM UTC-5, Ian Collins wrote: >>> On 03/17/17 07:47 AM, supercat wrote: >>>> That's only really relevant if the person who is using the compiler knows >>>> what kind of hardware will be used to run the generated code. Otherwise >>>> code orderings which improve performance on one processor may make it worse >>>> on another. >>> >>> Which is why compilers have extensive architecture related options... >> >> ...which are useful **in the case where the user of the compiler knows what >> kind of hardware will be used to run the generated code.** > > Which is their intent! Hence names like "-xtarget=native". > >> If an executable is being built for the purpose of publication, the person >> who built it may have no way of knowing everyone who might want to use it or >> what kind of hardware they may have. As such, it may not make sense to >> worry about the intricacies of particular processors' instruction scheduling >> except possibly to avoid performance disasters. > > Quite, in that case use generic options, such as (for Sun cc) > "-xchip=generic". I should also add that run time loaders should be able to tell whether an executable is is built for the current architecture. This certainly the case with Solaris, where I build my applications for the oldest architectures we support. -- Ian
[toc] | [prev] | [next] | [standalone]
| From | BartC <bc@freeuk.com> |
|---|---|
| Date | 2017-03-16 22:15 +0000 |
| Message-ID | <oaf2kk$qh7$1@dont-email.me> |
| In reply to | #106259 |
On 16/03/2017 18:17, Scott Lurndal wrote: > BartC <bc@freeuk.com> writes: > >> >> I don't understand what you mean about a function, above. But the code >> TCC32 generates for such a member access is: >> >> mov eax,[p] >> add eax,4 >> mov ecx,[eax] >> add ecx,3 >> mov [eax],ecx >> >>> to >>> >>> mov ebx,[p] >>> add [dword ebx],3 >> >> The code I generate is more like this (but with a +4 offset you may have >> missed). But which one is faster on x86 is anyone's guess (maybe >> read-modify-write instructions are slower). > > If you are writing a compiler, and you're not familiar with the > Intel Software/Architecture Optimization Guides, which tell you _exactly_ > how fast each instruction is, then you're not doing it right > (hint: The add instruction above, assuming a hit in L1, is a > single cycle instruction Which one? There are three. (with, perhaps a load-to-use penalty > of three or four cycles depending on where in the pipeline you > are)). > > That guide makes many recommendations to compiler writers on how > to generate optimally performing code, from simple things like > using xor to clear a register to how to most effectively schedule > instructions to keep all the out-of-order pipelines active. Another > recommendation is to use ADD/SUB instead of INC/DEC (due to potential > false dependencies on the processor flags), or to use LEA instead > of ADD/MUL in some situations. I've seen the AMD optimisation guide. I didn't find it that useful (a lot of it is about optimising C code, which I can already guess). However, if the starting point is the crude output from a simple code generator, then the necessary improvements are obvious. You don't need a book to tell you that repeatedly loading and storing the same value instead of keeping it in a register is not great code. But generating better code automatically from a program of arbitrary complexity is not straightforward. Still, there needn't be that much of a gulf between good and indifferent code. In the case of my own programs, compiled via C with gcc -O3 (no other arch-specific options nor tweaking with __inline__ everywhere etc) might take 25ms on a particular test; my own code might take 31ms. -- bartc
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2017-03-17 12:31 +0000 |
| Message-ID | <YGQyA.70016$Bp6.33652@fx36.iad> |
| In reply to | #106290 |
BartC <bc@freeuk.com> writes: >On 16/03/2017 18:17, Scott Lurndal wrote: >> BartC <bc@freeuk.com> writes: >> >>> >>> I don't understand what you mean about a function, above. But the code >>> TCC32 generates for such a member access is: >>> >>> mov eax,[p] >>> add eax,4 >>> mov ecx,[eax] >>> add ecx,3 >>> mov [eax],ecx >>> >>>> to >>>> >>>> mov ebx,[p] >>>> add [dword ebx],3 >>> >>> The code I generate is more like this (but with a +4 offset you may have >>> missed). But which one is faster on x86 is anyone's guess (maybe >>> read-modify-write instructions are slower). >> >> If you are writing a compiler, and you're not familiar with the >> Intel Software/Architecture Optimization Guides, which tell you _exactly_ >> how fast each instruction is, then you're not doing it right >> (hint: The add instruction above, assuming a hit in L1, is a >> single cycle instruction > >Which one? There are three. The phrase "assuming a hit in L1" implicitly reduces the population to one.
[toc] | [prev] | [next] | [standalone]
| From | already5chosen@yahoo.com |
|---|---|
| Date | 2017-03-16 15:24 -0700 |
| Message-ID | <9ed90e71-ea25-429c-8243-8aaf1585f828@googlegroups.com> |
| In reply to | #106259 |
On Thursday, March 16, 2017 at 8:18:08 PM UTC+2, Scott Lurndal wrote: > BartC <bc@freeuk.com> writes: > > > > >I don't understand what you mean about a function, above. But the code > >TCC32 generates for such a member access is: > > > > mov eax,[p] > > add eax,4 > > mov ecx,[eax] > > add ecx,3 > > mov [eax],ecx > > > >> to > >> > >> mov ebx,[p] > >> add [dword ebx],3 > > > >The code I generate is more like this (but with a +4 offset you may have > >missed). But which one is faster on x86 is anyone's guess (maybe > >read-modify-write instructions are slower). > > If you are writing a compiler, and you're not familiar with the > Intel Software/Architecture Optimization Guides, which tell you _exactly_ > how fast each instruction is, then you're not doing it right > (hint: The add instruction above, assuming a hit in L1, is a > single cycle instruction (with, perhaps a load-to-use penalty > of three or four cycles depending on where in the pipeline you > are)). > I don't write compilers, but I do read Intel Optimization Reference Manual regularly. I am pretty sure that Manual never mentioned the speed of read-modify-write operations, like "add [dword ebx],3" on "normal" Intel processors. May be, you can find info about old in-order Atoms in the manuals. May be, not even that. My personal guess is that in most situations 2-instructions sequences will run 1 clock faster than 5-instructions sequence. But 4-instructions sequence like below will run at the same speed as 2-instructions sequence. mov eax,[p] mov ecx,[eax+4] add ecx,3 mov [eax+4],ecx Yet another sequence that will also run at the same speed: mov eax,[p] mov ecx,3 add ecx,[eax+4] mov [eax+4],ecx If the speed is the same then it makes sense for compiler to generate 2-instruction sequence, because it occupies less space and uses up fewer registers. But "same speed: is just my guess. And manual is absolutely no help in this sort of situation. Only measurements can tell. But measurements also can't tell :(, because they are typically too noisy to detect such minor speed-ups or slow-downs. > That guide makes many recommendations to compiler writers on how > to generate optimally performing code, from simple things like > using xor to clear a register to how to most effectively schedule > instructions to keep all the out-of-order pipelines active. Another > recommendation is to use ADD/SUB instead of INC/DEC (due to potential > false dependencies on the processor flags), Manual does not tell you, but measurements show that on latest Intel processors ADD/SUB is no faster than INC/DEC. And INC/DEC is shorter. > or to use LEA instead > of ADD/MUL in some situations.
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2017-03-16 16:03 -0700 |
| Message-ID | <753c7540-d04f-47f9-b255-e079ae9e9285@googlegroups.com> |
| In reply to | #106293 |
On Thursday, March 16, 2017 at 5:24:15 PM UTC-5, already...@yahoo.com wrote: > If the speed is the same then it makes sense for compiler to generate 2-instruction sequence, because it occupies less space and uses up fewer registers. But "same speed: is just my guess. And manual is absolutely no help in this sort of situation. Only measurements can tell. But measurements also can't tell :(, because they are typically too noisy to detect such minor speed-ups or slow-downs. On many processors performance can be limited by several different bottlenecks. Even on the 8088, performance could be limited (rarely) by execution speed or (often) by memory-bus speed. Curiously, the 8088 documentation paid much more attention to execution speed even in cases where it would hardly ever matter. Intel's documentation suggests, for example, that "MOV AX,CX" should be faster (two cycles) than "XCHG AX,CX" (three cycles). Unless one of those instructions was prefetched before it would start execution, however, (rare on the 8088), the CPU will start fetching the next instruction at the same time as it begins execution of the MOV or XCHG, and that fetch will take at least four cycles. XCHG isn't "smaller but slower"--it's going to be faster unless it's between two slow instructions like MUL or DIV.
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2017-03-17 12:39 +0000 |
| Message-ID | <INQyA.70017$Bp6.8213@fx36.iad> |
| In reply to | #106293 |
already5chosen@yahoo.com writes: >On Thursday, March 16, 2017 at 8:18:08 PM UTC+2, Scott Lurndal wrote: >> If you are writing a compiler, and you're not familiar with the >> Intel Software/Architecture Optimization Guides, which tell you _exactly_ >> how fast each instruction is, then you're not doing it right >> (hint: The add instruction above, assuming a hit in L1, is a >> single cycle instruction (with, perhaps a load-to-use penalty >> of three or four cycles depending on where in the pipeline you >> are)). >I don't write compilers, but I do read Intel Optimization Reference Manual = >regularly. I am pretty sure that Manual never mentioned the speed of read-m= >odify-write operations, like "add [dword ebx],3" on "normal" Intel processo= >rs. May be, you can find info about old in-order Atoms in the manuals. May = >be, not even that. The Intel documention does cover that particular instruction, in terms of providing the number of cycles required to execute the instruction. Note that the performance of that instruction varies - if the cache line hasn't been fetched yet, then you'll pay a 20 to 100 ns penalty to fetch the line from a higher level cache or from DRAM. If the cache line is at the closest cache (L1D), then you pay the execution penalty (1 cycle, 333ps) and depending on where in the pipeline the instruction is executed, there may be a three cycle load-to-use latency to fetch the data from L1. > >My personal guess is that in most situations 2-instructions sequences will = >run 1 clock faster than 5-instructions sequence. But 4-instructions sequenc= >e like below will run at the same speed as 2-instructions sequence.=20 Actually, since all modern processors have at least two pipelines, with generally two ALUs, parallel load units and a one or more store units, two or three of those instructions may execute in a single cycle, depending on whether or not there are ordering dependencies between the instructions (which is why a good compiler will schedule the instructions to avoid such immediate dependencies). > > mov eax,[p] > mov ecx,[eax+4] > add ecx,3 > mov [eax+4],ecx > >> That guide makes many recommendations to compiler writers on how >> to generate optimally performing code, from simple things like >> using xor to clear a register to how to most effectively schedule >> instructions to keep all the out-of-order pipelines active. Another >> recommendation is to use ADD/SUB instead of INC/DEC (due to potential >> false dependencies on the processor flags),=20 > >Manual does not tell you, but measurements show that on latest Intel proces= >sors ADD/SUB is no faster than INC/DEC. And INC/DEC is shorter. You failed to read the manual correctly. It's not about the speed of the operation, its about false depenencies affecting the overall speed of the pipe. INC and DEC are defined by the architecture to affect the processor flags in a way that results in spurious pipeline dependencies that you don't see with ADD/SUB. That definition cannot be changed thirty-plus years into the life of the architecture.
[toc] | [prev] | [next] | [standalone]
| From | already5chosen@yahoo.com |
|---|---|
| Date | 2017-03-17 08:27 -0700 |
| Message-ID | <67d4104e-a7fd-4640-9111-fbd2976f65ed@googlegroups.com> |
| In reply to | #106334 |
On Friday, March 17, 2017 at 2:39:10 PM UTC+2, Scott Lurndal wrote: > already5chosen@yahoo.com writes: > >On Thursday, March 16, 2017 at 8:18:08 PM UTC+2, Scott Lurndal wrote: > > >> If you are writing a compiler, and you're not familiar with the > >> Intel Software/Architecture Optimization Guides, which tell you _exactly_ > >> how fast each instruction is, then you're not doing it right > >> (hint: The add instruction above, assuming a hit in L1, is a > >> single cycle instruction (with, perhaps a load-to-use penalty > >> of three or four cycles depending on where in the pipeline you > >> are)). > > >I don't write compilers, but I do read Intel Optimization Reference Manual = > >regularly. I am pretty sure that Manual never mentioned the speed of read-m= > >odify-write operations, like "add [dword ebx],3" on "normal" Intel processo= > >rs. May be, you can find info about old in-order Atoms in the manuals. May = > >be, not even that. > > The Intel documention does cover that particular instruction, in terms > of providing the number of cycles required to execute the instruction. > It sounds like last time you read an actual Intel optimization reference manual was 20 years ago. Please tell me the page in the latest manual where they say how many clocks it takes to do 'add [EAX+4], ECX' on the Ivy Bridge processor that I am using to type this message. Or, if you didn't find it, please say "Sorry". > Note that the performance of that instruction varies - if the cache line > hasn't been fetched yet, then you'll pay a 20 to 100 ns penalty to fetch > the line from a higher level cache or from DRAM. If the cache line is > at the closest cache (L1D), then you pay the execution penalty (1 cycle, > 333ps) and depending on where in the pipeline the instruction is > executed, there may be a three cycle load-to-use latency to fetch > the data from L1. > > > > >My personal guess is that in most situations 2-instructions sequences will = > >run 1 clock faster than 5-instructions sequence. But 4-instructions sequenc= > >e like below will run at the same speed as 2-instructions sequence.=20 > > Actually, since all modern processors have at least two pipelines, with > generally two ALUs, parallel load units and a one or more store units, > two or three of those instructions may execute in a single cycle, depending > on whether or not there are ordering dependencies between the instructions > (which is why a good compiler will schedule the instructions to avoid > such immediate dependencies). Except that all 4 instructions in above code sequence (BTW, why did you remove the sequence from the quote? it certainly does not help to understand your message) serially depend on each other. So, please, say "Sorry" one more time. > > > > > mov eax,[p] > > mov ecx,[eax+4] > > add ecx,3 > > mov [eax+4],ecx > > > > >> That guide makes many recommendations to compiler writers on how > >> to generate optimally performing code, from simple things like > >> using xor to clear a register to how to most effectively schedule > >> instructions to keep all the out-of-order pipelines active. Another > >> recommendation is to use ADD/SUB instead of INC/DEC (due to potential > >> false dependencies on the processor flags),=20 > > > >Manual does not tell you, but measurements show that on latest Intel proces= > >sors ADD/SUB is no faster than INC/DEC. And INC/DEC is shorter. > > You failed to read the manual correctly. It's not about the speed > of the operation, its about false depenencies affecting the overall > speed of the pipe. INC and DEC are defined by the architecture to > affect the processor flags in a way that results in spurious pipeline > dependencies that you don't see with ADD/SUB. That definition cannot > be changed thirty-plus years into the life of the architecture. It all depend on implementation. If all arithmetic flags renamed together then INC/DEC has false dependency on the previous arithmetic instruction. But if carry flag renamed separately from the rest then INC/DEC can be implemented without false dependencies. The later option is harder to implement, but not impossible. For example, AMD K7/K8/K10 processors always renamed carry flag separately.
[toc] | [prev] | [next] | [standalone]
| From | antispam@math.uni.wroc.pl |
|---|---|
| Date | 2017-03-16 01:35 +0000 |
| Message-ID | <oacq5n$5vs$1@z-news.wcss.wroc.pl> |
| In reply to | #106158 |
supercat@casperkitty.com wrote:
> On Tuesday, March 14, 2017 at 9:32:34 PM UTC-5, anti...@math.uni.wroc.pl wrote:
> > supercat wrote:
> > > Back when machines were smaller, it would have been considered obvious that
> > > a quality compiler should be able to handle programs whose source tree would
> > > be larger than the amount of RAM available to the compiler. Commonplace
> > > computers have enough memory that compilers have less need to handle programs
> > > whose source trees are bigger than memory, but if simple compilers can handle
> > > such programs it shouldn't be unreasonable to expect that fancier ones should
> > > be able to do so as well.
> >
> > My toy compiler (for a tiny pseudo Pascal) can compile Bart's 1000000
> > lines in 15s. It generates assembler source, and assembly takes
> > another 20s. Generated code is awful: 12 machine instructions and
> > four temporary variables per source line. I could improve output
> > a bit, but anything worth calling "optimization" would increase
> > memory use during compilation. In fact, adding essential usablity
> > features like better error reporting or debug info requires storing
> > extra information which would increase memory use.
>
> Going after low-hanging fruit is cheap and doesn't require much extra
> memory. For example, instead of having a function to generate code to
> put an effective address into EBX, one could pass a pointer to a structure
> that describes the effective address as one of several forms, and have
> code that would perform operations on [EBX] accept that structure and
> generate code for the effective address indicated therein. If one does
> likewise for code which would place value operands in EAX, then something
> like:
>
> p->member += 3;
>
> would be improved from:
>
> mov ebx,&p
> mov ebx,[ebx]
> add ebx,4 ; member offset
> mov eax,3
> add [dword ebx],eax
>
> to
>
> mov ebx,[p]
> add [dword ebx],3
>
> A huge improvement in code quality, but relatively cheap.
Well, it would take substantial work to get your first form.
As I wrote currently the compiler is a toy, it has 1458 lines
total from which 896 is code generator. And that is wc count,
including blank lines, comments and a lot of whitespace.
In pseudo Pascal single line version of Bart's routine is:
procedure foo;
var a, b, c, d;
begin
a := b + c*d;
end;
which generates:
.globl foo
.type foo, @function
foo:
subq $64, %rsp
movq 48(%rsp), %rax
movq %rax, 56(%rsp)
movq 32(%rsp), %rax
movq %rax, 40(%rsp)
movq 16(%rsp), %rax
movq %rax, 24(%rsp)
movq 40(%rsp), %rax
imulq 24(%rsp), %rax
movq %rax, 8(%rsp)
movq 56(%rsp), %rax
addq 8(%rsp), %rax
movq %rax, 0(%rsp)
addq $64, %rsp
ret
Let me explain how this code is created. First, compiler performs
tree walk of parse tree of the whole program. During tree walk
compiler introduces temporary variable for each inner node of an
expression, effectively transforming:
a = b + c*d
into
t1 = b
t3 = c
t4 = d
t2 = t3 + t4
a = t1 + t2
Next, compiler translates each of the operations above into
seqence of machine instructions with variables assumend on
the stack, but with unknown offsets. Then there is a pass
which goes along list of generated instructions and assigns
stack slots to all used variables and temporaries.
Note that in general expression may require more temporaries
than number of available registers, so _some_ temporaries
must be stored in memory (on the stack). Currently for simplicity
all temporaries are on stack. Let us look at the last
operation, that is 'a = t1 + t2'. Compiler first fetches
first argument, getting:
movq 56(%rsp), %rax
then adds the second one:
addq 8(%rsp), %rax
finally storing the result in the destination
movq %rax, 0(%rsp)
In other words, program is decomposed into sequence of 3 and
2 address operations, each taking arguments from memory
and producing result in mempory. As long hanging fruit
one could get rid of the first 3 operations which just
copy variables to temporaries. Namely currenty each
operation has destination and compier produces result
in this destination. However, for temporaries we do
not care where exactly they are stored, but only that
we have some memory space from which we can recall the
result. So intead of copying values from variables
to temporaries compiler could just replace reference
to temporary by reference to variable. In this case
this would eliminate 6 machine instructions and 3
temporaries leading to 6 instructions doing computations
and single temporary. Better than this does not
look so easy. In principle simple piphole optimizer
could eliminate some useless stores of temporaries
to memory. But thate would be an additional pass
and AFAICS in the example above it would lead to
no improvement. It is tempting to keep temporaries
in registers and generate intermediate results
directly to registers. But AMD64 instruction set
still has various irregularities and some arguments
and/or results need to be in specific registers.
So generators for primitive operations would have
to cope with arguments or results in "wrong" registers.
Also, when compiler runs out of registers it has to
spill something, so there is need to generate spill
code and manage info about current location of variables.
All doable in serious compiler, but would significantly
complicate my toy.
Let me add that one of goals for me was compiler that
is obviously correct -- the naive tactic is reasonably
close to this. Also, while this compiler is a toy
I used similar approach prototyping compiler for
higher level language using C as a target. Now,
gcc nicely elliminates all bloat due to unnecessary
temporaries and extra copies. In fact, somewhat
bloated C code compiled by gcc leads to very good
machine code. OTOH trying to produce tighter C
may lead to worse machine code. Namely, temporaries
in generated C code cannot alias anything and gcc
can easily deduce dependencies. Reusing temporaries
and especially directly using variables from
higher level obscures information and may force
gcc to generate more conservative code. My
conclusion from this is that for purpose of
translating higher level language I can outsource
low level optimisations to gcc, instead concetrating
on higher level aspects. My current estimate is
that gcc generates about 10 times faster code
that my generator. So it would be nice to have
fast generator of good code, but at least for me
it is long way to go...
> > In another post you write that whole-program optimization is
> > not needed. Whole-program probably not, but whole-function
> > optimization may be essential to generate correct and reasonable
> > code for large functions. Namely various offsets may cross
> > limits supported by instructions. Simple cases can be
> > deferred to assembler but on say ARM you need to have data
> > space for constant pool reachable by short offset -- compiler
> > may be forced to split function into pieces and insert extra
> > jumps around data.
>
> I think the ARM assembler has a directive which instructs the assembler to
> generate a jump ahead and produce a table for previous ldr= instructions if
> it's necessary to do so, and otherwise do nothing and generate no code. On
> some assemblers for the 8051 and 8088 (Keil's assembler and Borland's TASM,
> respectively) and likely some other chips as well there are options to
> replace "jnz foo" with "jz $+5 / jmp foo" when needed to allow longer branch
> range. If a compiler's going to need to track the size of generated code it
> may as well generate machine code itself without an assembler. If memory is
> tight, the compiler could generate a file containing a "patchable" format
> along with a second file containing a list of patches and relocation points.
> Those files could then be processed by a utility that wouldn't need to know
> anything about C, and could be much faster than would be possible if it had
> to process assembly source text.
Well, currently assembler takes more time then my compiler, so it
would make sense to generate code directly. The point is that
we need to store various intermediate information at least at
scale of a function. In old tradition one could store intermedate
data in files. However, correctly handling intermediate files
add complexity (think about deleting intermediate files when
compiler receives a signal). And on some filesystems limit
on the file size may be smaller than available RAM. Or
temporary filesystem may be in a ramdisk. So cost/benefits
ratio of various tricks to handle large functions looks low.
> > Or reserve register to serve as base
> > register for constant pool. IIUC register allocation is
> > frequently done on optimistic basis, assuming that some
> > problemetic situations will not occur. If optimistic
> > approach works it leads to better allocation. But if
> > optimistic approach fails one have to re-run register
> > allocation in reserving some registers to handle
> > problem. Ability to re-run means storing all relevant
> > data.
>
> A compiler will generally need to see an entire loop before deciding upon
> the optimal register allocation of variables at the start, but the larger
> a loop is the less relative cost there will be for guessing wrong. At worst,
> the compiler will have to shuffle some variables around before branching back
> to the start of the loop. If a compiler can hold off on generating the code
> for the start of the loop until it knows the best arrangement, that will allow
> better code than if it has to start generating code before it knows what's
> best, but if the compiler defaults to "safe" choices when generating code in
> such circumstances, it will be able to work around those choices later on.
Well, if you have a loop around a switch with many cases, then average
executed sequence of instructions may be moderate despite enormous
size of the whole loop. In similar spirit one can consider code
obtained via Boehm-Jacopini theorem. In this case one converts
aribtrary spagetti of gotos into a big loop with a chain of ifs.
Naively compiling obtained code leads to one loop iteration per
jump in orignal spagetti program. This basically leads to slowdown
proportional to number of labels in orignal program. But using known
optimization techniques one can essentially reconstruct original
spagetti from structured form. Main point is that structural
code assign to variable information about destination of jump
in spaggetti version. Optimizer can use known value of this
variable to find out next computational statement that will
be executed essentially bypassing long chain of ifs performing
dispatch in naive version. ATM I know of no compiler which
can do this on practical code, but gcc was quite close (it
implements all needed steps but was unable/unwilling to combine
them). In a bit different spirit, frequently error handling
code is more complicated than actial computation. To
ensure correctness C source will have a lot of checks
(either coming from macros or inserted by generator unable
to deduce if check can fail). In big loop compiler can
fing invariants and use them to prove that checks can not
fail and due to this substantially simplify the code.
As a realistic example consider bound checking array
accessor macro. IME gcc can eliminate most checks
inserted by such macros.
Anyway the point is that there are codes when large scale
optimization can give significant speedup. And some
folks write code assuming that quality compiler will perform
certain optimizations.
> > In old days compiler would not allocate variable in
> > register except for explicit register declaration.
> > Common subexpression elimiantion was limited to
> > single expression. We now expect much more, in
> > particular moving invariat computation out of loops
> > and good use of registers. In case of linear
> > sequence of inctructions register allocation
> > is easy, but gets more tricky in presence of
> > interesing control flow. And even in linear
> > case one may wish to reorder instructions for
> > better register allocation and/or better
> > scheduling.
>
> Of course, but such things have a certain cost. For some kinds of code, the
> payoffs may be huge, making such optimizations clearly worthwhile. For other
> kinds of code, the payoffs may be much smaller.
I know how to write C source so that even naive compiler will
give resonably fast machine code. But assuming that
C compiler will do reasonable job at optimization I
can write clearer and safer code. For example instead
of error prone reasoning which checks are needed I just
write redundant checks and let compiler remove useless
one. Putting checks in macros leads to compact code
which is obviously correct (because every operation
is checked).
> > Now consider why one would submit 1000000 line
> > function to the compiler. Such functions are
> > hard to understand and maintain by hand.
> > So the likely reason is that they are output
> > of a generator.
>
> Indeed.
>
> > In such case generator
> > presumably has more information then compiler
> > about resonable ways to split it. Anyway,
> > the main reason to keep such function as
> > a single unit would be to enable better
> > optiomization. Now, if compiler have to disable
> > some optimizations to handle such function,
> > then this defeats the purpose.
>
> I'd say that the most common reason to keep such a function as a single unit
> would be a lack of any particular reason to split it. If one wants to have
> a program generate C code to e.g. draw an object described in a vector-
> graphics file, and one passes it a file containing a single million-vector
> object, the output of the program would most likely be a huge C function that
> would draw the entire object. If each vector in the original object led to
> one line of generated C code, that would be a million-line function. Should
> such a program split large files into a sequence of smaller functions? On
> what basis should it do so?
>
> I'd suggest that if someone writing such a code generator were worried about
> the quality of the machine code that would be generated from the resulting
> C code, the code generator would be better placed than a C compiler to handle
> many non-localized optimizations. If a group of vectors precisely matches
> another, but shifted by some amount, it may be worthwhile for the utility that
> converts the vector-graphics file into C code to generate a function to draw
> that group of vectors with a given offset, and then replace each place where
> that sequence appears with a call to that function. Such optimization,
> however, should really be the job of the code generator, rather than the job
> of the C compiler.
Indeed, but splitting code into sensible pieces which can be
handled without trouble by C compiler is part of generator job.
And splitting is clearly related ot global optimization: when
all interesting dependecies were handled splitting should be
easy. As an example I have a code generator which can produce
potentially large expressions and convert them to code.
Generator introduces temporaries to split expression into
parts of managable size. And it performs common subexpresssion
elimination. In effect, if needed generator could split
expression into several functions without significant loss
of efficiency compared to putting expression in a single
function.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | BartC <bc@freeuk.com> |
|---|---|
| Date | 2017-03-16 02:18 +0000 |
| Message-ID | <oacsgf$3qn$1@dont-email.me> |
| In reply to | #106208 |
On 16/03/2017 01:35, antispam@math.uni.wroc.pl wrote: > In pseudo Pascal single line version of Bart's routine is: > > procedure foo; > var a, b, c, d; > begin > a := b + c*d; > end; > > which generates: > > .globl foo > .type foo, @function > foo: > subq $64, %rsp > movq 48(%rsp), %rax > movq %rax, 56(%rsp) > movq 32(%rsp), %rax > movq %rax, 40(%rsp) > movq 16(%rsp), %rax > movq %rax, 24(%rsp) > movq 40(%rsp), %rax > imulq 24(%rsp), %rax > movq %rax, 8(%rsp) > movq 56(%rsp), %rax > addq 8(%rsp), %rax > movq %rax, 0(%rsp) > addq $64, %rsp > ret > > Let me explain how this code is created. First, compiler performs > tree walk of parse tree of the whole program. During tree walk > compiler introduces temporary variable for each inner node of an > expression, effectively transforming: > > a = b + c*d > > into > > t1 = b > t3 = c > t4 = d > t2 = t3 + t4 I assume you mean t3*t4 > a = t1 + t2 This is 3-address code but a little unusual because you're not using variables directly. I tried your above code and executed it a billion times. It look 4.5 seconds. Then I eliminated those extraneous temps to get this: t2 = c * d a = b + t2 And time reduced to 2.7 seconds. About the same as my own code which doesn't use the t2 temporary. So that would be a worthwhile improvement. (I've tried 3-address code, but had trouble in getting rid of intermediate temps, and in mapping them to registers. In the end I found an ad hoc approach worked better. So for 'A+B', I would classify each operand as either simple or complex. Simple might be a variable name, or a constant. Both simple, you just load A to a register, then either load B, or do Add R,[B]. Both complex, you evaluate one operand then need to save it (on the stack) while working out the second. If A is simple and B is complex, you might evaluate B first, then add in A (if the op is reversible). etc. It worked fairly well. But I'm trying something a little different now because it would make the code generation simpler. However, it might not work...) > Let me add that one of goals for me was compiler that > is obviously correct -- the naive tactic is reasonably > close to this. Yes, I liked 3-address code for that reason. And it was easy to get things like this right (not C): if a=b=c # in C, if (a==b && b==c) Because, when b is complex, it gets evaluated and stored as a single temp. You don't get the problem of evaluating b twice. < My current estimate is > that gcc generates about 10 times faster code > that my generator. It won't be that much based on your sample code. Probably gcc is eliminated whole swathes of code rather than executing it, so results are misleading. -- bartc
[toc] | [prev] | [next] | [standalone]
| From | antispam@math.uni.wroc.pl |
|---|---|
| Date | 2017-03-18 00:45 +0000 |
| Message-ID | <oahvv0$ie0$1@z-news.wcss.wroc.pl> |
| In reply to | #106209 |
BartC <bc@freeuk.com> wrote:
> On 16/03/2017 01:35, antispam@math.uni.wroc.pl wrote:
>
> > In pseudo Pascal single line version of Bart's routine is:
> >
> > procedure foo;
> > var a, b, c, d;
> > begin
> > a := b + c*d;
> > end;
> >
> > which generates:
> >
> > .globl foo
> > .type foo, @function
> > foo:
> > subq $64, %rsp
> > movq 48(%rsp), %rax
> > movq %rax, 56(%rsp)
> > movq 32(%rsp), %rax
> > movq %rax, 40(%rsp)
> > movq 16(%rsp), %rax
> > movq %rax, 24(%rsp)
> > movq 40(%rsp), %rax
> > imulq 24(%rsp), %rax
> > movq %rax, 8(%rsp)
> > movq 56(%rsp), %rax
> > addq 8(%rsp), %rax
> > movq %rax, 0(%rsp)
> > addq $64, %rsp
> > ret
> >
> > Let me explain how this code is created. First, compiler performs
> > tree walk of parse tree of the whole program. During tree walk
> > compiler introduces temporary variable for each inner node of an
> > expression, effectively transforming:
> >
> > a = b + c*d
> >
> > into
> >
> > t1 = b
> > t3 = c
> > t4 = d
> > t2 = t3 + t4
>
> I assume you mean t3*t4
Yes, of course.
> > a = t1 + t2
>
> This is 3-address code but a little unusual because you're not using
> variables directly. I tried your above code and executed it a billion
> times. It look 4.5 seconds.
>
> Then I eliminated those extraneous temps to get this:
>
> t2 = c * d
> a = b + t2
>
> And time reduced to 2.7 seconds. About the same as my own code which
> doesn't use the t2 temporary.
>
> So that would be a worthwhile improvement.
I have implemented it now. Was easy, 18 extra lines. However,
note that each source line generates separate temporary. So
your 1 milion lines need 1 milion temporaries, that is 8 MB
of stack space. This is going to suffer some slowdown due
to L2 cache traffic.
Anyway, now compiling the 1 milion lines takes 8s.
> (I've tried 3-address code, but had trouble in getting rid of
> intermediate temps, and in mapping them to registers. In the end I found
> an ad hoc approach worked better.
>
> So for 'A+B', I would classify each operand as either simple or complex.
> Simple might be a variable name, or a constant. Both simple, you just
> load A to a register, then either load B, or do Add R,[B].
>
> Both complex, you evaluate one operand then need to save it (on the
> stack) while working out the second. If A is simple and B is complex,
> you might evaluate B first, then add in A (if the op is reversible). etc.
>
> It worked fairly well. But I'm trying something a little different now
> because it would make the code generation simpler. However, it might not
> work...)
For linear sequence of code at least in theory register allocation
is easy. For binary operators one may look at heights of arguments
and exaluate deeper argument first. Once expressions are flattenend
to a sequence one looks at places where variables are used and
keeps ones which are going to be used in first. But even such
simple optimizer is likely to be larger than rest of code
generator.
> < My current estimate is
> > that gcc generates about 10 times faster code
> > that my generator.
>
> It won't be that much based on your sample code. Probably gcc is
> eliminated whole swathes of code rather than executing it, so results
> are misleading.
I did not timing tests so this is just a guess. But somewhat
informed guess: for conditions I first compute boolean value
to a variable and in conditional I test stored value. Constants
are stored in memory before use -- one reason is that store
instruction accepts 64-bit constants while immediates are
limited to 32-bits. There is no constant propagation in
my compiler. My generator is going to create a lot
of dependencies between instructions, gcc is resonably good
at scheduling for parallel execution. gcc can make creative
use of addressing modes so that address arithmetic does not
need separate instuctions. I have a lot of references to
memory which may lead to extra latency.
Also, I timed tiny C on somewhat realistic compute intensive
code and gcc compiled code run 6 times faster. My code is
visibly worse than code from tiny C. OK, now the change I
made closes part of gap to tiny C, but not all.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | BartC <bc@freeuk.com> |
|---|---|
| Date | 2017-03-18 13:12 +0000 |
| Message-ID | <oajbig$h38$1@dont-email.me> |
| In reply to | #106421 |
On 18/03/2017 00:45, antispam@math.uni.wroc.pl wrote: > BartC <bc@freeuk.com> wrote: >> Then I eliminated those extraneous temps to get this: >> >> t2 = c * d >> a = b + t2 >> >> And time reduced to 2.7 seconds. About the same as my own code which >> doesn't use the t2 temporary. >> >> So that would be a worthwhile improvement. > > I have implemented it now. Was easy, 18 extra lines. However, > note that each source line generates separate temporary. So > your 1 milion lines need 1 milion temporaries, that is 8 MB > of stack space. This is going to suffer some slowdown due > to L2 cache traffic. I wouldn't worry about it. Don't forget, this is not real code, just a compiler test! Besides, the instruction cache will also suffer due to using one million copies of the same instructions rather using a loop. However, in more typical code, there will be some benefit in being able to reuse temporaries instead of creating new ones. (I think most are used only twice: once to write the value, once more to read it. Repeated of course each time a span of code is executed.) Of course, if there is also an option to somehow output C source code, then a normal C compiler can take care of these bothersome details when you need the extra performance. I wouldn't try it though when there are million line functions, as obviously some have trouble with those... >> It won't be that much based on your sample code. Probably gcc is >> eliminated whole swathes of code rather than executing it, so results >> are misleading. > > I did not timing tests so this is just a guess. But somewhat > informed guess: for conditions I first compute boolean value > to a variable and in conditional I test stored value. Constants > are stored in memory before use -- one reason is that store > instruction accepts 64-bit constants while immediates are > limited to 32-bits. There is no constant propagation in > my compiler. My generator is going to create a lot > of dependencies between instructions, gcc is resonably good > at scheduling for parallel execution. gcc can make creative > use of addressing modes so that address arithmetic does not > need separate instuctions. I have a lot of references to > memory which may lead to extra latency. > > Also, I timed tiny C on somewhat realistic compute intensive > code and gcc compiled code run 6 times faster. My code is > visibly worse than code from tiny C. OK, now the change I > made closes part of gap to tiny C, but not all. On real applications or just benchmarks? I compiled one of my interpreter projects with both. gcc-O3 was 2.3 times as fast as Tiny C in 32 bits, 2.1 times as fast in 64 bits (run on a small selection of test scripts). On my half-finished compiler operating on the test code in my OP, gcc-O3 was 2.15 times as fast as TCC (64 bits). (1.4 seconds/720Klps seconds vs. 2.95 seconds; even TCC-compiled code manages 340K lines/second!) I found that, on real apps, it was switch-statements that slowed down TCC further than the usual 2:1 ratio. Meanwhile, my own clunky code managed 1.7 seconds/590Klps, and that's with its weak optimiser turned off completely (actually it made no difference here!). That is, with no register variables, no recognising values already loaded, no nothing, not even passing parameters in registers as the 64-bit ABI stipulates. 1.4 ... 1.7 ... 3.0. I think you will find it easy to get performance between TCC and gcc, with the right sort of test application anyway. Make sure both TCC and gcc use either 32 or 64 bits to compare timings. gcc-m32 is a little faster than -m64. -- bartc
[toc] | [prev] | [next] | [standalone]
| From | antispam@math.uni.wroc.pl |
|---|---|
| Date | 2017-03-18 20:31 +0000 |
| Message-ID | <oak5en$qp5$1@z-news.wcss.wroc.pl> |
| In reply to | #106435 |
BartC <bc@freeuk.com> wrote:
> On 18/03/2017 00:45, antispam@math.uni.wroc.pl wrote:
> > BartC <bc@freeuk.com> wrote:
>
> >> Then I eliminated those extraneous temps to get this:
> >>
> >> t2 = c * d
> >> a = b + t2
> >>
> >> And time reduced to 2.7 seconds. About the same as my own code which
> >> doesn't use the t2 temporary.
> >>
> >> So that would be a worthwhile improvement.
> >
> > I have implemented it now. Was easy, 18 extra lines. However,
> > note that each source line generates separate temporary. So
> > your 1 milion lines need 1 milion temporaries, that is 8 MB
> > of stack space. This is going to suffer some slowdown due
> > to L2 cache traffic.
>
> I wouldn't worry about it. Don't forget, this is not real code, just a
> compiler test! Besides, the instruction cache will also suffer due to
> using one million copies of the same instructions rather using a loop.
>
> However, in more typical code, there will be some benefit in being able
> to reuse temporaries instead of creating new ones. (I think most are
> used only twice: once to write the value, once more to read it. Repeated
> of course each time a span of code is executed.)
Currently I could allocate and free temporaties in stack-like manner.
I am not doing this because I hope to write an optimizer someday.
With an optimizer temporary would have single definition (that
the point of current strategy) but possibly several uses.
> >> It won't be that much based on your sample code. Probably gcc is
> >> eliminated whole swathes of code rather than executing it, so results
> >> are misleading.
> >
> > I did not timing tests so this is just a guess. But somewhat
> > informed guess: for conditions I first compute boolean value
> > to a variable and in conditional I test stored value. Constants
> > are stored in memory before use -- one reason is that store
> > instruction accepts 64-bit constants while immediates are
> > limited to 32-bits. There is no constant propagation in
> > my compiler. My generator is going to create a lot
> > of dependencies between instructions, gcc is resonably good
> > at scheduling for parallel execution. gcc can make creative
> > use of addressing modes so that address arithmetic does not
> > need separate instuctions. I have a lot of references to
> > memory which may lead to extra latency.
> >
> > Also, I timed tiny C on somewhat realistic compute intensive
> > code and gcc compiled code run 6 times faster. My code is
> > visibly worse than code from tiny C. OK, now the change I
> > made closes part of gap to tiny C, but not all.
>
> On real applications or just benchmarks?
I do not remember details. I think 6 times was on TeX.
But I was also testing heapsort and maybe some similar
thing. Anyway, TeX is using large data structures
and in the past was considered to be large program
but when trying to predict TeX perfromance I noticed
that it corelates resonably well to Dhrystone.
Many modern program are memory bound, in such case
optimization have only limited effect. But in many
cases by using good algorithms and good data layout
programmer can improve memory use. So IMO when comparing
speed of compiler output interesting case is compute
bound programs. To put it differently: many real
programs are slow and hard to optimize. But for
me main point is how fast program can get assuming
that programmer spends some effort. And of course,
with good compiler I expect effort to get fast program
to be small. To clarify the last point let me
mention a microbenchmark that I did: I wrote a
simple loop in two ways, one using array access,
another using pointer aritmhetic. With gcc -O3
speed of both versions was the same 0.5s. With
gcc -O pointer version took 0.8s, while array
version took much longer time (IIRC 1.4s).
In my programs I prefer to write code in higher
level style (in particular avoid pointer arithmetic)
and most of the time gcc optimizations allow
me to do this. OTOH I am resonable good at
optimizing memory use, so my programs frequently
are compute bound and I get nice speedups from
gcc optimizations. And I believe that you
get smaller speedup on your programs -- maybe
you already optimized them by hand or the
problem is memory bound.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2017-03-18 17:31 -0700 |
| Message-ID | <2807ef3b-94df-4107-a3d4-7197439ac705@googlegroups.com> |
| In reply to | #106452 |
On Saturday, March 18, 2017 at 3:31:26 PM UTC-5, Waldek Hebisch wrote: > Many modern program are memory bound, in such case > optimization have only limited effect. But in many > cases by using good algorithms and good data layout > programmer can improve memory use. In some cases, the performance of memory-bound programs can be greatly improved by ensuring that the processor has something useful it can be doing while it's waiting for memory. Being able to treat operations on different memory objects as being independent can allow a compiler to reorder instructions in a way that helps achieve that, but the value of such ability is much higher in some application fields than others. > I wrote a > simple loop in two ways, one using array access, > another using pointer aritmhetic. With gcc -O3 > speed of both versions was the same 0.5s. With > gcc -O pointer version took 0.8s, while array > version took much longer time (IIRC 1.4s). > In my programs I prefer to write code in higher > level style (in particular avoid pointer arithmetic) > and most of the time gcc optimizations allow > me to do this. The value of using manual pointer arithmetic depends in large measure upon how well a processor's addressing modes line up with a language's constructs. If one is generating code for an 8086, accessing an element of a char[] using arr[i] may be just as fast as using *charPtr++, since the 8086 has [base+SI] and [BX+SI] addressing modes. Accessing an element of an int[] using arr[i] syntax may be much slower, however, since the processor doesn't have an addressing mode for [base+SI*2] or [BX+SI*2], making it necessary for the compiler to scale "i" by 2 every time it's used as an offset. On processors which include scaled addressing modes, the value of using "marching pointers" for array traversal is severely diminished. If a compiler isn't going to do any sort of aliasing analysis, passing a pointer to an element in an array is cheaper than passing a pointer to an array along with an index to it, but the syntactic equivalence between pointers to arrays versus pointers to elements thereof requires that compilers which are considering vectorizing code must check for aliasing forms which would not be an issue in languages like Fortran which pass references to arrays rather than pointers to elements. > OTOH I am resonable good at > optimizing memory use, so my programs frequently > are compute bound and I get nice speedups from > gcc optimizations. And I believe that you > get smaller speedup on your programs -- maybe > you already optimized them by hand or the > problem is memory bound. Some memory-bound problems are amenable to optimization, but some aren't.
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2017-03-16 09:22 -0700 |
| Message-ID | <bc4e795e-07d3-47d2-9e77-21fde4e7eeb2@googlegroups.com> |
| In reply to | #106208 |
On Wednesday, March 15, 2017 at 8:36:00 PM UTC-5, anti...@math.uni.wroc.pl wrote:
> supercat wrote:
> > Going after low-hanging fruit is cheap and doesn't require much extra
> > memory. For example, instead of having a function to generate code to
> > put an effective address into EBX, one could pass a pointer to a structure
> > that describes the effective address as one of several forms, and have
> > code that would perform operations on [EBX] accept that structure and
> > generate code for the effective address indicated therein. If one does
> > likewise for code which would place value operands in EAX, then something
> > like:
> >
> > p->member += 3;
> >
> > would be improved from:
> >
> > mov ebx,&p
> > mov ebx,[ebx]
> > add ebx,4 ; member offset
> > mov eax,3
> > add [dword ebx],eax
> >
> > to
> >
> > mov ebx,[p]
> > add [dword ebx],3
> >
> > A huge improvement in code quality, but relatively cheap.
>
> Well, it would take substantial work to get your first form.
> As I wrote currently the compiler is a toy, it has 1458 lines
> total from which 896 is code generator. And that is wc count,
> including blank lines, comments and a lot of whitespace.
Peephole optimizing isn't completely trivial, but it's low-hanging fruit
compared with the kinds of optimizations gcc goes after.
> In pseudo Pascal single line version of Bart's routine is:
>
> procedure foo;
> var a, b, c, d;
> begin
> a := b + c*d;
> end;
>
> which generates:
>
> .globl foo
> .type foo, @function
> foo:
> subq $64, %rsp
> movq 48(%rsp), %rax
> movq %rax, 56(%rsp)
> movq 32(%rsp), %rax
> movq %rax, 40(%rsp)
> movq 16(%rsp), %rax
> movq %rax, 24(%rsp)
> movq 40(%rsp), %rax
> imulq 24(%rsp), %rax
> movq %rax, 8(%rsp)
> movq 56(%rsp), %rax
> addq 8(%rsp), %rax
> movq %rax, 0(%rsp)
> addq $64, %rsp
> ret
>
> Let me explain how this code is created. First, compiler performs
> tree walk of parse tree of the whole program. During tree walk
> compiler introduces temporary variable for each inner node of an
> expression, effectively transforming:
>
> a = b + c*d
>
> into
>
> t1 = b
> t3 = c
> t4 = d
> t2 = t3 + t4
> a = t1 + t2
> In principle simple piphole optimizer
> could eliminate some useless stores of temporaries
> to memory. But thate would be an additional pass
> and AFAICS in the example above it would lead to
> no improvement. It is tempting to keep temporaries
> in registers and generate intermediate results
> directly to registers. But AMD64 instruction set
> still has various irregularities and some arguments
> and/or results need to be in specific registers.
> So generators for primitive operations would have
> to cope with arguments or results in "wrong" registers.
> Also, when compiler runs out of registers it has to
> spill something, so there is need to generate spill
> code and manage info about current location of variables.
> All doable in serious compiler, but would significantly
> complicate my toy.
Having a compiler look for cases where one operand of "+" or "*" is a
simple variable and the other is an expression, and evaluate the expression
first, is pretty easy, and would result in the only load and store of a
temporary being consecutive, which would be precisely the kind of thing that
peephole optimizers are good at handling.
> Let me add that one of goals for me was compiler that
> is obviously correct -- the naive tactic is reasonably
> close to this. Also, while this compiler is a toy
> I used similar approach prototyping compiler for
> higher level language using C as a target. Now,
> gcc nicely elliminates all bloat due to unnecessary
> temporaries and extra copies. In fact, somewhat
> bloated C code compiled by gcc leads to very good
> machine code. OTOH trying to produce tighter C
> may lead to worse machine code. Namely, temporaries
> in generated C code cannot alias anything and gcc
> can easily deduce dependencies. Reusing temporaries
> and especially directly using variables from
> higher level obscures information and may force
> gcc to generate more conservative code. My
> conclusion from this is that for purpose of
> translating higher level language I can outsource
> low level optimisations to gcc, instead concetrating
> on higher level aspects. My current estimate is
> that gcc generates about 10 times faster code
> that my generator. So it would be nice to have
> fast generator of good code, but at least for me
> it is long way to go...
Variable-lifetime graph coloring is a useful thing for compilers to be able
to do. While doing it perfectly may require exponential time, doing a fairly
basic job can be pretty easy. Having directives to indicate when a variable
could safely be set to an unspecified value might make graph coloring even
more effective, but there are no standards for such things. While some
compilers may use reserved identifiers to indicate unspecified values, an
intrinsic which took an lvalue would IMHO be better. If one has code like
someVariable = __UNSPECIFIED__;
one could make it work on compilers that don't recognize the intrinsic by
saying
#define __UNSPECIFIED__ 0
but that would in many cases compel such compilers to generate actual code
for it, defeating the entire purpose. By contrast, if there were an
intrinsic:
__ERASE_UNSPECIFIED(someVariable);
then a compiler which didn't know how to optimize usefully could be made
to simply ignore it.
> Well, currently assembler takes more time then my compiler, so it
> would make sense to generate code directly. The point is that
> we need to store various intermediate information at least at
> scale of a function. In old tradition one could store intermedate
> data in files. However, correctly handling intermediate files
> add complexity (think about deleting intermediate files when
> compiler receives a signal). And on some filesystems limit
> on the file size may be smaller than available RAM. Or
> temporary filesystem may be in a ramdisk. So cost/benefits
> ratio of various tricks to handle large functions looks low.
Older tools managed to have functions that would use ram buffers when space
allowed, and spool to disk when it didn't. On systems which handle virtual
memory effectively I could see justification for simply relying upon that
if available virtual space would be expected to be large enough to accommodate
any kind of program one would be called upon to process. On the other hand,
a simple and straightforward (but big) "do all these actions in sequence"
program should not require orders of magnitude more storage to compile than
it would to execute.
> > A compiler will generally need to see an entire loop before deciding upon
> > the optimal register allocation of variables at the start, but the larger
> > a loop is the less relative cost there will be for guessing wrong. At worst,
> > the compiler will have to shuffle some variables around before branching back
> > to the start of the loop. If a compiler can hold off on generating the code
> > for the start of the loop until it knows the best arrangement, that will allow
> > better code than if it has to start generating code before it knows what's
> > best, but if the compiler defaults to "safe" choices when generating code in
> > such circumstances, it will be able to work around those choices later on.
>
> Well, if you have a loop around a switch with many cases, then average
> executed sequence of instructions may be moderate despite enormous
> size of the whole loop. In similar spirit one can consider code
> obtained via Boehm-Jacopini theorem. In this case one converts
> aribtrary spagetti of gotos into a big loop with a chain of ifs.
> Naively compiling obtained code leads to one loop iteration per
> jump in orignal spagetti program. This basically leads to slowdown
> proportional to number of labels in orignal program. But using known
> optimization techniques one can essentially reconstruct original
> spagetti from structured form. Main point is that structural
> code assign to variable information about destination of jump
> in spaggetti version. Optimizer can use known value of this
> variable to find out next computational statement that will
> be executed essentially bypassing long chain of ifs performing
> dispatch in naive version. ATM I know of no compiler which
> can do this on practical code, but gcc was quite close (it
> implements all needed steps but was unable/unwilling to combine
> them).
It's certainly possible to have a loop with a huge amount of code in it
that ends up executing only a small amount of the code in most iterations.
On the other hand, a programmer who knows that some cases will be more
common than others should be able to arrange the code, or perhaps add
annotations, to help a compiler exploit that. Having a programmer do
such work once may make more sense than requiring a compiler to do extra
work every time a program is built.
Also, if I write something like:
... assume "x" is some integer type
if (x == 23)
...
else switch(x)
{
}
should a compiler absorb the code that handles a value of 23 into the switch
statement or leave it as-is? My feeling is that when I write code like that
it is--likely as not--because I expect performance to be dominated by cases
where x is 23 and any slowdown on those cases would degrade performance even
if it improved performance in all other cases. If a compiler can't see the
program's source of input, it would have no basis for assuming it knows more
than I do about its distribution.
> In a bit different spirit, frequently error handling
> code is more complicated than actial computation. To
> ensure correctness C source will have a lot of checks
> (either coming from macros or inserted by generator unable
> to deduce if check can fail). In big loop compiler can
> fing invariants and use them to prove that checks can not
> fail and due to this substantially simplify the code.
> As a realistic example consider bound checking array
> accessor macro. IME gcc can eliminate most checks
> inserted by such macros.
Having a compiler eliminate checks that are actually redundant can be good.
On the other hand, in cases where a program could meet requirements without
certain checks in the machine code, optimization will not be helped by
requiring that a programmer include those checks in the source code. If
the behavior of a the machine code would be affected by the presence or
absence of such checks, but both behaviors would be equally acceptable, there
may be no way to convince a compiler to omit those checks without it also
omitting checks which are crucial to correct operation.
> Anyway the point is that there are codes when large scale
> optimization can give significant speedup. And some
> folks write code assuming that quality compiler will perform
> certain optimizations.
Compilers should not expect to be suitable for all purposes if programmers
don't use options or directives to indicate what they actually need. There
are some situations where where high-end optimizations might yield orders-
of-magnitude performance increases which could not be achieved any other way.
There are many others where even a 1990s compiler would yield code whose
performance is within 10% of the best that could be achieved by any means
on the target platform.
My personal philosophy is that compilers should, by default, try to be fast
enough that programmers won't have to spend much time waiting for the
compiler, and should try to be compatible with a wide range of programs that
need to use features of the underlying platform but don't jump through hoops
in an effort to do so. If code generated with default settings runs slowly
enough that a programmer would want to make it faster, then a programmer can
see about enabling more optimizations. If cheap and safe optimizations would
suffice to meet requirements, however, any attempt to add others would be
"premature" (and, per the axiom, viewed as "evil").
> > Of course, but such things have a certain cost. For some kinds of code, the
> > payoffs may be huge, making such optimizations clearly worthwhile. For other
> > kinds of code, the payoffs may be much smaller.
>
> I know how to write C source so that even naive compiler will
> give resonably fast machine code. But assuming that
> C compiler will do reasonable job at optimization I
> can write clearer and safer code. For example instead
> of error prone reasoning which checks are needed I just
> write redundant checks and let compiler remove useless
> one. Putting checks in macros leads to compact code
> which is obviously correct (because every operation
> is checked).
There are a number of directives that could be added to the language to
reduce the need for compilers to include error-checking code that won't
help a program meet requirements. At present, there's no way by which
code can say e.g. "I'll need to know if an overflow happens anywhere in
this stretch of code, but I won't care exactly when", nor even "Set the
overflow flag if this calculation would overflow and its result would be
used, but if the result of the calculation isn't used feel free to omit
the overflow check". Letting programmers indicate what kinds of checking
are actually needed would help eliminate the need for redundant checks.
Using UB-based optimization, however, has the opposite effect, since it
compels programmers to include checks which would not need to be present
in the machine code for a program to meet requirements.
> Indeed, but splitting code into sensible pieces which can be
> handled without trouble by C compiler is part of generator job.
> And splitting is clearly related ot global optimization: when
> all interesting dependecies were handled splitting should be
> easy. As an example I have a code generator which can produce
> potentially large expressions and convert them to code.
> Generator introduces temporaries to split expression into
> parts of managable size. And it performs common subexpresssion
> elimination. In effect, if needed generator could split
> expression into several functions without significant loss
> of efficiency compared to putting expression in a single
> function.
If there would be a natural split in the source domain, it makes sense to
carry through such a split and generate multiple distinct functions. If,
however, something is simply a large blob in the source domain and doesn't
have any logical subdivisions, I see no reason to expect that a code
generator should partition a large function into pieces of some arbitrary
size unless it is expected to be used with a target that would impose some
limit (e.g. a segmented architecture where each function is required to fit
in a single segment).
[toc] | [prev] | [next] | [standalone]
| From | Nick Bowler <nbowler@draconx.ca> |
|---|---|
| Date | 2017-03-24 16:13 +0000 |
| Message-ID | <ob3gil$drf$1@dont-email.me> |
| In reply to | #106060 |
On Tue, 14 Mar 2017 10:24:52 -0700, supercat wrote: > A compiler for a small machine would benefit from building a tree when it > has enough space to do so, but a quality compiler for such a machine should > be able to generate working code even when it doesn't. [...] > Obviously the code would be bigger and slower than it would be if the > compiler hadn't run out of memory [...] If a compiler actually did this, its output would not be deterministic. The compiler's output today could be different from yesterday because of unrelated external activity causing memory pressure, even if none of the compiler's inputs have changed. This would be a total nightmare for anyone doing debugging or verifiable builds.
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2017-03-24 12:32 -0700 |
| Message-ID | <099f1bea-dbc7-4955-b2e4-df520abc90e4@googlegroups.com> |
| In reply to | #106936 |
On Friday, March 24, 2017 at 11:16:15 AM UTC-5, Nick Bowler wrote: > On Tue, 14 Mar 2017 10:24:52 -0700, supercat wrote: > > A compiler for a small machine would benefit from building a tree when it > > has enough space to do so, but a quality compiler for such a machine should > > be able to generate working code even when it doesn't. > [...] > > Obviously the code would be bigger and slower than it would be if the > > compiler hadn't run out of memory [...] > > If a compiler actually did this, its output would not be deterministic. > The compiler's output today could be different from yesterday because of > unrelated external activity causing memory pressure, even if none of the > compiler's inputs have changed. > > This would be a total nightmare for anyone doing debugging or verifiable > builds. Fair point; it would be better to have a compiler use a fallback strategy when things reach pre-determined (but possibly configurable) size limits rather than limits which automatically adjust to use all available storage. On the other hand, that would probably a good idea even if one didn't care about having repeated builds produce bit-identical output, since the likelihood of an optimization's benefits exceeding the costs will tend to fall as code grows beyond a certain point.
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2017-03-24 22:13 -0500 |
| Message-ID | <p0obdcdijaqig54jcfqu9ic2e4fku6fo21@4ax.com> |
| In reply to | #106993 |
On Fri, 24 Mar 2017 12:32:04 -0700 (PDT), supercat@casperkitty.com wrote: >On the other hand, that would probably a good idea even if one didn't care >about having repeated builds produce bit-identical output, since the >likelihood of an optimization's benefits exceeding the costs will tend to >fall as code grows beyond a certain point. I'm not sure how you'd support such a statement. Why would most of the non-code-expanding optimizations tend to be less effective on large routines? And even the ones that tend to expand code?
[toc] | [prev] | [next] | [standalone]
Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6 Next page →
Back to top | Article view | comp.lang.c
csiph-web