Golang学习之结构体和内存对齐、map设计思路

这篇具有很好参考价值的文章主要介绍了Golang学习之结构体和内存对齐、map设计思路。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

结构体和内存对齐

  • cpu要想从内存读取数据,需要通过地址总线,把地址传输给内存,内存准备好数据,输出到数据总线,交给CPU。
  • 如果地址总线只有8根,那这个地址就只有8位,可以表示256个地址,因为表示不了更多的地址就用不了更大的内存。
  • 所以256就是8根地址总线最大的寻址空间,要使用更大的内存,就要有更宽的地址总线。
  • Golang学习之结构体和内存对齐、map设计思路,学习
  • 每次操作一字节太慢,那就加宽数据总线。
  • 要每次操作4字节,就要至少32位数据总线。8字节64位。每次操作的字节数就是机器字长。
  • 逻辑上的内存:可以访问任意地址并将其输出到总线。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 实际上为了实现更高的访问效率,典型的内存布局。
  • 一个内存条的一面是一个Rabk,一个Chip包括8个Banks,到Banks就可以通过选择行和列来定位一个地址。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 非逻辑上连续的存在,但能共用一个地址,各自选择同一个位置的一个字节,再组合起来,作为我们逻辑上认为的连续8个字节。
  • 通过这样的并行操作,提高了内存访问效率。
  • 但这种方式地址必须是8的倍数,
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 不能在一次操作中被同一个地址选中,这样的地址是不能用的。硬件不支持。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 之所以有些cpu能支持访问任意地址,是因为其多做了许多处理。
  • 例如,想从1开始读8字节的数据,CPU会分两次读,第一次从0到7,但只取后7字节,第二次从8到15,但只取1字节。拼接获得所需数据,但这样做会影响性能。
    Golang学习之结构体和内存对齐、map设计思路,学习

内存对齐

  • 编译器会把各种类型的数据安排到合适的地址,并占用合适的长度,这就是内存对齐。
  • 每种类型的对齐值就是它的对其边界。
  • 内存对齐要求数据存储地址以及占用的字节数都要是它对齐边界的倍数,所以int32不能从2开始,要从4开始。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 如何确定每种类型的对应边界?这与平台有关
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 被Go语言成为寄存器宽度的这个值,可以理解为机器字长,也是平台对应的最大对齐边界。
  • 而数据类型的对齐边界是取类型大小与平台最大对齐边界中较小的那个
    Golang学习之结构体和内存对齐、map设计思路,学习
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 为何不统一平台最大对齐边界
    Golang学习之结构体和内存对齐、map设计思路,学习
    Golang学习之结构体和内存对齐、map设计思路,学习
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 这是小于最大对齐边界的情况
  • 假设要在32位平台存储一个Int64类型的数据,选择4,减少浪费,提高性能。

如何确定一个结构体的对其边界

  • 首先确定每个成员的对齐边界,然后取其中最大的,这就是结构体类型的对齐边界。
    Golang学习之结构体和内存对齐、map设计思路,学习
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 结构体整体占用字节数需要是类型对齐边界的倍数,不够的话要向后扩张,所以要扩充到相对地址23这里。
  • 最终,结构体类型的大小就是24字节。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 只有每个结构体的大小是对齐值的整数倍,才能保证数组里每一个都是内存对齐的。
    Golang学习之结构体和内存对齐、map设计思路,学习

map设计思路

哈希表与扩容

  • 哈希表通常会有一堆桶来存储键值对。
  • 若要利用哈希值从m个桶中选择一个,桶的编号区间为[0,m-1]
  • 方法一:取模法,得到桶编号
  • 方法二:与运算法,
  • 要限制桶的个数m必须是2的整数次幂,否则将出现某些桶绝对不会被选中。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 如果又有新的键值对选择了该桶,就是发生了哈希冲突,遍历桶找到key相等的桶。(开放地址法)
  • 冲突时,在它后面链一个新桶存储这个键值对,会顺着链表往后查找(拉链法)
  • 哈希冲突的发生会影响哈希表的读写效率,选择散列均匀的哈希函数可以减少哈希冲突的发生。适时的对哈希表进行扩容也是保障读写效率的有效手段。
  • 通常会把存储键值对的数目与桶的数目的比值,作为是否需要扩容的判断依据,这个比值被称为“负载因子”。需要扩容时就要分配更多的桶。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 需要在扩容时,先分配足够多的新桶,然后用一个字段记录旧桶的位置,再增加一个字段记录旧桶迁移的进度,例如记录下一个要迁移的旧桶编号。
  • 渐进式扩容:在哈希表每次读写操作时,如果检测到当前处于扩容阶段,就完成一部分键值对迁移任务,直到所有的旧桶迁移完成,旧桶不再使用,才算真正完成一次哈希表的扩容,像这样把键值对迁移的时间分摊到多次哈希表操作中的方式,就是渐进式扩容。
  • 可以避免一次性扩容带来的性能瞬时抖动。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • Go语言中map类型的底层实现就是哈希表
  • map类型的变量本质上是一个指针,指向hmap的结构体。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • count记录已经存储的键值对数目
  • B记录桶的数目是2的多少次幂,因为这里选择桶时用的是与运算的方法。
  • buckets记录桶在哪儿
  • oldbuckets用于在扩容阶段保存旧桶在哪儿
  • nevacuate记录渐进式扩容阶段下一个要迁移的旧桶编号
    Golang学习之结构体和内存对齐、map设计思路,学习

bmap的结构

  • 为了使结构更紧密,含八个键值对Golang学习之结构体和内存对齐、map设计思路,学习
  • 每个tophash都是对应哈希值的高8位
  • 最后为一个bmap型指针,指向一个溢出桶,溢出桶的内存布局与“常规桶”相同,是为了减少扩容次数而引入的。
  • 当一个桶存满了,还有可用的溢出桶时,就会在桶后面链一个溢出桶,继续往这里存。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 实际上,如果哈希表要分配的桶的数目大于2^4,就认为使用到溢出桶的几率较大,就会预分配
  • 2^(B-4)个溢出桶备用。
    *这些溢出桶与常规桶在内存中是连续的,只是前2^B个用作常规桶,后面的用作溢出桶。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • hmap结构体最后有一个extra字段,指向一个mapextra结构体,里面记录的是溢出桶相关的信息。
  • nextoverflow指向下一个空闲溢出桶;
  • overflow是一个slice,记录目前已经被使用的溢出桶的地址
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 假如编号为2的桶存满了,就会在后面链一个溢出桶,nextoverflow指向下一个空闲桶,noverflow记录使用的溢出桶数量,oldoverflow用于在扩容阶段存储旧桶用到的那些溢出桶的地址。
  • Golang学习之结构体和内存对齐、map设计思路,学习

练习

  • key和value都是string类型,所以64位下每个key和value都占用16字节
  • 取k1哈希值的高8位存在tophash
  • 字符串内容为k1,占用字节数目为2,value同理。(16个bytes,8ptr,4len,4cap)
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 如果把这个桶存满,这个哈希表是会创建溢出桶还是会发生扩容呢

map扩容规则

  • Go语言map的默认负载因子是6.5,超过这个数就会出发翻倍扩容,分配新桶的数目是旧桶的两倍,
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 例如:如果旧桶数量为4,新桶数量就是8
  • 如果一个哈希值选择0号旧桶,那么哈希值的二进制低两位一定为0。
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 选择新桶的结果只有两种,取决于哈希值的第三位是0还是1,如果第三位为0,则选择编号为0的新桶;如果第三位为1,则选择编号为4的新桶,因为桶的数量一定是2的整数次幂。
  • Golang学习之结构体和内存对齐、map设计思路,学习
  • Golang学习之结构体和内存对齐、map设计思路,学习
    所以,无论容量为多少,翻倍扩容后,每个旧桶都会按照这样的规律,分流到两个新桶中,
    Golang学习之结构体和内存对齐、map设计思路,学习
  • 如果负载因子没有超标,但是使用的溢出桶较多,也会触发扩容,但为等量扩容
    Golang学习之结构体和内存对齐、map设计思路,学习
    等量扩容就是创建和旧桶数目一样多的新桶,然后把原来的键值对迁移到新桶中。
    这种情况出现在有很多键值对被删除的情况,等量扩容的方式,使键值对排列的更加紧凑,从而减少溢出桶的使用
  • Golang学习之结构体和内存对齐、map设计思路,学习

文章来源地址https://www.toymoban.com/news/detail-572197.html

到了这里,关于Golang学习之结构体和内存对齐、map设计思路的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 结构体内存对齐(面试重点)

    1.1 结构体的概念 结构是⼀些值的集合,这些值称为成员变量。结构的每个成员可以是不同类型的变量。 1.1.1 结构的声明 例如描述⼀个学⽣: 1.1.2 结构体变量的创建和初始化 运行结果如图: 1.2 结构的特殊声明 在声明结构的时候,可以不完全的声明。 比如: 上⾯的两个结构

    2024年01月25日
    浏览(41)
  • 结构体内存对齐,位段,枚举相关问题.

    本文标签:    结构体内存对齐   结构位段问题   枚举 文章目录 目录 文章目录 一、结构体的内存对齐. 1.计算结构体大小 2.为什么存在内存对齐? 二、结构体的位段问题. 三、枚举 1.枚举类型定义 2.枚举的优点 为什么使用枚举? 总结 知道了结构体的基本使用,我们可以深入探

    2023年04月08日
    浏览(30)
  • C语言之结构体内存对齐与内存的简单理解

    文章目录 内存单元的理解 结构体中内存对齐的规则 为什么会存在内存对齐 首先先要介绍一下C语言中一些常见的存储单元     bit       存放一个二进制位     Byte   1Byte = 8 bit     KB     1KB   = 1024 Byte     MB     1MB   = 1024 KB     GB     1GB   = 1024 MB     TB 

    2023年04月26日
    浏览(43)
  • C语言——结构体类型(二)【结构体内存对齐,结构体数组】

    📝前言: 上一讲结构体类型(一)中,我们讲述了有关 结构体定义,创建,初始化和引用 的内容,这一讲,我们进一步学习结构体的相关知识: 1,结构体内存对齐 2,结构体数组 🎬个人简介:努力学习ing 📋个人专栏:C语言入门基础 🎀CSDN主页 愚润求学 🌄每日鸡汤:

    2024年01月24日
    浏览(70)
  • 【刷题笔记】结构体内存对齐举例+统计回文

    题目: 下面存在两个结构体: 在#pragma pack(4)和#pragma pack(8)的情况下, 结构体的大小 分别是? 分析:         C/C++中结构体计算其大小涉及到内存对齐问题。(详细可以参考我这篇博客:结构体、位段、共用体、枚举相关内存知识(c语言)_柒海啦的博客-CSDN博客)         这

    2024年02月03日
    浏览(38)
  • Golang实践:用Sync.Map实现简易内存缓存系统

    定义了一个Cache结构体,其中使用sync.Map作为底层数据结构来存储缓存项。Set方法用于设置缓存项,指定键、值以及过期时间。Get方法用于获取缓存项,如果缓存项存在且未过期,则返回值和true,否则返回nil和false。方法的接受者为指针类型,是为了对Cache对象进行操作,并在

    2024年04月15日
    浏览(43)
  • C语言如何计算结构体大小(结构体的内存对齐)

    结构体的内存对齐是有关结构体内容的很重要一个知识点,主要考察方式是计算结构体的字节大小。 当我们对计算结构体一无所知,我们不妨自己思索如何计算,是不是直接计算结构体成员变量占用内存的大小呢? 那我们先举个例子  观察发现结构体的大小计算跟我们想的

    2024年02月16日
    浏览(44)
  • 结构体占用内存大小如何确定?-->结构体字节对齐 | C语言

    目录 一、什么是结构体 二、为什么需要结构体 三、结构体的字节对齐 3.1、示例1 3.2、示例2 3.3、示例3  3.4、示例4 3.5、示例5 四、结构体字节对齐总结         结构体是将不同类型的数据按照一定的功能需 求进行整体封装,封装的数据类型与大小均可以由用户指定。 结

    2024年01月17日
    浏览(46)
  • 【C语言高阶篇】结构体 —— 什么是内存对齐?

    🎬 鸽芷咕 :个人主页  🔥 个人专栏 :《C语言初阶篇》 《C语言进阶篇》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位宝子们大家好啊,今天给大家带来的是结构体的内存对齐这部分知识,可以说是干货满满啦!    ⛳️ 在我们C语言的面试题中,结构体最

    2024年02月14日
    浏览(51)
  • 【C语言】什么是结构体内存对齐?结构体的大小怎么计算?

      目录 1.结构体内存对齐 对偏移量的理解:​ 2.结构体的大小计算 2.1结构体中只有普通的数据类型的大小计算 2.2 结构体中有嵌套的结构体的大小计算 3.修改默认对齐数 4.为什么存在内存对齐? 这篇文章主要介绍结构体内存对齐和如何计算大小。 在学习结构体内存对齐之前,

    2024年02月11日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包