How are keywords parsed into AST nodes in Go, and how would you go about adding one

[Kyle Stanly]

Example

The following code below is what I am referring to.

for k,v := range m {...}

Would turn it into

k := {Op: ONAME, Type: keyType}
v := {Op: ONAME, Type: valueType}
m := {Op: ONAME, Type: map[keyType]valueType} // Already exists as it's iterating over it
range := {Op: ORANGE, List: {k, v}, Right: m}
hit := {Op: ONAME, Type: *hiter } // Created or recycled iterator
iterConditional := {Op: ODOTPTR
for := {Op: OFOR, Ninit: init, Left: {Expr: {iter.key != nil}}, Right: {Op: OCALL, Function: "mapiternext"}}

Of course this is a simplified version, there's a lot more (I.E indirection of the key and value to return them by copy, the fact that we need to obtain the (*Sym) of the key and value (first two fields in the iterator), etc. I'm just trying to make a point here. Such a simple statement turns into a lot, and I'm very intrigued into how it does so.

For example, if 'for' gets turned into OFOR, and range turns into ORANGE, it still needs some way to get linked together. I.E, both tokens are not unrelated, and one requires the other to even make logical sense (I.E a range without a for loop wouldn't make much sense at all). Hence clearly it has a lot of rules set in place. Now I'm interested in how I could potentially add my own identifier/keyword, that also has it's own semantics as well.

New Keyword

The keyword I would like to implement maintains backwards compatibility in a rather unique way, which Go currently does not do, and I believe it can be implemented in a way that is not only very extensible (and allowing other additions to keywords, or at least newer semantics on the fly) but also in a way that makes sense (I.E, the keyword would make logical sense, and is not just a random token that cannot be used).

I want to implement a keyword that has the following rules and restrictions...

1) It must contain at least one parameter, of which the type must be a map, and explicitly, must be a certain type of map (to those who remember my previous posts, a Concurrent Map). Hence I need a way to typecheck reliably and throw compiler errors if it is wrong. It shouldn't be too hard, I'm no stranger by now to typechecking in the AST

2) A certain package must be included. The keyword 'belongs' to a certain package, and is only available while that package is imported. Hence, the lexer needs to recognize the '.' character as a potential valid character for a keyword. This also should not be hard.

3) Parse grammar and syntax into lexical tokens, which is the hardest part, as I'm not too familiar with how such things work. 

4) Depending on where it is used, depends on what it does. I plan on having the keyword modify range loop semantics for my particular type of map only (throw a compiler error if a non concurrent map is used).  The other is used at a statement level, which wraps a group of statements (which the statements inside shouldn't be too hard, there are examples inside the compiler I can work on). 

The 'sync.Interlocked' keyword

Originally I was going to go with 'runtime.Interlocked' keyword, but I figured 'sync' makes more sense. Here examples of it's statement-level semantics

m := make(map[int]int, 0, CONCURRENT)
sync.Interlocked m {
   m[1] += m[2] + m[3]
   m[2] -= m[3] - m[4]
}

Now imagine the body above was used in a shared concurrent map. The Read-Modify-Write instructions would be incorrect, even though the accesses themselves are fine and well protected. The issues here are of course that even though individual access to the map is atomic and fast (for record, currently the map is fully working, iteration, insertion, removal, retrieval, etc., are all working, and besides for iteration which has it's quirks, they all scale VERY well under little and high contention; under little contention, I see gains of 2 - 3x, with high contention, I see gains of up to 100x, not even lying about that either... then again, the tests used are still rather primitive, just randomized (millions of) operations on GOMAXPROCS Goroutines), instructions which rely on the previous for results are, unfortunately, not.

My goal is to acquire all locks in order, first, before proceeding. This requires the compiler to do some magic.The above will be transformed into

m := make(map[int]int, 0, CONCURRENT)
mapacquire(m, 2, 3, 1, 4)
m[1] += m[2] + m[3]
// Note that the key '1' is no longer used after the above Read-Modify-Write statement
maprelease(m, 1)
m[2] -= m[3] - m[4]
maprelease(m, 2, 3, 4)

Generally, any potentially deadlocks can be solved this way, as obtaining keys ahead of time ensures atomic access to the map until it completes, and it much easier than rolling back actions (especially since I wouldn't know where to begin implementing software transactional memory in Go). Any conflicts can result in a type of global ordering based on the Goroutines that want to acquire the keys. Exponential back-off is a way to prevent excessive livelock as well.(Speaking of which, if anyone could let me know how to make Goroutines sleep for a few cycles without the entire 'm' going to sleep, please let me know).

Next, is the range iterator portion.

m := make(map[int], 0, CONCURRENT)
for k, v := range sync.Interlockd m {
   v.field += something()
   v.someMutatingFunction()
}

The above is rather unique. The only difference is that the keyword 'sync.Interlocked' is there, which modifies the semantics of the iterator. The iterator will return the value by pointer (to the one stored in the bucket), and the lock on bucket only released after the bucket is exhausted and it moves on to the next.The main issue is that `someMutatingFunction()` could be a long function call, which is why the keyword modifies the semantics if and only if the user wants it that way. The normal mode acts on an atomic snapshot and greatly reduces contention by releasing the bucket immediately after copying. The issue there is that the value is returned by value, so modifications to it are not possible. This also allows the for loop body to execute for however long it wants, as it is working on a copy. Lastly, if an element is removed from the map, and it is still in the snapshot, it will still be available, which may not be what the user intends. The keyword 'sync.Interlocked'  will ensure that whatever they use will be in the list, as they always have the bucket lock.

I should also note that the map works by having individual bucket Test-And-Test-And-Set Spin Locks (in the future, with exponential backoff once I figured how to safely do so). Once a bucket is full, it just gets converted to another array of buckets (size increased by power of two of last one) to further increase concurrency and greatly reduce collision. The performance gain so far is enormous and I would like to continue with this, even if the general consensus is it not being approved. Hence, when I say "it acquires the keys', I mean it acquires the bucket lock.

TL;DR

1) How do I add a new keyword, 'sync.Interlocked' which can modify the semantics of pre-existing AST nodes, and also create my own

2) How do I turn my own keyword into AST nodes?

3) Are there any other things I need to know, like how AST nodes are transformed into actual executable code in the SSA? Or should the nodes be enough as they merely add some compiler-inserted additions and function calls, and/or change presently existing nodes.

All I need is the knowledge on where to begin with the keyword portion, and the rest I can do on my own.

[Josh Bleecher Snyder]

If you are ok with it being a predeclared function, like close, len,
etc., then you could take a look at
https://github.com/riscv/riscv-go/commit/7adaae94d4373cfc5c68d5503140dace6027930f
as an example to work from. That commit adds a predeclared riscvexit
function to the language to ease bootstrapping a new port. (It'll be
removed once bootstrapping is over.) The semantics are very simple for
it, so it could simply be passed all the way through the frontend and
the ssa backend basically unchanged; you'd have to figure out where
the most sensible place is to insert your own desired semantics. Most
likely it'd be in walk.go or during the Node-to-SSA conversion.

-josh

P.S. If anyone wants more details about the RISC-V port in progress or
(better yet!) wants to contribute, please drop a hello to
risc...@googlegroups.com. The repo is
https://github.com/riscv/riscv-go/ for now and code reviews are
happening at https://review.gerrithub.io/. :)

> --
> You received this message because you are subscribed to the Google Groups
> "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-dev+...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Kyle Stanly]

I honestly can't see it working as a predeclared function, as it requires quite a bit more care then that. The statement-level one would be possible if and only if it took a callback function, and I could treat the block to be executed like a closure, and make modifications specific to it (I.E, if in OCALL, the function to be called is "sync.Interlocked", then it can grab that closure, and perform some transformations on it, I.E

// Declaration in sync package
Interlocked(map[any]any, func(map[any]any))

// Usage of the function
sync.Interlocked(m, func(m){...})

However, see how ugly this is? If anything it makes harder, since I need to look into closure and figure out how I can modify the function directly. It'd be easier to just implement it as a keyword, and cleaner, since all they do modify the semantics.

Example:

The 'range sync.Interlocked m' can simply find, discard sync.Interlocked keyword, and mark/tag the ORANGE node as having my semantics, instead of needing to create an explicit word.

The 'sync.Interlocked m {...}' can also simply discard the node after being processed, as all I need it to do is mark where it starts, what ONAME/Sym/Whatever variable we are working on, etc. That's one potential easy solutions, another would be to have it as a cheap Node that has the functions inside it's 'Nbody', and have a special function walk it's body for keys and mapaccess/mapassign/mapdelete function calls. 

Overall, it should be relatively simple, its just not easy to learn due to the lack of documentation for the process (although there is some documentation, there isn't enough to fully understand without doing trial and error, and at this stage, I'm running too low on time to do so).

However, I would like to thank you for the commit, as I can definitely use it as an example if I have to go that route, and potentially for things I need to do on this route as well.

[Kyle Stanly]

In the case that people don't know (or do not wish to bother to get into the details), if someone could so let me know if there is a function like 'usleep' that can be used for putting the Goroutine to sleep without also causing the OS Thread, 'm', to sleep as well. I notice in their implementations (in assembly) of 'usleep' they result in system calls. If I wanted to remove a 'g' from the run queue and give up it's time-slice for a given few cycles, how would I go about doing that? Constantly called Gosched is okay, but it's eating the CPU up like crazy, I'm assuming due to the overhead of scheduler.

[Ian Lance Taylor]

On Mon, Jul 11, 2016 at 6:51 AM, Kyle Stanly <thei...@gmail.com> wrote:
> In the case that people don't know (or do not wish to bother to get into the
> details), if someone could so let me know if there is a function like
> 'usleep' that can be used for putting the Goroutine to sleep without also
> causing the OS Thread, 'm', to sleep as well. I notice in their
> implementations (in assembly) of 'usleep' they result in system calls. If I
> wanted to remove a 'g' from the run queue and give up it's time-slice for a
> given few cycles, how would I go about doing that? Constantly called Gosched
> is okay, but it's eating the CPU up like crazy, I'm assuming due to the
> overhead of scheduler.

How about time.Sleep?

Ian

[Kyle Stanly]

Is this available from inside of the runtime? I thought only the packages hosted inside of the runtime are available at runtime?

[Kyle Stanly]

Okay, I managed to create the keyword 'sync.Interlocked' on my own. It actually was relatively simple... now the hard part is the actual logic behind it. Still would be extremely interested in a more guided-approach and/or examples, as well as how to implement an exponential back off.

Pardon me if I ramble or become unclear, as I'm literally doing 10 different things at once. However, from what I am seeing, just like with everything else, the Go runtime was designed to be very minimal, and the only way to have a force a Goroutine to wait is using 'gopark' and it's variants. However, 'gopark' requires another Goroutine to wake it up, meaning its useless if I want to solely rely on time itself and not another Goroutine (as it's possible that while being put to sleep, the lock is already being released and no one is there to wake up the sleeping Goroutine). Hence I'm assuming that normally when you call time.Sleep, you have some sentinel Goroutine polling in the background to wake you up? I'm not even certain. The "Sleep" function in the 'time' package is a stub and I have no idea where the actual code is.

I'm not sure how I'll do it, but I was thinking of having the 'm' or 'p' have an additional wait queue (since sudog is designed with channels and blocking in mind, it won't work well for a non-blocking OS) with the time needed and the 'g' to wake-up there. The issue is that this requires a LOT of overhead, and it'll effect everything, not just the map itself. I guess I'll have to think of something to keep it down.

 
On Sunday, July 10, 2016 at 4:47:48 PM UTC-4, Kyle Stanly wrote:

[Uli Kunitz]

The code for time.Sleep can be found in runtime/time.go, look for function timeSleep. There is a single goroutine managing the timers. The main purpose of the goroutine is to have a single goroutine calling the kernel to wait for a timer. In a naive approach every goroutine could call the kernel on its own, but this would waste a kernel thread for each goroutine that uses a timer. In my experience the runtime is extremely well optimized and one would need to invest quite some time to come up with real improvements.

[Kyle Stanly]

Thank you for informing me where time.Sleep was implemented, I thought it'd be 'time_sleep' with an underscore just like all of the other //go:linkname annotations.

I suppose it makes sense to have one Goroutine handle everything, I mean after all, the entire philosophy is based on message passing over shared memory (with channels being the encouraged synchronization primitive and whatnot). I also definitely would like to avoid making system calls during a busy-wait. All I wanted was for it to be removed from the runqueue while it was backing off. If this does precisely that, it should be golden.

Also, I strongly agree that the runtime is very well optimized, for it's current design philosophy that is.

[Kyle Stanly]

Quick question about time.Sleep(). Does the scheduler have a priority for each Goroutine, wherein if the Goroutine yields their timeslice voluntarily they are more likely to be picked to go next in the runqueue, or rather, can Goroutines become 'interactive' Goroutines?

On Monday, July 11, 2016 at 1:29:07 PM UTC-4, Uli Kunitz wrote:

[Ian Lance Taylor]

On Mon, Jul 11, 2016 at 12:28 PM, Kyle Stanly <thei...@gmail.com> wrote:
> Quick question about time.Sleep(). Does the scheduler have a priority for
> each Goroutine, wherein if the Goroutine yields their timeslice voluntarily
> they are more likely to be picked to go next in the runqueue, or rather, can
> Goroutines become 'interactive' Goroutines?

The current scheduler implementation does not have any notion of
goroutine priority.

Ian

[Kyle Stanly]

Is there a reason why this has not been implemented or considered? Goroutine priorities sound like something that could come in handy.

For example, that sentinel Goroutine could have a 'background' priority, allowing it to detract less from the user Goroutines. Allowing the user to also set the Goroutine priority could also be very beneficial for those users who know they're doing.

[Ian Lance Taylor]

On Mon, Jul 11, 2016 at 1:21 PM, Kyle Stanly <thei...@gmail.com> wrote:
>
> Is there a reason why this has not been implemented or considered? Goroutine
> priorities sound like something that could come in handy.
>
> For example, that sentinel Goroutine could have a 'background' priority,
> allowing it to detract less from the user Goroutines. Allowing the user to
> also set the Goroutine priority could also be very beneficial for those
> users who know they're doing.

There are two different questions. One is whether goroutines should
support some sort of internally determined priority. I think that if
somebody can develop or copy a good algorithm, and provide benchmarks
showing that it is an improvement for real or real-ish code, that
would be great.

Letting users set a goroutine priority would be a very different
matter. That would require defining a new, clearly defined, API that
makes a difference for real programs and that we can support going
forward. That would require a lot of thought.

I think a major reason this has not been done is that goroutine
priorities are only going to matter for CPU-bound programs. Most Go
programs tend to be I/O-bound, and priorities are largely irrelevant.
The CPU-bound programs tend to not be interactive, so again priorities
are largely irrelevant. So the first step is definitely to find a
real-ish Go program for which goroutine priorities will make a real
difference.

Ian

[Kyle Stanly]

Alright guys, I managed to do it on my own. Both the syntax...

sync.Interlocked m { ... }

and

for k,v := range sync.Interlocked m { ... }

Turns out it was a bit more harder than I originally thought (the first one at least), but I made the changes to add a new node recognizable in the AST (typecheck and walk.go), Parser/Lexer, and SSA. I still don't know completely how the SSA works, so I was curious to how it all worked. Even an article would be nice, or even a basic rundown on how ssa.Block, ssa.Function, ssa.Value, etc, all come together. 

On Sunday, July 10, 2016 at 4:47:48 PM UTC-4, Kyle Stanly wrote:

[Josh Bleecher Snyder]

> Alright guys, I managed to do it on my own.

Many of your emails to this list have overtones of annoyance, despite
the fact that folks on this list have (I think) been pretty good about
trying to be helpful. I'm sure the tone is unintentional--tone
basically always is--which is why I'm mentioning it.

> Turns out it was a bit more harder than I originally thought (the first one
> at least), but I made the changes to add a new node recognizable in the AST
> (typecheck and walk.go), Parser/Lexer, and SSA. I still don't know
> completely how the SSA works, so I was curious to how it all worked. Even an
> article would be nice, or even a basic rundown on how ssa.Block,
> ssa.Function, ssa.Value, etc, all come together.

It's hard to know how to handle this kind of question. I'm not sure
what to say that will be most helpful; there are many, many ways to
answer this question, some of which are book-length. Asking more
specific questions will help you get better (and faster) answers.
Here's an attempt, though:

ssa.Function is the ssa representation of a Go function. ssa.Block is
a basic block in the function's cfg:
https://en.wikipedia.org/wiki/Control_flow_graph. ssa.Value is what
wikipedia calls an ssa variable:
https://en.wikipedia.org/wiki/Static_single_assignment_form.

Simplifying a lot, the front-end lexes, parses, typechecks, and does
some analysis, optimization, and simplification (inlining, escape
analysis, simplifying switch statements, range statements, panic
statements, etc.). We then convert from the front-end's output to an
ssa form. The ssa backend optimizes and then lowers to an
architecture-specific ssa. Further optimizations occur, as well as
decisions about how to lay out the blocks and values, assign values to
registers, etc. Then each architecture decides how to convert the
arch-specific ssa into actual instructions, roughly corresponding to
assembly one might write manually. Then that assembly gets lowered
into machine code.


Is your code open source somewhere? One really useful way to learn is
to ask for code reviews on work you've done, or even work you've made
substantive progress on but not quite completed. It helps focus the
conversation. And code in a code review or display tool is far easier
to read than code in an email. Code reviews can also spare you having
to discover subtle bugs later that might be obvious to experienced
reviewers.


Another useful thing you might consider doing is try to improve the
documentation for the code you encounter and then contribute back
those doc changes. Nothing helps you understand something like having
to re-present it. You'll get lots of feedback on the details that way,
and it'll benefit all future readers of the code, not just people who
dig up ancient mailing list threads. :)


-josh

[Kyle Stanly]

Many of your emails to this list have overtones of annoyance, despite 
the fact that folks on this list have (I think) been pretty good about 
trying to be helpful. I'm sure the tone is unintentional--tone 
basically always is--which is why I'm mentioning it. 

I was unaware that I came across in such a way, and I sincerely do apologize if I gave the impression of being annoyed at the developers. I know full and well that you guys are very busy, and the help that's been given has been fully appreciated; without the help I've been given in the past, I probably wouldn't have made it this far.

However, my annoyance is more towards the language than anything else. I specifically attempt to refrain from asking on the golang-dev mailing list because I don't want to come across as lazy, or 'beyond all help', or 'not worth the time', and if I do I try to (or at least I am now) formulate my questions to be as verbose, and general as possible. I normally spend at least a week attempting to solve any problems on my own, and then come to the developer forums if I truly need help. Now, trying and failing repeatedly at something causes a lot of irritation and annoyance (once again towards the language), and I had no idea that it seeped through to my question as well. It's no excuse, but hopefully it's a halfway-decent explanation.

It's hard to know how to handle this kind of question. I'm not sure 
what to say that will be most helpful; there are many, many ways to 
answer this question, some of which are book-length. Asking more 
specific questions will help you get better (and faster) answers. 

Now, another reason I try to be as general as possible is because I already know what the general consensus (or atleast I think I do) on where you guys stand on whether or not my project will be accepted. Hence, since my issues are normally specific enough to said project, wherein any change-log would be significant in size (over 2000 lines), I'd figure no one would want to bother digging through all of my code for a problem. Hence I try to keep it more vague, from what I thought, easier to answer.

I.E: Lets say I made a minor modification to the Garbage Collector and invoked some undefined behavior, it'd be nothing but my own fault and my own mess to clean up, and I wouldn't expect other people to trudge through my mess to find a solution, especially when they said "don't do that, do this instead", hence instead of asking directly for help, I ask for a way to solve the problem based on what I think the problem is.

Anyway, I'm rambling again, and I apologize, but the gist is: I'm sorry if I came off as arrogant and/or annoyed, I'm just frustrated with very little time left.

Another useful thing you might consider doing is try to improve the 
documentation for the code you encounter and then contribute back 
those doc changes.

I know it has been said many times before, but I do plan on doing so, but mostly towards the end with my proposal if/when I finish it. I'll even separate the documentation from the rest of the project in the case it gets rejected (most likely).

Is your code open source somewhere? One really useful way to learn is 
to ask for code reviews on work you've done, or even work you've made 
substantive progress on but not quite completed. It helps focus the 
conversation. And code in a code review or display tool is far easier 
to read than code in an email. Code reviews can also spare you having 
to discover subtle bugs later that might be obvious to experienced 
reviewers. 

Yes, I do have the code on GitHub, but it's out of date with the master branch (and has merge conflicts), Gerrit does not work well with Cygwin (at all) and I can't use that either. My main issue with code reviews is similar to why I try to refrain from asking for help (general consensus), but of course if that wasn't a problem, I'd definitely try to get one done before my project is due.

Also, thank you for the information on ssa.*, I know my question was vague, and I apologize. Most of the time I only reply when I have further questions/inquiries, so I hope that wasn't also misconstrued as being annoyed.

[Josh Bleecher Snyder]

Many of your emails to this list have overtones of annoyance, despite 
the fact that folks on this list have (I think) been pretty good about 
trying to be helpful. I'm sure the tone is unintentional--tone 
basically always is--which is why I'm mentioning it. 

I was unaware that I came across in such a way, and I sincerely do apologize if I gave the impression of being annoyed at the developers.

No worries, don't sweat it. And to be clear, my comment was meant as a friendly heads up, not a chastisement. :)

 

Is your code open source somewhere? One really useful way to learn is 
to ask for code reviews on work you've done, or even work you've made 
substantive progress on but not quite completed. It helps focus the 
conversation. And code in a code review or display tool is far easier 
to read than code in an email. Code reviews can also spare you having 
to discover subtle bugs later that might be obvious to experienced 
reviewers. 

Yes, I do have the code on GitHub, but it's out of date with the master branch (and has merge conflicts), Gerrit does not work well with Cygwin (at all) and I can't use that either. My main issue with code reviews is similar to why I try to refrain from asking for help (general consensus), but of course if that wasn't a problem, I'd definitely try to get one done before my project is due.

Would you mind opening an issue (golang.org/issue/new) with the details of the Cygwin/gerrit problems? Either there's a bug or there's a documentation deficiency, and either way we want to fix the problem. I'd hate for that to be the thing that stands in the way of you getting code-level feedback and/or of you being able to contribute changes.

Also, bear in mind that many of the people reading this list really like languages and compilers and runtimes and code. :) So while there's no guarantee that you'd get someone poring over every detail of a 2000 line CL, you might get more feedback than you expect. Particularly so if that 2000 line CL was actually 20 well-organized 100 line CLs. Also, I find the process of preparing code for review is itself very useful.

 Josh

[ad...@gardener.com]

On Wednesday, July 13, 2016 at 4:37:27 PM UTC-4, Josh Bleecher Snyder wrote:

Many of your emails to this list have overtones of annoyance, despite 
the fact that folks on this list have (I think) been pretty good about 
trying to be helpful. I'm sure the tone is unintentional--tone 
basically always is--which is why I'm mentioning it. 

I was unaware that I came across in such a way, and I sincerely do apologize if I gave the impression of being annoyed at the developers.

No worries, don't sweat it. And to be clear, my comment was meant as a friendly heads up, not a chastisement. :)

 

Certainly came across as an attack. Only after an apology did YOUR tone change. I'm shocked that you could find a tone within the OP message, but lack that insight with regard to your own messages, despite the fact that you know with certainty the tone you wish to project.
 

[Kyle Stanly]

While I appreciate standing up for me, I never felt it as an 'attack', per say, but as constructive criticism. He pointed out something I was unaware of, and something that would be beneficial to me to improve on. I however applaud you for standing up for a random person you felt was wronged, but really, I'm fine.

[Dan Kortschak]

On Wed, 2016-07-13 at 08:41 -0700, Josh Bleecher Snyder wrote:
> > Alright guys, I managed to do it on my own.
>
> Many of your emails to this list have overtones of annoyance, despite
> the fact that folks on this list have (I think) been pretty good about
> trying to be helpful. I'm sure the tone is unintentional--tone
> basically always is--which is why I'm mentioning it.
>

I read Kyle's emails as being chuffed about having done something
difficult by himself rather than passive aggressive complaining.

Dan

[Josh Bleecher Snyder]

Indeed. Thanks, Dan.

I just went and re-read a bunch of Kyle's emails to the list, and I see that while he has frequently been frustrated with the code and the lack of docs (a sentiment I share at times), he has always been polite and gracious with the people involved. As author of some small part of that code, I didn't do a good enough job keeping those separate as I read.

Kyle, I apologize.

Josh