14 ms·

> it turns out that computers are pretty fast at allocating memory Isn't this not the case? My understanding was that 90% of HPC is normally about making sure

by skohan 6y ago

> it turns out that computers are pretty fast at allocating memory Isn't this not the case? My understanding was that 90% of HPC is normally about making sure to avoid as many individual allocations/deallocations possible, because these are massively expensive compared to almost all user-space operations, and lead to cache-inefficient memory layouts, which can slow your code down by like a factor of 200

chrisseaton 6y ago
What do you think an allocation involves in a modern language implementation? It's about five machine instructions amortised. Load the allocation pointer, add the object size to it, check it's not got too large, store it. Deallocation though - yes that's slow!
- joosters 6y ago
  That's the absolute best case for the simplest malloc implementation possible. In the real world, a malloc can involve picking an appropriate zone/arena based upon allocation size & the current thread, obtaining locks, chasing some pointers through its data structures, doing some book-keeping, perhaps even calling up to the OS to increase the process space. Maybe in the very best case it can just shuffle a couple of pointers, but over time it has to do a lot more than that.
  - kragen 6y ago
    Well, chrisseaton did say amortised, not worst-case. He wasn't talking about malloc, which is a C function that indeed cannot be that fast, but about a modern language implementation. Results from some trivial benchmarks are in my comments at https://news.ycombinator.com/item?id=26438596 https://news.ycombinator.com/item?id=26438596 and https://news.ycombinator.com/item?id=26449902 https://news.ycombinator.com/item?id=26449902. You can reason it out from first principles, though. Picking the right arena is done at compile time, and you don't obtain locks or chase pointers on the open-coded fast path. Maybe once every 1024 allocations you have to do all that jazz, which costs you another 128 instructions, 0.125 instructions per allocation. And maybe once very 1024 times you do that, you need to call up to the OS to increase the process space at a cost of about 4096 instructions or so, 0.004 instructions per allocation. So the allocation fast path dominates your amortized allocation performance, even though the cases you're talking about are what dominate your worst-case performance.
- CyberDildonics 6y ago
  That is very wrong. If you allocate a a few bytes at a time, it will top out in the ballpark of 10 million per second per core, which is still 300 cycles at 3ghz. Realistically allocations mean mapping in more memory which is a system call, going to block and have both TLB and other cache effects. Every allocation will also need to be freed which needs to alter the heap data structure (there is a reason it's called the heap). This idea that allocation is simple and fast is bizarre in any context where speed matters. The lowest hanging fruit to optimization is usually cutting down on allocations inside loops and just reusing a single allocation made ahead of time. What this person was saying is true to an extent, although it is likely to be more in the ballpark of 5x to 10x slower instead of 200x. I would not say minimizing allocations is a big part of HPC, I would say that it is the bare minimum to any non-trivial program where speed could be an issue.
  - gsg 6y ago
    chrisseaton is talking about the bump-pointer allocator in a modern GC, not an implementation of malloc/free. The performance characteristics are quite different. In a generational copying system an object that is bump allocated and then is dead before being copied out of the young generation is indeed cheap - dead objects in the young generation don't need to be freed or even looked at in any way because the space for the young generation can simply be reused after everything is copied out of it. The slow part is elsewhere.
    - CyberDildonics 6y ago
      There are no situations where it makes sense to say that lots of allocations are cheap and only cost a few instructions. If lots of allocations are happening without freeing, more memory will have to be mapped in anyway on top of the constant pointer bumping - which means that a single allocation of an array would make sense instead. If lots of allocations are happening with freeing, 'objects'/allocations will have to be moved around constantly to cater to the 'cheap' bump allocation. If lots of allocations are happening then all being freed uniformly at the same time, it makes no sense to use lots of allocations since one array allocation would be fine. Basically, making lots of tiny allocations marginally cheaper is a terrible strategy since it will always be a drag on performance since it is a naive and wasteful way to write software.
- MauranKilom 6y ago
  If you don't use a per-thread heap, then you won't get around synchronizing different threads for allocation. If that necessarily serial part of your code makes up even 1% of the time your program needs (before parallelization), then going from 100 threads to 1000 threads will only be a speedup of 81% (whereas you'd ideally expect 900%). That's not good for HPC. See https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law.
  - deleted 6y ago
    [deleted]
  - CyberDildonics 6y ago
    There is a lot of truth to this and you are one of the few people I've seen mention amdahl's law in the correct context. There are multiple malloc implementations (gcc and maybe clang) that are supposedly multi-threaded now and multiple allocators are explicitly made for it like jemalloc, so I don't think the situation is quite as dire anymore. That being said, I agree that using per-thread heaps is a much better structure by default for a heavily multi-threaded program since allocations crossing threads probably should be handled explicitly and memory mapping from the OS will still block (as far as I know).
  - chrisseaton 6y ago
    > If you don't use a per-thread heap Well why wouldn't you? > See https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law Allocation should be embarrassingly parallel in the fast path.
- kragen 6y ago
  This is correct. Here is a Lisp function that allocates N cons cells: $ sbcl This is SBCL 1.0.57.0.debian, an implementation of ANSI Common Lisp. ... * (defun nlist (n) (loop for i from 1 to n collect i)) NLIST * (nlist 5) (1 2 3 4 5) * (compile 'nlist) NLIST NIL NIL Let’s see how long it takes to allocate two million 500-item lists, totaling a billion allocations: * (time (dotimes (i 2000000) (nlist 500))) Evaluation took: 6.477 seconds of real time 6.460403 seconds of total run time (6.416401 user, 0.044002 system) [ Run times consist of 0.384 seconds GC time, and 6.077 seconds non-GC time. ] 99.74% CPU 18,093,926,186 processor cycles 16,032,024,704 bytes consed NIL That’s 6.5 nanoseconds and 18 “processor cycles” (does SBCL use performance counters for this or is it guessing?) per 16-byte allocation. That’s about 150 million allocations per second, including the time to initialize those allocations and increment the loop counter and whatnot, and also (contra chrisseaton) the time to deallocate those lists. If we increase the list length and proportionally decrease the iteration count, this performance remains consistent up to 50,000-item lists, but at 2000 iterations of half a million items, it starts taking 10 seconds instead, presumably because the lists no longer fit into the generational garbage collector’s nursery, so it has to spend a third of its time in the garbage collector. The above is running on one core of a “Intel(R) Core(TM) i7-3840QM CPU @ 2.80GHz”, so if 18 processor cycles is not correct, it’s a damned good guess. Also, this CPU is from 02012, nine years ago. What does this look like at the machine level? NLIST disassembles to 87 lines of assembly, so I’ll spare you most of it and excerpt only one of the allocations: * (disassemble 'nlist) ; disassembly for NLIST ; 029ECE7D: 488B4DF8 MOV RCX, [RBP-8] ; no-arg-parsing entry point ... ; EF9: 4D8B5C2418 MOV R11, [R12+24] ; EFE: 498D4B10 LEA RCX, [R11+16] ; F02: 49394C2420 CMP [R12+32], RCX ; F07: 0F8696000000 JBE L9 ; F0D: 49894C2418 MOV [R12+24], RCX ; F12: 498D4B07 LEA RCX, [R11+7] ; F16: L4: 49316C2440 XOR [R12+64], RBP ... ; FA3: L9: 6A10 PUSH 16 ; FA5: 4C8D1C2570724200 LEA R11, [#x427270] ; alloc_tramp ; FAD: 41FFD3 CALL R11 ; FB0: 59 POP RCX ; FB1: 488D4907 LEA RCX, [RCX+7] ; FB5: E95CFFFFFF JMP L4 As best I’ve been able to figure out, the nursery allocation pointer is stored in memory at [R12+24], the pointer to the freshly allocated dotted pair comes out of this sequence (at L4) in RCX, and the pointer to the end of the nursery is stored in memory at [R12+32]. So the actual allocation is, in the normal case, the six instructions from 029ECEF9 up to 029ECF16. If the nursery is full, it takes the jump to L9 to invoke a minor garbage collection. It may help to know that on amd64 SBCL represents dotted-pair pointers with, essentially, a pointer to their 7th byte, which is what all that RCX+7 nonsense is about. In games it's common to use a similar pointer-bumping allocator for many allocations and then deallocate the whole heap at the end of the frame (by resetting the allocation pointer)—in that case, you don't even need the check against the heap limit, you just need to make sure you never come close to overflowing it. The Packrat-parsing backend of the project I'm working on at the moment, http://gitlab.special-circumstanc.es/hammer/hammer http://gitlab.special-circumstanc.es/hammer/hammer, does the same thing, but the arena is per-parse rather than per-frame, and it may be divided into multiple separately malloced blocks. Also, unlike SBCL, Hammer is in C, so it can't inline the calls to `h_arena_alloc`; they typically have to pay two instructions of argument setup, one instruction of function call, one instruction of return value handling, another instruction of PLT shared library overhead, and then the actual function is 26 instructions in the usual case. The moral of the story is that the performance of fundamental operations depends strongly on the tradeoffs you make in your system design. It's still true, though, that pointer-heavy data structures are terrible for cache locality (an L3 cache miss costs about 100 ns, as much as 15 allocations on one core, but typically the L3 cache is shared across all cores or at least all the cores on one socket), and that HPC consists mostly of large numerical arrays and not pointer chasing. Consequently, the software stacks used in HPC aren't optimized to make allocation cheap; they're optimized for other operations, and so they allow allocation to be expensive. I've explored this fascinating issue in somewhat more detail in http://canonical.org/~kragen/memory-models http://canonical.org/~kragen/memory-models. (It's a deeply damning commentary on the climate of boastful intellectual vacuity this site fosters that comments like this get downvoted for showing empirical evidence and comparing results from a wide variety of contexts, while confident but totally clueless comments about how an allocation necessarily involves acquiring locks and whatnot get voted up to the top. I guess they take less time to make!)

by skohan 6y ago

chrisseaton 6y ago

What do you think an allocation involves in a modern language implementation? It's about five machine instructions amortised. Load the allocation pointer, add the object size to it, check it's not got too large, store it. Deallocation though - yes that's slow!

joosters 6y ago
That's the absolute best case for the simplest malloc implementation possible. In the real world, a malloc can involve picking an appropriate zone/arena based upon allocation size & the current thread, obtaining locks, chasing some pointers through its data structures, doing some book-keeping, perhaps even calling up to the OS to increase the process space. Maybe in the very best case it can just shuffle a couple of pointers, but over time it has to do a lot more than that.
- kragen 6y ago
  Well, chrisseaton did say amortised, not worst-case. He wasn't talking about malloc, which is a C function that indeed cannot be that fast, but about a modern language implementation. Results from some trivial benchmarks are in my comments at https://news.ycombinator.com/item?id=26438596 https://news.ycombinator.com/item?id=26438596 and https://news.ycombinator.com/item?id=26449902 https://news.ycombinator.com/item?id=26449902. You can reason it out from first principles, though. Picking the right arena is done at compile time, and you don't obtain locks or chase pointers on the open-coded fast path. Maybe once every 1024 allocations you have to do all that jazz, which costs you another 128 instructions, 0.125 instructions per allocation. And maybe once very 1024 times you do that, you need to call up to the OS to increase the process space at a cost of about 4096 instructions or so, 0.004 instructions per allocation. So the allocation fast path dominates your amortized allocation performance, even though the cases you're talking about are what dominate your worst-case performance.
CyberDildonics 6y ago
That is very wrong. If you allocate a a few bytes at a time, it will top out in the ballpark of 10 million per second per core, which is still 300 cycles at 3ghz. Realistically allocations mean mapping in more memory which is a system call, going to block and have both TLB and other cache effects. Every allocation will also need to be freed which needs to alter the heap data structure (there is a reason it's called the heap). This idea that allocation is simple and fast is bizarre in any context where speed matters. The lowest hanging fruit to optimization is usually cutting down on allocations inside loops and just reusing a single allocation made ahead of time. What this person was saying is true to an extent, although it is likely to be more in the ballpark of 5x to 10x slower instead of 200x. I would not say minimizing allocations is a big part of HPC, I would say that it is the bare minimum to any non-trivial program where speed could be an issue.
- gsg 6y ago
  chrisseaton is talking about the bump-pointer allocator in a modern GC, not an implementation of malloc/free. The performance characteristics are quite different. In a generational copying system an object that is bump allocated and then is dead before being copied out of the young generation is indeed cheap - dead objects in the young generation don't need to be freed or even looked at in any way because the space for the young generation can simply be reused after everything is copied out of it. The slow part is elsewhere.
  - CyberDildonics 6y ago
    There are no situations where it makes sense to say that lots of allocations are cheap and only cost a few instructions. If lots of allocations are happening without freeing, more memory will have to be mapped in anyway on top of the constant pointer bumping - which means that a single allocation of an array would make sense instead. If lots of allocations are happening with freeing, 'objects'/allocations will have to be moved around constantly to cater to the 'cheap' bump allocation. If lots of allocations are happening then all being freed uniformly at the same time, it makes no sense to use lots of allocations since one array allocation would be fine. Basically, making lots of tiny allocations marginally cheaper is a terrible strategy since it will always be a drag on performance since it is a naive and wasteful way to write software.
MauranKilom 6y ago
If you don't use a per-thread heap, then you won't get around synchronizing different threads for allocation. If that necessarily serial part of your code makes up even 1% of the time your program needs (before parallelization), then going from 100 threads to 1000 threads will only be a speedup of 81% (whereas you'd ideally expect 900%). That's not good for HPC. See https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law.
- deleted 6y ago
  [deleted]
- CyberDildonics 6y ago
  There is a lot of truth to this and you are one of the few people I've seen mention amdahl's law in the correct context. There are multiple malloc implementations (gcc and maybe clang) that are supposedly multi-threaded now and multiple allocators are explicitly made for it like jemalloc, so I don't think the situation is quite as dire anymore. That being said, I agree that using per-thread heaps is a much better structure by default for a heavily multi-threaded program since allocations crossing threads probably should be handled explicitly and memory mapping from the OS will still block (as far as I know).
- chrisseaton 6y ago
  > If you don't use a per-thread heap Well why wouldn't you? > See https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law Allocation should be embarrassingly parallel in the fast path.
kragen 6y ago
This is correct. Here is a Lisp function that allocates N cons cells: $ sbcl This is SBCL 1.0.57.0.debian, an implementation of ANSI Common Lisp. ... * (defun nlist (n) (loop for i from 1 to n collect i)) NLIST * (nlist 5) (1 2 3 4 5) * (compile 'nlist) NLIST NIL NIL Let’s see how long it takes to allocate two million 500-item lists, totaling a billion allocations: * (time (dotimes (i 2000000) (nlist 500))) Evaluation took: 6.477 seconds of real time 6.460403 seconds of total run time (6.416401 user, 0.044002 system) [ Run times consist of 0.384 seconds GC time, and 6.077 seconds non-GC time. ] 99.74% CPU 18,093,926,186 processor cycles 16,032,024,704 bytes consed NIL That’s 6.5 nanoseconds and 18 “processor cycles” (does SBCL use performance counters for this or is it guessing?) per 16-byte allocation. That’s about 150 million allocations per second, including the time to initialize those allocations and increment the loop counter and whatnot, and also (contra chrisseaton) the time to deallocate those lists. If we increase the list length and proportionally decrease the iteration count, this performance remains consistent up to 50,000-item lists, but at 2000 iterations of half a million items, it starts taking 10 seconds instead, presumably because the lists no longer fit into the generational garbage collector’s nursery, so it has to spend a third of its time in the garbage collector. The above is running on one core of a “Intel(R) Core(TM) i7-3840QM CPU @ 2.80GHz”, so if 18 processor cycles is not correct, it’s a damned good guess. Also, this CPU is from 02012, nine years ago. What does this look like at the machine level? NLIST disassembles to 87 lines of assembly, so I’ll spare you most of it and excerpt only one of the allocations: * (disassemble 'nlist) ; disassembly for NLIST ; 029ECE7D: 488B4DF8 MOV RCX, [RBP-8] ; no-arg-parsing entry point ... ; EF9: 4D8B5C2418 MOV R11, [R12+24] ; EFE: 498D4B10 LEA RCX, [R11+16] ; F02: 49394C2420 CMP [R12+32], RCX ; F07: 0F8696000000 JBE L9 ; F0D: 49894C2418 MOV [R12+24], RCX ; F12: 498D4B07 LEA RCX, [R11+7] ; F16: L4: 49316C2440 XOR [R12+64], RBP ... ; FA3: L9: 6A10 PUSH 16 ; FA5: 4C8D1C2570724200 LEA R11, [#x427270] ; alloc_tramp ; FAD: 41FFD3 CALL R11 ; FB0: 59 POP RCX ; FB1: 488D4907 LEA RCX, [RCX+7] ; FB5: E95CFFFFFF JMP L4 As best I’ve been able to figure out, the nursery allocation pointer is stored in memory at [R12+24], the pointer to the freshly allocated dotted pair comes out of this sequence (at L4) in RCX, and the pointer to the end of the nursery is stored in memory at [R12+32]. So the actual allocation is, in the normal case, the six instructions from 029ECEF9 up to 029ECF16. If the nursery is full, it takes the jump to L9 to invoke a minor garbage collection. It may help to know that on amd64 SBCL represents dotted-pair pointers with, essentially, a pointer to their 7th byte, which is what all that RCX+7 nonsense is about. In games it's common to use a similar pointer-bumping allocator for many allocations and then deallocate the whole heap at the end of the frame (by resetting the allocation pointer)—in that case, you don't even need the check against the heap limit, you just need to make sure you never come close to overflowing it. The Packrat-parsing backend of the project I'm working on at the moment, http://gitlab.special-circumstanc.es/hammer/hammer http://gitlab.special-circumstanc.es/hammer/hammer, does the same thing, but the arena is per-parse rather than per-frame, and it may be divided into multiple separately malloced blocks. Also, unlike SBCL, Hammer is in C, so it can't inline the calls to `h_arena_alloc`; they typically have to pay two instructions of argument setup, one instruction of function call, one instruction of return value handling, another instruction of PLT shared library overhead, and then the actual function is 26 instructions in the usual case. The moral of the story is that the performance of fundamental operations depends strongly on the tradeoffs you make in your system design. It's still true, though, that pointer-heavy data structures are terrible for cache locality (an L3 cache miss costs about 100 ns, as much as 15 allocations on one core, but typically the L3 cache is shared across all cores or at least all the cores on one socket), and that HPC consists mostly of large numerical arrays and not pointer chasing. Consequently, the software stacks used in HPC aren't optimized to make allocation cheap; they're optimized for other operations, and so they allow allocation to be expensive. I've explored this fascinating issue in somewhat more detail in http://canonical.org/~kragen/memory-models http://canonical.org/~kragen/memory-models. (It's a deeply damning commentary on the climate of boastful intellectual vacuity this site fosters that comments like this get downvoted for showing empirical evidence and comparing results from a wide variety of contexts, while confident but totally clueless comments about how an allocation necessarily involves acquiring locks and whatnot get voted up to the top. I guess they take less time to make!)