用动态数组模拟链表做 GC 优化这个主意怎么样

[Nazz]

一个 LRU 缓存, 小堆维护过期时间, 链表维护最近访问数据, Map 提供随机访问能力

type (
	pointer uint32

	bucket struct {
		Map  *Map
		Heap *Heap
		List *List
	}

	Map map[string]pointer

	Heap []pointer

	List []Element

	Element struct {
		ptr, prev, next pointer
		Key             string
		Val             any
	}
)

[flynnlemon]

并发问题没有考虑吗？

[Nazz]

@flynnlemon 这里只讨论 GC

[flynnlemon]

@Nazz 上下文太少，很难直接理解你这个结构去做 GC 的使用场景，方便多说一点使用场景吗

[Nazz]

@flynnlemon bucket 是缓存库的基本存储结构, 源码见 https://github.com/lxzan/memorycache/tree/swiss .
现在的代码里面直接用指针式链表维护 LRU 缓存了, 实测数组链表对于 GC 优化帮助不大. 虽然数据表面都是值类型, 但实际上 string 底层是有指针的, any 可能也会被扫描.

[lysShub]

可以避免指针，prev 、next 是数组索引

[Nazz]

@lysShub 不过 string 底层还是有指针，这个解决起来很麻烦