Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Do we really need channels and goroutines? #38

Open
dragonsinth opened this issue Jan 7, 2017 · 17 comments
Open

Do we really need channels and goroutines? #38

dragonsinth opened this issue Jan 7, 2017 · 17 comments

Comments

@dragonsinth
Copy link
Contributor

I haven't done super serious profiling yet, but in a rather large application we run, our lexer keeps coming up in goroutine dumps at what seems to be a disproportionately high rate, especially given that we lex very small strings as a tiny part of everything our app does. I found a bunch of routines awaiting chan receive in the generated lexer, which kind of immediately raised my eyebrow. Given what the lexer does, does it really need to use channels and goroutines to accomplish its job? I'm not familiar with the design constraints or exactly what kind of guarantees we want to make for the user code that gets embedded in the generator, but it seems like this could all be done more efficiently single-threaded.

Thoughts?
@blynn
Copy link
Owner

blynn commented Jan 8, 2017

There are no design constraints or guarantees: nex started as a toy weekend project to help me get acquainted with Go. My understanding was that channels and goroutines are cheap, but it's certainly possible I used them badly. I keep meaning to revisit the code one day, but heaps of other toy projects get in the way.

I'd be happy to accept patches that improve efficiency.

@dragonsinth
Copy link
Contributor Author

dragonsinth commented Jan 8, 2017 •
edited
Loading

Thanks for the info, I'll take a look and see if I can reformulate it a callback instead of a channel.

@dragonsinth
Copy link
Contributor Author

I have a proof of concept of how the generated code can change. This works for my particular project (tests pass) and it's about 40% faster in an isolated benchmark I ran. Not sure it changes like this would impact other users. Take a look and tell me if you think this is a good direction, I went for minimal changes rather than a big overhaul.

@@ -13,7 +13,7 @@ type frame struct {
 }
 type Lexer struct {
 	// The lexer runs in its own goroutine, and communicates via channel 'ch'.
-	ch chan frame
+	scan func(func(frame))
 	// We record the level of nesting because the action could return, and a
 	// subsequent call expects to pick up where it left off. In other words,
 	// we're simulating a coroutine.
@@ -46,9 +46,8 @@ func NewLexerWithInit(in io.Reader, initFun func(*Lexer)) *Lexer {
 	if initFun != nil {
 		initFun(yylex)
 	}
-	yylex.ch = make(chan frame)
-	var scan func(in *bufio.Reader, ch chan frame, family []dfa, line, column int)
-	scan = func(in *bufio.Reader, ch chan frame, family []dfa, line, column int) {
+	var scan func(in *bufio.Reader, f func(frame), family []dfa, line, column int)
+	scan = func(in *bufio.Reader, f func(frame), family []dfa, line, column int) {
 		// Index of DFA and length of highest-precedence match so far.
 		matchi, matchn := 0, -1
 		var buf []rune
@@ -143,9 +142,9 @@ func NewLexerWithInit(in io.Reader, initFun func(*Lexer)) *Lexer {
 					text := string(buf[:matchn])
 					buf = buf[matchn:]
 					matchn = -1
-					ch <- frame{matchi, text, line, column}
+					f(frame{matchi, text, line, column})
 					if len(family[matchi].nest) > 0 {
-						scan(bufio.NewReader(strings.NewReader(text)), ch, family[matchi].nest, line, column)
+						scan(bufio.NewReader(strings.NewReader(text)), f, family[matchi].nest, line, column)
 					}
 					if atEOF {
 						break
@@ -160,9 +159,10 @@ func NewLexerWithInit(in io.Reader, initFun func(*Lexer)) *Lexer {
 				}
 			}
 		}
-		ch <- frame{-1, "", line, column}
 	}
-	go scan(bufio.NewReader(in), yylex.ch, []dfa{
+
+	yylex.scan = func(f func(frame)) {
+		scan(bufio.NewReader(in), f, []dfa{
 			// CrOS
 			{[]bool{false, false, false, false, true}, []func(rune) int{ // Transitions
 				func(r rune) int {
@@ -4401,6 +4401,8 @@ func NewLexerWithInit(in io.Reader, initFun func(*Lexer)) *Lexer {
 				},
 			}, []int{ /* Start-of-input transitions */ -1, -1}, []int{ /* End-of-input transitions */ -1, -1}, nil},
 		}, 0, 0)
+	}
+
 	return yylex
 }
 
@@ -4431,7 +4433,7 @@ func (yylex *Lexer) Column() int {
 	return yylex.stack[len(yylex.stack)-1].column
 }
 
-func (yylex *Lexer) next(lvl int) int {
+func (yylex *Lexer) next(lvl int, fr frame) int {
 	if lvl == len(yylex.stack) {
 		l, c := 0, 0
 		if lvl > 0 {
@@ -4441,7 +4443,7 @@ func (yylex *Lexer) next(lvl int) int {
 	}
 	if lvl == len(yylex.stack)-1 {
 		p := &yylex.stack[lvl]
-		*p = <-yylex.ch
+		*p = fr
 		yylex.stale = false
 	} else {
 		yylex.stale = true
@@ -4453,9 +4455,8 @@ func (yylex *Lexer) pop() {
 }
 func findTokens(ua string) (bits uint64) {
 	func(yylex *Lexer) {
-	OUTER0:
-		for {
-			switch yylex.next(0) {
+		yylex.scan(func(fr frame) {
+			switch yylex.next(0, fr) {
 			case 0:
 				{
 					// user code
@@ -4567,12 +4568,10 @@ func findTokens(ua string) (bits uint64) {
 				{ /* ignore */
 				}
 			default:
-				break OUTER0
-			}
-			continue
+				panic("shouldn't get here")
 			}
 			yylex.pop()
-
+		})
 	}(NewLexer(strings.NewReader(ua)))
 	return
 }

@blynn
Copy link
Owner

blynn commented Jan 8, 2017

Looks good. Replacing a channel with a callback should be harmless. I'd be happy to merge a commit with this change.

@dragonsinth
Copy link
Contributor Author

OK I'll put a PR together. Anything I should know about early exit? Previously the user code could probably break out of the loop early (although that would leak the go routine). With this formulation there's no way to early exit short of a panic. Is that OK or should I provide some way break out?

@blynn
Copy link
Owner

blynn commented Jan 9, 2017

I can't be sure anymore, but I have a feeling that the break is needed when there are nested patterns. Can you build a patched version of nex then run "go test" in the test/ subdirectory?

@dragonsinth
Copy link
Contributor Author

Yeah, just did that. In fact, the first test example (rp.nex) expects to be able to return an int from the main Lex() method, and another one hit the panic() I threw in for the default case, so it definitely expects to be able to break out.

To be fair, both of those examples aren't truly correct on master since they'll leak the background goroutine and basically pin everything, but it looks like I need a way to propagate an exit condition up.

@blynn
Copy link
Owner

blynn commented Jan 9, 2017 via email

@dragonsinth
Copy link
Contributor Author

dragonsinth commented Jan 9, 2017 •
edited
Loading

After digging on this more, I'm pretty sure the naive approach isn't going to work. The Yacc example expects to be able to call Lex() repeatedly and get a token at a time, and have it return and call it again in the same state. But all the DFA states, line, column are local to the scan routine, which means exiting and starting over resets everything.

Supporting that kind of operation means a more invasive refactor to move all the scan() local state into the Lexer itself.

Does all that gel with your understanding? Because I'm only like 90% sure that what I wrote is accurate.

@blynn
Copy link
Owner

blynn commented Jan 9, 2017 via email

@dragonsinth
Copy link
Contributor Author

Plugging the leaks is doable, basically you'd need a doneChan channel that runs in the opposite direction, from the consumer routine to the producer routine. You'd setup a defer in the consumer to close doneChan, and you'd turn frame writes into the frame channel into a select statement that will either write to the frame channel or read from the doneChan, and if you ever read from doneChan you exit immediately.

That said, I don't think our application is actually leaking goroutines here, and it's still slowish for us. On a non-leaking, single-threaded benchmark I wrote it went from 5.4s -> 3.1s just changing channels to callbacks.

I also got a (smaller) speedup by moving the static DFA transition table out to "constant" and sharing them being instances instead of recreating the static table each time, but I was going to submit a separate PR for that.

@dragonsinth
Copy link
Contributor Author

Hmm, actually when I dug in a bit, it's unclear when you would actually close the doneCh to signal the background routine to exit. For NN_FUN() type usages you could do it when the NN_FUN() returns, but for yacc-type use it's way less clear.

In the following code, when would you signal the background loop to exit?

// Lex runs the lexer. Always returns 0.
// When the -s option is given, this function is not generated;
// instead, the NN_FUN macro runs the lexer.
func (yylex *Lexer) Lex(lval *yySymType) int {
OUTER0:
	for {
		switch yylex.next(0) {
		case 0:
			{ /* Skip blanks and tabs. */
			}
		case 1:
			{
				lval.n, _ = strconv.Atoi(yylex.Text())
				return NUM
			}
		case 2:
			{
				return int(yylex.Text()[0])
			}
		default:
			break OUTER0
		}
		continue
	}
	yylex.pop()

	return 0
}
func main() {
	yyParse(NewLexer(os.Stdin))
}

@blynn
Copy link
Owner

blynn commented Jan 11, 2017 via email

@dragonsinth
Copy link
Contributor Author

Yeah, I think you're right. As long as all the input is ultimately consumed the background routine should exit.

@marsjupiter1
Copy link

I have running in to awful performance when reinvoking the lexer and have resorted to a "patch". The patch below never seems to fail and makes a 1000 fold and more speed increase.

--- generated_fxnn.go 2019-10-14 10:37:46.835681718 +0000
+++ generated_fxnn.go_works 2019-10-14 10:36:27.672678048 +0000
@@ -145,25 +145,10 @@
text := string(buf[:matchn])
buf = buf[matchn:]
matchn = -1

  •   			for {

  •   				sent := false

  •   				select {

  •   				case ch <- frame{matchi, text, line, column}:

  •   					{

  •   						sent = true

  •   					}

  •   				case stopped = <-ch_stop:

  •   					{

  •   					}

  •   				default:

  •   					{

  •   						// nothing

  •   					}

  •   				}

  •   				if stopped || sent {

  •   					break

  •   				}

  •   			}

  •   			ch <- frame{matchi, text, line, column}

  •   			if stopped {
  				break
  			}

@purpleidea
Copy link
Collaborator

@marsjupiter1 If you'd like to suggest a patch, submit it as a pull request please. The current form is not something we can read.

@marsjupiter1
Copy link

marsjupiter1 commented Oct 15, 2019 via email

This was referenced Oct 16, 2019
Open
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@blynn @purpleidea @dragonsinth @marsjupiter1