Using #= for integer comparison instead of #==

I'm not familiar with Squeak's GC... can you also assume that a GC (e.g.: a "new space" scavenge) won't move the marker so that the enumeration goes past it?

On 11/26/10 9:12 , Bert Freudenberg wrote:

On 26.11.2010, at 18:09, Andres Valloud wrote:

Can you assume that allocation is sequential?

I can.

- Bert -

On 11/26/10 8:59 , Bert Freudenberg wrote:

On 26.11.2010, at 17:43, Andres Valloud wrote:

You *must* use an end marker, i.e.,

       last := Object new. "end marker"
       obj := self someObject.
       [last == obj] whileFalse:[
               count := count + 1.
               obj := obj nextObject.
       ].

This will work because it counts between the beginning of memory and the
(arbitrary) end marker. Anything else basically should not be relied on
to work, jit or no.

What happens if a process with higher priority interrupts the iteration and creates more objects?

New objects would come after the end marker in memory.

- Bert -

Awesome, thank you!  That makes the "marker technique" more clear.  In HPS parlance (excuse me using the terminology I am most familiar with), Squeak has an eden plus two survivor semi spaces, and old space for the rest.  The incremental GC would be a scavenge of new space.  The full GC is a mark / sweep GC of all object data.  Does that make sense?

Also, would you mind a question?  If the new objects are above the old data, what happens when the old data grows large enough that it runs into the new object space?  Is the new object space moved upwards?

On 11/30/10 16:20 , Andreas Raab wrote:

http://stephane.ducasse.free.fr/FreeBooks/CollectiveNBlueBook/Rowledge-Final.pdf

On pp. 20 it has an excellent summary about how the Squeak GC works.

Cheers,
   - Andreas

On 11/30/2010 4:13 PM, Andres Valloud wrote:

Yes, from what I've seen, Squeak's GC is different from that in HPS. I
found some information scattered here and there in Google, but it's
mostly commentary. Ideally, I'd look at the source code and figure it
out but I don't quite have the time to look at it in all its detail. I
would really appreciate a current, 3-5 sentence summary of Squeak's GC
implementation. Does anyone have such a pointer? I hope this request is
not deemed ridiculous, I'm thinking it would be just as unreasonable to
expect anybody to look at HPS' GC implementation and get the gist of
what's going on in 5-10 minutes. Thanks in advance!

On 11/27/10 14:06 , Eliot Miranda wrote:

On Fri, Nov 26, 2010 at 9:15 AM, Andres Valloud
<[hidden email]
<mailto:[hidden email]>>  wrote:

I'm not familiar with Squeak's GC... can you also assume that a GC
(e.g.: a "new space" scavenge) won't move the marker so that the
enumeration goes past it?


IIUC, that's irrelevant. FOr the marker technique to work all that's
needed is that the relative order of live objects isn't changed. The
only thing that can change that is a become:. In the absence of a
become: the end marker, no matter how many GCs occur, stays above/after
all previously activated objects and below/before all subsequently
allocated objects. The Squeak GC effectively only compacts to squeeze
out reclaimed objects, it does not reorder. So this is very different
to the VM/HPS GC.

HTH
Eliot



On 11/26/10 9:12 , Bert Freudenberg wrote:


On 26.11.2010, at 18:09, Andres Valloud wrote:

Can you assume that allocation is sequential?


I can.

- Bert -

On 11/26/10 8:59 , Bert Freudenberg wrote:


On 26.11.2010, at 17:43, Andres Valloud wrote:

You *must* use an end marker, i.e.,

last := Object new. "end marker"
obj := self someObject.
[last == obj] whileFalse:[
count := count + 1.
obj := obj nextObject.
].

This will work because it counts between the
beginning of memory and the
(arbitrary) end marker. Anything else basically
should not be relied on
to work, jit or no.


What happens if a process with higher priority
interrupts the iteration and creates more objects?


New objects would come after the end marker in memory.

- Bert -

.

On Tue, 16 Nov 2010, Andreas Raab wrote:

On 11/16/2010 8:05 PM, Levente Uzonyi wrote:

I wasn't clear when I said atomic code. I expected #= (and #<, #>, etc)
to _not_ be a real message send when both the receiver and the argument
are SmallIntegers. Otherwise what's the point of having separate
bytecodes for them?

Space. It makes a big difference for the most common selectors (#at:, #at:put:, #size, #+ etc) to be be encoded as bytecodes. It avoids having to allocate a literal every time you see the selector. Often, the special

I just evaluated this:

| count specialSelectors |
count := 0.
specialSelectors := Smalltalk specialSelectors select: [ :each | each isSymbol ].
CompiledMethod allInstancesDo: [ :method |
       | messages |
       messages := method messages.
       count := count + (specialSelectors count: [ :selector |
               messages includes: selector ]) ].
count

The result is 50947 for a slightly modified Trunk image. This means that this technique saves less than 200kB (assuming 32-bit slots in the literal frame), but it uses 32 bytecodes.

200 kB is not much compared to the size of the image (about 1-2%).

Also the 32 most frequently used methods are not the 32 special selectors.

| b mostFrequentSelectors specialSelectors |
b := Bag new.
CompiledMethod allInstancesDo: [ :method | b addAll: method messages ].
mostFrequentSelectors := (b sortedCounts first: 32) replace: #value.
specialSelectors := Smalltalk specialSelectors select: #isSymbol.
{
       specialSelectors difference: mostFrequentSelectors. "Shouldn't be special"
       mostFrequentSelectors difference: specialSelectors. "Should be special"
}.

#(
       #(#'>=' #'~=' #/ #'\\' #bitShift: #'//' #bitAnd: #bitOr: #next #atEnd #blockCopy: #value #value: #x #y)
       #(#, #assert: #first #name #add: #nextPutAll: #isEmpty #error: #asString #includes: #default #translated #not #on: #collect:))

Another 40kB could be saved by changing these.

Btw, there's a "free" bytecode: 200 - #blockCopy:.

selector bytecodes look like this:

Interpreter>>bytecodePrimNextPut
       messageSelector := self specialSelector: 20.
       argumentCount := 1.
       self normalSend.

I.e., it just dispatches to normalSend where the regular lookup takes place. Of course, that also means it's a prime place for an optimization that will evaluate eagerly for known receiver types and so (over time) optimizations were added, but many of the optimizations that may make sense in an interpreter have very different tradeoffs in the jit. For a jit to generate the level of optimization makes no sense because the code size simply explodes at no benefit if the inline caches are any good (ours *are* the best Eliot knows how to do and that is a meaningful statement).

On to a finer point. The terminology "real message send" is misleading. Generally, we (the VM hackers) mean by "real" send a send that requires a method activation, i.e., the creation of a context, but *not* the lookup of the method. That excludes for example all (successful) primitives from being "real sends", and as a consequence writing "1 + 2" is not a real send by that measure (with or without the bytecode present) since the primitive will be executed successfully and no "real" send (method activation) has taken place.

To make matters more complicated, when we talk about "real" sends in the context of thread switches, semaphores and critical sections, what we mean is whether there is a suspension point in the send or not. Obviously, some primitives (#suspend, #yield) must have suspension points so not all activation-free methods are also suspension-point-free. I am not entirely sure what the current set of rules for suspension points in Cog is; in the interpreter it was part of the activation sequence so any primitive that isn't process related would not have a suspension point but I don't know if that's still true in Cog.

Thanks, this was very informative.


Levente

Cheers,
 - Andreas