基础篇-数据结构:容器的内存管理

你有种再说一遍

c++的std::vector扩容在不同平台是不一样的,通过编译器提供的标准库决定的.
win上面大多采用1.5倍,linux采用2倍.
1.5倍的好处是能够复用旧内存,节省内存.
2倍的好处是减少了乘法器和内存碎片.

众所周知,许多操作系统都是虚拟内存,虚拟内存可以使得物理内存不足时,仍然可以无限使用内存.
也可以在申请超过物理内存时候,通过表格来记录仅使用部分,从而实现稀疏数组.
不过物理内存足够的时候,可以大幅度减少页表交换,涉及磁盘/上下文/缓存的切换开销.

什么地方不用虚拟内存?单片机,航空航天,他们需要可观可测内存,所以是自己管理的.以及DMA直接内存访问技术.

虚拟内存的结构:
虚拟地址空间表
-> 快表(缓存虚拟和物理映射)
-> 页表
-> 页表项(可能指向大页或小页)
-> 物理页面(1页4KB或更大的大页)
位图在每一项上面都有用到.

linux内存分配器好几种.
系统内核:采用slab分配器,分配更小的单元.(我们不讨论它)
应用层大块内存:采用一种叫伙伴系统来进行,每个内存块大小都是2次幂.

系统寻址:先进入快表TLB(Translation Lookaside Buffer),若命中就返回物理地址,没有命中就进入页表,再进入页表项,得到物理地址,并回写快表.

系统内存分配:内存会被切割成内存页面(4k),通过位图(bitmap,一字节8位)来记录使用情况,1已分配,0未分配.

系统内存回收:伙伴系统之所以是伙伴,因为它会在回收指定内存块的时候,把旁边空闲的也合并过来,以此让下次申请的能够尽可能获取大块的连续内存.或者左边的伙伴如果需要扩容,可以直接使用.

容器扩容:通过系统内存分配机制去看看后面的内存块容量够不够,系统直接通过掩码+位运算,O(1)就完成了.那么后面如果未分配容量,那么直接拿过来用不就好了吗?还真是,有realloc(c函数).

容器缩容:并不一定生效,因为要2次幂,而且现在应用层大多是采取惰性回收策略,减少交还操作系统内存.因为伙伴系统可能合并内存块,如果需要再申请就可能遇到内存不足进行碎片整理,也可能需要切割.

linux就是容器std::vector和页面page都是对齐的.
win道理是相通的,页面大小也应该是对齐2次幂,在1.5扩容机制上面,它也是扩容到一个1.5倍大一点对齐数(可能是满一个page),好处就是节省了内存占用,但是扩容次数比较多.

文章[C++vector的动态扩容,为何是1.5倍或者是2倍]
(https://blog.csdn.net/qq_44918090/article/details/120583540)
文章[C++摒弃了C中的realloc()函数]
但是图形学上面是追求极限的,能写出比自带还快不是很好嘛?

数组不一定是连续的.
首先栈帧内的数组是必然连续的,而堆上面则不一定.
堆上面是通过一种叫"内存分配器"进行跟踪可用内存块,然后通过内存块进行跳转.
相当于封装了一层,让你在使用时候觉得是连续的.它为什么这样做呢?因为它需要解决内存分配速度和内存碎片问题.

c#的List动态数组的扩容其实充满着坎坷,需要申请一份新内存,再拷贝旧元素过去,以此实现扩容.
有没有一种可能,这是一种低效的做法?如果数组后面还有可以用的内存,那我不就可以不拷贝了吗?
想做一个比c#自带List还快的动态数组.我们要怎么做才能动态数组扩容减少拷贝旧元素呢?在哪里有realloc(c函数)呢?
还有SIMD指令集,c++的初始化memset为0是用了SSE2的,拷贝元素也可以对比一下c#Array.Copy和自己实现AVX512+循环展开比比速度.

如何调用win32api的realloc呢?
有下面两个:
Marshal.ReAllocHGlobal如果分配失败就是原始指针.Marshal.ReAllocCoTaskMem这个它的com版本.

```csharp
IntPtr originalPtr = Marshal.AllocHGlobal(size);
try
{
    IntPtr newPtr = Marshal.ReAllocHGlobal(originalPtr, newSize);
    if (newPtr == IntPtr.Zero)
    {
        // 重新分配失败,处理错误..申请并拷贝新的
    }
    else
    {
        // 重新分配成功，使用新的指针
        originalPtr = newPtr;
    }
}
finally
{
    // 无论成功与否,都需要释放原始指针指向的内存
    Marshal.FreeHGlobal(originalPtr);
}
```

转为托管内存
```csharp
int size = 1024; // 假设我们想要分配1024字节的内存
IntPtr originalPtr = Marshal.AllocHGlobal(size);

// 将非托管内存转换为托管内存
GCHandle handle = GCHandle.Alloc(originalPtr, GCHandleType.Pinned);

// 使用GCHandle来引用内存
byte* buffer = (byte*)handle.AddrOfPinnedObject();

// ... 在这里使用buffer ...

// 当不再需要时，释放托管内存
handle.Free();

// 此时，原始的非托管内存仍然需要手动释放
Marshal.FreeHGlobal(originalPtr);
```

Dllimport版本
```csharp
using System;
using System.Runtime.InteropServices;

class Program
{
    // 导入HeapReAlloc函数
    [DllImport("kernel32.dll", SetLastError = true)]
    static extern IntPtr HeapReAlloc(IntPtr hHeap, uint dwFlags, IntPtr lpMem, int dwBytes);

    // 导入GetProcessHeap函数
    [DllImport("kernel32.dll")]
    static extern IntPtr GetProcessHeap();

    // 导入HeapAlloc函数
    [DllImport("kernel32.dll", SetLastError = true)]
    static extern IntPtr HeapAlloc(IntPtr hHeap, uint dwFlags, IntPtr dwBytes);

    // 导入HeapFree函数
    [DllImport("kernel32.dll", SetLastError = true)]
    [return: MarshalAs(UnmanagedType.Bool)]
    static extern bool HeapFree(IntPtr hHeap, uint dwFlags, IntPtr lpMem);

    static void Main() {
        // 获取当前进程的堆句柄
        IntPtr hHeap = GetProcessHeap();

        // 分配10个int大小的内存
        IntPtr lpMem = HeapAlloc(hHeap, 0, (IntPtr)(10 * Marshal.SizeOf(typeof(int))));
        if (lpMem == IntPtr.Zero) {
            Console.WriteLine("HeapAlloc failed (Error: " + Marshal.GetLastWin32Error() + ")");
            return;
        }

        // 使用内存...

        // 假设我们需要重新分配内存大小为20个int
        IntPtr newMem = HeapReAlloc(hHeap, 0, lpMem, 20 * Marshal.SizeOf(typeof(int)));
        if (newMem == IntPtr.Zero) {
            Console.WriteLine("HeapReAlloc failed (Error: " + Marshal.GetLastWin32Error() + ")");
            HeapFree(hHeap, 0, lpMem);
            return;
        }

        // 更新指针到新分配的内存
        lpMem = newMem;

        // 使用新分配的内存...

        // 最后释放内存
        if (!HeapFree(hHeap, 0, lpMem)) {
            Console.WriteLine("HeapFree failed (Error: " + Marshal.GetLastWin32Error() + ")");
            return;
        }
    }
}

springwillow

厉害，居然用c#来操作内存。数组扩容一直都存在内存重新申请的问题，编程时尽量不采用扩容方案，一次性申请够。必须扩容重新拷贝一份可能还是比较合理的方案。