4 ms·

With a naive mark-and-sweep GC and a policy that runs the GC every N allocations minus frees, it's very easy to write an N^2 algorithm: r = [] for i in ran

With a naive mark-and-sweep GC and a policy that runs the GC every N allocations minus frees, it's very easy to write an N^2 algorithm: r = [] for i in range(1000000): r.append({}) IIRC, Python has (or used to have) the above property.

xxxyy 12y ago
Python uses reference counting to save on GC time. This is one of the reasons why it has GIL.
- stormbrew 12y ago
  There's nothing unique to refcounting garbage collection that implies you need or should use a GIL. Most naive tracing collectors also have one so they can stop the world and trace every thread's stack at the same time. In both cases there are workarounds that reduce throughput as a tradeoff for decreasing latency (and the two mechanisms start to converge into similar algorithms, incidentally).
  - foobar2020 12y ago
    There is: you either have to use atomic operations on all the reference counters, which is costly, and not available on all platforms, or you can have only one thread active at a time. This is the most classic problem: "x == 0"; parallel execution of "x += 1" and "x += 1"; now "x == 1" or "x == 2". I don't see why tracing collectors need GIL in particular to stop all threads, i.e. why should only one thread be running at a time.
    - stormbrew 12y ago
      I'm not sure why you seem to feel your first paragraph here is a disagreement with what I said. As you point out, there is a well known way to have refcounting act correctly in the face of multiple threads. There are other ways as well involving per-thread shadow counts and such, but that is the most basic way to (as I said) trade throughput for latency. Re. your second paragraph, it is again not inherent to the algorithm, but it does greatly simplify things. In particular, pretty much all tracing algorithms require at least some kind of stop the world event, though some can make this event very limited in duration. It is much much easier (and results in greater throughput) to stop the world if only one thread is running at a time, because you just do your collection when that one thread triggers a heap mutation. If you have multiple threads running at once you need to coordinate when you stop the world, which means waiting for the threads to all wind up in a state where they can be stopped (which gets a lot harder if, say, one of the threads never allocates because it's in a tight loop). If it takes too long to do this coordination, your heap might explode on you. Again, what I'm saying is that a GIL is not an inherent feature of either garbage collection mechanism. This is really pretty obvious when you consider that there's an abundance of implementations of all combinations of (RC, tracing)(GIL, no GIL). Python and Ruby's main implementations both chose a GIL for simplicity's sake (and an at the time safe assumption that single-core performance was more important than multi-core), but most C++ refcounting code uses interlocked counters and the JVM has obviously never used a GIL.
- chadaustin 12y ago
  Sure, but you'll notice the loop I gave never releases the objects, so the GC would still kick in, assuming the behavior I described.
koenigdavidmj 12y ago
Incidentally, if you're worried about the appends' reallocations throwing off your linear time, take a look at Objects/listobject.c : /* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
- chadaustin 12y ago
  Sure, the growth of the list itself is not quadratic, but the allocations of the new objects (the {} part) invokes a GC every K iterations, and a naive, stop-the-world, mark-and-sweep GC is O(n) in number of live objects.

xxxyy 12y ago

Python uses reference counting to save on GC time. This is one of the reasons why it has GIL.

stormbrew 12y ago
There's nothing unique to refcounting garbage collection that implies you need or should use a GIL. Most naive tracing collectors also have one so they can stop the world and trace every thread's stack at the same time. In both cases there are workarounds that reduce throughput as a tradeoff for decreasing latency (and the two mechanisms start to converge into similar algorithms, incidentally).
- foobar2020 12y ago
  There is: you either have to use atomic operations on all the reference counters, which is costly, and not available on all platforms, or you can have only one thread active at a time. This is the most classic problem: "x == 0"; parallel execution of "x += 1" and "x += 1"; now "x == 1" or "x == 2". I don't see why tracing collectors need GIL in particular to stop all threads, i.e. why should only one thread be running at a time.
  - stormbrew 12y ago
    I'm not sure why you seem to feel your first paragraph here is a disagreement with what I said. As you point out, there is a well known way to have refcounting act correctly in the face of multiple threads. There are other ways as well involving per-thread shadow counts and such, but that is the most basic way to (as I said) trade throughput for latency. Re. your second paragraph, it is again not inherent to the algorithm, but it does greatly simplify things. In particular, pretty much all tracing algorithms require at least some kind of stop the world event, though some can make this event very limited in duration. It is much much easier (and results in greater throughput) to stop the world if only one thread is running at a time, because you just do your collection when that one thread triggers a heap mutation. If you have multiple threads running at once you need to coordinate when you stop the world, which means waiting for the threads to all wind up in a state where they can be stopped (which gets a lot harder if, say, one of the threads never allocates because it's in a tight loop). If it takes too long to do this coordination, your heap might explode on you. Again, what I'm saying is that a GIL is not an inherent feature of either garbage collection mechanism. This is really pretty obvious when you consider that there's an abundance of implementations of all combinations of (RC, tracing)(GIL, no GIL). Python and Ruby's main implementations both chose a GIL for simplicity's sake (and an at the time safe assumption that single-core performance was more important than multi-core), but most C++ refcounting code uses interlocked counters and the JVM has obviously never used a GIL.
chadaustin 12y ago
Sure, but you'll notice the loop I gave never releases the objects, so the GC would still kick in, assuming the behavior I described.

koenigdavidmj 12y ago

Incidentally, if you're worried about the appends' reallocations throwing off your linear time, take a look at Objects/listobject.c : /* This over-allocates proportional to the list size, making room * for additional growth. The over-allocation is mild, but is * enough to give linear-time amortized behavior over a long * sequence of appends() in the presence of a poorly-performing * system realloc(). * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... */ new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

chadaustin 12y ago
Sure, the growth of the list itself is not quadratic, but the allocations of the new objects (the {} part) invokes a GC every K iterations, and a naive, stop-the-world, mark-and-sweep GC is O(n) in number of live objects.