Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.arch
Subject: Re: Tonight's tradeoff
Date: Sun, 28 Apr 2024 15:27:41 -0700
Organization: A noiseless patient Spider
Lines: 163
Message-ID: <86h6flunqa.fsf@linuxsc.com>
References: <us9ffo$argb$1@dont-email.me> <us9vc5$ffl5$1@dont-email.me> <usaciv$ibv9$1@dont-email.me> <e7e6d152876f385e78404b06eef87121@www.novabbs.org> <usbngu$tq9s$1@dont-email.me> <uscf92$12ifq$1@dont-email.me> <4072ddfc6031310c0f2a3237e6cb455e@www.novabbs.org> <usda1n$18gea$1@dont-email.me> <cmgmuilsa9bco9oboe9c46igr6dogb2ikc@4ax.com> <usgdrh$2033i$1@dont-email.me> <thlruit3i6t2jq9dt90nfvbfaljs0beg4a@4ax.com> <86zfv4rat6.fsf@linuxsc.com> <id52vid449tib9q6gu1i07n2k7g3i1o3ts@4ax.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Mon, 29 Apr 2024 00:27:44 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="c36476fd6bd91582cb5d0726d3f1692e";
	logging-data="1371881"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19JAkzKicxjony0a0BXM9iR//1CpTb/CIc="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:GhnNG3vjCUaCDdVTRlMlHEeyLFc=
	sha1:3mcnumRPxN829lop1ukh1MwmyEI=
Bytes: 7769

George Neuner <gneuner2@comcast.net> writes:

> On Mon, 11 Mar 2024 09:29:57 -0700, Tim Rentsch
> <tr.17687@z991.linuxsc.com> wrote:
>
>> George Neuner <gneuner2@comcast.net> writes:
>>
>>> On Fri, 8 Mar 2024 20:26:08 -0500, Robert Finch <robfi680@gmail.com>
>>> wrote:
>>>
>>>> I plan on having garbage collection as part of the OS.  There
>>>> is a shared hardware-card table involved.
>>>
>>> What kind?
>>> [Actually "kind" is the wrong word because any non-toy, real
>>> world GC will need to employ a combination of techniques.  So
>>> the question really should be "in what major class is your GC"?]
>>>
>>> Problem is - whatever you choose - it will be wrong and have bad
>>> performance for some important class of GC'd applications.
>>
>> I'm curious to know what you consider to be the different kinds,
>> or classes, of GC, and the same question for applications.
>>
>> Certainly, for any given GC implementation, one can construct an
>> application that does poorly with respect to that GC, but that
>> doesn't make the constructed application a "class".  For the
>> statement to have meaningful content there needs to be some kind
>> of identification of what are the classes of GCs, and what are
>> the classes of applications.
>
> Feeling mathematical are we?

If you're trying to say I make an effort to be accurate and
precise in my writing, I plead guilty as charged.

> Every application contains delineated portions of its overall
> allocation profile which correspond closely to portions of the
> profiles of other applications.
>
> If a given profile performs poorly under a given GC, it is
> reasonable to infer that other applications having corresponding
> profiles also will perform poorly while those profiles are in
> force.

An empty, circular observation.  Very disappointing.

> That said ...
>
>
>
> GC systems - including their associated allocator(s) - are categorized
> (better word?) by their behavior.  Unfortunately, behavior is
> described by a complex set of implementation choices.
>
> Understand that real world GC typically implement more than one
> algorithm, and often the algorithms are hybridized - derived from and
> relatable to published algorithms, but having unique mix of function
> that won't be found "as is" in any search of literature.  [In truth,
> GC literature tends to leave a lot as exercise for the reader.]
>
> GC behavior often is adaptive, reacting to run time conditions:  e.g.,
> based on memory fragmentation it could shift between non-moving
> mark/sweep and moving mark/compact.  It may also employ differing
> algorithms simultaneously in different spaces, such as being
> conservative in stacks while being precise in dynamic heaps, or being
> stop-world in thread private heaps while being concurrent or parallel
> in shared heaps.  Etc.
>
>
> Concurrent GC (aka incremental) runs as a co-routine with the mutator.
> These systems are distinguished by how they are triggered to run, and
> what bounds may be placed on their execution time.  There are
> concurrent systems having completely deterministic operation [their
> actual execution time, of course, may depend on factors beyond the
> GC's control, such as multitasking, caching or paging.]
>
> Parallel GC may be both prioritized and scheduled.  These systems may
> offer some guarantees about the percentage of (application) time given
> to collector vs mutator(s).
>
>
> Major choices:
>
>  -  precise or conservative?
>  -  moving or non-moving?
>  -  tracing (marking)?
>  -  copying / compacting?
>  -  stop-world, concurrent, or parallel?
>
>  -  single or multiple spaces?
>  -  semispaces?
>  -  generational?
>
> Minor choices:
>
>  -  software-only or hardware (MMU) assisted?
>  -  snapshot at beginning?
>
>  -  bump or block allocation?
>  -  allocation color?
>
>  -  free blocks coalesced? {if not compacting}
>
>  -  multiple mutators?
>  -  mutation color?
>  -  writable shared objects?
>  -  FROM-space mutation?
>  -  finalization?
>
>
> Note that all of these represent free dimensions in design.  As
> mentioned above, any particular system may implement multiple
> collection algorithms each embodying a different set of choices.

I'm familiar with many or perhaps most of the variations
and techniques used in garbage collection.  That isn't
what I was asking about.

> You may wonder why I didn't mention "sweeping" ... essentially it is
> because sequential scan is more an implementation detail than a
> technique.  Although "mark/sweep" is a well established technique, it
> is the marking (tracing) that really defines it.  Then too, modern
> collectors often are neither mark/sweep nor copying as presented in
> textbooks:  e.g., there are systems that mark and copy, systems that
> sweep and copy (without marking), and "copying" systems in which
> copies are logical and nothing actually changes address.
>
> Aside: all GC can be considered to use [logical] semispaces because
> all have the notion of segregated FROM-space and TO-space during
> collection.  True semispaces are a set of (address) contiguous spaces
> - not necessarily equally sized - which are rotated as targets for new
> allocation.  True semispaces do imply physical copying [but see the
> Treadmill for an example of "non-moving copy" using logical
> semispaces].
>
>
>
> So what do I consider to be the "kind" of a GC?
>
> The choices above pretty much define the extent of the design space
> [but note I did intentionally leave out reference counting].  However,
> the first 8 choices are structural, whereas the rest specify important
> characteristics but don't affect structure.
>
> A particular "kind" might be, e.g.,
>   "precise, generational, multispace, non-moving, concurrent
>    tracer".
> and so on.

In effect what you are saying is that if we list all the possible
attributes that a GC implementation might have, we can charactrize
what kind of GC it is by giving its value for each attribute.  Not
really a helpful statement.

> I'm guessing this probably didn't really answer your question,

Your comments didn't address either of my questions, nor as best
I can tell even make an effort to do so.

> but it was fun to write. ;-)

I see.  Next time I'll know better.