关于go:LC-359-日志速率限制器-笔记

间接用哈希表记录时间戳很简略，大家都会，参考代码中的ShouldPrintMessageDefault，等同官网题解 2。然而奇怪的是在这题中，如果应用 Go 语言配合 LRU 定期删除 map 中键值对，参考ShouldPrintMessageLRU，相似官网题解 1，不过队列改成了 LRU 缓存。仿佛对优化并不显著。不论是惯例 benchmark 还是 leetcode 计时器都显示区别不大。

Go map 自身不会放大。

map 自身如果因为某种起因产生了增长，则再也不会放大，即便删除了局部甚至全副键值对。因为删除键值对只是将 map 中键值对置 0，但曾经调配的桶不会被回收。然而短期来看，删除键值对的确能够减缓 map 增长的速率。因为 map 中的键值对少了，就不容易产生扩容。而主动扩容会导致不必要的内存调配，以及扩容过程中长期桶会造成额定的性能抖动。不过在足够多的测试下，map 会因为哈希抵触必然扩容。

该题值类型为int，自身太小了，无奈应用指针优化。

因为即便 map 自身不会放大，指针类型的值在置 0 后也会被 GC 回收。

数据问题。

在单次 benchmark 中，10 次调用，优化后内存占用相比不优化是 2 倍，也就是负优化。100 次调用则为 40%，开始有优化了，1000 次则为 21%，优化很显著。然而在数据始终减少大略到 1 千万时，就是没有区别了。leetcode 的数据都偏小，而 benchamrk 的规范基准测试都很大，而且会通过测试次数取平均值，最初后果是相似的。

package leetcode

import ("fmt")

type Logger struct {logHist  map[string]int //log 历史，k:log 信息，v: 工夫戳
    lruQueue []struct {     //lru 缓存
        msg string
        ts  int
    }
    timeLimit int
    capacity  int // 设定 LRU 容量

    maxMapLen   int // 呈现过的最长 map
    maxSliceLen int // 呈现过的最长 slice 长度
}

// 调试用，察看字段呈现的最长长度
func (l *Logger) PrintMaxLen() {fmt.Println("map", l.maxMapLen)
    fmt.Println("slice", l.maxSliceLen)
}

// 调试用，记录字段呈现的最长长度
func (l *Logger) logMaxLen() {max := func(a, b int) int {
        if a > b {return a} else {return b}
    }
    l.maxMapLen = max(l.maxMapLen, len(l.logHist))
    l.maxSliceLen = max(l.maxSliceLen, len(l.lruQueue))
}

func Constructor359() Logger {
    const CAPACITY = 10
    const TIMELIMIT = 10
    return Logger{logHist: make(map[string]int, CAPACITY),
        lruQueue: make([]struct {
            msg string
            ts  int
        }, 0, CAPACITY),
        timeLimit: TIMELIMIT,
        capacity:  CAPACITY}
}

// 简略的实现，间接在 map 中记录时间戳，map 会有限增长
func (l *Logger) ShouldPrintMessageDefault(ts int, msg string) bool {l.logMaxLen()
    if lastTs, ok := l.logHist[msg]; ok && ts-lastTs < 10 {return false}
    l.logHist[msg] = ts
    return true
}

// 简略的 LRU 实现，然而 map 依然可能忽然增长
func (l *Logger) ShouldPrintMessageLRU(ts int, msg string) bool {
    // get
    l.logMaxLen()
    var existed bool
    var lastTs int
    if lastTs, existed = l.logHist[msg]; existed && ts-lastTs < 10 {return false}
    //clean
    if len(l.lruQueue) > l.capacity && ts-l.lruQueue[0].ts > l.timeLimit {delete(l.logHist, l.lruQueue[0].msg)
        l.lruQueue[0] = struct { // 防止内存泄露
            msg string
            ts  int
        }{}
        //l.lruQueue = l.lruQueue[1:] // 防止数组始终往后缩导致重新分配
        l.lruQueue = append(l.lruQueue[:0], l.lruQueue[1:]...)
    }
    //put
    newNode := struct {
        msg string
        ts  int
    }{msg, ts}
    if existed {l.logHist[msg] = ts
        if len(l.lruQueue) > 1 {
            var oldIndex int
            for oldIndex = 0; l.lruQueue[oldIndex].msg == msg; oldIndex++ { }
            l.lruQueue = append(l.lruQueue[:oldIndex], l.lruQueue[oldIndex+1:]...)
            l.lruQueue[len(l.lruQueue)-1] = newNode
        }
    } else {l.logHist[msg] = ts
        l.lruQueue = append(l.lruQueue, newNode)
    }
    return true
}

import (
    "fmt"
    "math/rand"
    "runtime"
    "src/leetcode"
    "testing"
)

var words = []string{
    "apple", "banana", "cherry", "date", "elderberry",
    "fig", "grape", "honeydew", "kiwi", "lemon",
    "mango", "orange", "peach", "quince", "raspberry",
    "strawberry", "tangerine", "uva", "watermelon", "xylophone",
    "yam", "zucchini", "avocado", "blueberry", "carrot",
    "dragonfruit", "eggplant", "flan", "grapefruit", "huckleberry",
    "icecream", "jackfruit", "kiwifruit", "leek", "melon",
    "nectarine", "olive", "pineapple", "quail", "radish",
    "starfruit", "tomato", "ugli", "vanilla", "walnut",
    "ximenia", "yizdu", "ziti", "golang", "python",
}

// 内存占用打印
func printAlloc() {
    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    fmt.Printf("%d MB\n", m.Alloc/1024/1024)
}

func BenchmarkDefault(b *testing.B) {b.ResetTimer()
    l := leetcode.Constructor359()
    for i := 0; i < b.N; i++ {msg := words[rand.Intn(50)] + words[rand.Intn(50)] + words[rand.Intn(50)]
        l.ShouldPrintMessageDefault(i, msg)
    }
    // 单次测试的调试信息
    //B := *(*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(*(**int)(unsafe.Pointer(&l)))) + 9))
    //fmt.Println("\nthe hmap B size", B)
    //printAlloc()
    //l.PrintMaxLen()}

func BenchmarkOptimized(b *testing.B) {b.ResetTimer()
    l := leetcode.Constructor359()
    for i := 0; i < b.N; i++ {msg := words[rand.Intn(50)] + words[rand.Intn(50)] + words[rand.Intn(50)]
        l.ShouldPrintMessageLRU(i, msg)
    }
    // 单次测试的调试信息
    //B := *(*uint8)(unsafe.Pointer(uintptr(unsafe.Pointer(*(**int)(unsafe.Pointer(&l)))) + 9))
    //fmt.Println("\nthe hmap B size", B)
    //printAlloc()
    //l.PrintMaxLen()}

benchmark 后果

# 规范测试
$ go test -bench=. -run=none -benchmem                                           
goos: linux
goarch: amd64
BenchmarkDefault-4          3917066           292.1 ns/op          27 B/op           1 allocs/op
BenchmarkOptimized-4        4292064           306.7 ns/op          27 B/op           1 allocs/op

#单次一万次测试
$ go test -bench=. -run=none -benchmem -benchtime=1x                             
goos: linux
goarch: amd64
BenchmarkDefault-4                1       2304085 ns/op     1211632 B/op       10289 allocs/op
BenchmarkOptimized-4              1       2903396 ns/op      297440 B/op       10221 allocs/op

剖析了下起因有几个。

benchmark