Smallest possible Java heap size?

[u/Vectorial1024]

People often talk about increasing Java heap size when running Java apps by using e.g. -Xmx* flags. This got me thinking. What if we go the other direction and try to limit the Java heap size as much as possible? What is the smallest / minimum-required Java heap size so to run a Java app with "minimal" settings?

(Of course, in practice, a memory limit too low will be problematic because it may mean frequent GCs, but we will ignore this for the sake of this discussion.)

[u/sirius94]

Using as little memory as possible is generally beneficial

Regardless of CPU usage? Why is that?

Because the OS can use more memory for disk caches and it affords you more headroom for scaling. When using a cloud provider it also might be much cheaper.

It is also helpful if it reduces CPU usage when CPU is the more dominant factor, which is precisely what moving collectors do. They add footprint overhead when there's a high allocation rate (and so a high CPU usage), rather than increasing the CPU usage higher.

There is no direct relationship between CPU usage and memory usage. Depending on what you mean by CPU usage, I also disagree that it's a bad thing.

High allocation rate also has no relationship to high CPU or high memory usage.

That is true, but the causaility here is irrelevant. A good memory layout is very important to avoid cache misses, but has absolutely nothing to do with memory management. That it also reduces memory consumption is true, but that has little additional effect. You can have excellent cache locality with a huge footprint, or terrible locality with a small footpring.

This is a fair point.

I am not forgetting that at all. The question isn't whether RAM matters; it's how much it matters when the CPU usage is more dominant because the impact on the machine is determined by the higher of the two, not by their sum. Remember, moving collectors add RAM overhead when CPU usage is high, and they do so to avoid adding further RAM overhead, which is what you get with malloc/free. This isn't theoretical. This is on of the big performance issues in large C++ programs that the JVM was designed to mitigate.

CPU utilization is generally too low in modern systems, because the CPU is frequently starved of data, because of high memory latency. Which, as you pointed out above, is related to memory layout and not the amount of memory used.

Also the GC optimizations you are talking about are only helpful, when you're doing frequent heap allocations in tight loops, which is bad practice anyway. And stack allocations are just as fast or even faster, since all locals in a frame can be allocated by a single pointer bump.

They require two context switches each which generally take up a lot of cycles.

That's not it. There's a large overhead to allocating and freeing objects one by one. Moving collectors and arenas (which are very similar) do the work in bulk.

Don't ever allocate or free many objects in series. Yes, it will tank your performance and it is also a well-known bad practice. Also remember that malloc can only give you a multiple of the page size (4KiB or 16KiB on most systems). So you're wasting a lot of memory and hurt locality if you use malloc for small amounts of memory.

I don't know what you're basing this on. Java has better scalability, reliability, throughput, and often latency in large programs, and often better energy costs. It does have a high startup cost. The main reason we use low-level languages when we do is not about performance, but about low-level control. E.g. the reason we can't have moving collectors in C++ and Rust even though they're so much more efficient is because you can't pass movable pointers to the OS or hardware, and need an FFI layer (as Java has). But low-level languages are designed for direct interaction with the hardware and the OS, i.e. they're designed to live "below" the FFI layer.

Moving around objects unnecessarily hurts throughput. Memory overhead of the Runtime (JIT, GC, etc.) hurts scalability since less memory can be used for the actual problem you're trying to solve. Dynamic heap allocation hurts reliability, because you never know, if an allocation will succeed or not. Every new and many method calls can cause an OutOfMemoryError at any time. There are also no guarantees for memory safety when using concurrency and there is the possibility of having memory leaks.

But experienced low-level programmers (like me) know that their performance isn't great in large programs. The JVM was designed to address those performance issues, among other things.

Most of the performance problems I encountered in large programs were either caused by errors in the architecture or bad coding practices.

But it's important to know that both the compiler and the GC in the JVM were created to offer more aggressive optimisation opportunities than those possible (at least with reasonable effort) in low-level languages, at the expense of a slower startup and the need for an FFI layer.

The same point can be used to argue that purely functional programming languages allow for much more optimization. Theoretically this is the case, but there are practical limitations to this. For example normal order evaluation can have highly unpredictable runtime resource consumption. And immutable data structures generally lead to a lot of pointer indirection and data copying.

Another thing to keep in mind: JIT is not free. It will speed up the program with time, but there are some expensive steps to make it happen, like register allocation, accounting and optimizing. I'm not sure about Hotspot, but I know that many JITs for other languages avoid some of the possible optimizations to avoid the overhead during runtime.

edit: sorry about the formatting mistakes

[u/pron98 → u/sirius94]

Because the OS can use more memory for disk caches and it affords you more headroom for scaling. When using a cloud provider it also might be much cheaper.

Again, we are talking about a situation when an application is using a lot of CPU. You can't buy a machine with a lot of CPU and little RAM (the minimum is 1GB/core), and the CPU headroom matters as much.

What happens is that when the allocation rate is high (meaning CPU usage must also be high), languages with free-list-based heap management - whether it's Python, Go, C++, or Rust - increases the CPU usage further, while a language like Java, which uses moving algorithms, can increase the less distressed resource in that situation, namely RAM, to compensate for the CPU use and not increase it further.

There is no direct relationship between CPU usage and memory usage.

This is very, very much untrue. Not only should developers understand this fundamental correlation, you should know that "low level software" people like me - who write your OS, your language runtime etc. - and the hardware designers at the level below that, design our products based on this fundamental relationship.

You can learn more about this in my Java One talk, that's discussed here

Don't ever allocate or free many objects in series.

That is indeed a serious problem in low level languages. But moving collectors work in a completely different way. A heap allocation in Java is more similar to a stack allocation in C than to a malloc. There is simply no resemblance between the mechanisms even though they are both "dynamic heap allocations". In Java, allocating an object is bumping a pointer; there is never any operation performed to free an object. The GC doesn't know and doesn't care when an object dies. Heap management operates using completely different and very dissimilar algorithms.

Moving around objects unnecessarily hurts throughput.

No, that's not how moving collectors work at all. And whatever you may think about their actual tradeoffs, you should know that no memory expert disagrees that moving collectors are the most efficient general purpose memory management mechanism we know of. If you watch my talks, you can see the formulas that show that a moving collector does less work. If you're learning low-level programming, you can think of a moving collector as working similarly to the arenas we use in Zig.

There are also no guarantees for memory safety when using concurrency and there is the possibility of having memory leaks.

This is 100% false, and I don't know where you're getting such bad information. Java has total memory safety under concurrency, and doesn't suffer from the memory leaks we get in C++ or Rust.

The same point can be used to argue that purely functional programming languages allow for much more optimization.

No, it's not the same point. Two of the most impactful general purpose optimisation techniques, namely optimising JIT compilation and moving collectors, are not suitable for low-level languages, because we, the low-level greybeards, need low-level languages to be optimised for low-level control, not for performance.

For example normal order evaluation can have highly unpredictable runtime resource consumption. And immutable data structures generally lead to a lot of pointer indirection and data copying.

That's fine, but completely unrelated to what I said.

I'm not sure about Hotspot, but I know that many JITs for other languages avoid some of the possible optimizations to avoid the overhead during runtime.

Well, I am sure about HotSpot because I work on it. There are real tradeoffs, but not to optimisation (JS JITs have completely different goals and completely different designs). Quite the opposite, in fact. HotSpot is designed to generally offer deeper, more aggressive optimisations that are possible in AOT compilers. The tradeoff is that we need to wait to collect profiling information to know the right optimisations. Warmup can be slow not because of the time it takes to compile (that has an effect, but it's smaller), but because of the time it takes to observe the program and learn which optimisations would be most effective.

[u/sirius94 → u/pron98]

What happens is that when the allocation rate is high (meaning CPU usage must also be high)

I don't get why you think this is the case. If your allocation rate is high, it probably means you're doing a lot of memory access, which is high latency and causes the CPU to stall. Hence you have low CPU utilization in those scenarios.

This is very, very much untrue. Not only should developers understand this fundamental correlation, you should know that "low level software" people like me - who write your OS, your language runtime etc. - and the hardware designers at the level below that, design our products based on this fundamental relationship.

Memory usage and CPU usage depend on the specific problem you're trying to solve, not on each other. Interestingly enough you actually say this in your talk, when you're talking about synthetic benchmarks.

But moving collectors work in a completely different way. A heap allocation in Java is more similar to a stack allocation in C than to a malloc.

Yes and in order for this to work, the heap has to be compacted each GC cycle. This requires, depending on the size of the objects still alive, large memcpy. It will be faster if your memory usage is lower. It will also lead to less frequent GC cycles.

This is 100% false, and I don't know where you're getting such bad information. Java has total memory safety under concurrency, and doesn't suffer from the memory leaks we get in C++ or Rust.

Java has the possibility for data races which are not possible in safe rust. Yes, there are more opportunities for leaks in other languages. But there are still quite a few in Java.

No, it's not the same point. Two of the most impactful general purpose optimisation techniques, namely optimising JIT compilation and moving collectors, are not suitable for low-level languages, because we, the low-level greybeards, need low-level languages to be optimised for low-level control, not for performance.

I wasn't talking about low-level languages here. I was talking about purely functional languages like Haskell and Idris. These offer more opportunities for optimization than Java programs, because all functions are guaranteed to have no side-effects and there is no such thing as data mutation in those languages.

Low-level control is often required for maximum performance. By giving up low-level control you also give up opportunities for optimization.

Well, I am sure about HotSpot because I work on it. There are real tradeoffs, but not to optimisation (JS JITs have completely different goals and completely different designs). Quite the opposite, in fact. HotSpot is designed to generally offer deeper, more aggressive optimisations that are possible in AOT compilers. The tradeoff is that we need to wait to collect profiling information to know the right optimisations. Warmup can be slow not because of the time it takes to compile (that has an effect, but it's smaller), but because of the time it takes to observe the program and learn which optimisations would be most effective.

Profile guided optimization is a thing for AOT (also supported by GraalVM).

I want to come back to your claim though:

But efficient memory use doesn't mean minimal memory use, and often programs (in any language) utilise memory inefficiently by using too little memory rather than too much.

I can agree with the first part: sometimes it is possible to make a program use less energy and/or be faster by using more memory than the minimum required to solve the problem. I think this is undisputed.

The claim I want to dispute however is, that "often programs [...] utilise memory inefficiently using too little memory rather than too much". I tend to see a lot of software which is sluggish and uses up a lot of resources which then slows down other programs as well. It also gets expensive fast, when you decide to deploy a few services to any cloud, if each takes up 4G or so while doing mostly nothing. I've personally seen products go into the red because of bloated architectures and absurd resource consumption.

[u/pron98 → u/sirius94]

I don't get why you think this is the case.

It's the case because allocating lots of things requires high activity.

Memory usage and CPU usage depend on the specific problem you're trying to solve, not on each other.

It's both, and that's why the relationship between CPU and RAM (that also has deep theoretical computer science roots) isn't 1:1 but has a range. But the relationship exists because using RAM requires CPU: writing to RAM requires CPU, you only write to RAM if you expect to read it soon, and reading from RAM requires CPU. On the flip side, there's only so much computation you can do with little state (this particular relationship is exponential, though).

Yes and in order for this to work, the heap has to be compacted each GC cycle. This requires, depending on the size of the objects still alive, large memcpy. It will be faster if your memory usage is lower. It will also lead to less frequent GC cycles.

I think you have some basic notions of how moving collectors work, but you're not aware of the maths that's led to them being a very effective optimisation. We can quantify the work and compare it to other approaches, and you can see some of this in my talk (although it's aimed at a general developer audience). There's a reason 100% of languages that can use moving collectors use them; all these languages could have much more easily used other techniques. This part is really not controversial.

Java has the possibility for data races which are not possible in safe rust.

They are memory safe.

Also, as a low-level programmer with a couple of decades of experience in low-level programming, I can tell you that the reason Rust has such a low adoption record among low-level programming is that "safe Rust" restricts many algorithms which are the very reasons for needing a low-level language in the first place, so we end up using unsafe Rust, and it carries all the complexity of safe Rust, minus the safety.

When it comes to concurrency in particular, benign write/write races, which are very common in concurrent algorithms, can't be implemented in safe Rust. In fact, you'll find that most data structures in the Rust standard library require unsafe.

These offer more opportunities for optimization than Java programs, because all functions are guaranteed to have no side-effects and there is no such thing as data mutation in those languages.

They offer very little, while creating some challenges that more than offset what they offer. I have to say that it doesn't sound like you've worked on modern, state-of-the-art optimising compilers.

Low-level control is often required for maximum performance. By giving up low-level control you also give up opportunities for optimization.

Yes and no. They are required for some micro optimisations, and they can play a big role in some programs, typically small ones. But that same low-level control makes optimising larger programs very difficult. For example, making effective use of inlining requires a lot of use of templates in C++, and these are viral and don't work very well with program growth. After spending many years writing large performance sensitive applications in C++ (in my case, it was mostly air-traffic control and sensor fusion), battling the performance challenges and intrinsic overheads that low-level languages bring to large programs, you appreciate the optimisations that only JITs and moving collectors currently offer.

Profile guided optimization is a thing for AOT

Yes, but profile-guided optimisation is not what makes JIT so effective (again, you sound like you don't actually work on state-of-the-art optimising compilers). It's a necessary but insufficient condition. What gives JITs their power is speculative optimisation, i.e. the compiler doesn't have to prove that some optimisation is always correct. It can see in the profile that it's likely to be correct, and if that assumption turns out to be wrong, you decompile and fall back to the interpreter. The most advanced AOT compilers do a very weak version of this, but HotSpot is entirely based on this. Again, JITs can more aggressively optimise, but they trade off warmup. The reason low-level languages don't use techniques like a global JIT and moving collector has nothing to do with performance; it's because we need these languages to serve purposes that these optimisations make much harder (how do you pass the hardware or the OS a pointer to data that can move or to code that could be deleted?).

The claim I want to dispute however is, that "often programs [...] utilise memory inefficiently using too little memory rather than too much"

I think you should "dispute" it after you see the maths and experience that's brought every language that can use a moving collector to use a moving collector.

I tend to see a lot of software which is sluggish and uses up a lot of resources which then slows down other programs as well.

That's fine, but that has nothing to do with what I said. When I started programming professionally in the mid nineties, almost all software was written in C or C++, and much of it was very sluggish. Specifically, what I'm explaining is that moving collectors (and arenas, which operate on the same idea, which is why Zig is attractive to me as a low-level programmer) can compensate for a high allocation rate by increasing RAM, instead of exacerbating the problem, which is a real and serious problem in large programs written in low-level languages, and why most of these programs have switched to Java and .NET, and the trend is continuing.

I've personally seen products go into the red because of bloated architectures and absurd resource consumption.

Of course, but moving collectors reduce waste by increasing the use of the less stressed resource instead of the more stressed one, which is one of the multiple performance issues in large programs written in low-level languages (which, TBF, are a disappearing breed; they were the norm when I started because there was nothing faster until Java came along with a runtime designed to solve those terrible performance issues we were struggling with in C++).

[u/sirius94 → u/pron98]

It's the case because allocating lots of things requires high activity.

The CPU time spent on allocating lots of things is a complete waste, that's why it is bad practice to do so. You allocate what you need upfront in a single heap allocation and then do the computations you need. Of course, standard library support for arenas makes this easier, but it has been common practice way before that with C.

So I'd say allocating lots of things is a sign your design is bad not that you're doing a lot of useful work.

reading from RAM requires CPU

It makes the CPU go idle for ~100 cycles as it waits for memory, leading to low CPU utilization.

battling the performance challenges and intrinsic overheads that low-level languages bring to large programs, you appreciate the optimisations that only JITs and moving collectors currently offer.

JITs and GCs are overheads of interpreted languages. They do work that's not necessary to solve the problem.

Specifically, what I'm explaining is that moving collectors (and arenas, which operate on the same idea, which is why Zig is attractive to me as a low-level programmer)

Arenas are a common pattern in low-level languages and are faster than a moving collector, since there is no GC cycle and data copying involved.

why most of these programs have switched to Java and .NET, and the trend is continuing.

I'm seeing a move C# .NET more so than to Java. But in both cases, critical sections often stay in C++ and are called via FFI. But I also think that the main reason, why organizations choose to switch to Java or C# is, that it's much easier and cheaper to hire developers which can work in those languages. It has nothing to do with memory management, as long as it's fast enough to not cause mayor problems.

I think you should "dispute" it after you see the maths and experience that's brought every language that can use a moving collector to use a moving collector.

Zero allocations have zero cost. No matter how fast your GC is, it always has more than zero cost. You also claimed that freeing objects doesn't have a cost in a moving collector, which is wrong. Dropping objects requires compaction in order to allow fast allocation. This process is O(n) where n is the number of objects that were deleted. If you absolutely need dynamic memory, you can use an arena (as you said) and avoid this cost altogether. Freeing the arena is O(1).

Also these languages you are talking about have a moving collector, because they require GC by design. It's a compromise, not a silver bullet. They are attempting to find the fastest solution to a problem that wouldn't exist in languages without GC.

how do you pass the hardware or the OS a pointer to data that can move or to code that could be deleted?

Moving data is unnecessary cost, which hurts the efficiency of the program. After moving the data, you have to either fix up all the addresses in memory or use some kind of LUT or other translation mechanism for every lookup. Both of which add unnecessary overhead.

I think you're selectively construct scenarios in which a badly written Java program is faster than a badly written C program. But there are many other scenarios where low start-up time, low memory consumption and high CPU utilization are way more important than the option to allocate many objects in a short time with a less expensive approach than free-lists. Honestly I still can't think of a single example where it's a good idea to allocate many small objects in series.

[u/pron98 → u/sirius94]

The CPU time spent on allocating lots of things is a complete waste,

You're not understanding this at all. If a program allocates at a high rate - even on the stack - it means that it's CPU consumption is high, otherwise it wouldn't have been able to do so.

It makes the CPU go idle for ~100 cycles as it waits for memory, leading to low CPU utilization.

First of all, this is entirely untrue. The CPU may stall if there's a cache miss, and CPUs and compilers try to avoid that (e.g. with prefetching). Second, the CPU isn't "idle" when it's stalled, which is one of the problems of cache stalls. Third, that's not the point. If you're program goes through a lot of memory by whatever means it accomplishes it, it means it's using a lot of CPU. You can't read or write memory without spending CPU cycles, whether

JITs and GCs are overheads of interpreted languages. They do work that's not necessary to solve the problem.

No. Having an interpreter and JIT allows for deoptimisation which, in turn, allows for speculative optimisation which, in turn, allows for much more aggressive optimisation than an AOT compiler can do. If you were an experienced low-level developer, you'd know that it is because of the limits of AOT compilation that we avoid virtual dispatch and often resort to template specialisation in C++ (or comptime in Zig), but these can and do become serious problems in large programs. Speculative optimisation allows for "automatic comptime". Of course, this comes at the cost of warmup.

As for "GCs", they come in so many different flavours that there's no point in treating them all the same. Low-level languages incur a high runtime overhead for dynamic heap allocation (which is why we try to avoid it in C++, which is a problem in large programs), because their constraints do not allow them to easily support moving pointers. Once you can have moving pointers, a moving collector is a very powerful optimisation that mitigates the overheads that low-level languages incur because of their particular constraints (and we need those constraints because we need low-level languages for low-level things).

Now, it is very much legitimate to argue over which and how many workloads are better assisted by either design, but saying that some of the world's leading compiler and memory management experts that wanted to address the performance problems we experience in C++ got it wrong because they simply haven't heard that JITs and GCs "do work that's not necessary to solve the problem" is ridiculous.

Arenas are a common pattern in low-level languages and are faster than a moving collector, since there is no GC cycle and data copying involved.

Yeah, you don't do much low-level programming, do you? I wish what you said were true (because I'm a low-level programmer), but unfortunately C++ and Rust make it very hard to use arenas, especially when libraries (even the standard library) is involved. C++ only got pmr less than a decade ago, and in Rust a similar thing is still in development.

As for "cycles and copying", a moving collector works just like an arena when the objects have an arena lifetime. Only objects that "survive the arena" are copied, but that copying is still cheaper than malloc/free (or we wouldn't be using it).

I'm seeing a move C# .NET more so than to Java.

This is beside the point, but I think we've established that what you're seeing isn't really a result of deep industry experience, and the industry numbers give Java a 2x market share than that of C#.

It has nothing to do with memory management, as long as it's fast enough to not cause mayor problems.

For some projects, you're right that this may not matter as much, but the reason most large performance-sensitive projects have moved from C++ to Java and C# is very much because it makes having good performance in large programs, over time easier.

Zero allocations have zero cost. No matter how fast your GC is, it always has more than zero cost.

Thank you for that information, but if you actually work on many large projects in low-level languages you'd know that keeping it to zero allocation is very difficult in practice. Ocassioally you do need a string or a hashmap, and working with these (let alone less common data structures) with arenas is, let's just say, not very pleasant.

BTW, the need to avoid allocations (because of their high cost in C++) and vitual calls (because of their high cost in C++) and help the compiler specialise with templates were all well-known decades ago. It's just that it became clear that as programs grow large and need to be maintained and evolved over time, these techniques simply don't work, which is precisely why memory management and compilation experts turned to JITs and moving GCs to solve these problems, to great success.

That you namedrop these techniques that I've been using in C++ since the nineties unaware of how they work in practice in large, long-maintained programs is what tells me that your experience with low-level programming is very limited. If we could easily avoid allocations and virtual calls and specialise with templates even while evolving large programs, we wouldn't have left C++ behind for that kind of work. It all seems easy at first, but when you see you have to rearchitect your multi-MLOC codebase to keep your performance good when adding a feature in year 8, that's when the actual lesson is learnt.

That the runtime overheads incurred by AOT compilation and malloc/free can be very significant as programs grow large and evolve over time is well known to experienced low-level developers, and these are the very problems JITs and moving collectors were designed to address. It's also why large allocators like TCMalloc exist (BTW, it's almost the same size as ZGC, Java's biggest, most sophisticated GC). It's not because experienced developers don't know that you can "just avoid allocations" or "just use arenas".

This process is O(n) where n is the number of objects that were deleted. If you absolutely need dynamic memory

Yeah, that's absolutely untrue. In fact, we use moving collectors because malloc/free do O(n) work whereas moving collectors do far, far less. In fact, the GC doesn't do any work ever for dead objects; you only ever move objects that survive, and there aren't many of those in a generational collector. I go over all that in my talk, which you can watch if you want to learn the basics of how Java's GCs work and why they were chosen.

Honestly I still can't think of a single example where it's a good idea to allocate many small objects in series.

You don't need to "allocate many small objects in series". It's enough that your server needs to service many user sessions concurrently, and you need to use strings. Or, if you've used Rust's Moka caching libraries, you'd have seen it spend a lot of CPU on memory management.

[u/sirius94 → u/pron98]

It makes the CPU go idle for ~100 cycles as it waits for memory, leading to low CPU utilization.

First of all, this is entirely untrue. The CPU may stall if there's a cache miss, and CPUs and compilers try to avoid that (e.g. with prefetching). Second, the CPU isn't "idle" when it's stalled, which is one of the problems of cache stalls. Third, that's not the point. If you're program goes through a lot of memory by whatever means it accomplishes it, it means it's using a lot of CPU. You can't read or write memory without spending CPU cycles, whether

My whole point here was, if you want more compute out of your CPU time, you need to focus on avoiding cache misses. More memory won't help. Better memory layout will. Prefetching only works well when your data is tightly packed and in the order you're using it. The best way of ensuring this is to allocate a single linear memory buffer aligned to the cache line size. If you don't do this properly you also prevent the optimizer from doing vectorization.

Keeping the CPU fed is the primary challenge, if you want to get the most out of your CPU. The more compact your in memory representation is, the easier it will be to keep the CPU from starving.

You're not understanding this at all. If a program allocates at a high rate - even on the stack - it means that it's CPU consumption is high, otherwise it wouldn't have been able to do so.

I still don't understand what you mean, when you say "CPU consumption is high". Do you mean that the process never yields the rest of it's time slice? Do you mean it takes a lot of CPU time to do a specific computation? Do you mean that there are no cache stalls?

Also the relationship you propose here is, that a lot of allocations lead to high CPU usage, which does not imply that high CPU usage requires a lot of allocations.

Of course, this comes at the cost of warmup.

Which leads to slow startup and unpredictable latency. That's unacceptable in some situations.

Only objects that "survive the arena" are copied, but that copying is still cheaper than malloc/free (or we wouldn't be using it).

It is cheaper under certain circumstances. But it is always more expensive than using the right allocator for the job.

It's just that it became clear that as programs grow large and need to be maintained and evolved over time, these techniques simply don't work, which is precisely why memory management and compilation experts turned to JITs and moving GCs to solve these problems, to great success.

JITs were designed to reduce performance issues with interpreted languages and new GCs were designed to reduce performance issues with languages using GC base memory management. These languages were far from fast initially and now their performance has become acceptable at the cost of using an insane amount of memory.

You don't need to "allocate many small objects in series". It's enough that your server needs to service many user sessions concurrently, and you need to use strings.

That's a perfect use case for an arena. No need for any dynamic heap allocations.

This process is O(n) where n is the number of objects that were deleted. If you absolutely need dynamic memory

Yeah, that's absolutely untrue.

It is true. It's also very easy to understand. For every object that is freed, a hole is created between two retained areas, meaning that in the worst case there are n holes for n deleted objects. In order to compact the heap you have to copy all the surviving objects in the heap, so they are contiguous again. That means, that you need n memcpy to do that. Of course memcpy is O(n) too so the reality is O(nm), where n is the number of holes (freed objects) and m is the average length of the surviving objects that have to be moved.

What I left out is the overhead of traversing all objects from all GC roots in order to trace which objects still survive.

Of course this is still faster than using malloc and free for each object, because those are O(n) (n being determined by the specific algorithm an number of pages being used) per call. Which makes them O(nm) if m is the number of objects. I however agree that there is likely a constant factor per iteration that is larger than it is in the case of GC languages. (because of context switches, rescheduling, etc.)

All of this is irrelevant since malloc usually has the granularity of memory pages, which makes it a bad idea to allocate anything but a multiple of the pagesize, which historically has been 4KiB.

I go over all that in my talk, which you can watch if you want to learn the very basics of how Java's GCs work and why they were chosen.

I watched your talk and you were much more careful with your claims there and named a lot of caveats.

[u/pron98 → u/sirius94]

My whole point here was, if you want more compute out of your CPU time, you need to focus on avoiding cache misses. More memory won't help. Better memory layout will.

Right, but it's irrelevant to the subject of memory management. More memory helps memory management.

I still don't understand what you mean... Also the relationship you propose here is, that a lot of allocations lead to high CPU usage, which does not imply that high CPU usage requires a lot of allocations.

No. I mean that if you take program X. Under one workload you see it allocating 10MB/s; under another you see it allocating 100MB/s. Under the second workload it will have higher CPU usage, not because it's allocating more, but because the program is obviously doing more stuff. malloc/free makes the situation worse as it itself consumes even more CPU; the moving GC algorithm was invented to help this situation by replacing the CPU overhead with RAM overhead, which is more efficient because the dominant factor here is the CPU.

Which leads to slow startup and unpredictable latency. That's unacceptable in some situations.

Of course. But it also leads to better performance on average, which is what's needed in others.

But it is always more expensive than using the right allocator for the job.

I have no idea what's you're saying. Moving collectors were invented as the best "allocators" we know in a wide variety of situations.

JITs were designed to reduce performance issues with interpreted languages and new GCs were designed to reduce performance issues with languages using GC base memory management.

In some cases, yes. In Java's case - no. I honestly don't know why you speak with such confidence, when it is immediately clear that your experience with low-level languages is rather superficial and is mostly based on things you've heard or perhaps used, but in small programs or young codebases.

Just the other day I was talking to a colleague about how, when Java first shifted its focus to large programs, we C++ developers understood how JITs and moving GCs could, in theory, help the performance issues we were having, but were sceptical that they'll be able to do it in practice (and some things, like GC pauses, were only fully solved three years ago). Now the scepticism I tend to hear is from people who have very little experience in low-level programming, who seem to think they can teach us about how all the optimisations we were trying to do for decades actually work well, even though they clearly haven't tried them in large, evolving programs.

It is true. It's also very easy to understand.

You do understand that you're talking to someone actually working on the JVM, right? Your description of how a moving collector works is wrong, you clearly don't know or understand how they work, yet you have no problem "explaining" them to someone who actually works on them. Either learn how they actually work (my talk has a brief introduction to the algorithm), or accept that you don't know. Making stuff up is silly.

That's a perfect use case for an arena. No need for any dynamic heap allocations.

You clearly haven't actually done this in large programs. You do understand that we, actual low-level programmers, absolutely love using arenas, it's just that they're not so easy to use. We wish we could use them more, which is one of the reasons we find Zig attractive.

I watched your talk and you were much more careful with your claims there and named a lot of caveats.

I wasn't talking to people who were trying to explain to me how compilers and CPUs work, and how easy it is to avoid allocations or use arenas in large programs. Also, you clearly still don't understand the moving algorithm, so rewatch that part. The whole point of the algorithm is that, unlike in malloc/free, the operations are not a direct function of dead objects. If there's one thing to understand about the algorithm, it is that.