Stuck on dropping `HashMap` with numerous `Vec<u8>` exceeding 16KB on Windows

[MrBeanCpp]

I tried this code:

let mut map = HashMap::new();
for i in 0..350000 {
    map.insert(i, vec![0u8; 1024 * 17]); //17KB
}
drop(map); //stuck here for a long time

I add println! before and after drop(map) , and it runs for a long time (more than couples of minutes).

But, if I change 1024 * 17 to 1024 * 16, then things will be different.

let mut map = HashMap::new();
for i in 0..350000 {
    map.insert(i, vec![0u8; 1024 * 16]); //16KB
}
drop(map); //1s

The drop(map) will end in just about 1 second!

But everything runs well on Linux, either 16KB or 17KB.

Is 16KB a magic number ?

But it doesn't make any sense why it's stuck and the memory usage(about 5.8GB) hasn't been continuously decreasing on Windows.

And if I change HashMap to Vec, it works well too.

let mut arr = Vec::new();
for i in 0..350000 {
    arr.push(vec![0u8; 1024 * 17]); //17KB
}
drop(arr); //fast

System Info

OS: Windows 11 22H2
CPU: 12th Gen Intel(R) Core(TM) i7-12700H   2.70 GHz
Memory: 32G (16G * 2)

Meta

rustc --version --verbose:

rustc 1.76.0 (07dca489a 2024-02-04)
binary: rustc
commit-hash: 07dca489ac2d933c78d3c5158e3f43beefeb02ce
commit-date: 2024-02-04
host: x86_64-pc-windows-msvc
release: 1.76.0
LLVM version: 17.0.6

[ChrisDenton]

If using the default allocator (HeapAlloc/HeapFree) then yes, if the allocation is big enough it may skip it's own allocator and call VirtualAlloc/VirtualFree directly which can be slower.

You might like to try mimalloc as an alternative allocator.

[MrBeanCpp]

Wow, it works! Thank you! Your assistance is greatly appreciated.
However, I'm still puzzled as to why the default implementation in Rust would cause the program to freeze, rather than just slow down.

[ChrisDenton]

In short, it's not Rust it's the default windows allocator. If you're patient enough it does eventually finish.

As a demonstration the following highly optimized program allocates memory using the windows API directly (HeapAlloc) instead of going through Rust. This doesn't take too long. However, when we use the API to deallocate memory (HeapFree) the loop slows to a crawl.

fn main() {
    let mut memory = Vec::with_capacity(350000);
    let heap = unsafe { GetProcessHeap() };
    println!("allocating memory...");
    for _ in 0..memory.capacity() {
        let ptr = unsafe { HeapAlloc(heap, HEAP_ZERO_MEMORY, 17 * 1024) };
        memory.push(ptr);
    }
    println!("done.");
    println!("deallocating memory...");
    while let Some(ptr) = memory.pop() {
        unsafe { HeapFree(heap, 0, ptr) };
        if memory.len() % 1_000 == 0 {
            println!("remaining: {}", memory.len());
        }
    }
    println!("done.");
}

type HANDLE = isize;
type BOOL = i32;
const HEAP_ZERO_MEMORY: u32 = 0x00000008;

extern "system" {
    fn GetProcessHeap() -> HANDLE;
    fn HeapAlloc(hHeap: HANDLE, dwFlags: u32, dwBytes: usize) -> *mut ();
    fn HeapFree(hHeap: HANDLE, dwFlags: u32, lpMem: *mut ()) -> BOOL;
}

If you run this you can watch it slowly counting down as it works.

[MrBeanCpp]

I understand now! Thank you for the thorough explanation.

I've also conducted the same test with C++, and the deallocation process is similarly slow in MSVC, or even worse(stuck while 16KB). But everything is good in g++ (fix: no, in g++ & mingw, it also stuck with 17KB).
This confirms that it is indeed an issue with the system API (and compiler strategy).

However, I'm somewhat puzzled. Why hasn't this issue been optimized in the standard implementations of C++ and Rust?
Is it because such scenarios are uncommon, or would optimizing for them introduce complexity that could degrade performance in more typical use cases?

[ChrisDenton]

Well optimizing this is what mimalloc does. Why isn't that the default? It does increase code size, though this is only significant for very small applications. Using the system allocator by default can also be useful for interoperability. So making things like mimalloc opt-in is the safer option, if not the most performant.

[MrBeanCpp]

I see. It's a trade-off.
Sincerely thank you again for your patient answer.