6 ms·

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 3g

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.
  - kragen 6y ago
    > There are no situations where it makes sense to say that lots of allocations are cheap and only cost a few instructions. This is so trivially shown to be false that I suspect you are trolling. There is, for example, the situation I showed in https://news.ycombinator.com/item?id=26438596 https://news.ycombinator.com/item?id=26438596. Moreover, as gsg says, this is very generally true of pointer-bumping allocators in modern GCs; SBCL's GC isn't even all that modern.
    - CyberDildonics 6y ago
      What you are talking about is the equivalent of adding 1 to the size of a C++ vector with a large capacity on each iteration of a loop. The memory has already been mapped in (through a blocking system call) and it is contiguous. The "allocation" here is just the same uniform increment in an unbroken span of memory already in the process without taking into anything that makes memory allocation problematic for performance. There is no point to the situation you described, it is a nonsense way to do something trivial. If that's what you want, allocate a single array. The fact remains that memory allocation is often huge low hanging fruit for optimization. If it was 'just a few instructions' this would not be true. Garbage collection does not change this. You can read endless threads about 'performance java' people taking about allocating all their memory when their program starts and never inside their loops. The reasons why have mostly been explained (system calls, heaps, copying in GCs, cache effects, TLB effects, etc.) though people have left out other nuances like mapped pages triggering interrupts on their first write to save time in the memory mapping call. I think it will probably help to look into this further, thinking memory allocation is bumping a pointer is a simplification that will confuse any optimization until you understand it and profile.
      - chrisseaton 6y ago
        > There is no point to the situation you described, it is a nonsense way to do something trivial. I mean... it's how real allocators work in real VMs, so it's not nonsense, is it?

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.
- kragen 6y ago
  > There are no situations where it makes sense to say that lots of allocations are cheap and only cost a few instructions. This is so trivially shown to be false that I suspect you are trolling. There is, for example, the situation I showed in https://news.ycombinator.com/item?id=26438596 https://news.ycombinator.com/item?id=26438596. Moreover, as gsg says, this is very generally true of pointer-bumping allocators in modern GCs; SBCL's GC isn't even all that modern.
  - CyberDildonics 6y ago
    What you are talking about is the equivalent of adding 1 to the size of a C++ vector with a large capacity on each iteration of a loop. The memory has already been mapped in (through a blocking system call) and it is contiguous. The "allocation" here is just the same uniform increment in an unbroken span of memory already in the process without taking into anything that makes memory allocation problematic for performance. There is no point to the situation you described, it is a nonsense way to do something trivial. If that's what you want, allocate a single array. The fact remains that memory allocation is often huge low hanging fruit for optimization. If it was 'just a few instructions' this would not be true. Garbage collection does not change this. You can read endless threads about 'performance java' people taking about allocating all their memory when their program starts and never inside their loops. The reasons why have mostly been explained (system calls, heaps, copying in GCs, cache effects, TLB effects, etc.) though people have left out other nuances like mapped pages triggering interrupts on their first write to save time in the memory mapping call. I think it will probably help to look into this further, thinking memory allocation is bumping a pointer is a simplification that will confuse any optimization until you understand it and profile.
    - chrisseaton 6y ago
      > There is no point to the situation you described, it is a nonsense way to do something trivial. I mean... it's how real allocators work in real VMs, so it's not nonsense, is it?