I was able to get it down to a single allocation for the log string, but with your current API of using a map[string]interface{}
, I can’t think of an efficient allocation-free way to “sort” the map. Every iteration of a map can come out in a different order, so I used some nested, repetitive loops to keep track of the last key that was logged and keep skipping already-logged keys. I think the algorithm is n^2, so I do not recommend it.
If you can change your Field
implementation to something like this:
type Field []struct{
Key string
Value interface{}
}
Then, because it’s a slice, it can be sorted inside of log
without any additional allocations. This would change your call to log
from this:
log("hello", Field{"str": "val", "int": 1, "flo": 1234567890.01234567, "bol": true})
to this:
log("hello", Field{{"str", "val"}, {"int", 1}, {"flo", 1234567890.01234567}, {"bol", true}})
Changed API, faster
// You can edit this code!
// Click here and start typing.
package main
import (
"sort"
"strconv"
"strings"
"unsafe"
)
const useUnsafe = false
type Field []struct {
Key string
Value interface{}
}
func _() interface {
sort.Interface
} {
return (*Field)(nil)
}
func (fs *Field) Less(i, j int) bool {
return strings.Compare((*fs)[i].Key, (*fs)[j].Key) < 0
}
func (fs *Field) Swap(i, j int) {
(*fs)[i], (*fs)[j] = (*fs)[j], (*fs)[i]
}
func (fs *Field) Len() int { return len(*fs) }
func (fs *Field) estimateStringLength() (estimate int) {
for _, kvp := range *fs {
// include space for leading ," and trailing "
estimate += len(`,""`)
estimate += len(kvp.Key)
switch val := kvp.Value.(type) {
case string:
estimate += len(val) + len(`""`)
case int:
estimate += 20 // length of math.MinInt64
case float64:
// I don't actually know how to find out the
// maximum number of characters are needed to
// represent a float value. If you know that,
// use that here instead.
estimate += 24
case bool:
estimate += len("false")
}
}
return
}
var unsafeFieldsSortTypePointer = func() unsafe.Pointer {
var si sort.Interface = (*Field)(nil)
return (*(*[2]unsafe.Pointer)(unsafe.Pointer(&si)))[0]
}()
func log(line string, fields Field) string {
sb := make([]byte, len(line), len(line)+fields.estimateStringLength())
sb = append(sb, line...)
if useUnsafe {
// sort.Sort should not hold a reference, so we're
// going to build a sort.Interface manually that won't
// escape.
//
// This might break if Go ever starts relocating its
// allocations. In that case, just get rid of this
// if useUnsafe block.
var si sort.Interface
siPtrs := (*struct {
p unsafe.Pointer
u uintptr
})(unsafe.Pointer(&si))
siPtrs.p = unsafeFieldsSortTypePointer
siPtrs.u = uintptr(unsafe.Pointer(&fields))
sort.Sort(si)
} else {
sort.Sort(&fields)
}
for _, kvp := range fields {
sb = append(sb, `,"`...)
// Note that you're not escaping any quotes
// that might be inside of the field key:
sb = append(sb, kvp.Key...)
sb = append(sb, `":`...)
switch x := kvp.Value.(type) {
case string:
sb = append(sb, '"')
// Note that you're not escaping any quotes
// that might be inside of the field value:
sb = append(sb, x...)
sb = append(sb, '"')
case int:
sb = strconv.AppendInt(sb, int64(x), 10)
case float64:
sb = strconv.AppendFloat(sb, x, 'f', -1, 64)
case bool:
sb = strconv.AppendBool(sb, x)
}
}
if useUnsafe {
return *((*string)(unsafe.Pointer(&sb)))
}
return string(sb)
}
Output:
Running tool: C:\Program Files\Go\bin\go.exe test -benchmem -run=^$ -bench ^Benchmark_log$ forum.golangbridge.org/improving-performance-of-a-function_30627 -v -cover
goos: windows
goarch: amd64
pkg: forum.golangbridge.org/improving-performance-of-a-function_30627
cpu: Intel(R) Core(TM) i9-9900 CPU @ 3.10GHz
Benchmark_log
Benchmark_log-16
3858253 311.4 ns/op 96 B/op 1 allocs/op
PASS
coverage: 94.6% of statements
ok forum.golangbridge.org/improving-performance-of-a-function_30627 1.718s
Same API, 3x slower
// You can edit this code!
// Click here and start typing.
package main
import (
"strconv"
"strings"
"unsafe"
)
const useUnsafe = true
type Field map[string]interface{}
func (fs Field) estimateStringLength() (estimate int) {
for k, v := range fs {
// include space for leading ," and trailing "
estimate += len(`,""`)
estimate += len(k)
switch val := v.(type) {
case string:
estimate += len(val) + len(`""`)
case int:
estimate += 20 // length of math.MinInt64
case float64:
// I don't actually know how to find out the
// maximum number of characters are needed to
// represent a float value. If you know that,
// use that here instead.
estimate += 24
case bool:
estimate += len("false")
}
}
return
}
func log(line string, fields Field) string {
sb := make([]byte, 0, len(line)+fields.estimateStringLength())
sb = append(sb, line...)
lastKey := ""
for i := 0; i < len(fields); i++ {
nextKey, nextVal := "", interface{}(nil)
for k, v := range fields {
if i > 0 && strings.Compare(k, lastKey) <= 0 {
continue
}
nextKey, nextVal = k, v
break
}
for k, v := range fields {
if i > 0 && strings.Compare(k, lastKey) <= 0 {
continue
}
if strings.Compare(k, nextKey) < 0 {
nextKey, nextVal = k, v
}
}
lastKey = nextKey
sb = append(sb, `,"`...)
// Note that you're not escaping any quotes
// that might be inside of the field key:
sb = append(sb, nextKey...)
sb = append(sb, `":`...)
switch x := nextVal.(type) {
case string:
sb = append(sb, '"')
// Note that you're not escaping any quotes
// that might be inside of the field value:
sb = append(sb, x...)
sb = append(sb, '"')
case int:
sb = strconv.AppendInt(sb, int64(x), 10)
case float64:
sb = strconv.AppendFloat(sb, x, 'f', -1, 64)
case bool:
sb = strconv.AppendBool(sb, x)
}
}
if useUnsafe {
return *((*string)(unsafe.Pointer(&sb)))
}
return string(sb)
}
Output:
Running tool: C:\Program Files\Go\bin\go.exe test -benchmem -run=^$ -bench ^Benchmark_log$ forum.golangbridge.org/improving-performance-of-a-function_30627 -v -cover
goos: windows
goarch: amd64
pkg: forum.golangbridge.org/improving-performance-of-a-function_30627
cpu: Intel(R) Core(TM) i9-9900 CPU @ 3.10GHz
Benchmark_log
Benchmark_log-16
1357574 915.1 ns/op 96 B/op 1 allocs/op
PASS
coverage: 97.4% of statements
ok forum.golangbridge.org/improving-performance-of-a-function_30627 2.314s