3 ms·

Wouldn’t memory allocation still be IO of a different resource? We’re still getting slowed down reading and writing bits to a storage device. Perhaps it’s not t

Wouldn’t memory allocation still be IO of a different resource? We’re still getting slowed down reading and writing bits to a storage device. Perhaps it’s not the hard drive but the claimed blocker here doesn’t appear to be CPU.

cb321 4y ago
Indeed - for that particular problem a big cost is the "IO" from main memory "into the CPU cache". Ben is careful to qualify it as "disk" IO, but even this is somewhat vague. (as is "CPU cache" vs L3/L2/L1 - Ben's interview problem is highly L2 sensitive, I think, and increasing variety in that size will make results harder to interpret.) On a modern gen4 NVMe, I routinely get 7 GiB/s. gen5 is supposed to double that (as soon as manufactures get "enough" money out of gen4 given PCIe4's extremely short life compared to gen3's extremely long one.) There was a time not long ago (maybe still) where highly scaled up, many core (40+) Intel CPUs could not match that getting from DIMMs into L3 for just 1 core (as per his interview problem). So, we are indeed moving into an era where "IO" from the primary persistent device is indeed no worse than IO from DIMMs, at least in bandwidth terms. DIMMs still have much better latency and the latency-BW ambiguity has been observed elsethread. EDIT: I should clarify, to connect my text with your comment, that the real cost of (1-core, uncontended) allocation is also more "populating/mapping the cache" with copies, not just "allocation" in itself.
School-Cotton 4y ago
Reading and writing to main memory is not usually called “IO” in this context.
dahfizz 4y ago
Not really, no. Allocation involves reading/writing to memory, but that's not why it's slow. It's slow because allocation involves a context switch into the kernel. And an allocation algorithm itself isn't trivial.
- zabzonk 4y ago
  user space code will not use the kernel and there will be no context switch. it will call a function such as malloc, which is a user-space function. malloc will then go on to interact with the memory allocation sub-system, which may occasionally need to ask the os for more memory via a system call, if the allocator is any good.
  - dahfizz 4y ago
    Yeah malloc is user space code, but it will do a syscall like sbrk to actually get memory from the kernel. The default malloc in glibc does not pad the values given to sbrk, so you have to do a syscall for every 4k chunk of memory (the pagesize). So unless you do lots of very small (<<4k) allocations, you call sbrk pretty often. You will also page fault when you access the new pages, and this traps into kernel code again. So yeah, you are technically correct that some allocations may be fast because the memory is already available and mapped. Allocations, on average, are still slow because it involves context switches to the kernel (potentially multiple). TLDR: you make it sound like a syscall within malloc is rare, but many/most allocations will trigger a syscall.
    - morelisp 4y ago
      It is rare because one of the very first things anyone does if they're concerned about allocations is replace glibc malloc.
    - Agingcoder 4y ago
      No, for a start some allocators don't even use sbrk (all mmap), and glibc's ptmalloc will use mmap for large allocations, ie you can allocate multiple megabytes with a single syscall with ptmalloc. Granted, if memory has been mmaped, you will pay a page fault because of the zero page optimization when you first write to it. Furthermore, memory which is freed is often not returned to the os, either for fragmentation (you've used sbrk..) , or performance reasons (minimize syscalls), and put in a free list instead. The next call to malloc then will not require a syscall, if it can be satisfied with existing freed blocks.
diarrhea 4y ago
That discussion reminds me of Intel Optane. The current distinction between hard disks and RAM isn’t a necessity dictated by some law of nature. Yet it’s the box most people think within (for good reason).

cb321 4y ago

Indeed - for that particular problem a big cost is the "IO" from main memory "into the CPU cache". Ben is careful to qualify it as "disk" IO, but even this is somewhat vague. (as is "CPU cache" vs L3/L2/L1 - Ben's interview problem is highly L2 sensitive, I think, and increasing variety in that size will make results harder to interpret.) On a modern gen4 NVMe, I routinely get 7 GiB/s. gen5 is supposed to double that (as soon as manufactures get "enough" money out of gen4 given PCIe4's extremely short life compared to gen3's extremely long one.) There was a time not long ago (maybe still) where highly scaled up, many core (40+) Intel CPUs could not match that getting from DIMMs into L3 for just 1 core (as per his interview problem). So, we are indeed moving into an era where "IO" from the primary persistent device is indeed no worse than IO from DIMMs, at least in bandwidth terms. DIMMs still have much better latency and the latency-BW ambiguity has been observed elsethread. EDIT: I should clarify, to connect my text with your comment, that the real cost of (1-core, uncontended) allocation is also more "populating/mapping the cache" with copies, not just "allocation" in itself.

School-Cotton 4y ago

Reading and writing to main memory is not usually called “IO” in this context.

dahfizz 4y ago

Not really, no. Allocation involves reading/writing to memory, but that's not why it's slow. It's slow because allocation involves a context switch into the kernel. And an allocation algorithm itself isn't trivial.

zabzonk 4y ago
user space code will not use the kernel and there will be no context switch. it will call a function such as malloc, which is a user-space function. malloc will then go on to interact with the memory allocation sub-system, which may occasionally need to ask the os for more memory via a system call, if the allocator is any good.
- dahfizz 4y ago
  Yeah malloc is user space code, but it will do a syscall like sbrk to actually get memory from the kernel. The default malloc in glibc does not pad the values given to sbrk, so you have to do a syscall for every 4k chunk of memory (the pagesize). So unless you do lots of very small (<<4k) allocations, you call sbrk pretty often. You will also page fault when you access the new pages, and this traps into kernel code again. So yeah, you are technically correct that some allocations may be fast because the memory is already available and mapped. Allocations, on average, are still slow because it involves context switches to the kernel (potentially multiple). TLDR: you make it sound like a syscall within malloc is rare, but many/most allocations will trigger a syscall.
  - morelisp 4y ago
    It is rare because one of the very first things anyone does if they're concerned about allocations is replace glibc malloc.
  - Agingcoder 4y ago
    No, for a start some allocators don't even use sbrk (all mmap), and glibc's ptmalloc will use mmap for large allocations, ie you can allocate multiple megabytes with a single syscall with ptmalloc. Granted, if memory has been mmaped, you will pay a page fault because of the zero page optimization when you first write to it. Furthermore, memory which is freed is often not returned to the os, either for fragmentation (you've used sbrk..) , or performance reasons (minimize syscalls), and put in a free list instead. The next call to malloc then will not require a syscall, if it can be satisfied with existing freed blocks.

diarrhea 4y ago

That discussion reminds me of Intel Optane. The current distinction between hard disks and RAM isn’t a necessity dictated by some law of nature. Yet it’s the box most people think within (for good reason).