Posts

TCMalloc 给每个线程都分配一个局部缓存，采用线程局部数据技术。小块内存的分配从线程局部缓存分配即可满足。同时周期性地将线程缓存内存回收到中心缓存中，线程局部缓存不足时从中心缓存中申请。 小对象分配(<=256K) 对于256K以内的内存大小，划分了约88个种类，每个size class对应一个种类，分配时是将申请内存大小向上取整到size class类别的大小，比如申请5bytes会分配8bytes，由于分配的内存会大于申请的内存，则会造成内存浪费。 每个线程分配单独的缓存ThreadCache，ThreadCache中对于每个size class都分配一个FreeList用于分配和回收该大小的内存空间。小对象的分配直接在ThreadCache中对应大小的FreeList中获取空闲对象 全局共享缓存CentralCache，对于每个size class都分配一个CentralFreeList，当ThreadCache尝试分配发现没有空闲对象时，就从CentralCache的对应大小的CentralFreeList中获取一部分空闲对象，这里需要加锁。 当CentralCache中的CentralFreeList没有空闲对象时，向PageHeap申请内存，将其划分成对应大小的空闲对象，加入到空闲链表中。 内存回收时，将空闲对象插入对应的ThreadCache的FreeList中，当满足一定条件将FreeList中的内存归还给CentralCache，当满足一定条件将CentralCache的CentralFreeList中的内存归还给PageHeap 中对象分配(256K<size<=1M) 对于中对象的分配，从PageHeap中的FreeLsit中获取，PageHeap划分为128个span，每个span由1,2…128个page组成。 分配内存时首先向上取整到对应K个page 从PageHeap的对应大小的FreeList中尝试获取span 如果该大小没有空闲的span，则增大page往下寻找 找个n个page的span后，将该span划分为两部分 将k个page的span作为结果返回 将剩余的n-k个page的span，插入到PageHeap中 如果128个spanlist都没有空闲对象，则当做大对象来分配 大对象分配(>1M) 对于大于1m的对象或者小于1m但PageHeap的spanList无法满足的对象，则采用大对象分配。 首先向上取整到对应K个page 大于128K的span都是使用红黑树来保存的，然后使用best-fit首次适应算法，找到合适的span 找个n个page的span后，将该span划分为两部分 将k个page的span作为结果返回 将剩余的n-k个page的span，如果n-k>128则插入红黑树中继续用于大对象的分配，n-k<=128则插入到PageHeap中 如果无法找到足够大小的空闲对象，则需要向系统申请新的内存 内存分配 分级分配 golang根据对象内存大小划分为3类， 微对象：0~16B 小对象：16B~32KB，以及<16B的指针对象 大对象：32KB以上 三级内存管理 线程缓存：每个线程有自己的内存缓存，如果内存大小能够满足，则直接在线程缓存上分配，不需要考虑全局锁的问题 中心缓存：当线程缓存无法满足时，就需要在全局的中心缓存来分配 页堆：当需要分配32KB以上的大对象时，使用页堆 内存管理 内存管理单元mspan 每个mspan都管理npages个8K的页 比如最小的分配8B的mspan，则需要一个8K的页，因此最后可以分配8K/8B=1024个对象 比如最大的分配32K的mspan，则需要4个8K的页，因此最多可以分配32K/32K=1个对象 mspan中使用allocBits来标记内存的占用情况，1表示已分配，0表示未使用 mspan分为无指针的noscan和有指针的两种，与gc有关 线程缓存mcache 每个P都有自己的mcache，用于分配小对象 每个mcache都有alloc [numSpanClasses]*mspan，67*2=134个mspan，用来分配不同大小的对象 每个P在初始化时会调用allocmcache来初始化mcache 初始化时mcache中每个mspan都是空的emptymspan，并没有内存空间 当mcache中的mspan满或者为emptymspan时，调用refill从中心缓存中获取至少包含一个空闲对象空间的mspan 中心缓存mcentral 每个spanclass对应一个mcentral，共134个 mcentral中主要维护两个spanlist nonempty mSpanList：表示存在空闲对象空间的mspan empty mSpanList：表示没有空闲对象空间的mspan或者缓存在mcache中 主要方法cacheSpan该方法来返回span给mcache // Allocate a span to use in an mcache. func (c *mcentral) cacheSpan() *mspan { sg := mheap_....

柱状图中最大的矩形 题目描述 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 ...

LFU 缓存 题目描述 请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。 实现 LFUCache 类： LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。 void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。 注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。 为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。 当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lfu-cache 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 你是否可以在 O(1) 时间复杂度内完成这两种操作？ ...

将数组分成三个子数组的方案数 题目描述 我们称一个分割整数数组的方案是 好的 ，当它满足： 数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。 left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。 给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对 109 + 7 取余后返回。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ways-to-split-array-into-three-subarrays 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ...

转变数组后最接近目标值的数组和 题目描述 给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。 如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。 请注意，答案不一定是 arr 中的数字。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ...