Optimization of function call stack in go

Function call stack can be regarded as the necessary knowledge for bald programmers. This article does not cover it completely, but only explains why I encounter call stack. I only think about it according to my case. I will put the specific articles I have read at the end

Why do you think of the problem of function call stack? Look at the following two functions

// For example, the use of hash functions such as MD5 and SHA1 can be used directly
// xxx.Sum() is good. I began to think that since the hash function needs to be reused, I
// Just write a global variable (xxx.New()). Can I use it? It turns out that the reality is not
// Yes, if you don't know, you can look at the source code, XXX Sum () has done it internally
// Define variables, initialize, write and calculate; The New global object
// It also has the same effect as the above in specific use (the memory is not used much less,
// The Sum method of the structure will copy itself), and there will be concurrency problems
// You will notice by observing the source code, which is also described below
func MD5(data string) string {
	tmp := md5.Sum([]byte(data))
	return hex.EncodeToString(tmp[:])
}
// OK, it has been explained that TMP: = MD5 Sum([]byte(data))
// There is no optimization problem in this sentence
// The key to my thinking about optimization is the following sentences
// hex.EncodeToString(tmp[:])
// This function initializes the slice internally, calls the Encode method, and returns the string converted by the slice
func MD52(data string) string {
	tmp := md5.Sum([]byte(data))
	tmp2 := make([]byte, 32)
	hex.Encode(tmp2, tmp[:])
	return string(tmp2)
}
  • The above two functions are before and after optimization. I wonder if you can see where the optimization has been carried out?
  • Of course, this optimization is not big. After testing, it is about 20ns 😂, But from the bottom principle, it is optimized
  • Here are some of my explanations for the above notes
// Use global XXX Problems with new() object
// I was just going to use a global variable to do this
// It is found that there is a concurrency problem, and using global variables does not save space at all
// Maybe people didn't use it like this. I have to think so 😂
import (
	"crypto/md5"
	"encoding/hex"
)

var h = md5.New()

func main() {
	_ = MD5("hello,world!")
}

func MD5(data string) string {
	// Concurrency problem
	// After Write, if other goroutine s just call Reset
	// Just blow it up??
	// So XXX That's not how new () works
	// If you don't know, pay attention. If you know, when I didn't say it-_-
	h.Reset()
	h.Write([]byte(data))

	// Sum function will copy the structure, so it can't save memory
	tmp := h.Sum(nil)
	return hex.EncodeToString(tmp[:])
}

/*
// Sum function
func (d *digest) Sum(in []byte) []byte {
	// Make a copy of d so that caller can keep writing and summing.
	// The structure copy refers to here!!!
	d0 := *d
	hash := d0.checkSum()
	return append(in, hash[:]...)
}
*/

// =====================================================

// Why is it possible to optimize here???
// EncodeToString returns a string to the superior MD5 function
// MD5 returns a string to the superior
// I thought, is there another copy here?
// If you change what you do in EncodeToString to MD5 function
// Isn't there one less return?
// Just check the knowledge point of function call stack (fortunately, I've heard it before, ha ha 😄)

// EncodeToString returns the hexadecimal encoding of src.
func EncodeToString(src []byte) string {
	dst := make([]byte, EncodedLen(len(src)))
	Encode(dst, src)
	return string(dst)
	// The first time it returns, a copy occurs
}

func MD5(data string) string {
	h.Reset()
	h.Write([]byte(data))
	tmp := h.Sum(nil)
	return hex.EncodeToString(tmp[:])
	// On the second return, a copy occurs again
}
  • Then I check the articles related to the knowledge point of function call stack to verify whether it is consistent with what I expected, and there will be one more copy (depending on how the return value is implemented)
  • After searching, roughly explain the calling process, and only give a simple example
  • When a function call occurs in the main function, the main function is called caller and the called function is called callee
  • The function argument is in the caller stack frame, the return value is in the callee stack frame, and the return value is copied to the caller's local variable
  • The function argument enters the caller stack frame from right to left, and the return value enters the callee stack frame from left to right. When it is copied to the caller stack frame, it is from right to left
  • So simply draw a picture
  • I don't know if it's useful 😂, That is, one less function call can reduce one copy
  • Test:
package hashs_test

import (
	"crypto/md5"
	"crypto/sha1"
	"encoding/hex"
	"testing"
)

func MD5(data string) string {
	tmp := md5.Sum([]byte(data))
	return hex.EncodeToString(tmp[:])
}

func MD52(data string) string {
	tmp := md5.Sum([]byte(data))
	tmp2 := make([]byte, 32)
	hex.Encode(tmp2, tmp[:])
	return string(tmp2)
}

func SHA1(data string) string {
	tmp := sha1.Sum([]byte(data))
	return hex.EncodeToString(tmp[:])
}

func SHA12(data string) string {
	tmp := sha1.Sum([]byte(data))
	tmp2 := make([]byte, 40)
	hex.Encode(tmp2, tmp[:])
	return string(tmp2)
}

func BenchmarkMD5(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = MD5("hello,world")
	}
}

func BenchmarkMD52(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = MD52("hello,world")
	}
}

func BenchmarkSHA1(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = SHA1("hello,world")
	}
}

func BenchmarkSHA12(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = SHA12("hello,world")
	}
}
/*
// Several tests have been stable at about 182 ns/op
goos: windows
goarch: amd64
pkg: tiku/hashs
cpu: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
BenchmarkMD5
BenchmarkMD5-12    	 6508209	       183.0 ns/op
PASS

// Stable at 162-164
goos: windows
goarch: amd64
pkg: tiku/hashs
cpu: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
BenchmarkMD52
BenchmarkMD52-12    	 7254024	       163.3 ns/op
PASS

// 223 - 225
goos: windows
goarch: amd64
pkg: tiku/hashs
cpu: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
BenchmarkSHA1
BenchmarkSHA1-12    	 5296179	       224.6 ns/op
PASS

// 200
goos: windows
goarch: amd64
pkg: tiku/hashs
cpu: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
BenchmarkSHA12
BenchmarkSHA12-12    	 5926756	       200.9 ns/op
PASS
*/

In the real scene, we don't need to pay attention to these details (and we don't notice them), because the invention of functions is for us to use, and it doesn't need to be considered as a business. When we want to make a framework and need a lot of reuse, we are considering optimizing methods such as reducing the number of copies

reference resources:
Go function call ━ stack and Register Perspective
Call Stack

Keywords: Go

Added by dvt85 on Mon, 07 Mar 2022 22:44:42 +0200