游戏开发中字典数据的优化方案 golang版本

        大部分的游戏开发过程中，会出现大量的游戏对象，大量的游戏对象产生大量的对象属性，不可避免地会使用到map也就是hash字典来存储数据。

        那么为什么需要用字典存储呢？我开发过程中经常遇到的是这样的需求，游戏单位有自己的唯一标识符，任何对象只能通过这个标识符来唯一定位。这种情况下，数组下标就是一个比较尴尬的东西，如果用数组下标作为标识符，那么数据只能自增的情况下数组会无限扩展，显然不可行。如果将数组下标作为附加的标识，那就代表着需要维护两个能定位到对象的参数，逻辑上埋下了一些隐患。所以最后大部分情况下都选择了hash字典来存储。看起来非常美好。随用随存。直接key访问和移除。大部分时候到这里就结束了。

        but！随着开发的持续以及字典的大量使用和逻辑参与的情况下。可怕的情况出现了。map的遍历大量出现在逻辑中。我自己的游戏在开发后期通过profiler查看cpu耗时的时候发现。有80%以上的耗时出现在map的遍历上。是单纯的map遍历。而不包括获取对象之后的操作。这就非常可怕了。于是做了许多测试和尝试。发现slice的遍历在数据量非常大的情况下。依然有非常好的体验。于是有了一些大胆的想法。能不能构造一个既包含map特性同时又有slice性能的结构体呢。

        首先看一下这段测试代码。

func SliceAndMapTest() {
	mp := map[int]int{}
	testSize := 9999999
	slice := make([]int, testSize)
	now := time.Now()
	fmt.Printf("开始测试Map插入\n")
	for i := 0; i < testSize; i++ {
		mp[i] = i
	}
	fmt.Printf("数据量 %v Map插入耗时 %v\n", testSize, time.Since(now))
	now = time.Now()
	fmt.Printf("开始测试Slice插入\n")
	for i := 0; i < testSize; i++ {
		slice[i] = i
	}
	fmt.Printf("数据量 %v Slice插入耗时 %v\n", testSize, time.Since(now))
	now = time.Now()
	fmt.Printf("开始测试Map range遍历\n")
	for i, j := range mp { //无序的
		_, _ = i, j
	}
	fmt.Printf("数据量 %v Map range遍历耗时 %v\n", testSize, time.Since(now))
	now = time.Now()
	fmt.Printf("开始测试Map index遍历\n")
	for i := 0; i < testSize; i++ {
		_, _ = mp[i]
	}
	fmt.Printf("数据量 %v Map index遍历耗时 %v\n", testSize, time.Since(now))
	now = time.Now()
	fmt.Printf("开始测试Slice range遍历\n")
	for i, j := range slice {
		_, _ = i, j
	}
	fmt.Printf("数据量 %v Slice range遍历耗时 %v\n", testSize, time.Since(now))
	now = time.Now()
	fmt.Printf("开始测试Slice index遍历\n")
	for i := 0; i < testSize; i++ {
		_ = slice[i]
	}
	fmt.Printf("数据量 %v Slice index遍历耗时 %v\n", testSize, time.Since(now))
}

 这是执行后的输出。

开始测试Map插入
数据量 9999999 Map插入耗时 1.8680628s
开始测试Slice插入
数据量 9999999 Slice插入耗时 22.478ms
开始测试Map range遍历
数据量 9999999 Map range遍历耗时 129.8605ms
开始测试Map index遍历
数据量 9999999 Map index遍历耗时 692.2344ms
开始测试Slice range遍历
数据量 9999999 Slice range遍历耗时 2.9917ms
开始测试Slice index遍历
数据量 9999999 Slice index遍历耗时 2.9932ms

        可以看到slice的性能暴打map。那么如何构造一个既拥有slice特性又有map的无限扩展性的结构呢。我思考了很久。最后想到将两个key，也就是slice的index以及map的key进行结合。再生成唯一key去进行操作的方式。 看看具体的实现。

package funs

//用slice代替map做快速访问的结构

type SliceMapValidInterface interface {
	Cache()        //回收时的处理 只需要处理外部的回收逻辑 非必要接口 可以直接为空函数
	IsValid() bool //判定数据是否依然有效 非必要接口 可以直接返回true
}

type SliceMap struct {
	Index      int64   //当前的可用index
	CacheIndex []int64 //当前的回收index列表
	Vs         []SliceMapValidInterface
	Max        int64 //当前的最大index上限
	BaseAppend int64 //数据位不够的时候的自动扩展值
}

func getSliceIndex(combineIndex int64) int64 {
	return combineIndex << 32 >> 32 //过滤掉左边32位的数据 剩下的就是真实的数组index
}

//其实使用过程中大部分时候combineIndex本身作为外部唯一key就够了 mapIndex只是过度
func GetMapIndex(combineIndex int64) int64 {
	return combineIndex >> 32
}

func getCombineIndex(sliceIndex int64, mapIndex int64) int64 { //将数组index和字典index合并为一个唯一index
	return mapIndex<<32 ^ (sliceIndex << 32 >> 32)
}

func GetNewSliceMap(baseMax int64, baseAppend int64) SliceMap {
	if baseAppend <= 0 {
		baseAppend = 1
	}
	return SliceMap{
		Index:      1, //0位数据舍弃 有些讨厌的逻辑要判定0
		CacheIndex: []int64{},
		Vs:         make([]SliceMapValidInterface, baseMax),
		Max:        baseMax,
		BaseAppend: baseAppend,
	}
}

func (this *SliceMap) Clear(cache bool) {
	if cache {
		for i := int64(0); i < this.Index; i++ {
			buf := this.Vs[i]
			if buf != nil {
				buf.Cache()
				this.Vs[i] = nil
			}
		}
	} else {
		for i := int64(0); i < this.Index; i++ {
			buf := this.Vs[i]
			if buf != nil {
				this.Vs[i] = nil
			}
		}
	}
	this.Index = 1 //重置index和回收列表
	if len(this.CacheIndex) > 0 {
		this.CacheIndex = []int64{}
	}
}

func (this *SliceMap) Range(f func(SliceMapValidInterface) bool) {
	for i := int64(0); i < this.Index; i++ {
		in := this.Vs[i]
		if in != nil && in.IsValid() {
			if !f(in) {
				break
			}
		}
	}
}

//单纯移除Index不调用回收函数 游戏开发中移除通常是做一个标记位 等逻辑全部执行完毕在帧末再遍历移除 所以提供了这样临时移除的函数
func (this *SliceMap) JustRemove(index int64) {
	index = getSliceIndex(index)
	if this.Vs[index] != nil {
		this.Vs[index] = nil
		this.CacheIndex = append(this.CacheIndex, index)
	}
}

//移除且调用回收函数
func (this *SliceMap) Remove(index int64) bool {
	index = getSliceIndex(index)
	if this.Vs[index] != nil {
		this.Vs[index].Cache()
		this.Vs[index] = nil
		this.CacheIndex = append(this.CacheIndex, index)
		return true
	}
	return false
}

//获取指定combineIndex的对象
func (this *SliceMap) Get(combineIndex int64) (SliceMapValidInterface, bool) {
	index := getSliceIndex(combineIndex)
	if index >= 0 {
		v := this.Vs[index]
		if v != nil && v.IsValid() {
			return v, true
		}
	}
	return nil, false
}

//存入对象并返回唯一的combineIndex作为后续记录的关键
func (this *SliceMap) Save(in SliceMapValidInterface, mapIndex int64) int64 {
	index := int64(0)
	if in != nil {
		if len(this.CacheIndex) > 0 {
			index = this.CacheIndex[0]
			this.Vs[index] = in
			this.CacheIndex = this.CacheIndex[1:]
		} else {
			for {
				if this.Index >= this.Max {
					if this.BaseAppend <= 0 {
						this.BaseAppend = 1
					}
					this.Vs = append(this.Vs, make([]SliceMapValidInterface, this.BaseAppend)...)
					this.Max += this.BaseAppend
				} else {
					break
				}
			}
			if this.Index < this.Max {
				index = this.Index
				this.Vs[index] = in
				this.Index++
			}
		}
		return getCombineIndex(index, mapIndex)
	}
	return -1
}

        这样的话。数据又有无限自增的key（mapIndex）。也有数组内部访问的key（sliceIndex）。也有合并后全局唯一的key（combineIndex）。

        那么同样做一下新结构的测试。

func SliceAndSliceMapTest() {
	testSize := 9999999
	slice := make([]int, testSize)
	sliceMap := GetNewSliceMap(int64(testSize), 1)
	now := time.Now()
	fmt.Printf("开始测试Slice插入\n")
	for i := 0; i < testSize; i++ {
		slice[i] = i
	}
	fmt.Printf("数据量 %v Slice插入耗时 %v\n", testSize, time.Since(now))
	now = time.Now()
	fmt.Printf("开始测试SliceMap插入\n")
	for i := 0; i < testSize; i++ {
		buf := &SliceMapValidSc{}
		buf.CombineIndex = sliceMap.Save(buf, int64(i))
	}
	fmt.Printf("数据量 %v SliceMap 插入耗时 %v\n", testSize, time.Since(now))
	now = time.Now()
	fmt.Printf("开始测试Slice range遍历\n")
	for i, j := range slice {
		_, _ = i, j
	}
	fmt.Printf("数据量 %v Slice range遍历耗时 %v\n", testSize, time.Since(now))
	now = time.Now()
	fmt.Printf("开始测试Slice index遍历\n")
	for i := 0; i < testSize; i++ {
		_ = slice[i]
	}
	fmt.Printf("数据量 %v Slice index遍历耗时 %v\n", testSize, time.Since(now))
	now = time.Now()
	fmt.Printf("开始测试 SliceMap 遍历\n")
	sliceMap.Range(func(in SliceMapValidInterface) bool {
		_ = (in.(*SliceMapValidSc)).CombineIndex
		return true
	})
	fmt.Printf("数据量 %v SliceMap 遍历耗时 %v\n", testSize, time.Since(now))
}

输出如下。 

开始测试Slice插入
数据量 9999999 Slice插入耗时 7.9781ms
开始测试SliceMap插入
数据量 9999999 SliceMap 插入耗时 265.6321ms
开始测试Slice range遍历
数据量 9999999 Slice range遍历耗时 2.9924ms
开始测试Slice index遍历
数据量 9999999 Slice index遍历耗时 4.9866ms
开始测试 SliceMap 遍历
数据量 9999999 SliceMap 遍历耗时 39.8935ms

可以看到虽然不如原生slice那样的快。毕竟内部做了很多判定和操作。 但是无论如何是比map的性能优化了非常多。后续也许还有优化点。但是我们的项目在做完这个优化之后瓶颈就不出现在这里了。就没做更多的尝试。