Queue cleanup

[Paul Rubin]

Lawrence D'Oliveiro <ldo at geek-central.gen.new_zealand> writes:
>> A minimal naive implementation indeed doubles the memory requirements,
>> but from a Python perspective where every integer takes something like
>> 24 bytes already, even that doesn't seem so terrible.
>
> Doubling 24 is less terrible than doubling 4 or 8?? You’re kidding, right?

No, it would be doubling 4 or 8 bytes.  The extra overhead like the
reference count would not be there to bloat up the integer like in
Python.

>> More sophisticated implementations use multiple small heaps or other tricks.
> More and more complications to patch up the idea. At some point, you have to 
> admit there is something fundamentally flawed about the whole concept.

Oh sheesh, that's silly.  Every area of programming where performance
matters is full of optimization tricks.  Look at any serious database
implementation for example.  Or any compiler.  Look at Python's
implementation of dictionaries.  Yeah, the optimizations add complexity
to improve performance, sometimes even in heuristic ways that can fail.
That doesn't mean the concepts are fundamentally flawed.  GC is no
different.

>> The new heap is filled sequentially so accesses to it will have good
>> locality.
> what does matter is the frequency distribution of references,

Sorry, just I meant during the gc operation itself.  The gc's access
pattern in the new heap is completely sequential as the gc just copies
stuff to it linearly from from the old heap, bumping a pointer upwards.
The access pattern when the user application is running is of course not
predictable.

> Your generational garbage collector completely breaks this assumption, by 
> regularly forcing an access to every single object in the heap. Cache-
> thrashing, anyone?

In the minor collections, the whole minor heap fits in cache, so there's
no thrashing.  The major collections can use a different strategy, or
you can simply rely on their relative infrequency.  Why do you speculate
like this?  If you run a GHC program with profiling active, it tells you
exactly how much time is spent in minor gc and how much time is in major
gc, and it's all generally pretty tolerable unless your program has
bugs.  (Unfortunately Haskell programs are notoriously susceptable to a
certain type of bug that causes them to still give the right answers,
but use much more memory than they should.  The usual sign of that
happening is high gc load).

>> It's also the case that programs with very large memory consumption tend
>> to use most of the memory for large arrays that don't contain pointers
> But your generational garbage collector still has to copy those very large 
> objects to the new heap, with all the cache-hostile consequences therefrom.

Not necessarily, depends on how you write the program and how the gc works.

> By the way, isn’t this the opposite of the array-of-pointers example you 
> were using earlier to try to cast reference-counting in a bad light?

I wasn't trying to cast reference counting in a bad light, I was
pointing out that reference counting can experience pauses just like
traditional gc approaches.  Most programs including "soft" real time
programs can tolerate an occasional pause.  If your program is not one
of those, and you need guaranteed upper bounds on pauses so you can't
use traditional gc, switching from gc to reference counting won't save
you.

> It seems to me a reference count would work very well for such a
> large, simple object.

Mark/sweep would do it too.  Some gc's use a hybrid approach, with
mark/sweep for older or larger objects.

> But not garbage collection. This is because of the asymmetric way in
> which hardware has become faster:...  the effectiveness of that
> caching depends crucially on certain assumptions about the runtime
> behaviour of the programs: and garbage collection breaks those
> assumptions. ...
> You may want to enlighten yourself by meditating on this seeming paradox of 
> modern computing hardware: memory is cheap, but accessing memory is 
> expensive.

I'm interested in receiving enlightment if you've got some pointers into
the research literature that back up your views.  Right now it sounds
like you're going by some intuitions you have that aren't backed up by
evidence.  Anyone who has performance-tuned a program knows that
intuition can give reasonable starting points for experiments and
measurements, but once the results start coming in, a lot of the
intuitions end up invalidated.  

By now, there is enough experimental and theoretical literature about gc
that opinions like yours, that don't seem to be grounded in any
knowledge of that literature, are not very persuasive no matter how
superficially attractive the raw intuition might be.  Especially in your
case, where you seem to have decided ahead of time what conclusion you
want to reach and are looking for ways to justify it.