乐趣区

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

作者：

jiezi

在

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

剖析了下起因有几个。

  1. Go map自身不会放大。

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

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

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

  1. 数据问题。

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

更多文章