Go leverages the one-time energy optimization of PProf

This article uses a topic from LeetCode to explain how to optimize our program through PProf. The topic is as follows: Longest Substring Without Repeating Characters

First give us our general solution

func lengthOfNonRepeatingSubStr(s string) int {
	lastOccurred := make(map[rune]int)
	start := 0
	maxLength := 0

	for i, ch := range []rune(s) {
		if lastI, ok := lastOccurred[ch]; ok && lastI >= start {
			start = lastI + 1
		}
		if i-start+1 > maxLength {
			maxLength = i - start + 1
		}
		lastOccurred[ch] = i
	} 

	return maxLength
}
Copy the code

The performance test shows 200 times and takes 6970790 ns/op

PProf analysis

go testGo tool pprof - HTTP =:8080./ Start pprof visual interface to analyze cpu.out fileCopy the code

By accessing http://localhost:8080/ui/ can check to the following page

It can be seen that the main consumption of time in two blocks, one is MapAccess, MapAssign, and one is decoderune. Decoderune mainly decodes UFT8 characters, converting strings to []rune(s) is unavoidable. So the main problem is to solve the map access and assignment problem, which is lastOccurred in the code

Optimization analysis

Operations such as space allocation will slow down operations because map needs to hash weights. The solution is to replace time with space and slice with map.

The modified code is as follows:

Func lengthOfNonRepeatingSubStr2 string (s) int {lastOccurred: make = (int [], 0 XFFFF) / / assign an initial valuefor i := range lastOccurred {
		lastOccurred[i] = -1
	}
	start := 0
	maxLength := 0

	for i, ch := range []rune(s) {
		iflastI := lastOccurred[ch]; lastI ! = -1 && lastI >= start { start = lastI + 1 }if i-start+1 > maxLength {
			maxLength = i - start + 1
		}
		lastOccurred[ch] = i
	}

	return maxLength
}
Copy the code

The performance test shows that 500 takes 2578859 ns/op. Compared to the previous 6970790 ns/ OP, this is a great optimization

The follow-up to optimize

Pprof shows that some time is spent with a makeslice in addition to a decoderune. This is because each call to a function is made with a makeslicke, so slice can be declared outside the function. See how the pprof image makeslice is removed.

PProf uses the performance profile of Golang killer that can be viewed

This article is also published in the wechat public number [Alley Information], welcome to scan the code to pay attention to!