[go-nuts] exp/ssa questions

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).
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.

--

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
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)

--

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

I agree! Good news about 1.1 by the way :-)

--

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) :)

--

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

--

Extremely interested also!

--

I will be reviewing and submitting the exp/ssa package in 5 installments;
the interpreter is the fifth.

Yes, it will be available as an example and as a test, but it's not
appropriate for any kind of production use.

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

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
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!

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!)

--

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.

--