没有设置，是不是最多 256 * 256 个key

Xuzan9396 commented 2 years ago

楼主，我这边有个优化建议用 murmur3 hash算法，代替源码的 indexof ，速度快一半 murmur3.Sum32([]byte("xxxxx"))%uint32(256)
https://github.com/spaolacci/murmur3

FishGoddess commented 2 years ago

不是最多 256*256 个 key，segmentSize 是锁细化程度，256 表示有 256 个分片，mapSize 则是每个分片 map 的初始化大小，这个和 map 的性能有关，而 key 的数量则和你的内存有关。

FishGoddess commented 2 years ago

楼主，我这边有个优化建议用 murmur3 hash算法，代替源码的 indexof ，速度快一半 murmur3.Sum32([]byte("xxxxx"))%uint32(256) https://github.com/spaolacci/murmur3

有意思哈哈，可以提供下你的测试代码么，我看看

Xuzan9396 commented 2 years ago

func BenchmarkMurmur3(b *testing.B) {
    for i := 0; i < b.N; i++ {
        res2 := murmur3.Sum32([]byte("xxxxx"))%uint32(256)
        _ = res2
    }
}

func BenchmarkIndexOf(b *testing.B) {
    for i := 0; i < b.N; i++ {
        res := indexOf("xxxxx")&(256-1)
        _ = res
    }
}

func  indexOf(key string) int {
    index := 1469598103934665603
    keyBytes := []byte(key)

    for _, b := range keyBytes {
        index = (index << 5) - index + int(b&0xff)
        index *= 1099511628211
    }
    return index
}

FishGoddess commented 2 years ago

可以的，从性能上看确实 murmur3 的要比 index 快不少，这个我再调试下看看是啥导致的性能差距，不过我可能不会采用 murmur3 的算法，原因如下哈

我在 Cache 中使用 murmur3 算法之后进行了一次性能测试，就是 https://github.com/FishGoddess/cachego/blob/master/_examples/performance_test.go 中的例子，结果显示在高负载的情况下，两者并没有性能差别，这就说明散列算法并不是性能瓶颈了。

我写了一个小例子去测试两种算法的散列均匀程度，例子如下：


func findMinAndMax(m map[int]int) (int, int) {
min := math.MaxInt64
max := math.MinInt64

for _, count := range m {
    if count < min {
        min = count
    }

    if count > max {
        max = count
    }
}
return min, max
}

// go test -v -cover -run=^TestHashMethod$ func TestHashMethod(t *testing.T) { rand.Seed(time.Now().UnixNano())

murMap := make(map[int]int, 256)
for i := 0; i < 4096; i++ {
    index := int(murmur3.Sum32([]byte(strconv.Itoa(rand.Int()))) & 4095)
    murMap[index] = murMap[index] + 1
}

fmt.Println(len(murMap))
fmt.Println(findMinAndMax(murMap))
//fmt.Println(murMap)

indexMap := make(map[int]int, 256)
for i := 0; i < 4096; i++ {
    index := indexOf(strconv.Itoa(rand.Int())) & 4095
    indexMap[index] = indexMap[index] + 1
}

fmt.Println(len(indexMap))
fmt.Println(findMinAndMax(indexMap))
//fmt.Println(indexMap)

}



多次执行的结果可以发现，两者的散列均匀程度也没啥区别，可以认为两者散列出来的数据都挺均匀的，这一点上 murmur3 并不占优势。

综合来看，murmur3 带来的这点性能提升其实意义并不大，或者说没有打到痛点上，加入 murmur3 还得引入一个额外的包（我有一点代码洁癖哈哈），所以我不太考虑改成 murmur3 的方式。

PS：不过你倒是提醒了我，可以把 indexOf 方法抽出来变成全局公开的，默认就是使用现在的算法，如果用户想用自己的散列算法，重写 indexOf 方法即可，这样可以把选择权交给用户 : )

FishGoddess commented 2 years ago

可以的，从性能上看确实 murmur3 的要比 index 快不少，这个我再调试下看看是啥导致的性能差距，不过我可能不会采用 murmur3 的算法，原因如下哈

我在 Cache 中使用 murmur3 算法之后进行了一次性能测试，就是 https://github.com/FishGoddess/cachego/blob/master/_examples/performance_test.go 中的例子，结果显示在高负载的情况下，两者并没有性能差别，这就说明散列算法并不是性能瓶颈了。

我写了一个小例子去测试两种算法的散列均匀程度，例子如下：
func findMinAndMax(m map[int]int) (int, int) {
  min := math.MaxInt64
  max := math.MinInt64

  for _, count := range m {
      if count < min {
          min = count
      }

      if count > max {
          max = count
      }
  }
  return min, max
}

// go test -v -cover -run=^TestHashMethod$
func TestHashMethod(t *testing.T) {
  rand.Seed(time.Now().UnixNano())

  murMap := make(map[int]int, 256)
  for i := 0; i < 4096; i++ {
      index := int(murmur3.Sum32([]byte(strconv.Itoa(rand.Int()))) & 4095)
      murMap[index] = murMap[index] + 1
  }

  fmt.Println(len(murMap))
  fmt.Println(findMinAndMax(murMap))
  //fmt.Println(murMap)

  indexMap := make(map[int]int, 256)
  for i := 0; i < 4096; i++ {
      index := indexOf(strconv.Itoa(rand.Int())) & 4095
      indexMap[index] = indexMap[index] + 1
  }

  fmt.Println(len(indexMap))
  fmt.Println(findMinAndMax(indexMap))
  //fmt.Println(indexMap)
}
多次执行的结果可以发现，两者的散列均匀程度也没啥区别，可以认为两者散列出来的数据都挺均匀的，这一点上 murmur3 并不占优势。

综合来看，murmur3 带来的这点性能提升其实意义并不大，或者说没有打到痛点上，加入 murmur3 还得引入一个额外的包（我有一点代码洁癖哈哈），所以我不太考虑改成 murmur3 的方式。

PS：不过你倒是提醒了我，可以把 indexOf 方法抽出来变成全局公开的，默认就是使用现在的算法，如果用户想用自己的散列算法，重写 indexOf 方法即可，这样可以把选择权交给用户 : )

Index 函数目前已在 v0.3.7 版本中提取为公开变量，用户可以自定义哈希算法！

FishGoddess / cachego

没有设置，是不是最多 256 * 256 个key #4