Welcome to Blogs @ Andrew Qu
Blog Index
All blogs
Search results

Routines, Channels and Multi-Threading in GO Language

Summary

With Android Nougat released recently, the build system used is switching from Make to Ninja. To generate Ninja files, Android uses Blue Print files that are basically GO programs. While studying GO language, I noticed its multi-threading model is facinating. In this post, I will try to discribe this model.

Installation and the Hello Go Program

Install GO compiler from this link : Install GO

Once installed, we are ready to write the first GO program with the following steps (I am using Unix) :

$ mkdir goprojs
$ cd goprojs
$ mkdir src
$ cd src
$ mkdir hellogo
$ echo "package main" >hellogo\hello.go
$ gedit hellogo/hello.go and insert code shown in the next listing
$ go install hellogo
$ ../bin/hellogo
Output: Helloo go!
Listing of hello.go
package main

import "fmt"

func main() {
   fmt.Println("Hello go!")
}

GO Routine and Thread

To start a new thread in GO is very easy. Simply call the function after the go keyword. For example,

package main

import (
   "fmt"
   "time"
)

func print_letters(s string) {
   for i := 0; i < len(s); i++ {
      fmt.Printf("%c\n", s[i]);
      time.Sleep(time.Millisecond * 500)
   }
}

func main( ) {
   go print_letters("12345")  // Prints 12345 in a separate thread
   print_letters("67890")     // Prints 67890 in the main thread
}
Output :
1
6
2
7
3
8
4
9
5
0
Channels in GO

go func() starts a new thread. After starting, the main thread continues. If any result needs to be returned to the main thread, a channel must be used.

For example, if we want to return the number of letters printed from function print_letters(), the following code will not return the number of letters to the main thread if the func is run on a separate thread.

func print_letters(s string) {
   for i := 0; i < len(s); i++ {
      fmt.Printf("%c\n", s[i]);
      time.Sleep(time.Millisecond * 500)
   }
   return len(s)
}
What we need is to pass the result through a so called channel.
func print_letters(s string, ch_num_letters (chan int)) int {
   for i := 0; i < len(s); i++ {
      fmt.Printf("%c\n", s[i]);
      time.Sleep(time.Millisecond * 500)
   }
   if ch_num_letters != nil {   // Send number of letters to the channel if given
       ch_num_letters <- len(s)
   }
   return len(s)
}
Modify the main() func as follows to call the revised print_letters() function:
func main() {
   ch_num_letters := make(chan int)
   go print_letters("123456", ch_num_letters)  // Prints 123456 in a separate thread
   len2 := print_letters("67890", nil)         // Prints 67890 in the main thread

   num_letters := <- ch_num_letters
   fmt.Println("Number of letters: ", num_letters, "and", len2)
}
Some quick points about channels :
ch := make(chan int)  Makes a channel that sends or receives type int.
ch <- 2          Sends number 2 to the channel, waits if the channel is busy.
n := <- ch       Try to receive an element from the channel. Waits if the channel is empty
n,ok := <- ch    Same as the previous line, but sets ok to true if a value is retrieved,
                 sets ok to false if the channel has been closed

Algorithm to Evaluate Numerical Expression

I will use GO routines and channels to evaluate numerical expression. I will first demonstrate the algorithm of evaluating numerical expressions.

The purpose of the algorithm is to evaluate a numerical expression. For example, given an expression, 2 * 5 + 15, we wan to find the answer 25.

The steps are (sample expression 2 * 5 + 15) :

1. Parsing the expression to produce a list of tokens, ignoring white spaces.
    For the sample expression, the list is [2,*,5,+,15]
2. Build a binary tree, for example,
         +
       / \
      *  15
     / \
    2   5

In the tree, each operator node has a left and right nodes (operands). The numbers are always leaf nodes. When building the tree, we must note that operator has precedences/priorities. */ have higher precedence than +-. This will be shown in code later.

3. Evaluate the tree to get the answer. This is done starting at the root node. If the node is an operator, evaluate its left and right nodes, then evaluate the node itself. This will require a stack and push, pop elements as needed. However, for most modern language with recursive functions, the stack is not explicitly needed. It is provided by the recursive function calls. The pseudo execution for the sample expression is:

Root node +
Evaluate root_left *
   Evaluate left node, result : 2
   Evaluate right node, result : 5
   Evaluate left * right, result : 10
Evaluate root_right 15, result : 15
Evaluate root_left + root_right, result: 25
Some Necessary GO Types

I will first define some GO types that are needed for solving the problem.

// Represents a token in expressions
type Token struct {
   IsOperator bool;
   Value int
}
// Return the token's operator (+ - * / ( ))
func (tk *Token) Operator() int {
    if !tk.IsOperator {
        panic("Try to get operator, but it is an operand.")
    }
    return tk.Value
}
// Return the token's operand
func (tk *Token) Operand() int {
    if tk.IsOperator {
        panic("Try to get operanad, but it is an operator.")
    }
    return tk.Value
}

// A tree node in the binary tree representing an expression
type TokenNode struct {
   TheToken Token;
   LeftNode *TokenNode;
   RightNode *TokenNode;
   Parent *TokenNode;
}
Token examples are
plus := Token { true, '+' }
n100 := Token { false, 100 }
For the sample expression, 2 * 5 + 15, the binary tree is :
t2 := TokenNode { Token { false, 2 }, nil, nil, &time }
t5 := TokenNode { Token { false, 5 }, nil, nil, &time }
t15 := TokenNode { Token { false, 15 }, nil, nil, &plus }
time := TokenNode { Token { true, '*' }, &t2, &t5, &plus }
plus := TokenNode { Token { true, '+' }, &time, &t15, nil)
root := &plus
The code for building the tree is a bit complex and will be explained in the next section. However, evaluating the tree is simple, as shown below :
// Recursively evaluate tree node
func EvalTreeNode(node *TokenNode) int {
   if node.TheToken.IsOperator == false {
      return node.TheToken.Operand()
   } else {
      a := EvalTreeNode(node.LeftNode)
      b := EvalTreeNode(node.RightNode)
      switch node.TheToken.Operator() {
      case '+' :
         return a + b
      case '-' :
         return a - b
      case '*' :
         return a * b
      case '/' :
         return a / b
      }
      return 0;
   }
}
Parsing and Making the Binary without Using GO Channels

In this process, the expression will be parsed and all tokens are stored in an array. Then the tokens are processed into a binary tree. The code is shown below:

import (
   "strconv"
   "strings"
)
// Represents a tokens array
type TokenArray struct {
   NumTokens int;
   Tokens [] Token
}
// Add a token into the tokens array
func (ta *TokenArray) AddToken(isOperator bool, value int) {
   if ta.NumTokens < len(ta.Tokens) {
      ta.Tokens[ta.NumTokens] = Token { isOperator, value }
      ta.NumTokens++
   } else {
      panic("Token array is full")
   }
}
// Tokenise an expression into an tokens array
func (ta *TokenArray) Tokenise(exp string) {
   ops := "+-*/()"
   exp = strings.Replace(exp, " ", "", len(exp))
   
   ta.Tokens = make([] Token, len(exp))
   ta.NumTokens = 0
   
   ts := 0 // Start of the next token
   for i := 0; i < len(exp); i++ {
      if strings.IndexByte(ops, exp[i]) >= 0 {
         if ts < i {
            n, _ := strconv.Atoi(exp[ts : i])
            ta.AddToken(false, n)
         }
         ta.AddToken(true, int(exp[i]))
         ts = i + 1
      } else if '0' <= exp[i] && exp[i] <= '9' {
      // A digit, continue
      } else {
         panic(strings.Join([] string { "Invalid character at", exp[: i+1]}, ""))
      }
   }
   if ts < len(exp) {
      n, _ := strconv.Atoi(exp[ts : ])
      ta.AddToken(false, n)
   }
}
// Build the binary tree from the tokens array
func (ta *TokenArray) MakeBinaryTree( ) *TokenNode {
   root := &TokenNode { ta.Tokens[0], nil, nil, nil }
   if root.TheToken.IsOperator == true {
      panic("Error: first token of the expression cannot be an operator!")
   }
   lastNode := root

   for i := 1; i < ta.NumTokens; i++ {
      tkn := ta.Tokens[i]
      node := TokenNode { tkn, nil, nil, nil}
      if tkn.IsOperator == false {
         if lastNode.TheToken.IsOperator == false {
            panic("Error: Near token \"" + string(tkn.Operand()) + "\"")
         }
         lastNode.RightNode = &node
         node.Parent = lastNode
      } else {	// An operator, search for the node to replace
          p := node.Priority()
          replNode := lastNode
          for ; replNode.Parent != nil; {
              if replNode.Parent.Priority() <= p {
                  break
              } else {
                  replNode = replNode.Parent
              }
          }
          // Replace the node
          if replNode.Parent == nil {
              root = &node
          } else {
              replNode.Parent.RightNode = &node
              node.Parent = replNode.Parent
          }
          node.LeftNode = replNode
          replNode.Parent = &node
      }
      lastNode = &node
   }
   return root
}
// Evaluate an expression. This is the API function
func EvalExpression0(exp string) (int, *TokenNode) {
    tokens := TokenArray { }
    tokens.Tokenise(exp)
    root := tokens.MakeBinaryTree()
    return EvalTreeNode(root), root
}

func Tokenise() should be straight forward. It parses the expression and adds each token found into the tokens array.

func MakeBinaryTree() process the tokens one by one. It starts the first token as the root node. Then it tries to insert the next token into the tree.

If the last node is an operator, then insert the current node as the RightNode of the last node. If the last node is not an operator, we need to check the insertion position up the tree until an operator that has lower or equal precedence. When inserting the current node, the replaced node becomes the LeftNode of the current node. The parent's RightNode points now to the current node. If the parent of the replaced node is nil, then the current node becomes the new root node.

func EvalExpression0() is the API function the be called. It declares a TokenArray, then tokenizes the expression. Calls the MakeBinaryTree() function and EvalTreeNode(). Finally, returns the result and root node of the binary tree.

Using GO Routines and Channels

The above code can be improved for performance by using GO routines and channels. in doing so, we do not need to store the tokens into the TokenArray. In stead, we send the token directly into a channel as soon as it is parsed. We then use a second thread to read the tokens from the channel and build the binary tree at the same time. Threfore, we can get rid of the TokenArray. Also we can speed up the execution since the parsing and building tree are done in parallel.

The revised code is shown below:

import (
   "strconv"
   "strings"
)
// Tokenise an expression and pipe tokens to the given channel
func Tokenise(exp string, ch (chan Token) ) {
   ops := "+-*/()"
   exp = strings.Replace(exp, " ", "", len(exp))
   defer func() { close(ch) }()

   ts := 0 // Start of the next token
   for i := 0; i < len(exp); i++ {
      if strings.IndexByte(ops, exp[i]) >= 0 {
         if ts < i {
            n, _ := strconv.Atoi(exp[ts : i])
            ch <- Token { false, n }
         }
         ch <- Token { true, int(exp[i]) }
         ts = i + 1
      } else if '0' <= exp[i] && exp[i] <= '9' {
      // A digit, continue
      } else {
         panic(strings.Join([] string { "Invalid character at", exp[: i+1]}, ""))
      }
   }
   if ts < len(exp) {
      n, _ := strconv.Atoi(exp[ts : ])
      ch <- Token { false, n }
   }
}
// Build the binary tree from the tokens array
func MakeBinaryTree(ch (chan Token), ch_root (chan *TokenNode) ) {
   defer func() { close(ch_root) }()    // Make sure the chan is always closed

   tkn, ok := <- ch
   if !ok { return }

   root := &TokenNode { tkn, nil, nil, nil }
   if root.TheToken.IsOperator == true {
      panic("Error: first token of the expression cannot be an operator!")
   }
   lastNode := root

   for tkn = range ch {
      node := TokenNode { tkn, nil, nil, nil}
      if tkn.IsOperator == false {
         if lastNode.TheToken.IsOperator == false {
            panic("Error: Near token \"" + string(tkn.Operand()) + "\"")
         }
         lastNode.RightNode = &node
         node.Parent = lastNode
      } else {	// An operator, search for the node to replace
          p := node.Priority()
          replNode := lastNode
          for ; replNode.Parent != nil; {
              if replNode.Parent.Priority() <= p {
                  break
              } else {
                  replNode = replNode.Parent
              }
          }
          // Replace the node
          if replNode.Parent == nil {
              root = &node
          } else {
              replNode.Parent.RightNode = &node
              node.Parent = replNode.Parent
          }
          node.LeftNode = replNode
          replNode.Parent = &node
      }
      lastNode = &node
   }
   ch_root <- root
}
// Evaluate an expression. This is the UI function
func EvalExpression(exp string) (int, *TokenNode) {
    ch := make( chan Token, 10)         // Channel for tokens
    ch_root := make(chan *TokenNode)    // Channel for the root of the binary tree

    go MakeBinaryTree(ch, ch_root)  // Start the thread that receives and process tokens
    // When all done, the root of the binary tree will be sent through ch_root

    Tokenise(exp, ch)   // Tokenise the expression and send tokens to ch

    root, ok := <- ch_root  // Wait for tree root from MakeBinaryTree thread
    if ok {
        return EvalTreeNode(root), root 
    } else {
        return 0, nil
    }
}

The Tokenise() and MakeBinaryTree() are not changed too much. Everywhere previously calls AddToken(), now the token is sent directly to the channel. Similarly, in MakeBinaryTree(), the tokens are read from the channel, instead of reading from the TokenArray. However, since we need to send the root node back to the main thread, we need to use a second channel, ch_root to pass back to the main thread.

Both channels are closed using defer functions, that executes after the functions returned.

The logic of EvalExpression() is shown in the following flow chart:



Download/View whole source code

Ads from Googlee
Dr Li Anchor Profi
www.anchorprofi.de
Engineering anchorage plate design system
©Andrew Qu, 2014. All rights reserved. Code snippets may be used "AS IS" without any kind of warranty. DIY tips may be followed at your own risk.