SwissMap正在替换主流语言中哈希表的原有实现

• Boost 没有特定公司维护 7k https://github.com/boostorg/boost

• Abseil 是谷歌的 14k https://github.com/abseil/abseil-cpp

• Folly 是Facebook 的 28k https://github.com/facebook/folly

基本都是参考rust和C++的Boost/Abseil/Folly 进行移植[破涕为笑]

https://github.com/golang/go/issues/54766

https://abseil.io/about/design/swisstables

https://www.cnblogs.com/apocelipes/p/17562468.html

https://groups.google.com/g/golang-codereviews/c/vMuGzXnqdh8

https://go.dev/blog/swisstable

https://blog.csdn.net/weixin_46825193/article/details/145941933

我是用gocircit发现了这个问题

疑似发现的新问题: ./src/cmd/link/internal/ld/deadcode.go:563:3: dupBranchBody: both branches in if statement have same body

func (d *deadcodePass) decodetypeMethods(ldr *loader.Loader, arch *sys.Arch, symIdx loader.Sym, relocs *loader.Relocs) []methodsig {
	p := ldr.Data(symIdx)
	if !decodetypeHasUncommon(arch, p) {
		panic(fmt.Sprintf("no methods on %q", ldr.SymName(symIdx)))
	}
	off := commonsize(arch) // reflect.rtype
	switch decodetypeKind(arch, p) {
	case abi.Struct: // reflect.structType
		off += 4 * arch.PtrSize
	case abi.Pointer: // reflect.ptrType
		off += arch.PtrSize
	case abi.Func: // reflect.funcType
		off += arch.PtrSize // 4 bytes, pointer aligned
	case abi.Slice: // reflect.sliceType
		off += arch.PtrSize
	case abi.Array: // reflect.arrayType
		off += 3 * arch.PtrSize
	case abi.Chan: // reflect.chanType
		off += 2 * arch.PtrSize
	case abi.Map:
		if buildcfg.Experiment.SwissMap {
			off += 4*arch.PtrSize + 8 // internal/abi.SwissMapType
		} else {
			off += 4*arch.PtrSize + 8 // internal/abi.OldMapType
		}
	case abi.Interface: // reflect.interfaceType
		off += 3 * arch.PtrSize
	default:
		// just Sizeof(rtype)
	}

	mcount := int(decodeInuxi(arch, p[off+4:], 2))
	moff := int(decodeInuxi(arch, p[off+4+2+2:], 4))
	off += moff                // offset to array of reflect.method values
	const sizeofMethod = 4 * 4 // sizeof reflect.method in program
	return d.decodeMethodSig(ldr, arch, symIdx, relocs, off, sizeofMethod, mcount)
}

这段 Go 代码是一个解码类型方法的函数，主要用于解析反射相关的类型信息，特别是类型的函数方法。下面是对代码的逐步解释以及可能存在的 bug 讨论。

代码解释

1. 函数定义：

   func (d *deadcodePass) decodetypeMethods(ldr *loader.Loader, arch *sys.Arch, symIdx loader.Sym, relocs *loader.Relocs) []methodsig

   • d *deadcodePass：接收者，表示该方法属于 deadcodePass 类型。
   • ldr *loader.Loader：加载器，用于加载符号和类型信息。
   • arch *sys.Arch：系统架构信息。
   • symIdx loader.Sym：符号索引。
   • relocs *loader.Relocs：重定位信息。

2. 获取符号数据：

   p := ldr.Data(symIdx)

3. 检查是否有不常见的方法：

   if !decodetypeHasUncommon(arch, p) {
       panic(fmt.Sprintf("no methods on %q", ldr.SymName(symIdx)))
   }

4. 计算偏移量：

   off := commonsize(arch) // reflect.rtype

5. 根据类型种类调整偏移量：

   switch decodetypeKind(arch, p) {
   // 处理不同的类型并调整偏移量
   }

6. 解码方法计数和偏移：

   mcount := int(decodeInuxi(arch, p[off+4:], 2))
   moff := int(decodeInuxi(arch, p[off+4+2+2:], 4))

7. 返回方法签名：

   return d.decodeMethodSig(ldr, arch, symIdx, relocs, off, sizeofMethod, mcount)

可能的 Bugs 和改进点

1. 偏移量计算：

   • 在不同类型的情况下，偏移量的计算依赖于架构和类型的大小。如果任何情况下计算出的偏移量不正确，可能会导致访问越界或读取错误的数据。

2. panic 处理：

   • 直接使用 panic 来处理没有方法的情况可能会导致程序崩溃。可以考虑使用错误返回值而不是 panic，这样可以更优雅地处理错误。

3. 类型解码的完整性：

   • 该段代码假设了所有类型都被正确解码。如果存在未考虑的类型（在 default 中），可能会导致后续代码逻辑不正确。

4. magic numbers：

   • 代码中使用了一些魔法数字（例如 4*arch.PtrSize + 8），建议将其替换为常量，增加可读性。

总结

这段代码的主要功能是解码与反射相关的类型方法，但在偏移量计算和错误处理上可能存在潜在问题。仔细检查偏移量计算和类型种类的处理是确保代码正确性的关键。

进而了解了下什么是 SwissMapType

可以看下鸟窝大佬的 替换标准库的map实现，SwissTable更快？

最早是谷歌在C++里搞的, Rust目前也跟进了

SwissTable是谷歌开源的一个哈希表(hash table、map)的实现，在cppcon 2017大会上公布出来，Google内部大量采用它替换std:unordered_map,精巧的设计使的它非常的高效，它也被port到其他语言，比如Rust语言中有一个库hashbrown就是根据SwissTable实现的，并且在Rust 1.36中开始替换标准库的HashMap。

Go正在实验..

key比较少时,优势不明显

Swisstable：C++中比std::unordered_map更快的hash表

GigaCache 是一个基于 swissmap 的高性能 Go 缓存库，为 GB 级序列化数据而设计，支持设置过期时间与淘汰机制，相比 stdmap 有更快的速度，更高的内存效率，和更小的延迟。

高性能缓存 GigaCache

SwissMap(Go外部哈希表)

推荐开源项目：SwissMap —— 高性能的Golang哈希表

https://github.com/dolthub/swiss

SwissMap是什么？谁提出来的？和传统的map比有何区别？占几个字节

SwissMap是由Google工程师提出的一种新的哈希表实现方案，旨在改进Go语言中现有的map数据结构。这个提案是在2023年提出的，目前还处于讨论和实验阶段，尚未正式集成到Go语言中。

主要特点和与传统map的区别：

1. 内存效率：SwissMap设计为更节省内存。它通过使用更紧凑的数据结构来减少内存占用。

2. 性能：在某些情况下，SwissMap可能比传统map具有更好的性能，特别是在处理大量小对象时。

3. 实现方式：SwissMap使用了一种称为”Swiss table”的技术，这是一种改进的开放寻址哈希表算法。

4. 碰撞处理：SwissMap采用了新的方法来处理哈希冲突，可能导致更少的缓存未命中。

5. 可扩展性：设计上考虑了更好的并发性能，虽然目前的提案版本还不是并发安全的。

关于SwissMap占用的字节数，这个问题没有一个固定的答案，因为：

1. SwissMap的大小会根据存储的元素数量动态变化。
2. 具体的实现细节可能会影响其内存占用。
3. 目前SwissMap还在提案阶段，最终实现可能会有变化。

根据提案，SwissMap的设计目标之一是减少内存占用。在某些情况下，它可能比传统map占用更少的内存，特别是对于存储大量小对象的情况。但是，确切的字节数会根据具体使用情况而变化。

需要注意的是，SwissMap目前仍处于实验阶段，还没有被正式纳入Go语言。它的具体实现细节和性能特征可能会在未来发生变化。如果你对最新的发展感兴趣，建议关注Go语言的官方GitHub仓库和相关讨论。

---

https://go-review.googlesource.com/c/go/+/580779

好吧, 看这个提交的注释,是故意的…

又是zhangyunhao116 这哥们提的issue
https://github.com/golang/go/issues/54766

https://github.com/abseil/abseil-cpp

Abseil 是一个开源的 C++ 库，旨在扩展 C++ 标准库的功能。它由谷歌内部的 C++ 代码库提取而来，经过广泛测试，并已在生产环境中使用。Abseil 提供了标准库中缺失的部分功能，以及一些用于特殊需求的替代方案。主要组件包括基础库、算法库、内存管理、调试工具等。用户可以使用 Bazel 或 CMake 来构建 Abseil。建议用户保持使用最新版本，同时也提供长期支持版本。Abseil 代码库遵循 Apache 许可证。

感觉和boost差不多啊,都是领先的,先进的

Abseil 和 Boost 都是 C++ 的库，它们提供了许多扩展标准库的功能和工具，但它们的设计目标和使用场景有所不同。

Abseil

• 定义：Abseil 是由 Google 开发的一个开源 C++ 库，旨在提供一些常用的功能，这些功能在 C++ 标准库中可能并不存在或不够完善。
• 主要特点：
  • 提供了许多通用的工具和数据结构，如字符串处理、时间管理、并发支持等。
  • 设计上与 C++ 标准库兼容，旨在无缝集成。
  • 关注于高效的性能和简化的 API。
• 适用场景：主要用于 Google 内部和其他需要高性能和高可用性的应用程序。

Boost

• 定义：Boost 是一个广泛的开源 C++ 库集合，包含了 C++ 标准库中许多扩展和补充的功能。
• 主要特点：
  • 包含超过 160 个库，功能覆盖广泛，如智能指针、正则表达式、线程、图形等。
  • 许多 Boost 库的功能在后来的 C++ 标准中被采纳和标准化（如 shared_ptr）。
  • 提供了高度可移植的代码，适用于各种平台和编译器。
• 适用场景：适合所有 C++ 开发者，尤其是在寻找标准库之外的功能时。

主要区别

1. 设计目标：

   • Abseil 主要是为 Google 的开发需求而设计，关注于性能和易用性。
   • Boost 是一个社区驱动的项目，旨在提供广泛的功能和工具。

2. 功能范围：

   • Abseil 提供的功能相对较少，主要集中在常用的实用工具。
   • Boost 提供了丰富的库，几乎覆盖了所有 C++ 开发的需求。

3. 与标准库的关系：

   • Abseil 的目标是与 C++ 标准库兼容，提供标准库所缺少的功能。
   • Boost 早期是为了补充标准库，后来的许多库被纳入 C++ 标准库中。

总结

• Abseil 和 Boost 都是 C++ 开发中重要的库，前者更注重于 Google 的需求和高性能场景，后者则是一个广泛的社区项目，包含丰富多样的功能。两者都在扩展 C++ 标准库方面发挥了重要作用。

还有什么类似的吗？facebook是不是也有一个库

是的，Facebook 也有一个广泛使用的 C++ 库，叫做 Folley。以下是关于 Folley 及其他一些类似库的介绍：

Folly

• 定义：Folly 是 Facebook 开发的一个 C++ 库，旨在提供高性能的实用工具和数据结构。
• 主要特点：
  • 包含许多高效的算法、数据结构和工具，特别关注于并发和异步编程。
  • 提供了现代 C++ 特性，优化了性能。
  • 设计上考虑了与 Facebook 内部系统的兼容性。

其他类似库

1. SPDK (Storage Performance Development Kit)：

   • 主要用于高性能存储应用，特别是针对 NVMe 存储设备的开发。
   • 提供了用户态驱动程序和性能优化的库。

2. gRPC：

   • 虽然主要是一个 RPC 框架，但其 C++ 实现提供了高效的网络通信库。
   • 支持多种语言，方便跨平台和跨语言服务的互操作。

3. TBB (Threading Building Blocks)：

   • Intel 开发的一个 C++ 库，专注于并发和多线程编程。
   • 提供了高层次的并发算法和数据结构，简化多线程编程的复杂性。

4. OpenCV：

   • 专注于计算机视觉和图像处理的库，提供了丰富的功能。
   • 适用于图像处理、机器学习等领域。

总结

除了 Abseil 和 Boost，Facebook 的 Folly 是一个重要的 C++ 库，提供高性能的工具和数据结构。还有许多其他库可供选择，满足不同的需求和场景。选择合适的库可以根据项目的具体需求、性能要求和社区支持来决定。

• Boost 没有特定公司维护 7k https://github.com/boostorg/boost

• Abseil 是谷歌的 14k https://github.com/abseil/abseil-cpp

• Folly 是Facebook 的 28k https://github.com/facebook/folly

---

https://tonybai.com/2024/11/14/go-map-use-swiss-table/

文章目录

1. 代码解释
2. 可能的 Bugs 和改进点
3. 总结
4. SwissMap是什么？谁提出来的？和传统的map比有何区别？占几个字节

1. Abseil
2. Boost
3. 主要区别
4. 总结

还有什么类似的吗？facebook是不是也有一个库

1. Folly
2. 其他类似库
3. 总结

原文链接: https://dashen.tech/2018/08/30/SwissMap正在替换主流语言中哈希表的原有实现/

版权声明: 转载请注明出处.