On 2024-03-08 2:41 p.m., George Neuner wrote:
> On Thu, 7 Mar 2024 16:02:45 -0500, Robert Finch <robfi680@gmail.com>
> wrote:
>
>> A page marked RWE=000 is an unusable page. Perhaps to signal bad memory.
>> Or perhaps as a hidden data page full of comments or remarks. If its not
>> readable-writeable or executable what is it? Nothing should be able to
>> access it, except maybe the machine/debug operating mode.
>
> The ability to change (at least data) pages between "untouchable" and
> RW is required for MMU assisted incremental GC. If the GC also
> handles code, then it must be able to mark pages executable as well.
>
> If an "untouchable" page can't be manipulated by user software, then
> you've disallowed an entire class of GC systems.

Garbage collection seems to be common.

I plan on having garbage collection as part of the OS. There is a shared
hardware-card table involved. So, I guess that would disallow user
garbage collectors using untouchable pages. The MMU could be faked out
using a VM, so I have read.

On 3/8/2024 5:13 PM, David W Schroth wrote:
> On Thu, 7 Mar 2024 11:58:53 -0800, Stephen Fuld
> <sfuld@alumni.cmu.edu.invalid> wrote:
>
>> On 3/5/2024 9:32 AM, MitchAlsup1 wrote:
>>
>> snip
>>
>>> I also believe in the tension between pages that are too small and those
>>> that are too large. 256B is widely seen as too small (VAX). I think most
>>> people are comfortable in the 4KB range. I think 64KB is too big since
>>> something like cat needs less code, less data, and less stack space than
>>> 1 single 64KB page and another 64KB page to map cat from its VAS. So, now;
>>> instead of four* 4KB pages (16KB ={code, data, stack, map} ) we now need
>>> four 64KB pages 256KB. It is these small applications that drive the
>>> minimum page size down.
>>
>> In thinking about this, an idea occurred to me that may ease this
>> tension some. For a large page, you introduce a new protection mode
>> such that, for example, the lower half of the addresses in the page are
>> execute only, and the upper half are read/write enabled. This would
>> allow the code and the data, and perhaps even the stack for such a
>> program to share a single page, while still maintaining the required
>> access protection. I think the hardware to implement this is pretty
>> small. While the benefits of this would be modest, if such "small
>> programs" occur often enough it may be worth the modest cost of the
>> additional hardware.
>
> I would suggest that your proposal would be better done by splitting
> access/protection from virtual to physical translation (think Mill
> turfs).

I think we are in general agreement here. As you implied, the
fundamental problem is that most current systems "overload" two pieces
of functionality (memory management and protection) onto a single
mechanism (paging). I like Mill's approach as it clearly separates the
two functions, though it does require more hardware, and I am not sure
how much easier it is for them than it would be for other systems since
they use a single address space. My proposal was for a low hardware
cost and easily implemented mechanism.

> I suppose OS2200 could use our existing protection to
> implement what you propose, but we haven't (largely because there
> seems to be no need/call for the capability).

Since the 2200 already separates the protection function (banking) from
the memory management function (paging), I think all that would be
required is to allow multiple banks, perhaps even from multiple programs
to use different parts of a page. But I agree that, with ~16 KB pages,
the savings would be much less than if larger pages were used, so the
benefits would be modest at best and probably not worth the effort.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

Lynn Wheeler wrote:
>
> Nearly 15yrs later at Dec81 ACM SIGOPS, Jim Gray ask if I could help a
> Tandem co-worker get Stanford Phd .... it involved similar global LRU to
> the work that I had done in the 60s and there were "local LRU" forces
> from the 60s lobbying hard not to award a Phd (that wasn't "local
> LRU"). I had real live data from a CP/67 with global LRU on 768kbyte
> (104 pageable pages) 360/67 with 80users that had better response and
> throughput compared to a CP/67 (with nearly identical type of workload
> but 35users) that implemented 60s "local LRU" implementation and 1mbyte
> 360/67 (155 pageable pages after fixed storage) ... aka half the users
> and 50% more real paging storage.

I assume by "local LRU" you mean local working set management,
as opposed to global working set e.g. WSClock.

Are you saying some people tried to block someone from getting a PhD
because he researched a different working set management than their
pet approach?

If so, wow...

On 3/7/2024 9:13 PM, Robert Finch wrote:
> On 2024-03-07 2:58 p.m., Stephen Fuld wrote:
>> On 3/5/2024 9:32 AM, MitchAlsup1 wrote:
>>
>> snip
>>
>>> I also believe in the tension between pages that are too small and
>>> those that are too large. 256B is widely seen as too small (VAX). I
>>> think most
>>> people are comfortable in the 4KB range. I think 64KB is too big since
>>> something like cat needs less code, less data, and less stack space than
>>> 1 single 64KB page and another 64KB page to map cat from its VAS. So,
>>> now;
>>> instead of four* 4KB pages (16KB ={code, data, stack, map} ) we now need
>>> four 64KB pages 256KB. It is these small applications that drive the
>>> minimum page size down.
>>
>> In thinking about this, an idea occurred to me that may ease this
>> tension some.  For a large page, you introduce a new protection mode
>> such that, for example, the lower half of the addresses in the page
>> are execute only, and the upper half are read/write enabled.  This
>> would allow the code and the data, and perhaps even the stack for such
>> a program to share a single page, while still maintaining the required
>> access protection.  I think the hardware to implement this is pretty
>> small.  While the benefits of this would be modest, if such "small
>> programs" occur often enough it may be worth the modest cost of the
>> additional hardware.
>>
>>
> I had thoughts along this line too. I have added user access rights for
> each 1/4 of a page. Only a single 64kB page split in four is needed for
> a small app then.

Yes, similar. I suspect your solution is more general than mine and
thus handles more cases, but requires more hardware, especially bits in
the PTE. It's all a tradeoff.

--
- Stephen Fuld
(e-mail address disguised to prevent spam)

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.

>So, I guess that would disallow user
>garbage collectors using untouchable pages. The MMU could be faked out
>using a VM, so I have read.

Yes, a VM can emulate MMU operation, but currently that requires using
a hypervisor - a heavyweight solution that also requires a guest OS to
run the program.

There are a number of light(er) weight VMs for running programs in
managed environments [which include GC] ... but all of them have to
run under an OS and are at its mercy.

GCs that use no-access pages are not rare, and they are just one class
of MMU assisted GC systems. There are a number of ways a collector
can leverage the MMU to help.

On Sun, 10 Mar 2024 14:29:52 -0400, George Neuner
<gneuner2@comcast.net> wrote:

>Problem is - whatever [GC] you choose - it will be wrong and have bad
>performance for some important class of GC'd applications.

"bad performance" may mean "slow", but also may mean memory use much
higher than should be necessary.

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.

George Neuner <gneuner2@comcast.net> writes:

> On Sun, 10 Mar 2024 14:29:52 -0400, George Neuner
> <gneuner2@comcast.net> wrote:
>
>
>> Problem is - whatever [GC] you choose - it will be wrong and have bad
>> performance for some important class of GC'd applications.
>
> "bad performance" may mean "slow", but also may mean memory use much
> higher than should be necessary.

Understood. And there are other relevant metrics as well, as
for example not throughput but worst-case latency.

On 2024-03-10 7:53 p.m., George Neuner wrote:
> On Sun, 10 Mar 2024 14:29:52 -0400, George Neuner
> <gneuner2@comcast.net> wrote:
>
>
>> Problem is - whatever [GC] you choose - it will be wrong and have bad
>> performance for some important class of GC'd applications.
>
> "bad performance" may mean "slow", but also may mean memory use much
> higher than should be necessary.

I have not chosen a specific class yet. It will be incremental though.
There is a timer or two dedicated in the system for garbage collection.
It may be left up to the app to do garbage collection, with timing
notifications sent to the app. IRL garbage collection is done periodically.

GC is prevalent in many applications, it should be supported somehow.

On Mon, 11 Mar 2024 09:32:40 -0700, Tim Rentsch
<tr.17687@z991.linuxsc.com> wrote:

>George Neuner <gneuner2@comcast.net> writes:
>
>> On Sun, 10 Mar 2024 14:29:52 -0400, George Neuner
>> <gneuner2@comcast.net> wrote:
>>
>>
>>> Problem is - whatever [GC] you choose - it will be wrong and have bad
>>> performance for some important class of GC'd applications.
>>
>> "bad performance" may mean "slow", but also may mean memory use much
>> higher than should be necessary.
>
>Understood. And there are other relevant metrics as well, as
>for example not throughput but worst-case latency.

If latency is the primary concern, then you should use a deterministic
system such as Baker's Treadmill.

Treadmill essentially is just a set of linked lists, and collectio
operations like marking and sweeping simply move blocks from one list
to another. But you pay for that determinism with space - compared to
other systems, Treadmills have a lot of per-block metadata.

Note that for allocating and freeing to be deterministic, a Treadmill
has to work with fixed size blocks. But you can run multiple
Treadmills for common block sizes, with a catchall for big blocks.
Some malloc/free style allocators already work like this, using
separate lists for some commonly requested block sizes.

Depending on how you handle the metadata, Treadmills also are amenable
to coalescing free space and/or compacting the heap / working set. But
note that these types of operations can't be made deterministic.

George Neuner <gneuner2@comcast.net> writes:

> On Mon, 11 Mar 2024 09:32:40 -0700, Tim Rentsch
> <tr.17687@z991.linuxsc.com> wrote:
>
>> George Neuner <gneuner2@comcast.net> writes:
>>
>>> On Sun, 10 Mar 2024 14:29:52 -0400, George Neuner
>>> <gneuner2@comcast.net> wrote:
>>>
>>>
>>>> Problem is - whatever [GC] you choose - it will be wrong and have bad
>>>> performance for some important class of GC'd applications.
>>>
>>> "bad performance" may mean "slow", but also may mean memory use much
>>> higher than should be necessary.
>>
>> Understood. And there are other relevant metrics as well, as
>> for example not throughput but worst-case latency.
>
> If latency is the primary concern, then you should use a deterministic
> system such as Baker's Treadmill. [...]

Does this mean you aren't going to answer my other question?

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?

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.

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.

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.

I'm guessing this probably didn't really answer your question, but it
was fun to write.
;-)

George

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.