4 ms·

Small C programs start up faster than HLL programs. Small C programs run faster. When they get bigger, they quickly bloat up to compensate for how hard C make

Small C programs start up faster than HLL programs. Small C programs run faster. When they get bigger, they quickly bloat up to compensate for how hard C makes it to write large-scale software. Oh, and it takes a lot longer to modify those C programs, for the same reasons. C's malloc() time is also a lot slower than GC'd languages. For them, a memory allocation isn't much more than a subtraction.

tptacek 18y ago
First, cite sources for specific cases where a mainstream malloc() is "a lot slower" than a specific GC'd allocation in a mainstream HLL. This rings more truthy than true to me. Second, fixing malloc slowness is among the easiest and fastest optimizations you can make in a C program (in most cases, a pool and freelist will get you 90% of the way there), and no GC'd allocator is faster than pool and arena allocation (which is usually just a couple ALU operations in both the alloc and free cases). Third, large C programs tend to start up faster than large HLL programs. For instance, Eclipse is slower to start for me than Firefox --- and if you're thinking of Firefox as your archetypal "big bloated C++ program", remember that Firefox is by design the most complicated application most people ever run. To make that argument work, you have to find a HLL program of comparable complexity. You didn't do that; you just imply that one exists. I'm calling you out on that.
- jjs 18y ago
  > First, cite sources for specific cases where a mainstream malloc() is "a lot slower" than a specific GC'd allocation in a mainstream HLL. This rings more truthy than true to me. > Second, fixing malloc slowness is among the easiest and fastest optimizations you can make in a C program (in most cases, a pool and freelist will get you 90% of the way there), and no GC'd allocator is faster than pool and arena allocation (which is usually just a couple ALU operations in both the alloc and free cases). In a semispace or generational GC, allocating memory is just bumping a pointer.
  - tptacek 18y ago
    You're not counting the cost of deallocation.
    - lallysingh 18y ago
      Not an easy thing to count globally. Your GC cost (at least in mark-sweep) is dependent on the number of objects you're not deallocating. The rest are implicitly destroyed.
      - tptacek 18y ago
        You can't decouple the cost of malloc() from the cost of free(); if malloc has to do any more work than simply bumping a pointer (or, in the general case, grabbing a mutex and then bumping a pointer), it's a concession to free() (or to defragmentation, a side effect of free).
        jjs 18y ago
        Semispace (and generational) collectors do decouple the cost of allocation from the cost of collection by only considering the set of live objects. They also compact (defragment) as a side effect of collection.
      - brl 18y ago
        In the case of a minor collection, you don't do a full mark-sweep. You only look at a small fraction of the live objects. Generally you only need to trace objects in the youngest generation which are reachable from GC roots. Since you expect most young generation objects to be eligible for collection, this is extremely fast. It is unusual for a lot of references to exist from older generations to the youngest generation, but when this occurs there are data structures for detecting and resolving these references very efficiently.
    - jjs 18y ago
      In the collectors I mentioned, deallocation is a matter of moving the live objects to the other semispace, and considering the "current" semispace to be garbage. If you're allocating a lot of short-lived objects, then explicitly keeping the live objects is much more efficient than explicitly culling the dead objects.
- viraptor 18y ago
  Actually firefox is a large hll program. It's a javascript / xul engine in a large part. The frontend of firefox is actually javascript AFAIK. Maybe someone has more precise information? 1 and 2 were already commented on, so I'll just add that, there was a proof that a copying gc with enough memory can be faster than manual allocation. http://www.cs.umass.edu/~emery/pubs/04-17.pdf http://www.cs.umass.edu/~emery/pubs/04-17.pdf
  - tptacek 18y ago
    The paper you're citing doesn't contain the evidence you claim it has, and in GC vs. "manual" studies, you have to make sure they're not comparing GC to malloc(). Malloc has design goals other than speed. Performant code very often replaces malloc.
    - viraptor 18y ago
      You're right - I made a stupid copy&paste mistake with both documents open :/ This is the link I was thinking about: http://www.cs.ucsb.edu/~grze/papers/gc/appel87garbage.pdf http://www.cs.ucsb.edu/~grze/papers/gc/appel87garbage.pdf
      - brl 18y ago
        Just from the title alone, I can tell I'm going to like this paper :)
      - tptacek 18y ago
        Doesn't this paper basically say: * Garbage collection is faster than manual frees when you provide processes with so much memory that collection happens so rarely that its cost is lost in the noise, and * Garbage collection is faster than manual frees when you ignore all the constant factors in both collection and manually freeing, for instance the cost of taking page faults?
        viraptor 18y ago
        Yes - that's true. But it also gives you additional information: how to check if the cost can be ignored and whether it will be lost in the noise. And that's important, because in serious VMs you can often control the GC parameters. That means you cam make sure that those asymptotes are as close to reality as possible for your exact problem. It's the same story for hashed collections. You can find big O costs for their operations, but they're amortised costs. Sure - once in a while you have to realloc / rehash / copy the table depending on the implementation - but then you know how to judge if that collection is ok for you. You can modify the starting size exactly in order to lose the rare cost in the noise. The trick is knowing the limits. Yet somehow many people who love hashmaps hate GC... You're right about what the paper says, it just didn't spell out the reason why that info is useful ;)

tptacek 18y ago

First, cite sources for specific cases where a mainstream malloc() is "a lot slower" than a specific GC'd allocation in a mainstream HLL. This rings more truthy than true to me. Second, fixing malloc slowness is among the easiest and fastest optimizations you can make in a C program (in most cases, a pool and freelist will get you 90% of the way there), and no GC'd allocator is faster than pool and arena allocation (which is usually just a couple ALU operations in both the alloc and free cases). Third, large C programs tend to start up faster than large HLL programs. For instance, Eclipse is slower to start for me than Firefox --- and if you're thinking of Firefox as your archetypal "big bloated C++ program", remember that Firefox is by design the most complicated application most people ever run. To make that argument work, you have to find a HLL program of comparable complexity. You didn't do that; you just imply that one exists. I'm calling you out on that.

jjs 18y ago
> First, cite sources for specific cases where a mainstream malloc() is "a lot slower" than a specific GC'd allocation in a mainstream HLL. This rings more truthy than true to me. > Second, fixing malloc slowness is among the easiest and fastest optimizations you can make in a C program (in most cases, a pool and freelist will get you 90% of the way there), and no GC'd allocator is faster than pool and arena allocation (which is usually just a couple ALU operations in both the alloc and free cases). In a semispace or generational GC, allocating memory is just bumping a pointer.
- tptacek 18y ago
  You're not counting the cost of deallocation.
  - lallysingh 18y ago
    Not an easy thing to count globally. Your GC cost (at least in mark-sweep) is dependent on the number of objects you're not deallocating. The rest are implicitly destroyed.
    - tptacek 18y ago
      You can't decouple the cost of malloc() from the cost of free(); if malloc has to do any more work than simply bumping a pointer (or, in the general case, grabbing a mutex and then bumping a pointer), it's a concession to free() (or to defragmentation, a side effect of free).
      - jjs 18y ago
        Semispace (and generational) collectors do decouple the cost of allocation from the cost of collection by only considering the set of live objects. They also compact (defragment) as a side effect of collection.
    - brl 18y ago
      In the case of a minor collection, you don't do a full mark-sweep. You only look at a small fraction of the live objects. Generally you only need to trace objects in the youngest generation which are reachable from GC roots. Since you expect most young generation objects to be eligible for collection, this is extremely fast. It is unusual for a lot of references to exist from older generations to the youngest generation, but when this occurs there are data structures for detecting and resolving these references very efficiently.
  - jjs 18y ago
    In the collectors I mentioned, deallocation is a matter of moving the live objects to the other semispace, and considering the "current" semispace to be garbage. If you're allocating a lot of short-lived objects, then explicitly keeping the live objects is much more efficient than explicitly culling the dead objects.
viraptor 18y ago
Actually firefox is a large hll program. It's a javascript / xul engine in a large part. The frontend of firefox is actually javascript AFAIK. Maybe someone has more precise information? 1 and 2 were already commented on, so I'll just add that, there was a proof that a copying gc with enough memory can be faster than manual allocation. http://www.cs.umass.edu/~emery/pubs/04-17.pdf http://www.cs.umass.edu/~emery/pubs/04-17.pdf
- tptacek 18y ago
  The paper you're citing doesn't contain the evidence you claim it has, and in GC vs. "manual" studies, you have to make sure they're not comparing GC to malloc(). Malloc has design goals other than speed. Performant code very often replaces malloc.
  - viraptor 18y ago
    You're right - I made a stupid copy&paste mistake with both documents open :/ This is the link I was thinking about: http://www.cs.ucsb.edu/~grze/papers/gc/appel87garbage.pdf http://www.cs.ucsb.edu/~grze/papers/gc/appel87garbage.pdf
    - brl 18y ago
      Just from the title alone, I can tell I'm going to like this paper :)
    - tptacek 18y ago
      Doesn't this paper basically say: * Garbage collection is faster than manual frees when you provide processes with so much memory that collection happens so rarely that its cost is lost in the noise, and * Garbage collection is faster than manual frees when you ignore all the constant factors in both collection and manually freeing, for instance the cost of taking page faults?
      - viraptor 18y ago
        Yes - that's true. But it also gives you additional information: how to check if the cost can be ignored and whether it will be lost in the noise. And that's important, because in serious VMs you can often control the GC parameters. That means you cam make sure that those asymptotes are as close to reality as possible for your exact problem. It's the same story for hashed collections. You can find big O costs for their operations, but they're amortised costs. Sure - once in a while you have to realloc / rehash / copy the table depending on the implementation - but then you know how to judge if that collection is ok for you. You can modify the starting size exactly in order to lose the rare cost in the noise. The trick is knowing the limits. Yet somehow many people who love hashmaps hate GC... You're right about what the paper says, it just didn't spell out the reason why that info is useful ;)