In a modern pausing GC allocation rates are normally limited by the size of your new generation space so are often best considered in terms of MBs. Thread local allocation buffers often allow an allocation to be a simple pointer increment, so the cost per allocation is tiny providing you can collect or promote from that buffer fast enough.

> However, AFAIK, a memory allocator takes time proportional to the number of allocations, NOT the total amount of memory allocated.

Depends on the allocator. On a C-style malloc? "Yes". On a Java-style new? No. Because Java is designed to be sandboxed, and as such cannot allow uninitialized memory to exist. And as such has to make sure that when you create that 1000-element array that all 1000 elements are null. And as such, takes time proportional to both the number of allocations and the amount of memory allocated.

Er, this is conflating two different things. Initialization is always linear the number of objects unless it's just not done, but generally speaking even in C or C++ you will still need to perform some kind of initialization on those elements. But really, this has nothing to do with the allocator, which is at a lower level.

Malloc is linear to the number of allocations. Automatic tracing garbage collectors are linear to the live set (because they tend to only explore live objects, and there are techniques to make disposing of the non-live objects happen in less than linear time[1]). This can really go either way as to which is better, depending on your allocation rate, which is why this is a point of contention.

But none of that has to do with how long it takes to initialize the objects.

[1] Semi-space and variants, which are usually used in the allocation-rate-heavy young or nursery generation. Of course if there's extensive use of finalizers you still have to touch those objects to deallocate them.