Re: [go-nuts] Is Go a single pass compiler?
Algol 68 allowed use before definition which would force more than one pass but I believe many Algol 68 compilers didn’t allow this and forced forward declarations much like in C. I suspect “multiple pass” makes less sense for modern compilers. When you can keep an entire program in memory, using multiple representations, you can have many walks over the same trees. Almost by definition an “optimizing” compiler has to go over the same code fragment multiple times. I wonder what all the Stalin compiler for R4RS Scheme did. It ran slow as molasses to produce C code but this ran faster than hand optimized C code! > On Mar 2, 2019, at 4:16 AM, Jesper Louis Andersen > wrote: > >> On Thu, Feb 28, 2019 at 12:46 AM wrote: > >> Thanks, Ian. >> >> I remember reading in some compiler book that languages should be designed >> for a single pass to reduce compilation speed. >> > > As a guess: this was true in the past, but in a modern setting it fails to > hold. > > Andy Keep's phd dissertation[0] implements a "nanopass compiler" which is > taking the pass count to the extreme. Rather than having a single pass, the > compiler does 50 passes or so over the code, each pass doing a little > simplification. The compelling reason to do so is that you can do cut, paste, > and copy (snarf) each pass and tinker much more with the compilation pipeline > than you would normally be able to do. Also, rerunning certain simplify > passes along the way tend to help the final emitted machine code. You might > wonder how much this affects compilation speed. Quote: > > "The new compiler meets the goals set out in the research plan. When compared > to the original compiler on a set of benchmarks, the benchmarks, for the new > compiler run, on average, between 15.0% and 26.6% faster, depending on the > architecture and optimization level. The compile times for the new compiler > are also well within the goal, with a range of 1.64 to 1.75 times slower. " > > [Note: the goal was a factor 2.0 slowdown at most] > > The compiler it is beating here is Chez Scheme, a highly optimizing Scheme > compiler. > > Some of the reasons are that intermediate representations can be kept in > memory nowadays, where it is going to be much faster to process. And that > memory is still getting faster, even though at a slower pace than the CPUs > are. The nanopass framework is also unique because it has macro tooling for > creating intermediate languages out of existing ones. So you have many IR > formats in the compiler as well. > > In conclusion: if a massive pass blowup can be implemented within a 2x factor > slowdown, then a couple of additional passes is not likely to make the > compiler run any slower. > > [0] http://andykeep.com/pubs/dissertation.pdf > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is Go a single pass compiler?
It makes sense to me - since very often many of the parts that are processed are stand-alone and compile correctly (almost) by themselves (maybe a package clause to be complete in a source). These smaller pieces have to have one pass to grab their trees and symbols, and joined to the other parts. Go's compiler dodges a lot of this extra work by caching intermediate binary objects. On Saturday, 2 March 2019 13:17:34 UTC+1, Jesper Louis Andersen wrote: > > On Thu, Feb 28, 2019 at 12:46 AM > > wrote: > >> Thanks, Ian. >> >> I remember reading in some compiler book that languages should be >> designed for a single pass to reduce compilation speed. >> >> > As a guess: this was true in the past, but in a modern setting it fails to > hold. > > Andy Keep's phd dissertation[0] implements a "nanopass compiler" which is > taking the pass count to the extreme. Rather than having a single pass, the > compiler does 50 passes or so over the code, each pass doing a little > simplification. The compelling reason to do so is that you can do cut, > paste, and copy (snarf) each pass and tinker much more with the compilation > pipeline than you would normally be able to do. Also, rerunning certain > simplify passes along the way tend to help the final emitted machine code. > You might wonder how much this affects compilation speed. Quote: > > "The new compiler meets the goals set out in the research plan. When > compared to the original compiler on a set of benchmarks, the benchmarks, > for the new compiler run, on average, between 15.0% and 26.6% faster, > depending on the architecture and optimization level. The compile times for > the new compiler are also well within the goal, with a range of 1.64 to > 1.75 times slower. " > > [Note: the goal was a factor 2.0 slowdown at most] > > The compiler it is beating here is Chez Scheme, a highly optimizing Scheme > compiler. > > Some of the reasons are that intermediate representations can be kept in > memory nowadays, where it is going to be much faster to process. And that > memory is still getting faster, even though at a slower pace than the CPUs > are. The nanopass framework is also unique because it has macro tooling for > creating intermediate languages out of existing ones. So you have many IR > formats in the compiler as well. > > In conclusion: if a massive pass blowup can be implemented within a 2x > factor slowdown, then a couple of additional passes is not likely to make > the compiler run any slower. > > [0] http://andykeep.com/pubs/dissertation.pdf > > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is Go a single pass compiler?
On Thu, Feb 28, 2019 at 12:46 AM wrote: > Thanks, Ian. > > I remember reading in some compiler book that languages should be designed > for a single pass to reduce compilation speed. > > As a guess: this was true in the past, but in a modern setting it fails to hold. Andy Keep's phd dissertation[0] implements a "nanopass compiler" which is taking the pass count to the extreme. Rather than having a single pass, the compiler does 50 passes or so over the code, each pass doing a little simplification. The compelling reason to do so is that you can do cut, paste, and copy (snarf) each pass and tinker much more with the compilation pipeline than you would normally be able to do. Also, rerunning certain simplify passes along the way tend to help the final emitted machine code. You might wonder how much this affects compilation speed. Quote: "The new compiler meets the goals set out in the research plan. When compared to the original compiler on a set of benchmarks, the benchmarks, for the new compiler run, on average, between 15.0% and 26.6% faster, depending on the architecture and optimization level. The compile times for the new compiler are also well within the goal, with a range of 1.64 to 1.75 times slower. " [Note: the goal was a factor 2.0 slowdown at most] The compiler it is beating here is Chez Scheme, a highly optimizing Scheme compiler. Some of the reasons are that intermediate representations can be kept in memory nowadays, where it is going to be much faster to process. And that memory is still getting faster, even though at a slower pace than the CPUs are. The nanopass framework is also unique because it has macro tooling for creating intermediate languages out of existing ones. So you have many IR formats in the compiler as well. In conclusion: if a massive pass blowup can be implemented within a 2x factor slowdown, then a couple of additional passes is not likely to make the compiler run any slower. [0] http://andykeep.com/pubs/dissertation.pdf -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is Go a single pass compiler?
Was this book written in the '70s or '80s? Single-pass compilation is great in some ways (memory and time efficient), not in others (usability). C is (sort of) single-pass (if you don't count the preprocessor, optimization passes, etc), which is why you need function prototypes. Assemblers are very often single-pass. C is basically a user-friendly front-end to the assembler anyway, so. Languages built for the the minicomputers of the '70s and microcomputers of the '80s should be designed for a single pass, because if you were trying to do anything bigger than that it would likely take forever or exceed your available resources. I don't think that has been a valid constraint on anything for a long time unless you're planning on e.g. compiling something on an AVR (for example, Forth is a single-pass language if you squint at it hard enough, and it fits nicely on some REALLY small things). - Dave > On Feb 27, 2019, at 6:46 PM, ivan.medoe...@gmail.com wrote: > > Thanks, Ian. > > I remember reading in some compiler book that languages should be designed > for a single pass to reduce compilation speed. > > Go proves that wrong :) It's amazingly fast, looks like computers are pretty > good at traversing AST trees. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is Go a single pass compiler?
The first computer I ever programmed[1] had a Fortran compiler that stored its intermediate representation on paper tape. As you might imagine, the number of passes affected compilation speed a lot. I don't do compilers, but I suspect that other bottlenecks matter much more today. Jim [1] - https://en.wikipedia.org/wiki/Monrobot_XI On Wed, Feb 27, 2019 at 6:46 PM wrote: > Thanks, Ian. > > I remember reading in some compiler book that languages should be designed > for a single pass to reduce compilation speed. > > Go proves that wrong :) It's amazingly fast, looks like computers are > pretty good at traversing AST trees. > > On Wednesday, February 27, 2019 at 11:50:05 PM UTC+1, Ian Lance Taylor > wrote: >> >> On Wed, Feb 27, 2019 at 2:42 PM wrote: >> > >> > In Go functions can be used before they are defined, but as I >> understand, it's still possible to have a single pass compiler. >> >> I don't think it's possible to compile Go in a single pass compiler, >> unless you consider a separate parsing and code generation step to be >> a single pass compiler. In the general case, you can't generate code >> for any Go function until you've seen all the functions in the >> package. >> >> There are multiple Go compilers. All the ones I am aware of are have >> many passes. >> >> Ian >> > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is Go a single pass compiler?
The Go compiler was single pass until we allowed use before declaration. -rob On Thu, Feb 28, 2019 at 10:46 AM wrote: > Thanks, Ian. > > I remember reading in some compiler book that languages should be designed > for a single pass to reduce compilation speed. > > Go proves that wrong :) It's amazingly fast, looks like computers are > pretty good at traversing AST trees. > > On Wednesday, February 27, 2019 at 11:50:05 PM UTC+1, Ian Lance Taylor > wrote: >> >> On Wed, Feb 27, 2019 at 2:42 PM wrote: >> > >> > In Go functions can be used before they are defined, but as I >> understand, it's still possible to have a single pass compiler. >> >> I don't think it's possible to compile Go in a single pass compiler, >> unless you consider a separate parsing and code generation step to be >> a single pass compiler. In the general case, you can't generate code >> for any Go function until you've seen all the functions in the >> package. >> >> There are multiple Go compilers. All the ones I am aware of are have >> many passes. >> >> Ian >> > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is Go a single pass compiler?
Thanks, Ian. I remember reading in some compiler book that languages should be designed for a single pass to reduce compilation speed. Go proves that wrong :) It's amazingly fast, looks like computers are pretty good at traversing AST trees. On Wednesday, February 27, 2019 at 11:50:05 PM UTC+1, Ian Lance Taylor wrote: > > On Wed, Feb 27, 2019 at 2:42 PM > > wrote: > > > > In Go functions can be used before they are defined, but as I > understand, it's still possible to have a single pass compiler. > > I don't think it's possible to compile Go in a single pass compiler, > unless you consider a separate parsing and code generation step to be > a single pass compiler. In the general case, you can't generate code > for any Go function until you've seen all the functions in the > package. > > There are multiple Go compilers. All the ones I am aware of are have > many passes. > > Ian > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [go-nuts] Is Go a single pass compiler?
On Wed, Feb 27, 2019 at 2:42 PM wrote: > > In Go functions can be used before they are defined, but as I understand, > it's still possible to have a single pass compiler. I don't think it's possible to compile Go in a single pass compiler, unless you consider a separate parsing and code generation step to be a single pass compiler. In the general case, you can't generate code for any Go function until you've seen all the functions in the package. There are multiple Go compilers. All the ones I am aware of are have many passes. Ian -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
