cyclic looping with [0 == object] whileFalse: [object := object nextObject].

What gaurantees that doing loops with #nextObject won't cause cyclic looping
whereby you process the same set of objects over and over again?

The work I was doing was testing changing the parser to eliminate #ifTrue:
macros from compiled methods and recompiled the entire image.  I saved the
image.  When I started the image it was frozen.  I broke into it and it was
looping in the method CommandHistory class>>#forgetAllGrabCommandsFrom:.  I
took the loop and modified it slightly to see what it was processing:

    | object count objects |
    objects := OrderedCollection new: 1000000.
    count := 0.
    object _ nil.
    [0 == object or: [count > 500000]] whileFalse: [
        count := count + 1.
        objects add: object.
        object isMorph ifTrue: [object removeProperty: #undoGrabCommand].
        object _ object nextObject].
    objects

It was looping through objects defined by this loop, block contexts defined
by my change to #ifTrue: bytecodes - they now create block contexts.

[] in UndefinedObject>>DoIt {[object removeProperty: #undoGrabCommand]}
[] in UndefinedObject>>DoIt {[count > 500000]}
OrderedCollection>>add:
OrderedCollection>>addLast:
[] in OrderedCollection>>addLast: {[self makeRoomAtLast]}
False>>or:
[] in UndefinedObject>>DoIt {[object removeProperty: #undoGrabCommand]}
[] in UndefinedObject>>DoIt {[count > 500000]}
. . .

What guarantee is there supposed to be that #nextObject won't loop back into
a cycle?  What did I do to break that guarantee and how can I reestablish
it?

cheers,
Rob

On Nov 5, 2007, at 6:39 PM, Rob Withers wrote:


I think your test is wrong 0 == object while always evaluate to false.
#nextObject return the nextObject in memory. But integer are not  
object in memory they are pointer (need to be confirm).


So you could try:

| object count objects |
    objects := OrderedCollection new: 1000000.
    count := 0.
    object := nil.
    firstObject := object
    [firstObject == object or: [count > 500000]] whileFalse: [
        count := count + 1.
        objects add: object.
        object isMorph ifTrue: [object removeProperty:  
#undoGrabCommand].
        object _ object nextObject].
    objects

HTH

        Mth

On 11/5/07, Rob Withers <[hidden email]> wrote:

> What gaurantees that doing loops with #nextObject won't cause cyclic looping
> whereby you process the same set of objects over and over again?

I think that would be the surrounding code. Certainly sending
#nextObject can't always succeed; it should eventually run out of real
objects and return zero. If you send #nextObject to 0, a SmallInteger,
it should fail for sure.

>    object _ nil.
>     [0 == object or: [count > 500000]] whileFalse: [

This should drop out when 0 is encountered, or when 500000 objects
have been counted. The first should eventually happen, and so should
the second. Are you sure you let this loop run long enough?

But I've got to say it seems odd that the loop starts at nil. Most
users of #nextObject don't use it like that, since nil isn't
guaranteed to be at any particular place in the enumeration of all
objects. Shouldn't it be something like this?

  object := self someObject.

> What guarantee is there supposed to be that #nextObject won't loop back into
> a cycle?

Zero is the guarantee.

> What did I do to break that guarantee and how can I reestablish
> it?

I don't think you broke it, unless you redefined
SmallInteger>>nextObject or something like that.

Hope this helps!

--Tom Phoenix

On 11/5/07, Mathieu Suen <[hidden email]> wrote:

> I think your test is wrong 0 == object while always evaluate to false.
> #nextObject return the nextObject in memory. But integer are not
> object in memory they are pointer (need to be confirm).

You've almost got the right idea; #nextObject doesn't return
SmallIntegers normally, just items from the object memory. But it does
return 0 at the end, as the indicator that there are no more objects
to enumerate. Of course nil can't be returned to mean no more elements
because it is one of the objects in memory that #nextObject actually
does return. If a programmer were to invoke SmallInteger>>nextObject,
that method should use #shouldNotImplement or something similar to
stop the potential infinite loop.

Additionally, remembering the initial object so as to recognize it
when it "comes around again" doesn't generally work. After all, once
the last SmallInteger is incremented, it becomes some LargeInteger,
which is a new object in memory, so #nextObject would continue on from
that one toward the end of the object memory, likely never returning
to the initial object. That's why users of #nextObject always check
whether it returns 0.

Cheers!

--Tom Phoenix

Consider that memory is allocated from a low address to a high address.

Given the method below, we invoke "someObject" which technically is  
misnamed since it actually returns the first object at the lowest  
memory address. It's doubtful that object
will ever be garbage collected so asking for self someObject will  
always return the same object across every image startup.

allObjectsDo: aBlock
        "Evaluate the argument, aBlock, for each object in the system
        excluding SmallIntegers."
        | object |
        object _ self someObject.
        [0 == object]
                whileFalse: [aBlock value: object.
                        object _ object nextObject]

nextObject then returns the object found after the location of the  
object that is the receiver. In theory this object is older.

Now the trick here is that as we are iterating over objects from old  
to new, we must NOT be creating objects that will continue to
grow the image, if for example you allocate a new object for each  
nextObject processing you won't complete the loop.

Cyclic?

I believe if you become object, thus changing object from an new  
object to an old object, thus changing the memory location from
an new higher address to an older object in lower address space you  
are making a cycle.

In the code below I wonder what removeProperty does?

On Nov 5, 2007, at 9:39 AM, Rob Withers wrote:

--
========================================================================
===
John M. McIntosh <[hidden email]>
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
========================================================================
===

On 11/5/07, Rob Withers <[hidden email]> wrote:

Now that I look at this code again, I see more. (What's the last line
supposed to be doing?) The method looks to be building a collection of
all (or up to half a million) objects in object memory, for no
apparent reason. As a side effect, or maybe its main effect, it
affects some Morphs.

Let's take care of the Morphs first. You probably want to process all
of them, not just many of them, so maybe something like this:

  Morph allSubInstancesDo: [:m |
    m removeProperty: #undoGrabCommand ].

If you really want a collection of all (or up to half a million)
objects from memory, that's easily done as well, built around
something like

  SystemNavigation default allObjectsDo: [:ob | "....whatever...." ].

But there's probably a better way to do what you want to do than to
build a collection of most of the items in the object memory.

Cheers!

--Tom Phoenix

Tom, the original loop that was looping forever was the method
#forgetAllGrabCommandsFrom:

    | object |
    object _ starter.
    [
        [0 == object] whileFalse: [
            object isMorph ifTrue: [object removeProperty:
#undoGrabCommand].
            object _ object nextObject].
        ] ifError: [:err :rcvr | "object is obsolete"
            self forgetAllGrabCommandsFrom: object nextObject].

where starter was set to "self someObject".   more below...

----- Original Message -----
From: "Tom Phoenix" <[hidden email]>


I thought of a possibility.  It could be that I am creating objects
(BlockContexts and MethodContexts) as fast as I process them in this loop.
If the loop is creating objects, then they are bound to be at the end of
memory and I am bound to not be able to catch up to them.  In this case, my
#ifTrue: msg is a real msg creating a real BlockContext each time through
the loop, because of my Compiler changes, and the associated MethodContexts
are being created too.  (My addition of
anOrderedCollection>>#add:/#addLast:/#grow... are being recorded as well).
Each time through a new instance of the BlockContext is being created.

That sucks.  I can't do anything about it.

>
>>    object _ nil.
>>     [0 == object or: [count > 500000]] whileFalse: [
>
> This should drop out when 0 is encountered, or when 500000 objects
> have been counted. The first should eventually happen, and so should
> the second. Are you sure you let this loop run long enough?

My modified loop does stop because of count > 500000.  Then I was able to
see the cyclic looping.

>
> But I've got to say it seems odd that the loop starts at nil. Most
> users of #nextObject don't use it like that, since nil isn't
> guaranteed to be at any particular place in the enumeration of all
> objects. Shouldn't it be something like this?
>
>  object := self someObject.

I switched to this.


It helps me understand!  Thanks!  I don't know what I can do about it.

Cheers,
Rob

----- Original Message -----
From: "Tom Phoenix" <[hidden email]>
To: "The general-purpose Squeak developers list"
<[hidden email]>
Sent: Monday, November 05, 2007 10:40 AM
Subject: Re: cyclic looping with [0 == object] whileFalse: [object :=
objectnextObject].


This was only my method of detecting whether there was a cycle in the
objects it was processing.  That's all.  Now why they don't just do:

>  Morph allSubInstancesDo: [:m |
>    m removeProperty: #undoGrabCommand ].

in #forgetAllGrabCommandsFrom: in the first place, I don't know.

Beyond this instance of using #nextObject to loop, it seems that if objects
are created inside of that loop, then it may loop forever.

Cheers,
Rob

On Nov 5, 2007, at 10:44 AM, Rob Withers wrote:

As an optimization methodContexts are recycled and reused, this  
feature decreases the time take
to make a new context. When a method returns the local context is  
then stuffed onto the free context chain.
However on a GC the free context chain is GCed also. So usually you  
are not making a new object (MethodContexts ) for the message  
activation.


--
========================================================================
===
John M. McIntosh <[hidden email]>
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
========================================================================
===

Actually if you look at users of nextObject there is a case where you  
iterate over all the objects
doing isMorph then perform some cleanup action. I had also thought  
that doing Morph allSubInstancesDo: would
be faster.

But was surprised to see that iterating over all the object was like  
10x faster.
Why, well the nextObject is really fast...
and if you look at Behavior allInstancesDo: it actually does the  
someInstance, nextInstance dance

allInstancesDo: aBlock
        "Evaluate the argument, aBlock, for each of the current instances of  
the
        receiver.
       
        Because aBlock might change the class of inst (for example, using  
become:),
        it is essential to compute next before aBlock value: inst."
        | inst next |
        self ==  UndefinedObject ifTrue: [^ aBlock value: nil].
        inst _ self someInstance.
        [inst == nil]
                whileFalse:
                [
                next _ inst nextInstance.
                aBlock value: inst.
                inst _ next]

That uses the follow primitives in interp.c

instanceAfter: objectPointer
        "Support for instance enumeration. Return the next instance
        of the class of the given object, or nilObj if the enumeration
        is complete."
        | classPointer thisObj thisClass |
        classPointer := self fetchClassOf: objectPointer.
        thisObj := self accessibleObjectAfter: objectPointer.
        [thisObj = nil]
                whileFalse: [thisClass := self fetchClassOf: thisObj.
                        thisClass = classPointer ifTrue: [^ thisObj].
                        thisObj := self accessibleObjectAfter: thisObj].
        ^ nilObj


accessibleObjectAfter: oop
        "Return the accessible object following the given object or
        free chunk in the heap. Return nil when heap is exhausted."
        | obj |
        self inline: false.
        obj := self objectAfter: oop.
        [self oop: obj isLessThan: endOfMemory]
                whileTrue: [(self isFreeObject: obj) ifFalse: [^ obj].
                        obj := self objectAfter: obj].
        ^ nil



However given you are doing message sends, block evaluations etc in  
allInstancesDo:. Then *MILLIONS* of bytecodes  and 100 of thousands  
of method invocations run
to do the same task.  Thus in a simple loop iterating over an object  
and doing a message send to ask them if they are a Morph is *way faster*




On Nov 5, 2007, at 10:40 AM, Tom Phoenix wrote:

--
========================================================================
===
John M. McIntosh <[hidden email]>
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
========================================================================
===

On Nov 5, 2007, at 8:18 PM, John M McIntosh wrote:


But MethodContext are no more recyvled when thisContext is push one  
the stack:

pushActiveContextBytecode
        "Puts reclaimability of this context in question."

        self fetchNextBytecode.
        reclaimableContextCount := 0.
        self internalPush: activeContext.

And context are puch on the stack when a block is create.


        Mth

----- Original Message -----
From: "John M McIntosh" <[hidden email]>
To: "The general-purpose Squeak developers list"
<[hidden email]>
Sent: Monday, November 05, 2007 11:18 AM
Subject: Re: cyclic looping with [0 == object] whileFalse: [object
:=objectnextObject].


In my test code, I am stuffing each object into an OrderedCollection, so
they won't be recycled for sure.  I'll try printing them to the transcript
to detect a 'cycle', but not hang on to them.

The question remains with the original code, which is not saving each
object, why it is stuck processing more and more objects.  As I said, I
changed the compiler to stop inlining #ifTrue: and this was the result of
that (after recompileAll).   I would like to find out why, and see if it is
something I have done wrong with #ifTrue: msg sending.

Is it as Mathieu Suen says?  Are they getting trapped in  the stack?

thanks,
Rob

> However given you are doing message sends, block evaluations etc in
> allInstancesDo:. Then *MILLIONS* of bytecodes  and 100 of thousands of
> method invocations run
> to do the same task.  Thus in a simple loop iterating over an object and
> doing a message send to ask them if they are a Morph is *way faster*

Unfortunately, something like this would also be slower than #nextObject:

     Morph withAllSubclassesDo: [ :each |
         inst _ each someInstance.
         [inst == nil] whileFalse:
             [next _ inst nextInstance.
             inst removeProperty: #undoGrabCommand.
             inst _ next]

because of the *huge* amount of Morph subclasses in the image.    You
are walking the object memory hundreds of times rather than one, and I
found out a few years ago (on a different computer) that using a Set (!)
and #nextObject is faster than using #nextInstance if you have about 20
subclasses (or more).

This would work for Rob however.

Paolo

----- Original Message -----
From: "Paolo Bonzini" <[hidden email]>

> This would work for Rob however.
>
> Paolo
>

Hi Paolo,

That would work for me in this situation, yes.  Also, I thought that
Andreas' use of a marker to stop iteration would also work in this
situation.  The issue is that I caused the situation by turning off ifTrue:
inlining in the compiler (with help from others).

This is just an intermediate step to where I really want to be, which is
writing a macro which tests whether the receiver is Boolean, and if it is
then run the inline form of ifTrue:, and if it is not then run the msg send
form of ifTrue:.  This would avoid the above problem by keeping things
inlined.  I have this new compound macro coded up, compiling and some basic
tests and it works, but it makes my environment unstable.  I am getting the
emergency evaluator or outright image crashes when using it.  It is driving
me crazy, if I wasn't already.

I am attching the Compiler package that I believe will load up for those who
may be willing to help me figure this out.  After loading into a scratch
image, run 'Compiler recompileAll'.  Then debug 'FileList open'.   This will
show you one of the soft crashes (the emergency evaluator).  I suspect that
I don't have things I need to do syntax highlighting in the debugger for the
new macro code, but I am not sure if that is enough to cause crashes.  It
does strange things like switch arguments, in this case a DirectoryEntry
suddenly becomes 6.

thanks for any assistance,
Rob

Oh shoot.   This won't work since there are new bytecodes I have compiled
into the vm that are needed.  If someone really wants to help me investigate
this, and I hope someone does, let me know and I can send you a Win32 VM or
the package to allow you to compile a vm on the platform of your choice.

Rob

----- Original Message -----
From: "Rob Withers" <[hidden email]>
To: "Paolo Bonzini" <[hidden email]>; <[hidden email]>;
"The general-purpose Squeak developers list"
<[hidden email]>
Sent: Tuesday, November 06, 2007 8:23 AM
Subject: Re: cyclic looping with [0 == object] whileFalse: [object :=
objectnextObject].



--------------------------------------------------------------------------------


>
>