FAQ
Hi,

I've been tracking the SSA package on the dev mailing list. It looks really
interesting and I'm just being nosy!

https://codereview.appspot.com/7071058/

Is the intention that this sits in front of the compilers for the different
architectures (5,6,8) and they change to accept the SSA output? Or is it a
tool to help analyse Go source and improve the efficiency of the compilers,
still accepting Go source as the input?

Would SSA output make it a lot easier for third parties to write Go
compilers?

Just interested, it always amazes me how many different Java VM's are
available. Is this a move to open up Go to the world of competitive
compiler implementations?

Cheers,
Donovan.

--

Search Discussions

  • Minux at Jan 22, 2013 at 11:22 am

    On Tue, Jan 22, 2013 at 7:08 PM, Donovan Hide wrote:

    I've been tracking the SSA package on the dev mailing list. It looks
    really interesting and I'm just being nosy!

    https://codereview.appspot.com/7071058/

    Is the intention that this sits in front of the compilers for the
    different architectures (5,6,8) and they change to accept the SSA output?
    Or is it a tool to help analyse Go source and improve the efficiency of the
    compilers, still accepting Go source as the input?
    the latter. As explained in the comment, it's not written with writing Go
    backend in mind.
    however, I think it's quite possible that we use to write a SSA backend
    (for example, the llgo
    project might be able to utilize this package).
    Would SSA output make it a lot easier for third parties to write Go
    compilers?
    Very probably, despite the fact the original author doesn't support this.
    Just interested, it always amazes me how many different Java VM's are
    available. Is this a move to open up Go to the world of competitive
    compiler implementations?
    Just a note: a Java VM doesn't contain the javac compiler.

    And just like Java, Go has a non-trivial portion of support functionality
    implemented in its runtime, so
    even though writing a Go backend with exp/ssa might not be hard (by
    utilizing SSA-based compiler
    backends, e.g. LLVM and libFirm and maybe GCC's Tree SSA), writing all the
    runtime supports is not
    a trivial undertaking (esp. the garbage collector and goroutine scheduler).

    Most probably, 3rd party implementation of Go will be utilizing existing
    runtime implementation, but
    it's easy to see, efficiency of Go programs depends on the runtime much,
    esp. for IO and memory
    intensive program.

    --
  • Donovan Hide at Jan 22, 2013 at 11:37 am
    Thank you for that explanation! The thing I like most about Go is how
    transparent the development of it is; you can really learn a lot from
    watching it change day to day.

    And just like Java, Go has a non-trivial portion of support functionality
    implemented in its runtime, so
    even though writing a Go backend with exp/ssa might not be hard (by
    utilizing SSA-based compiler
    backends, e.g. LLVM and libFirm and maybe GCC's Tree SSA), writing all the
    runtime supports is not
    a trivial undertaking (esp. the garbage collector and goroutine scheduler).
    I suppose the solution to this problem is to write more of the runtime in
    Go itself, rather than C? I often wonder how much slower a Go version of
    hashmap would run? Sounds like a challenge to myself :-) Could the authors
    ever foresee the addition of builtins written in Go?

    --
  • Minux at Jan 22, 2013 at 11:48 am

    On Tue, Jan 22, 2013 at 7:37 PM, Donovan Hide wrote:

    And just like Java, Go has a non-trivial portion of support functionality
    implemented in its runtime, so
    even though writing a Go backend with exp/ssa might not be hard (by
    utilizing SSA-based compiler
    backends, e.g. LLVM and libFirm and maybe GCC's Tree SSA), writing all
    the runtime supports is not
    a trivial undertaking (esp. the garbage collector and goroutine
    scheduler).
    I suppose the solution to this problem is to write more of the runtime in
    Go itself, rather than C? I often wonder how much slower a Go version of
    hashmap would run? Sounds like a challenge to myself :-) Could the authors
    ever foresee the addition of builtins written in Go?
    Right. It's possible and even encouraged to use Go instead of C in the
    runtime package.
    In theory, properly written C-level (read: system-level) Go should be as
    fast as its C
    counterpart (although we might need some trivial language extensions like
    defining
    functions of another package).

    If we have a Go runtime mostly written in Go, then we have achieved a major
    milestone, IMO.
    and this goal is very much worth pursuing (not at this time, though, as Go
    1.1 is about to be
    released)

    --
  • Donovan Hide at Jan 22, 2013 at 12:00 pm

    Right. It's possible and even encouraged to use Go instead of C in the
    runtime package.
    In theory, properly written C-level (read: system-level) Go should be as
    fast as its C
    counterpart (although we might need some trivial language extensions like
    defining
    functions of another package).
    And perhaps exposing an iterator type (maybe a tuple for the index,value
    and key,value ranging?). The array, map, string, slice and chan iterators
    are all hardcoded in at the moment:

    http://golang.org/src/cmd/gc/range.c

    If we have a Go runtime mostly written in Go, then we have achieved a
    major milestone, IMO.
    and this goal is very much worth pursuing (not at this time, though, as Go
    1.1 is about to be
    released)
    I agree! Good news about 1.1 by the way :-)

    --
  • Donovan Hide at Jan 22, 2013 at 1:02 pm
    Straying into the realm of language design here, but thinking about how you
    could get hold of an iterator if you did want to implement, for instance,
    go based hashmaps, would the following syntax get round the need to
    introduce generics/templates/specialisation into the whole of the language:

    m:=make(map[int]string) // Existing usage

    m,iter:=make(map[int]string) // m is the map, iter is an inferred (possibly
    anonymous?) interface with the following generated definition

    type Iter interface {
    Next() (int,string)
    Done() bool
    }

    which could then be used as an alternative to range:

    for !iter.Done(){
    k,v:=iter.Next()
    // do something with k,v
    }

    I suppose you still have the problem of passing the two types to the map
    factory which builds the iterator, but it does at least mean you don't have
    to have a whole new subset of <Type> definitions floating around in user
    code. Sure this has been discussed before, but definitely seems linked to
    the whole idea of implementing more of Go in Go :-)

    A nice side-effect would be that you could offer a lot more interesting
    builtins just by altering the iterator, sortedMap, or upperCaseString for
    instance. Basically, can we have a compile-time, statically-typed Python
    yield equivalent in Go :-)

    --
  • Adonovan at Jan 23, 2013 at 9:56 pm

    On Tuesday, 22 January 2013 08:02:50 UTC-5, Donovan wrote:

    Straying into the realm of language design here, but thinking about how
    you could get hold of an iterator if you did want to implement, for
    instance, go based hashmaps, would the following syntax get round the need
    to introduce generics/templates/specialisation into the whole of the
    language:

    m:=make(map[int]string) // Existing usage

    m,iter:=make(map[int]string) // m is the map, iter is an inferred
    (possibly anonymous?) interface with the following generated definition

    type Iter interface {
    Next() (int,string)
    Done() bool
    }

    which could then be used as an alternative to range:

    for !iter.Done(){
    k,v:=iter.Next()
    // do something with k,v
    }

    I suppose you still have the problem of passing the two types to the map
    factory which builds the iterator, but it does at least mean you don't have
    to have a whole new subset of <Type> definitions floating around in user
    code. Sure this has been discussed before, but definitely seems linked to
    the whole idea of implementing more of Go in Go :-)

    A nice side-effect would be that you could offer a lot more interesting
    builtins just by altering the iterator, sortedMap, or upperCaseString for
    instance. Basically, can we have a compile-time, statically-typed Python
    yield equivalent in Go :-)
    Hi Donovan,

    glad to hear you're interested in the exp/ssa package I've been working on.
    I hope to get it submitted in the next couple of weeks. As minux said, my
    intended application is source analysis tools, not code generation. (I do
    have a interpreter in Go that operates directly on the SSA form, which is
    asymptotically inefficient but a boon for testing that the SSA builder is
    faithful to the language spec.)

    Regarding map iterators, this was one of the challenges in building the
    interpreter since Go doesn't provide any efficient means in the language to
    build an iterator over a map: using a co-routine style iterator leaks
    goroutines, and making a slice of key/value pairs makes accessing the first
    element take O(n) space---plus it has the wrong update semantics.

    The good news is that the reflect.MapKeys function internally contains
    everything you need to do it right, so a future version of the reflect
    package could provide just such an iterator.

    cheers
    Alan (also Donovan) :)

    --
  • Minux at Jan 23, 2013 at 7:55 pm

    On Thu, Jan 24, 2013 at 3:39 AM, wrote:
    glad to hear you're interested in the exp/ssa package I've been working
    on. I hope to get it submitted in the next couple of weeks. As minux
    said, my intended application is source analysis tools, not code
    generation. (I do have a interpreter in Go that operates directly on the
    SSA form, which is asymptotically inefficient but a boon for testing that
    the SSA builder is faithful to the language spec.)
    Great, will the interpreter available as, say, an example of exp/ssa?
    btw, do you have plan to move exp/ssa to go/ssa before Go 1.1?

    I'm quite excited that we could have a Go interpreter written in Go, and
    that might streamline the conversion of the current C-based runtime to Go.
    thank you for the exp/ssa work.

    --
  • Sebastien Binet at Jan 23, 2013 at 8:00 pm

    On Wed, Jan 23, 2013 at 8:55 PM, minux wrote:
    On Thu, Jan 24, 2013 at 3:39 AM, wrote:

    glad to hear you're interested in the exp/ssa package I've been working
    on. I hope to get it submitted in the next couple of weeks. As minux said,
    my intended application is source analysis tools, not code generation. (I
    do have a interpreter in Go that operates directly on the SSA form, which is
    asymptotically inefficient but a boon for testing that the SSA builder is
    faithful to the language spec.)
    Great, will the interpreter available as, say, an example of exp/ssa?
    btw, do you have plan to move exp/ssa to go/ssa before Go 1.1?

    I'm quite excited that we could have a Go interpreter written in Go, and
    that might streamline the conversion of the current C-based runtime to Go.
    thank you for the exp/ssa work.
    I'd be very much interested in having a look at that exp/ssa-based
    interpreter as well !

    -s

    --
  • Donovan Hide at Jan 23, 2013 at 8:35 pm
    Extremely interested also!

    --
  • Alan Donovan at Jan 23, 2013 at 9:56 pm
    I will be reviewing and submitting the exp/ssa package in 5 installments;
    the interpreter is the fifth.


    On 23 January 2013 15:35, Donovan Hide wrote:

    Extremely interested also!
    --
  • Alan Donovan at Jan 23, 2013 at 9:56 pm
    On 23 January 2013 14:55, minux wrote:
    On Thu, Jan 24, 2013 at 3:39 AM, wrote:

    glad to hear you're interested in the exp/ssa package I've been working
    on. I hope to get it submitted in the next couple of weeks. As minux
    said, my intended application is source analysis tools, not code
    generation. (I do have a interpreter in Go that operates directly on the
    SSA form, which is asymptotically inefficient but a boon for testing that
    the SSA builder is faithful to the language spec.)
    Great, will the interpreter available as, say, an example of exp/ssa?
    btw, do you have plan to move exp/ssa to go/ssa before Go 1.1?
    Yes, it will be available as an example and as a test, but it's not
    appropriate for any kind of production use.

    I'm quite excited that we could have a Go interpreter written in Go, and
    that might streamline the conversion of the current C-based runtime to Go.
    thank you for the exp/ssa work.
    I must again stress that this interpreter is for testing and evaluation
    only. Its performance is not in the same league as what you probably
    expect from an interpreter. Its sole purpose is to faithfully implement
    the language spec as clearly and simply as possible.

    --
  • Minux at Jan 24, 2013 at 12:41 pm

    On Thursday, January 24, 2013, Alan Donovan wrote:
    I must again stress that this interpreter is for testing and evaluation
    only. Its performance is not in the same league as what you probably
    expect from an interpreter. Its sole purpose is to faithfully implement
    the language spec as clearly and simply as possible.
    understood. when i said move C-based runtime to Go, what i have in mind
    is that with the help of go/ssa, writing a Go compiler will be easier, and
    i expect bigger part of runtime writing in Go will also facilitate that.
    To be clear, i was not sugguesting using Go interpreter for production use.

    however, i think that when writing Go compiler/interpreters, having a gold
    standard would be much invaluable. and that, i think, should be the mainuse
    of your interpreter.

    btw, i think speeding the interpreter up with llvm should not be a difficult
    task, so, yes, i think we can say that a Go interpreter is in the works. :)

    --
  • Sebastien Binet at Jan 24, 2013 at 4:08 pm

    minux writes:
    On Thursday, January 24, 2013, Alan Donovan wrote:

    I must again stress that this interpreter is for testing and evaluation
    only. Its performance is not in the same league as what you probably
    expect from an interpreter. Its sole purpose is to faithfully implement
    the language spec as clearly and simply as possible.
    understood. when i said move C-based runtime to Go, what i have in mind
    is that with the help of go/ssa, writing a Go compiler will be easier, and
    i expect bigger part of runtime writing in Go will also facilitate that.
    To be clear, i was not sugguesting using Go interpreter for production use.

    however, i think that when writing Go compiler/interpreters, having a gold
    standard would be much invaluable. and that, i think, should be the mainuse
    of your interpreter.

    btw, i think speeding the interpreter up with llvm should not be a difficult
    task, so, yes, i think we can say that a Go interpreter is in the
    works. :)
    in a sense, there is already a Go interpreter in the works:
    https://github.com/sbinet/go-eval

    although a not very complete one :)

    -s
  • Donovan Hide at Jan 23, 2013 at 10:15 pm
    Hi Alan,

    thanks for the reply, got this after minux's response, some weird golang
    nuts temporal discontinuity :-)

    Regarding map iterators, this was one of the challenges in building the
    interpreter since Go doesn't provide any efficient means in the language to
    build an iterator over a map: using a co-routine style iterator leaks
    goroutines, and making a slice of key/value pairs makes accessing the first
    element take O(n) space---plus it has the wrong update semantics.
    Yes, this has been a source of frustration for me. I do a lot of work with
    hash tables and the inability to tweak the hash or equality functions to
    work with different comparisons and distributions has been a little bit
    off-putting when contrasted with the open nature of C++ implementations. In
    other words I'd love to be able to get inside a Go implementation of a hash
    table, not necessarily in order to suggest changing the standard builtin
    map, but just to be able to optimise certain things like memory allocation
    for uint64 based keys in specific use cases that I have. I think your work
    on enabling transfer some of the core runtime to Go is great work! If a
    good way of doing iterators comes out of, even better!

    The good news is that the reflect.MapKeys function internally contains
    everything you need to do it right, so a future version of the reflect
    package could provide just such an iterator.
    Yes, there does seem to be a lot of hooks in the runtime C code to make
    special exception for the reflect package. I guess pragmatism surpassed
    idealism in the amount of Go code that could be trusted to do the job well
    and fast in getting 1.0 out the door.

    Anyway, look forward to tracking this exciting package!

    Likewise,
    Donovan (I feel like your inverse!)

    --
  • Alan Donovan at Jan 23, 2013 at 11:03 pm

    On 23 January 2013 17:15, Donovan Hide wrote:

    I think your work on enabling transfer some of the core runtime to Go is
    great work!
    Sorry to keep repeating myself, but I wish to dispel any misunderstandings
    about the nature of this work before someone mistakenly blogs that "a Go
    interpreter is in the works". The tool is merely a utility for testing the
    correctness of the SSA representation. None of my work has any bearing on
    the core runtime.

    --

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedJan 22, '13 at 11:08a
activeJan 24, '13 at 4:08p
posts16
users4
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase