3 ms·

Yes, allocation can be incrementally be made cheaper with a copying GC. But you have to realize that it still comes at a cost, and allocation speed isn't always

Yes, allocation can be incrementally be made cheaper with a copying GC. But you have to realize that it still comes at a cost, and allocation speed isn't always a bottleneck. You have a runtime process intercepting your code state, scanning and analyzing your heap and making a decision to keep, copy, or free. For anything larger than a trivially small object graph, that additional processing can easily overwhelm any incremental allocation speed benefit that you get. I get that it is theoretically possible for GC to be faster, but I literally have never seen it pan out in practice.

tsimionescu 6y ago
Im very skeptical that the comparison really makes sense. Programs written in GC languages are so different in their allocation behavior from those written in manual memory languages that I don't think you can meaningfully compare them. And comparing regular C++ with Boehm GC is probably not that interesting, as Boehm is extremely limited by the semantics of C++. And whichever way you look at it, the GC doesn't really have to outperform manual memory management to be extremely useful. It just has to be close enough, the correctness guarantees alone make it worth it as long as the performance difference is not too large, in many domains, not to mention the productivity boost and program readability.
- darksaints 6y ago
  > And whichever way you look at it, the GC doesn't really have to outperform manual memory management to be extremely useful. It just has to be close enough, the correctness guarantees alone make it worth it as long as the performance difference is not too large, in many domains, not to mention the productivity boost and program readability. I agree with all of this. But it is a very different argument than the theoretical argument that garbage collection can be faster than manual memory management. Rust, for example, is manually managed or compiler managed, depending on how you look at it. But its semantics are extremely crude and naive: allocate on creation, free once an object leaves its current scope. There is no optimization of heap fragmentation, there is no optimization of large bulk frees...the compiler literally just inserts the malloc/free statements for you in a static location that you don't get to choose. And despite the crudeness of its memory allocation behavior, it runs circles around garbage collected languages all day long. Even fast ones...I have done more than a handful of comparisons between Scala, Java, Go, SML (MLTon), OCaml, F#, and Rust...and Rust always comes out on top. That doesn't mean the performance advantages are worth the extra pain of dealing with a borrow checker...for most of my code, I default to Scala for all the reasons you've mentioned. But I don't delude myself into thinking it is faster.
  - jashmatthews 6y ago
    What you're really seeing the benefit of here isn't manual memory allocation but stack allocation. Hammering malloc/free in Rust is slower than using even a pretty simple GC which is why there are crates to do arena based allocation. As a more concrete example splitting strings by copying in Rust and hammering malloc and memcpy is 4-5x slower than using slices in Go and letting the GC deal with keeping things alive. You might say that's not a fair comparison but few businesses can tolerate the messing around that is writing zero copy Rust. malloc implementations actually do optimize by delaying the work of free(1). They do a lot of complex stuff hidden behind those function calls to improve performance.
  - tsimionescu 6y ago
    But Rust is designed to be blazing fast in many aspects, even if it uses a traditional malloc/free. Most likely if you compare a Rust and Java program that both run a loop creating a million node linked list and then starting over, you'll see that the Java program is much faster. I'll actually try to do that and confirm, but I believe it should be the case. Even if you were to allocate arrays (Vec) you may see the same. But, of course, that is not a fair comparison. Rust gives you tools to avoid allocation in the first place. It also optimizes so many things that Java doesn't. Summing up all of the values in an ArrayList<Integer> in Java is going to be so much slower than doing the same in Rust it's not even funny. I'm not even sure that Java implements vectorization yet. It would be very interesting to see what performance a Rust program would get with a good, concurrent parallel generational copying collector. Perhaps in a few years there will be some interest in that.
    - pjmlp 6y ago
      Intel has contributed vectorization support, all the way to AVX.
      - saagarjha 6y ago
        To OpenJDK’s JIT? I’ll have to try that sometime on ArrayList.
Skinney 6y ago
> You have a runtime process intercepting your code state, scanning and analyzing your heap and making a decision to keep, copy, or free. Most generational gc's don't call free (the ones in Java can, but not per object, the reason for doing it is for returning memory to the OS). The GC will scan every _living_ object, but only those it is interested in. So if the decision to be made is which newly allocated objects should be copied over to the old gen, the gc will avoid scanning objects known to already be old. The sentence you wrote made it seem like it scans the entire heap and decides which object should be kept, which should be copied and which should be free'd, but this is far from the case. Since allocation with a GC is usually much cheaper than in non-GC systems (bump allocator) and since free is rarely, if ever, called, you can in theory get better performance from a GC than in a system with manual memory management. Of course, it all depends on the system. The systems I write (mostly CRUD web apps) benefit from it, because requests to my service allocate little and run pretty fast, they're unlikely to survive to the next GC, and so I mostly pay for bump-allocation (which is cheap). However, while the performance might be better my systems are prone to unexpected pauses while the GC does run. That pause might be less than the time spent in free in a manual memory managed system, but of course saving up all that time and spending it in one place does make it more noticable. Thankfully, Java's G1 and collectors have managed to reduce these pauses so they're no longer noticable for my use. Pauses are less than 100ms (usually much lower) which is about the same variation I get from calling a third-party http service.
- saagarjha 6y ago
  Yup, and many GCs have the freedom to move objects around due to language semantics so they can do things like munmap pages if they want to rather than calling free. > Pauses are less than 100ms (usually much lower) which is about the same variation I get from calling a third-party http service. Note that a pause for calling a web service is different than a GC pause, because in the former you can do other useful things while you wait.

tsimionescu 6y ago

Im very skeptical that the comparison really makes sense. Programs written in GC languages are so different in their allocation behavior from those written in manual memory languages that I don't think you can meaningfully compare them. And comparing regular C++ with Boehm GC is probably not that interesting, as Boehm is extremely limited by the semantics of C++. And whichever way you look at it, the GC doesn't really have to outperform manual memory management to be extremely useful. It just has to be close enough, the correctness guarantees alone make it worth it as long as the performance difference is not too large, in many domains, not to mention the productivity boost and program readability.

darksaints 6y ago
> And whichever way you look at it, the GC doesn't really have to outperform manual memory management to be extremely useful. It just has to be close enough, the correctness guarantees alone make it worth it as long as the performance difference is not too large, in many domains, not to mention the productivity boost and program readability. I agree with all of this. But it is a very different argument than the theoretical argument that garbage collection can be faster than manual memory management. Rust, for example, is manually managed or compiler managed, depending on how you look at it. But its semantics are extremely crude and naive: allocate on creation, free once an object leaves its current scope. There is no optimization of heap fragmentation, there is no optimization of large bulk frees...the compiler literally just inserts the malloc/free statements for you in a static location that you don't get to choose. And despite the crudeness of its memory allocation behavior, it runs circles around garbage collected languages all day long. Even fast ones...I have done more than a handful of comparisons between Scala, Java, Go, SML (MLTon), OCaml, F#, and Rust...and Rust always comes out on top. That doesn't mean the performance advantages are worth the extra pain of dealing with a borrow checker...for most of my code, I default to Scala for all the reasons you've mentioned. But I don't delude myself into thinking it is faster.
- jashmatthews 6y ago
  What you're really seeing the benefit of here isn't manual memory allocation but stack allocation. Hammering malloc/free in Rust is slower than using even a pretty simple GC which is why there are crates to do arena based allocation. As a more concrete example splitting strings by copying in Rust and hammering malloc and memcpy is 4-5x slower than using slices in Go and letting the GC deal with keeping things alive. You might say that's not a fair comparison but few businesses can tolerate the messing around that is writing zero copy Rust. malloc implementations actually do optimize by delaying the work of free(1). They do a lot of complex stuff hidden behind those function calls to improve performance.
- tsimionescu 6y ago
  But Rust is designed to be blazing fast in many aspects, even if it uses a traditional malloc/free. Most likely if you compare a Rust and Java program that both run a loop creating a million node linked list and then starting over, you'll see that the Java program is much faster. I'll actually try to do that and confirm, but I believe it should be the case. Even if you were to allocate arrays (Vec) you may see the same. But, of course, that is not a fair comparison. Rust gives you tools to avoid allocation in the first place. It also optimizes so many things that Java doesn't. Summing up all of the values in an ArrayList<Integer> in Java is going to be so much slower than doing the same in Rust it's not even funny. I'm not even sure that Java implements vectorization yet. It would be very interesting to see what performance a Rust program would get with a good, concurrent parallel generational copying collector. Perhaps in a few years there will be some interest in that.
  - pjmlp 6y ago
    Intel has contributed vectorization support, all the way to AVX.
    - saagarjha 6y ago
      To OpenJDK’s JIT? I’ll have to try that sometime on ArrayList.

Skinney 6y ago

> You have a runtime process intercepting your code state, scanning and analyzing your heap and making a decision to keep, copy, or free. Most generational gc's don't call free (the ones in Java can, but not per object, the reason for doing it is for returning memory to the OS). The GC will scan every _living_ object, but only those it is interested in. So if the decision to be made is which newly allocated objects should be copied over to the old gen, the gc will avoid scanning objects known to already be old. The sentence you wrote made it seem like it scans the entire heap and decides which object should be kept, which should be copied and which should be free'd, but this is far from the case. Since allocation with a GC is usually much cheaper than in non-GC systems (bump allocator) and since free is rarely, if ever, called, you can in theory get better performance from a GC than in a system with manual memory management. Of course, it all depends on the system. The systems I write (mostly CRUD web apps) benefit from it, because requests to my service allocate little and run pretty fast, they're unlikely to survive to the next GC, and so I mostly pay for bump-allocation (which is cheap). However, while the performance might be better my systems are prone to unexpected pauses while the GC does run. That pause might be less than the time spent in free in a manual memory managed system, but of course saving up all that time and spending it in one place does make it more noticable. Thankfully, Java's G1 and collectors have managed to reduce these pauses so they're no longer noticable for my use. Pauses are less than 100ms (usually much lower) which is about the same variation I get from calling a third-party http service.

saagarjha 6y ago
Yup, and many GCs have the freedom to move objects around due to language semantics so they can do things like munmap pages if they want to rather than calling free. > Pauses are less than 100ms (usually much lower) which is about the same variation I get from calling a third-party http service. Note that a pause for calling a web service is different than a GC pause, because in the former you can do other useful things while you wait.