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

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

剖析了下起因有几个。

1. Go map 自身不会放大。

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

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

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

3. 数据问题。

   在单次 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
}

benchmark

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