Account Options

  1. Sign in
The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Google Groups Home
« Groups Home
self-hosting gc, narrowed
There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic.
There was an error processing your request. Please try again.
flag
  Messages 76 - 100 of 121 - Collapse all  -  Translate all to Translated (View all originals) < Older  Newer >
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Thomas Bushnell, BSG  
View profile  
 More options Mar 13 2002, 4:30 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: tb+use...@becket.net (Thomas Bushnell, BSG)
Date: 13 Mar 2002 13:25:09 -0800
Local: Wed, Mar 13 2002 4:25 pm
Subject: Re: self-hosting gc, narrowed

Sander Vesik <san...@haldjas.folklore.ee> writes:
> Ah, ok, so you would have a "non-proccess based" system. Or rather,
> a system where processes would be represented as threads?

Yes, absolutely.

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Sander Vesik  
View profile  
 More options Mar 13 2002, 5:47 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Sander Vesik <san...@haldjas.folklore.ee>
Date: Wed, 13 Mar 2002 22:47:26 +0000 (UTC)
Local: Wed, Mar 13 2002 5:47 pm
Subject: Re: self-hosting gc, narrowed
In comp.lang.scheme Thomas Bushnell, BSG <tb+use...@becket.net> wrote:

> Sander Vesik <san...@haldjas.folklore.ee> writes:

>> Actually, if the OS cannot trust (but needs to), then allowing for pointers
>> outside of that area is a bug. Because the user can then effectively
>> change the data dispite the fact that the OS supposedly secured it.

> No, no, you don't really understand the permission model.  The OS
> *knows* that the user can "change the data", and that's not harmful at
> all, as long as the OS exercises proper care when reading it.

How can I understand a permission model that has not been presented? 8-)

--
        Sander

+++ Out of cheese error +++


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Thomas Bushnell, BSG  
View profile  
 More options Mar 13 2002, 6:00 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: tb+use...@becket.net (Thomas Bushnell, BSG)
Date: 13 Mar 2002 14:58:16 -0800
Local: Wed, Mar 13 2002 5:58 pm
Subject: Re: self-hosting gc, narrowed

Sander Vesik <san...@haldjas.folklore.ee> writes:
> In comp.lang.scheme Thomas Bushnell, BSG <tb+use...@becket.net> wrote:
> > Sander Vesik <san...@haldjas.folklore.ee> writes:
> >> Actually, if the OS cannot trust (but needs to), then allowing
> >> for pointers outside of that area is a bug. Because the user can
> >> then effectively change the data dispite the fact that the OS
> >> supposedly secured it.

> > No, no, you don't really understand the permission model.  The OS
> > *knows* that the user can "change the data", and that's not harmful at
> > all, as long as the OS exercises proper care when reading it.

> How can I understand a permission model that has not been presented? 8-)

Here's the real clincher.

The gc needs access to primitives that can destroy the memory model of
the system if misused.

If everyone is sharing memory, then the gc is able to hose everybody.

Accordingly, the gc must be privileged.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Joe Marshall  
View profile  
 More options Mar 13 2002, 11:35 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: "Joe Marshall" <prunesqual...@attbi.com>
Date: Thu, 14 Mar 2002 04:32:15 GMT
Local: Wed, Mar 13 2002 11:32 pm
Subject: Re: self-hosting gc, narrowed

"Thomas Bushnell, BSG" <tb+use...@becket.net> wrote in message
news:87henkqhzy.fsf@becket.becket.net...

> "Joe Marshall" <prunesqual...@attbi.com> writes:

> > While I tend to doubt that the processor can take a fault like this
> > in less than 100 instructions (well the *count* may be less, but I bet
> > the execution time isn't), I have seen lots of cases where fast consing
> > is used.

> IIRC, the Utah Flux group executed a syscall trap in a total of less
> than a hundred exceptions, and that was doing some message passing
> too.

> I'm not talking about doing this on Unix; geez, if you have to go
> through the kernel, the signal code, user interrupt handlers, and all
> the rest, it's a pain.

I was speculating that the time it took between the processor issuing
a write to the non-existant page until the processor was executing
the code that created the page would be quite high.

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Thomas Bushnell, BSG  
View profile  
 More options Mar 14 2002, 3:10 am
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: tb+use...@becket.net (Thomas Bushnell, BSG)
Date: 14 Mar 2002 00:06:21 -0800
Local: Thurs, Mar 14 2002 3:06 am
Subject: Re: self-hosting gc, narrowed

"Joe Marshall" <prunesqual...@attbi.com> writes:
> I was speculating that the time it took between the processor issuing
> a write to the non-existant page until the processor was executing
> the code that created the page would be quite high.

VM ain't really that slow these days.  It can be high, but it's
certainly not on the order of 125,000 instructions, which is what it
costs to execute two extra instructions per cons.

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Daniel C. Wang  
View profile  
 More options Mar 14 2002, 10:27 am
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: nospam+dcw...@agere.com (Daniel C. Wang)
Date: 14 Mar 2002 10:24:27 -0500
Local: Thurs, Mar 14 2002 10:24 am
Subject: Re: self-hosting gc, narrowed

tb+use...@becket.net (Thomas Bushnell, BSG) writes:
{stuff deleted}

> If everyone is sharing memory, then the gc is able to hose everybody.

> Accordingly, the gc must be privileged.

Not if you're type system can gurantee your GC is type-preserving.

http://www.cs.princeton.edu/~danwang/Papers/tpsrvgc/

http://flint.cs.yale.edu/flint/publications/gc.html

http://ncstrl.cs.princeton.edu/expand.php?id=TR-640-01

Extending the proof that the GC is value preserving is still an open
question, but I think within the realm of "standard" type systems.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Ji-Yong D. Chung  
View profile  
 More options Mar 15 2002, 2:49 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: "Ji-Yong D. Chung" <virtualcy...@erols.com>
Date: Fri, 15 Mar 2002 14:58:34 -0500
Local: Fri, Mar 15 2002 2:58 pm
Subject: Re: self-hosting gc, narrowed
Hi

"Thomas Bushnell, BSG" <tb+use...@becket.net> wrote in message
news:878z8xn17o.fsf@becket.becket.net...

> Sander Vesik <san...@haldjas.folklore.ee> writes:

> > This can lead to unwanted amounts of fragmentation very easily if
> > data is accessed from more than one thread.
> ...
> But you are right that this is a worry.  So my idea for that problem
> (which is really quite vague at this point) is to use a generational
> copy scheme, which moves data into global heaps and gets (hopefully
> better) locality for such data.

    When you implement a generational collector, each arena
will have a finite size.  Thus, if your overall heap size is 1 meg,
and each arena is 300k (assuming you have approximately 3
generations).  Each arena is further partitioned for
each "native Scheme object" type.

    So, you will end up with many small heaps.

    In such cases, if your nursery allocates a relatively large
object (i.e., vector of very large dimension), it will not
be possible to promote that object to the next generation
(during a collection), because the available to-space in the
next generation will not be sufficient.

    There are two ways to deal with the problem -- (1)
introduce big objects and/or (2) use expandable arenas.
Either case, it is a pain in the neck.

=====================

    You might consider BIBOP.

    Personally, I have found Kent Dybvig's paged memory
to be useful in this regard.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Rahul Jain  
View profile  
 More options Mar 15 2002, 3:40 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Rahul Jain <rj...@sid-1129.sid.rice.edu>
Date: 15 Mar 2002 14:34:37 -0600
Local: Fri, Mar 15 2002 3:34 pm
Subject: Re: self-hosting gc, narrowed
"Ji-Yong D. Chung" <virtualcy...@erols.com> writes:

> When you implement a generational collector, each arena will have a
> finite size. Thus, if your overall heap size is 1 meg, and each
> arena is 300k (assuming you have approximately 3 generations).  Each
> arena is further partitioned for each "native Scheme object" type.

WHY?? No Lisp implementation I know of does such a crazy thing. I
never knew there were people who wanted to make their implementations
that bad.

>     So, you will end up with many small heaps.

If that were the case, how on earth would any reasonable
implementations of any garbage-collected, strongly-typed language
exist?

>     In such cases, if your nursery allocates a relatively large
> object (i.e., vector of very large dimension), it will not
> be possible to promote that object to the next generation
> (during a collection), because the available to-space in the
> next generation will not be sufficient.

You could collect the next generation, too...

>     There are two ways to deal with the problem -- (1)
> introduce big objects

I assume that means promoting the object to an older generation or
allocating it outside of the generations. This is the typical
strategy.

> and/or (2) use expandable arenas.
> Either case, it is a pain in the neck.

It is?

--
-> -/                        - Rahul Jain -                        \- <-
-> -\  http://linux.rice.edu/~rahul -=-  mailto:rj...@techie.com   /- <-
-> -/ "Structure is nothing if it is all you got. Skeletons spook  \- <-
-> -\  people if [they] try to walk around on their own. I really  /- <-
-> -/  wonder why XML does not." -- Erik Naggum, comp.lang.lisp    \- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
   (c)1996-2002, All rights reserved. Disclaimer available upon request.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Ji-Yong D. Chung  
View profile  
 More options Mar 17 2002, 7:14 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: "Ji-Yong D. Chung" <virtualcy...@erols.com>
Date: Sun, 17 Mar 2002 19:24:22 -0500
Local: Sun, Mar 17 2002 7:24 pm
Subject: Re: self-hosting gc, narrowed
Hi
"Rahul Jain" <rj...@sid-1129.sid.rice.edu> wrote in message

news:87663xwowy.fsf@photino.sid.rice.edu...

> "Ji-Yong D. Chung" <virtualcy...@erols.com> writes:

> > When you implement a generational collector, each arena will have a
> > finite size. Thus, if your overall heap size is 1 meg, and each
> > arena is 300k (assuming you have approximately 3 generations).  Each
> > arena is further partitioned for each "native Scheme object" type.

> WHY?? No Lisp implementation I know of does such a crazy thing. I
> never knew there were people who wanted to make their implementations
> that bad.

    Actually, I have made an error in using the term "arena."  I meant
that each generation is further partitioned into arenas.

    If I remember right, SML/NJ (correct me here, as I am walking on
thin ice!!!), I think partitions heap as I said.  I thought the collector
for Larceny did the same.  It has been a while since I looked at
their source code, though.

    BIBOP maps each object type into different arenas.

    In my implementation, I did not further partition each
arena -- I did not use traditional BIBOP object mapping scheme.

> >     So, you will end up with many small heaps.

> If that were the case, how on earth would any reasonable
> implementations of any garbage-collected, strongly-typed language
> exist?

    Without specifics, this is not really answerable.  Also,
I am rather ignorant on the topic of using generational gc for
strongly typed language.

> >     In such cases, if your nursery allocates a relatively large
> > object (i.e., vector of very large dimension), it will not
> > be possible to promote that object to the next generation
> > (during a collection), because the available to-space in the
> > next generation will not be sufficient.

> You could collect the next generation, too...

    That would not work -- because the maximum
to-space is bound by the size of the arena.

> >     There are two ways to deal with the problem -- (1)
> > introduce big objects

> I assume that means promoting the object to an older generation or
> allocating it outside of the generations. This is the typical
> strategy.

    Yes.

> > and/or (2) use expandable arenas.
> > Either case, it is a pain in the neck.

> It is?

    Big objects are pain in the neck, because these
objects need to be treated specially.  They need to be
scanned for pointers, after "normal collection."  Furthermore,
it can introduce heap fragmentation.  (I have read that, _in practice_,
fragmentation is not really a problem for Chez Scheme or
Larceny -- but, at least, it is an issue one needs to think about).

    Having expandable arenas are pain in the neck, because
this means one has to make arenas of different sizes.  This
also means keeping track of extra parameters for computing
available heap space for promotion.  When the arena sizes
are identical, one can calculate the available promotion space
based on simple algorithms.

    Take for example the following algorithm for computing available
arena space for promotion: first, collect _within_ the same
generation, doing a simple transfer of objects from from-space
to to-space.  If objects survive twice, we promote.

    The preceding algorithm is inefficient, because it copies
objects at least once prior to copying for promotion..

    In any case, there are additional problems with
expandable arenas -- I am not saying they are very
difficult to implement.  It is just that, IMHO, one loses
a lot of design elegance and introduces unnecessary
complexity.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Rahul Jain  
View profile  
 More options Mar 17 2002, 7:40 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Rahul Jain <rj...@sid-1129.sid.rice.edu>
Date: 17 Mar 2002 18:33:14 -0600
Local: Sun, Mar 17 2002 7:33 pm
Subject: Re: self-hosting gc, narrowed
"Ji-Yong D. Chung" <virtualcy...@erols.com> writes:

> Hi
> "Rahul Jain" <rj...@sid-1129.sid.rice.edu> wrote in message
> news:87663xwowy.fsf@photino.sid.rice.edu...
> > "Ji-Yong D. Chung" <virtualcy...@erols.com> writes:
> > > When you implement a generational collector, each arena will have a
> > > finite size. Thus, if your overall heap size is 1 meg, and each
> > > arena is 300k (assuming you have approximately 3 generations).  Each
> > > arena is further partitioned for each "native Scheme object" type.
> > WHY?? No Lisp implementation I know of does such a crazy thing. I
> > never knew there were people who wanted to make their implementations
> > that bad.
>     Actually, I have made an error in using the term "arena."  I meant
> that each generation is further partitioned into arenas.

I understood what you were saying even though the terminology may have
not been what I was used to. It was the partitioning of the
generations by type that I don't understand.

>     If I remember right, SML/NJ (correct me here, as I am walking on
> thin ice!!!), I think partitions heap as I said.  I thought the collector
> for Larceny did the same.  It has been a while since I looked at
> their source code, though.

That's a really strange way to do things. I can't imagine what the
material gain would be. Maybe a few bits on the fixnum type?

>     Without specifics, this is not really answerable.  Also,
> I am rather ignorant on the topic of using generational gc for
> strongly typed language.

Typically, the way I understand Lisp GCs work is that each object has
type information in its header, which allows the GC to know how large
the object is and whether (and where) it contains references to other
objects.

>     Big objects are pain in the neck, because these
> objects need to be treated specially.  They need to be
> scanned for pointers, after "normal collection."  Furthermore,
> it can introduce heap fragmentation.  (I have read that, _in practice_,
> fragmentation is not really a problem for Chez Scheme or
> Larceny -- but, at least, it is an issue one needs to think about).

it's true that you have to make special considerations for such
objects. If there are enough of them to cause a problem, you're
probably using the wrong gc (settings) for your application.

>     In any case, there are additional problems with
> expandable arenas -- I am not saying they are very
> difficult to implement.  It is just that, IMHO, one loses
> a lot of design elegance and introduces unnecessary
> complexity.

Yes, I'd have to agree with this now. Expandable arenas are really a
waste of effort, since it would be easier to just have them fit some
fixed portion of memory space, and map only what it needed for the
current generation size. I suppose this is effectively "expandable" in
that the generation does not chew up more VM than the generation's
size, and the generations can grow to some size that is fixed by the
implementation's choice of VM layout.

--
-> -/                        - Rahul Jain -                        \- <-
-> -\  http://linux.rice.edu/~rahul -=-  mailto:rj...@techie.com   /- <-
-> -/ "Structure is nothing if it is all you got. Skeletons spook  \- <-
-> -\  people if [they] try to walk around on their own. I really  /- <-
-> -/  wonder why XML does not." -- Erik Naggum, comp.lang.lisp    \- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
   (c)1996-2002, All rights reserved. Disclaimer available upon request.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Jeffrey Siegal  
View profile  
 More options Mar 18 2002, 2:29 am
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Jeffrey Siegal <j...@quiotix.com>
Date: Sun, 17 Mar 2002 23:29:58 -0800
Local: Mon, Mar 18 2002 2:29 am
Subject: Re: self-hosting gc, narrowed

Rahul Jain wrote:
> >     If I remember right, SML/NJ (correct me here, as I am walking on
> > thin ice!!!), I think partitions heap as I said.  I thought the collector
> > for Larceny did the same.  It has been a while since I looked at
> > their source code, though.

> That's a really strange way to do things. I can't imagine what the
> material gain would be. Maybe a few bits on the fixnum type?

It eliminates the need for a separate tag (which is only a few bits in a
langauge with few types) on every object, not just fixnums.

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Erik Naggum  
View profile  
 More options Mar 18 2002, 4:42 am
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Erik Naggum <e...@naggum.net>
Date: Mon, 18 Mar 2002 09:42:20 GMT
Local: Mon, Mar 18 2002 4:42 am
Subject: Re: self-hosting gc, narrowed
* Jeffrey Siegal <j...@quiotix.com>
| It eliminates the need for a separate tag (which is only a few bits in a
| langauge with few types) on every object, not just fixnums.

  I have wondered about this, so maybe you can help me understand.  When
  you allocate objects from type-specific arenas, how many types do you do
  this for?  Does a user-defined class hierarchy get their own arena for
  each class?  How do you get the type of the object?  (I think one would
  either have type information at the beginning of the page or use the page
  number as some kind of index into a table, or use virtual memory address
  space to sort of have tag bits in the upper address bits.)  This would
  save space compared to using type information in the object itself, but
  it seems the pages would have to be fairly large to make sure the type
  information would be in an active cache line.  However, this approach
  seems to me to work well only if you do not use the type information all
  the time, because the memory accesses required to obtain the type would
  be fairly expensive compared to extracting low-end bits.  I have read
  about BIBOP long ago, but I did not find an explanation of how you mad
  back from page to type or for which types this was employed.

///
--
  In a fight against something, the fight has value, victory has none.
  In a fight for something, the fight is a loss, victory merely relief.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Jeffrey Siegal  
View profile  
 More options Mar 18 2002, 5:42 am
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Jeffrey Siegal <j...@quiotix.com>
Date: Mon, 18 Mar 2002 02:42:23 -0800
Local: Mon, Mar 18 2002 5:42 am
Subject: Re: self-hosting gc, narrowed

Erik Naggum wrote:

> * Jeffrey Siegal <j...@quiotix.com>
> | It eliminates the need for a separate tag (which is only a few bits in a
> | langauge with few types) on every object, not just fixnums.

>   I have wondered about this, so maybe you can help me understand.  When
>   you allocate objects from type-specific arenas, how many types do you do
>   this for?

Were I implementing such a system, I would probably do it for every
type, but not in the first GC generation.  I would size the arenas based
on previous collections, on the theory that usage has some measure of
stability.

>   Does a user-defined class hierarchy get their own arena for
>   each class?  How do you get the type of the object?  (I think one would
>   either have type information at the beginning of the page or use the page
>   number as some kind of index into a table, or use virtual memory address
>   space to sort of have tag bits in the upper address bits.)

Agreed.

>   This would
>   save space compared to using type information in the object itself, but
>   it seems the pages would have to be fairly large to make sure the type
>   information would be in an active cache line.  However, this approach
>   seems to me to work well only if you do not use the type information all
>   the time, because the memory accesses required to obtain the type would
>   be fairly expensive compared to extracting low-end bits.

This would of course depend on the size and relative speed of cache,
etc., but I suspect that you would get more from being able to store
more objects in cache than you would lose by occasionally having a cache
miss when looking up types.  Keep in mind that with type inference, you
can often determine types at compile type, but unless you can type-infer
the entire program, you still need to store types in memory.  A more
compact representation in memory will still yield a benefit in terms of
increased cache hit rate even in this case, and in this case it is a
pure gain, since there is no need to reference the types at all.

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Matthias Blume  
View profile  
 More options Mar 18 2002, 7:31 am
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Matthias Blume <bl...@hanabi.research.bell-labs.com>
Date: Mon, 18 Mar 2002 12:30:56 GMT
Local: Mon, Mar 18 2002 7:30 am
Subject: Re: self-hosting gc, narrowed

Erik Naggum <e...@naggum.net> writes:
> * Jeffrey Siegal <j...@quiotix.com>
> | It eliminates the need for a separate tag (which is only a few bits in a
> | langauge with few types) on every object, not just fixnums.

>   I have wondered about this, so maybe you can help me understand.  When
>   you allocate objects from type-specific arenas, how many types do you do
>   this for?  Does a user-defined class hierarchy get their own arena for
>   each class?  How do you get the type of the object?  (I think one would
>   either have type information at the beginning of the page or use the page
>   number as some kind of index into a table, or use virtual memory address
>   space to sort of have tag bits in the upper address bits.)

You snipped the a relevant part of the discussion leading up to this, namely that
this scheme is being used by SML/NJ -- an implementation of a statically typed language.

The BIBOP allocation scheme worries about "representation types" only:  Everything that
looks (in memory) like a cons cell is allocated in the cons arena.  The BIBOP is not
sufficient to answer the question "which high-level type does this value belong to",
but since it is only used so the GC can do its tracing, such a question never comes
up.

Matthias


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Erik Naggum  
View profile  
 More options Mar 18 2002, 7:39 am
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Erik Naggum <e...@naggum.net>
Date: Mon, 18 Mar 2002 12:39:40 GMT
Local: Mon, Mar 18 2002 7:39 am
Subject: Re: self-hosting gc, narrowed
* Matthias Blume
| You snipped the a relevant part of the discussion leading up to this,
| namely that this scheme is being used by SML/NJ -- an implementation of a
| statically typed language.

  Yes, I did, as is common when discussing things on USENET -- we do not
  generally post multimegabyte messages to keep all the context -- but you
  imply that I had not understood that.  Please refrain from such dirty
  tactics.  You have not helped answer my question, either.

///
--
  In a fight against something, the fight has value, victory has none.
  In a fight for something, the fight is a loss, victory merely relief.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Duane Rettig  
View profile  
 More options Mar 18 2002, 12:01 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Duane Rettig <du...@franz.com>
Date: Mon, 18 Mar 2002 17:00:01 GMT
Local: Mon, Mar 18 2002 12:00 pm
Subject: Re: self-hosting gc, narrowed

FranzLisp used this bibop method.  The way they (UCB students) and we
(Franz Inc) did it was to preallocate an array of 8-bit typecodes, one
for each allocation page, and then assign each entry in the array which
corresponded to the new page being allocated.  The "types" were really
only implementational types; any composite types would be allocated
based on the 8-bit type code associated with the object.  And FranzLisp
didn't have CLOS, so that meta-type structure didn't exist.  Flavors
covered that time period, but flavors classes were not discriminated
with that low-level mechanism.  Think of the typing being equivalent
to the 8-bit "other" type codes that are currently stored in the header
of each object in CL implementations when they are not determined by
their tag (i.e. when they have a tag of "other").

In FranzLisp's bibop, to get from any address to its type. you hash on
the address.  Suppose the allocation page size is 8 kbytes.  Then to
get an index into the typetable vector, you shift the address of your
object right 13 bits, and use that to index into your type vector.
Since it was a byte vector, it needed no other shifts to account for
element width.

Obviously, when we created Allegro CL (called ExCL at the time), we
changed the basic philosophy of typing, partly due to the number of
instructions and memory references it took to get the type of an object.

--
Duane Rettig          Franz Inc.            http://www.franz.com/ (www)
1995 University Ave Suite 275  Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253   du...@Franz.COM (internet)


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Thomas Bushnell, BSG  
View profile  
 More options Mar 18 2002, 12:30 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: tb+use...@becket.net (Thomas Bushnell, BSG)
Date: 18 Mar 2002 09:28:26 -0800
Local: Mon, Mar 18 2002 12:28 pm
Subject: Re: self-hosting gc, narrowed

Erik Naggum <e...@naggum.net> writes:
> * Matthias Blume
> | You snipped the a relevant part of the discussion leading up to this,
> | namely that this scheme is being used by SML/NJ -- an implementation of a
> | statically typed language.

>   Yes, I did, as is common when discussing things on USENET -- we do not
>   generally post multimegabyte messages to keep all the context -- but you
>   imply that I had not understood that.  Please refrain from such dirty
>   tactics.  You have not helped answer my question, either.

I think Matthias' point is that in a statically typed language, you
don't need to detect types at runtime, or something like that.
(Except in GC, where the costs you point out are not so severe.)

At least, that's what I took Matthias to be saying.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Erik Naggum  
View profile  
 More options Mar 18 2002, 1:28 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Erik Naggum <e...@naggum.net>
Date: Mon, 18 Mar 2002 18:28:28 GMT
Local: Mon, Mar 18 2002 1:28 pm
Subject: Re: self-hosting gc, narrowed
* Thomas Bushnell, BSG
| I think Matthias' point is that in a statically typed language, you
| don't need to detect types at runtime, or something like that.
| (Except in GC, where the costs you point out are not so severe.)
|
| At least, that's what I took Matthias to be saying.

  Let me repeat what I actually wrote:

    However, this approach seems to me to work well only if you do not use
    the type information all the time

  which I think any reasonably smart reader would understand implied that
  (1) I had already figured out that it works best for statically typed
  languages that do little dynamic typing, and (2) wondered about the
  design in a language that did have dynamic typing, where is also used.

  So what was Matthias saying?  Nothing.  One does not need to post an
  article to say nothing.  Posting an article to say nothing is rude.

///
--
  In a fight against something, the fight has value, victory has none.
  In a fight for something, the fight is a loss, victory merely relief.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Rahul Jain  
View profile  
 More options Mar 18 2002, 2:30 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Rahul Jain <rj...@sid-1129.sid.rice.edu>
Date: 18 Mar 2002 13:26:20 -0600
Local: Mon, Mar 18 2002 2:26 pm
Subject: Re: self-hosting gc, narrowed

Jeffrey Siegal <j...@quiotix.com> writes:
> Keep in mind that with type inference, you can often determine types
> at compile type, but unless you can type-infer the entire program,
> you still need to store types in memory.

It seems this strategy will only work for static languages, then. In
Lisp, functions and types can be redefined on the fly, changing the
time-dependent assumptions of the compiler.

--
-> -/                        - Rahul Jain -                        \- <-
-> -\  http://linux.rice.edu/~rahul -=-  mailto:rj...@techie.com   /- <-
-> -/ "Structure is nothing if it is all you got. Skeletons spook  \- <-
-> -\  people if [they] try to walk around on their own. I really  /- <-
-> -/  wonder why XML does not." -- Erik Naggum, comp.lang.lisp    \- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
   (c)1996-2002, All rights reserved. Disclaimer available upon request.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Jeffrey Siegal  
View profile  
 More options Mar 18 2002, 3:06 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Jeffrey Siegal <j...@quiotix.com>
Date: Mon, 18 Mar 2002 12:05:59 -0800
Local: Mon, Mar 18 2002 3:05 pm
Subject: Re: self-hosting gc, narrowed

Rahul Jain wrote:
> > Keep in mind that with type inference, you can often determine types
> > at compile type, but unless you can type-infer the entire program,
> > you still need to store types in memory.

> It seems this strategy will only work for static languages, then. In
> Lisp, functions and types can be redefined on the fly, changing the
> time-dependent assumptions of the compiler.

That was precisely my point about still needing to store types in
memory, even if they often won't be used.  Type inference can work even
in a dynamic language for some pieces of code, due to lexical scope and
declarations, but since usually it can't work for the whole program,
types must be stored, somehow, in memory, even when they often will not
be used in performance-critical code (because this code will often make
use of the above techniques to allow a compiler to optimize).

However, even in the fully-general case of code which always checks
types at run time, it isn't clear that storing type by arena would not
be faster today.  Given the extreme spread between cache speed and main
memory speed, compared to only a few years ago, it can sense to do a lot
of work to get more objects to fit in cache (effectively making the
cache larger).


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Rahul Jain  
View profile  
 More options Mar 18 2002, 3:20 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Rahul Jain <rj...@sid-1129.sid.rice.edu>
Date: 18 Mar 2002 14:13:22 -0600
Local: Mon, Mar 18 2002 3:13 pm
Subject: Re: self-hosting gc, narrowed

Jeffrey Siegal <j...@quiotix.com> writes:
> That was precisely my point about still needing to store types in
> memory, even if they often won't be used.

So why not place the type tag in the low bits rather than the high bits?

> However, even in the fully-general case of code which always checks
> types at run time, it isn't clear that storing type by arena would not
> be faster today.  Given the extreme spread between cache speed and main
> memory speed, compared to only a few years ago, it can sense to do a lot
> of work to get more objects to fit in cache (effectively making the
> cache larger).

This would mean that you don't want to spread objects all over the
memory space. You're more likely to have more objects in cache if
objects are more densely pcked in memory.

Actually, this scheme would completely destroy the idea of a fixnum,
since there would be "holes" all over the fixnum space which coincide
with where the arenas are...

--
-> -/                        - Rahul Jain -                        \- <-
-> -\  http://linux.rice.edu/~rahul -=-  mailto:rj...@techie.com   /- <-
-> -/ "Structure is nothing if it is all you got. Skeletons spook  \- <-
-> -\  people if [they] try to walk around on their own. I really  /- <-
-> -/  wonder why XML does not." -- Erik Naggum, comp.lang.lisp    \- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
   (c)1996-2002, All rights reserved. Disclaimer available upon request.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Jeffrey Siegal  
View profile  
 More options Mar 18 2002, 3:54 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Jeffrey Siegal <j...@quiotix.com>
Date: Mon, 18 Mar 2002 12:54:36 -0800
Local: Mon, Mar 18 2002 3:54 pm
Subject: Re: self-hosting gc, narrowed

Rahul Jain wrote:
> > That was precisely my point about still needing to store types in
> > memory, even if they often won't be used.

> So why not place the type tag in the low bits rather than the high bits?

In fact the low few bits probably should be used for tags, since they're
otherwise useless given that objects will always be aligned.

However, there are only a few usable low bits.  To encode a more than a
few primitive types, you need more.  Probably the low bits can be used
to encode primitive types and arenas can be used to encode user defined
types.

> > However, even in the fully-general case of code which always checks
> > types at run time, it isn't clear that storing type by arena would not
> > be faster today.  Given the extreme spread between cache speed and main
> > memory speed, compared to only a few years ago, it can sense to do a lot
> > of work to get more objects to fit in cache (effectively making the
> > cache larger).

> This would mean that you don't want to spread objects all over the
> memory space. You're more likely to have more objects in cache if
> objects are more densely pcked in memory.

Cache lines aren't that large.  As long as you aren't dealing with one
each from a zillion different types, which I rather doubt is the usual
case, locality should be fine.  

> Actually, this scheme would completely destroy the idea of a fixnum,
> since there would be "holes" all over the fixnum space which coincide
> with where the arenas are...

Fixnums can have a unique tag in the low-order bits.

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Rahul Jain  
View profile  
 More options Mar 18 2002, 4:50 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Rahul Jain <rj...@sid-1129.sid.rice.edu>
Date: 18 Mar 2002 15:40:30 -0600
Local: Mon, Mar 18 2002 4:40 pm
Subject: Re: self-hosting gc, narrowed

Jeffrey Siegal <j...@quiotix.com> writes:
> Rahul Jain wrote:
> > > That was precisely my point about still needing to store types in
> > > memory, even if they often won't be used.

> > So why not place the type tag in the low bits rather than the high bits?

> In fact the low few bits probably should be used for tags, since they're
> otherwise useless given that objects will always be aligned.

> However, there are only a few usable low bits.  To encode a more than a
> few primitive types, you need more.  Probably the low bits can be used
> to encode primitive types and arenas can be used to encode user defined
> types.

The way most lisp implementations do it is to have "headers" on object
to indicate what type it is. There are often so many different
user-defined types (and builtin types) that you'd need hundreds of
arenas.

From debian's cmucl 3.0.9 without loading any other code,

* (inspect (find-class t))

#<BUILT-IN-CLASS T (read-only) {28000A65}> is a structure.
6. SUBCLASSES: #<EQ hash table, 478 entries {280C3695}>

That would require at LEAST 400 arenas. Way too much fragmentation for
real use.

> > This would mean that you don't want to spread objects all over the
> > memory space. You're more likely to have more objects in cache if
> > objects are more densely pcked in memory.

> Cache lines aren't that large.  As long as you aren't dealing with one
> each from a zillion different types, which I rather doubt is the usual
> case, locality should be fine.  

Well, lisp systems make good use of user-defined types. When you
actually load an application, that number can increase
dramatically. E.g., I estimate that DefDoc (my vaporware document
processing system) will define at least 100 types, allowing for
another 100 or so to be generated dynamically at runtime without
explicit defintion.

> > Actually, this scheme would completely destroy the idea of a fixnum,
> > since there would be "holes" all over the fixnum space which coincide
> > with where the arenas are...

> Fixnums can have a unique tag in the low-order bits.

How is that guaranteed to be unique and not intersect with the arena
segments?

--
-> -/                        - Rahul Jain -                        \- <-
-> -\  http://linux.rice.edu/~rahul -=-  mailto:rj...@techie.com   /- <-
-> -/ "Structure is nothing if it is all you got. Skeletons spook  \- <-
-> -\  people if [they] try to walk around on their own. I really  /- <-
-> -/  wonder why XML does not." -- Erik Naggum, comp.lang.lisp    \- <-
|--|--------|--------------|----|-------------|------|---------|-----|-|
   (c)1996-2002, All rights reserved. Disclaimer available upon request.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Jeffrey Siegal  
View profile  
 More options Mar 18 2002, 6:04 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Jeffrey Siegal <j...@quiotix.com>
Date: Mon, 18 Mar 2002 15:04:27 -0800
Local: Mon, Mar 18 2002 6:04 pm
Subject: Re: self-hosting gc, narrowed

Rahul Jain wrote:
> That would require at LEAST 400 arenas. Way too much fragmentation for
> real use.

That depends how large the arenas are and also how much overall benefit
is realized by using them.  I don't believe you can say "way too much
fragmentation" without actually measuring, or at least modeling, both
the costs and benefits.

> > > Actually, this scheme would completely destroy the idea of a fixnum,
> > > since there would be "holes" all over the fixnum space which coincide
> > > with where the arenas are...

> > Fixnums can have a unique tag in the low-order bits.

> How is that guaranteed to be unique and not intersect with the arena
> segments?

Because objects stored in segments are always aligned, so their
low-order bits can be a constant.  Fixnums can be tagged in their low
order bits using a distinct constant.

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Matthias Blume  
View profile  
 More options Mar 18 2002, 7:44 pm
Newsgroups: comp.lang.lisp, comp.lang.scheme
From: Matthias Blume <bl...@hanabi.research.bell-labs.com>
Date: Tue, 19 Mar 2002 00:44:40 GMT
Local: Mon, Mar 18 2002 7:44 pm
Subject: Re: self-hosting gc, narrowed

Erik Naggum <e...@naggum.net> writes:
> * Matthias Blume
> | You snipped the a relevant part of the discussion leading up to this,
> | namely that this scheme is being used by SML/NJ -- an implementation of a
> | statically typed language.

>   Yes, I did, as is common when discussing things on USENET -- we do not
>   generally post multimegabyte messages to keep all the context -- but you
>   imply that I had not understood that.

I did not imply any such thing, at least not intentionally.  I merely
said that you did (snip), and as you say yourself, that is a fact.

>   Please refrain from such dirty tactics.

You are hallucinating.  No tactics, dirty or clean.  (What would be the point?)

>  You have not helped answer my question, either.

I am truly sorry about that.

Matthias


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Messages 76 - 100 of 121 < Older  Newer >
« Back to Discussions « Newer topic     Older topic »