Open Source Software Optimization - Practice of Parallel Programming in Code Validation Algorithms

The code validation algorithm is used to validate the code format of a data sequence. A typical example is the UTF-8 code validation algorithm. The UTF-8 validation algorithm is used to check whether the data sequence complies with the UTF-8 coding standards. For example, the UTF-8 validation algorithm can be used to validate the encoding of emails, web pages, and application data encoded by UTF-8. This document uses the UTF-8 validation algorithm optimization case in the Go open-source community as an example to describe the general algorithm analysis and optimization methods.

1. UTF-8 Coding Validation Algorithm of Go

Go implements the UTF-8 coding validation algorithm to check UTF-8 encoded data. The algorithm is designed based on the UTF-8 coding feature of variable lengths. UTF-8 encoding uses 1 to 4 bytes to encode each character. ASCII encoding is the scenario when the length of the UTF-8 code is 1 byte. Based on this feature, the UTF-8 validation algorithm uses a character to determine whether the character is encoded by ASCII. If not, it checks whether the character is of another UTF-8 encoding type. The sample code is as follows:

// The UTF-8 validation algorithm before optimization uses a byte to check whether it is encoded by ASCII. If not, it checks whether the character is of another UTF-8 encoding type.
func Valid(p []byte) bool {
 n := len(p)
 for i := 0; i < n; {
  // Check whether the byte character is encoded by ASCII. When there are a large number of ASCII coded characters, the calculation efficiency drops.
  pi := p[i]
  if pi < RuneSelf {
   i++
   continue
  }

  // Check whether the byte character is of another UTF8 encoding type.
  x := first[pi]
  if x == xx {
   return false // Illegal starter byte.
  }
  size := int(x & 7)
  if i+size > n {
   return false // Short or invalid.
  }
  accept := acceptRanges[x>>4]
  if c := p[i+1]; c < accept.lo || accept.hi < c {
   return false
  } else if size == 2 {
  } else if c := p[i+2]; c < locb || hicb < c {
   return false
  } else if size == 3 {
  } else if c := p[i+3]; c < locb || hicb < c {
   return false
  }
  i += size
 }
 return true
}

2. Scenario and Problem Analysis

After analyzing the UTF-8 validation algorithm before the Go language is optimized, it is found that the algorithm is also used to check ASCII characters. It is also common to see a large number of ASCII coded characters in a long English email. The following figure shows an English email containing 1705 ASCII characters.

When the UTF-8 validation algorithm is used to check the encoding of English email content, 1705 comparisons are required, as shown in the following figure.

Therefore, in a scenario where a large amount of ASCII encoded data needs to be validated, the UTF-8 coding validation algorithm before optimization uses the single-character comparison to check the encoding until the entire data is checked cyclically. The algorithm execution is time-consuming, and the performance needs to be improved.

3. Optimization Solution and Implementation

To improve the UTF-8 validation algorithm, parallel programming can be applied to check multiple ASCII encoded characters at a time, reducing the number of comparison times, accelerating the validation, and improving the algorithm performance. The UTF-8 validation algorithm of the Go language uses the algorithm optimization solution based on the parallel programming idea. Eight ASCII encoded characters can be checked at a time, greatly improving the performance. The following figure shows the code comparison before and after the algorithm optimization.

The optimized code is analyzed as follows:

// The optimized code, based on the parallel programming idea, checks whether eight bytes are ASCII encoded characters at a time.
func Valid(p []byte) bool {
 // Check whether eight bytes are ASCII encoded characters in each epoch.
 for len(p) >= 8 {
  // Two uint32 variables, first32 and second32, are used to store 4-byte data, respectively.
  first32 := uint32(p[0]) | uint32(p[1])<<8 | uint32(p[2])<<16 | uint32(p[3])<<24
  second32 := uint32(p[4]) | uint32(p[5])<<8 | uint32(p[6])<<16 | uint32(p[7])<<24
  // The result of the AND operation between any ASCII encoded character and 0x80 is 0. The 8-byte ASCII character check is implemented through the AND operation between (first32|second32) and 0x80808080.
  if (first32|second32)&0x80808080 != 0 {
   break
  }
  p = p[8:]
 }

 // Check whether a byte is encoded in UTF-8 mode each time.
 ......
}

In order to further analyze the parallel optimization technique, the disassembly method is used to obtain the assembly code before and after the algorithm optimization. The assembly code before optimization is as follows:

The assembly code after optimization is as follows:

According to the analysis, before the optimization, one unit8 variable is used to store data for encoding validation. Corresponding to the assembly code, the MOVBU instruction is used to obtain one byte of data to the register R4, and the encoding of one-byte data is validated at a time. In the optimized code, two unit32 variables are used to store data for encoding validation. In the corresponding assembly code, the MOVWU instruction is used to obtain a piece of W (4 bytes) data to registers R3 and R4, respectively, and the encoding of 8-byte data is validated at a time. This optimization method increases the amount of data stored in the register in the assembly instruction by using more unit32 variable types for storing data in the Go language code, and implements parallel validation of more encoded data during the register comparison operation.

4. Optimization Result

Use the Go benchmark to test the algorithm performance before and after the optimization, and use the Go benchstat to compare the performance test results before and after the optimization. The following table lists the test results:

Note: -8 indicates the GOMAXPROCS value when the function is running, and ns/op indicates the average nanosecond duration for running the function each time.

According to the performance test result, after the UTF-8 encoding validation algorithm is optimized, the average time consumed for validating ASCII encoding is reduced, and the performance is improved by up to 49%.

5. Summary

The optimization case of the UTF-8 verification algorithm of the Go language analyzes the performance problems of the algorithm in a specific scenario, provides an optimization solution based on the idea of parallel programming, and verifies the optimization result. It is an algorithm optimization practice worth learning. The parallel programming idea in the case cannot only be used to optimize code validation of data, but also be applied to other scenarios such as encoding, decoding, compression, and storage of data.