DependentsArray size and subscript is out of bounds

> Le Jeudi 20 Juillet 2006 00:38, mathieu a écrit :
>> Hi,
>>
>> It is normal that:
>>
>> (DependentsArray new: 100) size
>>
>> return 0?
>
> Yes
>
>> If yes so why?
>
> DependentsArray count only non nil elements
>
>> And if I do:
>> | o |
>>
>> o := WriteStream on: (DependentsArray new: 100).
>> 1 to: 24 do: [:each | o nextPut: Object new]. "do it sevral time"
>>
>> it raise an error 'subscript is out of bounds: 22' from time to time
>> why?
>
> You cannot do that with DependentsArray.
>
> DependentsArray are weak array: that mean that storing an object into a
> DependentsArray does not prevent it from being garbageCollected.
>
> When an element is garbage collected, corresponding index in DependentsArray
> is replaced by nil.
>
> All is occuring in pastEndPut:
> Since initial size (non nil elements) is zero, then the array is grown to
> size: oldSize + ((oldSize max: 20) min: 1000000)
>
> When no garbageCollection occurs, that works fine (except a new
> DependentsArray is created each time you add an Object).
>
> When a garbage collect occurs, all unreferenced (Object new) are removed from
> the DependentsArray, except one (I do not know who is referencing it, maybe
> the BlockContext...).
>
> Thus you allocate a DependentsArray of size 21 and fail when storing element
> number 22...
>
>> Thx
>> Math
>
> What do you need DependentsArray for?
>
> Nicolas

> nicolas cellier a écrit :
> > Le Jeudi 20 Juillet 2006 00:38, mathieu a écrit :
> >> Hi,
> >>
> >> It is normal that:
> >>
> >> (DependentsArray new: 100) size
> >>
> >> return 0?
> >
> > Yes
> >
> >> If yes so why?
> >
> > DependentsArray count only non nil elements
> >
> >> And if I do:
> >> | o |
> >>
> >> o := WriteStream on: (DependentsArray new: 100).
> >> 1 to: 24 do: [:each | o nextPut: Object new]. "do it sevral time"
> >>
> >> it raise an error 'subscript is out of bounds: 22' from time to time
> >> why?
> >
> > You cannot do that with DependentsArray.
> >
> > DependentsArray are weak array: that mean that storing an object into a
> > DependentsArray does not prevent it from being garbageCollected.
> >
> > When an element is garbage collected, corresponding index in DependentsArray
> > is replaced by nil.
> >
> > All is occuring in pastEndPut:
> > Since initial size (non nil elements) is zero, then the array is grown to
> > size: oldSize + ((oldSize max: 20) min: 1000000)
> >
> > When no garbageCollection occurs, that works fine (except a new
> > DependentsArray is created each time you add an Object).
> >
> > When a garbage collect occurs, all unreferenced (Object new) are removed

> > the DependentsArray, except one (I do not know who is referencing it, maybe
> > the BlockContext...).
> >
> > Thus you allocate a DependentsArray of size 21 and fail when storing element
> > number 22...
> >
> >> Thx
> >> Math
> >
> > What do you need DependentsArray for?
> >
> > Nicolas
>
> ok thx :)
>
> In fact this is "used" in SmaCC and raise this error:
>
> ======================================================
> DependentsArray(Object)>>error:
> Receiver: a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";"
> <period> ">" <name> E O F)
> Arguments and temporary variables:
> aString: *'subscript is out of bounds: 23'*
> Receiver's instance variables:
> a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";" <period> ">"
> <name> E O F)
>
> DependentsArray(Object)>>errorSubscriptBounds:
> Receiver: a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";"
> <period> ">" <name> E O F)
> Arguments and temporary variables:
> index: 23
> Receiver's instance variables:
> a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";" <period> ">"
> <name> E O F)
>
> DependentsArray(Object)>>at:put:
> Receiver: a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";"
> <period> ">" <name> E O F)
> Arguments and temporary variables:
> index: 23
> value:
> Receiver's instance variables:
> a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";" <period> ">"
> <name> E O F)
>
> WriteStream>>pastEndPut:
> Receiver: <<error during printing>>
> Arguments and temporary variables:
> anObject:
> oldSize: 2
> grownCollection: a DependentsArray(<keyword> ")" "]" <binarySymbol>
> "}" ";" <pe...etc...
> Receiver's instance variables:
> collection: a DependentsArray(<keyword> ")" "]" <binarySymbol> "}"
> ";" <period>...etc...
> position: 23
> readLimit: 23
> writeLimit: 1
>
>
> --- The full stack ---
> DependentsArray(Object)>>error:
> DependentsArray(Object)>>errorSubscriptBounds:
> DependentsArray(Object)>>at:put:
> WriteStream>>pastEndPut:
>  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
> WriteStream>>nextPut:
> [] in DependentsArray>>copyWith: {[:s |  self   do: [:item | s nextPut:
> item].  s nextPut: newElement]}
> DependentsArray class(SequenceableCollection class)>>streamContents:
> DependentsArray>>copyWith:
> DependentsArray(Array)>>copyWithDependent:
> SmaCCSymbolSet(Object)>>addDependent:
> SmaCCSymbolSet>>addComponent:
> SmaCCSymbolSet>>baseOn:
> SmaCCSymbolSet class>>basedOn:
> SmaCCLR1Item>>moveNext
> [] in SmaCCItemSet>>moveOn: {[:each | each nextSymbol == aGrammarSymbol
>   ifTrue: [anItemSet add: each mo...]}
> SmaCCItemSet(Set)>>do:
> SmaCCItemSet>>moveOn:
> [] in SmaCCGrammarCompiler>>createItemSets {[:each |  newState :=
> itemSet moveOn: each.  newState notEmpty   ifTrue: [sh...]}
> SortedCollection(OrderedCollection)>>do:
> SmaCCGrammarCompiler>>createItemSets
> SmaCCGrammarCompiler>>transitionTable
> SmaCCGrammarCompiler>>compileTransitionTable
> SmaCCGrammarCompiler>>compileParser
> SmaCCGrammarCompiler>>createChanges
> ======================================================
>
>
>
>

> Hi,
> I think that the problem occurs iff a garbage collect/finalization occurs during
> the DependentsArray>>copyWith: .
>
> This code exhibits the problem that you describe...
>
>      d := (DependentsArray new: 1).
>      1 to: 50 do:[:i |
>         d := d copyWith: Object new ].
>
> whereas this code runs without error....
>
>     d := (DependentsArray new: 1).
>     1 to: 50 do:[:i |
>           Smalltalk garbageCollect.
>           d := d copyWith: Object new ].
>
> I have also seen this problem when using Smacc, but didn't solve the root cause
> of the problem. I just did a garbage collect before generating the
> parser/scanner and the problem went away.
>
> Hope this helps.
> Cheers,
> Andy
>
>
>
> ----- Original Message -----
> From: "mathieu" <[hidden email]>
> To: <[hidden email]>; "The general-purpose Squeak developers list"
> <[hidden email]>
> Sent: Thursday, July 20, 2006 6:49 AM
> Subject: Re: DependentsArray size and subscript is out of bounds
>
>
>  
>> nicolas cellier a écrit :
>>    
>>> Le Jeudi 20 Juillet 2006 00:38, mathieu a écrit :
>>>      
>>>> Hi,
>>>>
>>>> It is normal that:
>>>>
>>>> (DependentsArray new: 100) size
>>>>
>>>> return 0?
>>>>        
>>> Yes
>>>
>>>      
>>>> If yes so why?
>>>>        
>>> DependentsArray count only non nil elements
>>>
>>>      
>>>> And if I do:
>>>> | o |
>>>>
>>>> o := WriteStream on: (DependentsArray new: 100).
>>>> 1 to: 24 do: [:each | o nextPut: Object new]. "do it sevral time"
>>>>
>>>> it raise an error 'subscript is out of bounds: 22' from time to time
>>>> why?
>>>>        
>>> You cannot do that with DependentsArray.
>>>
>>> DependentsArray are weak array: that mean that storing an object into a
>>> DependentsArray does not prevent it from being garbageCollected.
>>>
>>> When an element is garbage collected, corresponding index in DependentsArray
>>> is replaced by nil.
>>>
>>> All is occuring in pastEndPut:
>>> Since initial size (non nil elements) is zero, then the array is grown to
>>> size: oldSize + ((oldSize max: 20) min: 1000000)
>>>
>>> When no garbageCollection occurs, that works fine (except a new
>>> DependentsArray is created each time you add an Object).
>>>
>>> When a garbage collect occurs, all unreferenced (Object new) are removed
>>>      
> from
>  
>>> the DependentsArray, except one (I do not know who is referencing it, maybe
>>> the BlockContext...).
>>>
>>> Thus you allocate a DependentsArray of size 21 and fail when storing element
>>> number 22...
>>>
>>>      
>>>> Thx
>>>> Math
>>>>        
>>> What do you need DependentsArray for?
>>>
>>> Nicolas
>>>      
>> ok thx :)
>>
>> In fact this is "used" in SmaCC and raise this error:
>>
>> ======================================================
>> DependentsArray(Object)>>error:
>> Receiver: a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";"
>> <period> ">" <name> E O F)
>> Arguments and temporary variables:
>> aString: *'subscript is out of bounds: 23'*
>> Receiver's instance variables:
>> a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";" <period> ">"
>> <name> E O F)
>>
>> DependentsArray(Object)>>errorSubscriptBounds:
>> Receiver: a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";"
>> <period> ">" <name> E O F)
>> Arguments and temporary variables:
>> index: 23
>> Receiver's instance variables:
>> a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";" <period> ">"
>> <name> E O F)
>>
>> DependentsArray(Object)>>at:put:
>> Receiver: a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";"
>> <period> ">" <name> E O F)
>> Arguments and temporary variables:
>> index: 23
>> value:
>> Receiver's instance variables:
>> a DependentsArray(<keyword> ")" "]" <binarySymbol> "}" ";" <period> ">"
>> <name> E O F)
>>
>> WriteStream>>pastEndPut:
>> Receiver: <<error during printing>>
>> Arguments and temporary variables:
>> anObject:
>> oldSize: 2
>> grownCollection: a DependentsArray(<keyword> ")" "]" <binarySymbol>
>> "}" ";" <pe...etc...
>> Receiver's instance variables:
>> collection: a DependentsArray(<keyword> ")" "]" <binarySymbol> "}"
>> ";" <period>...etc...
>> position: 23
>> readLimit: 23
>> writeLimit: 1
>>
>>
>> --- The full stack ---
>> DependentsArray(Object)>>error:
>> DependentsArray(Object)>>errorSubscriptBounds:
>> DependentsArray(Object)>>at:put:
>> WriteStream>>pastEndPut:
>>  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
>> WriteStream>>nextPut:
>> [] in DependentsArray>>copyWith: {[:s |  self   do: [:item | s nextPut:
>> item].  s nextPut: newElement]}
>> DependentsArray class(SequenceableCollection class)>>streamContents:
>> DependentsArray>>copyWith:
>> DependentsArray(Array)>>copyWithDependent:
>> SmaCCSymbolSet(Object)>>addDependent:
>> SmaCCSymbolSet>>addComponent:
>> SmaCCSymbolSet>>baseOn:
>> SmaCCSymbolSet class>>basedOn:
>> SmaCCLR1Item>>moveNext
>> [] in SmaCCItemSet>>moveOn: {[:each | each nextSymbol == aGrammarSymbol
>>   ifTrue: [anItemSet add: each mo...]}
>> SmaCCItemSet(Set)>>do:
>> SmaCCItemSet>>moveOn:
>> [] in SmaCCGrammarCompiler>>createItemSets {[:each |  newState :=
>> itemSet moveOn: each.  newState notEmpty   ifTrue: [sh...]}
>> SortedCollection(OrderedCollection)>>do:
>> SmaCCGrammarCompiler>>createItemSets
>> SmaCCGrammarCompiler>>transitionTable
>> SmaCCGrammarCompiler>>compileTransitionTable
>> SmaCCGrammarCompiler>>compileParser
>> SmaCCGrammarCompiler>>createChanges
>> ======================================================
>>
>>
>>
>>
>>    
>
>
>  

>
> On 20.07.2006, at 10:37, Andrew Tween wrote:
>
> >
> >
> > I have also seen this problem when using Smacc, but didn't solve
> > the root cause
> > of the problem. I just did a garbage collect before generating the
> > parser/scanner and the problem went away.
> >
>
> So I changed the parser generator to do a "Smalltalk garbageCollect"
> befor compiling
> a grammar. It's in SmaCCDev-md.4.mcz
>
> http://www.squeaksource.com/SmaccDevelopment
>
> I did not yet test if it really helps, though.
>
>         Marcus
>
>

> if you try this:
>
> | a |
> a := DependentsArray new.
> [1 to: 1000 do: [:i | a := a copyWith: Object new]] timeToRun
>
> The old code will complete that in less than a second. Your version
> takes 3 minutes (I think because of hidden size calls on the
> DependentsArray which are very expensive). This is not a realistic
> use case, but still ;-)

>
> I suggest the following:
>
> copyWith: newElement
> "Re-implemented to not copy any niled out dependents."
> | copy i |
> copy := self class new: self size + 1.
> i := 0.
> self do: [:item | copy at: (i:=i+1) put: item].
> copy at: (i:=i+1) put: newElement.
> ^copy
>
> This appears to be even more efficient than the original. I'll attach
> the CS.

> ..
>> if you try this:
>>
>> | a |
>> a := DependentsArray new.
>> [1 to: 1000 do: [:i | a := a copyWith: Object new]] timeToRun
>>
>> The old code will complete that in less than a second. Your version
>> takes 3 minutes (I think because of hidden size calls on the
>> DependentsArray which are very expensive). This is not a realistic
>> use case, but still ;-)
>
> Well...the old code fails within a second , at least on my machine ;)
> With a slightly different test...
>     | a |
>     a := DependentsArray new.
>     [1 to: 1000 do: [:i | a := a copyWith: i]] timeToRun.
> I get these timings...
> old code: 5.5 minutes
> my fix: 5.6 minutes
>
>> I suggest the following:
>>
>> copyWith: newElement
>> "Re-implemented to not copy any niled out dependents."
>> | copy i |
>> copy := self class new: self size + 1.
>> i := 0.
>> self do: [:item | copy at: (i:=i+1) put: item].
>> copy at: (i:=i+1) put: newElement.
>> ^copy

>>
>> This appears to be even more efficient than the original. I'll attach
>> the CS.
>
> Using the same timing test as above, we have....
>
> old code: 5.5 minutes
> my fix: 5.6 minutes
> your fix: 0.6 seconds
>
> Congrats. I think that qualifies for 'speed-up' of the day (or month, or year,
> or decade ?)
> Cheers,
> Andy
>
> ..
>
>

>
> On 20.07.2006, at 10:37, Andrew Tween wrote:
>
>>
>>
>> I have also seen this problem when using Smacc, but didn't solve the
>> root cause
>> of the problem. I just did a garbage collect before generating the
>> parser/scanner and the problem went away.
>>
>
> So I changed the parser generator to do a "Smalltalk garbageCollect"
> befor compiling
> a grammar. It's in SmaCCDev-md.4.mcz
>
> http://www.squeaksource.com/SmaccDevelopment
>
> I did not yet test if it really helps, though.
>
>        Marcus
>
>
> ------------------------------------------------------------------------
>
>

> ..
>> if you try this:
>>
>> | a |
>> a := DependentsArray new.
>> [1 to: 1000 do: [:i | a := a copyWith: Object new]] timeToRun
>>
>> The old code will complete that in less than a second. Your version
>> takes 3 minutes (I think because of hidden size calls on the
>> DependentsArray which are very expensive). This is not a realistic
>> use case, but still ;-)
>
> Well...the old code fails within a second , at least on my machine ;)
> With a slightly different test...
>     | a |
>     a := DependentsArray new.
>     [1 to: 1000 do: [:i | a := a copyWith: i]] timeToRun.
> I get these timings...
> old code: 5.5 minutes
> my fix: 5.6 minutes
>
>>
>> I suggest the following:
>>
>> copyWith: newElement
>> "Re-implemented to not copy any niled out dependents."
>> | copy i |
>> copy := self class new: self size + 1.
>> i := 0.
>> self do: [:item | copy at: (i:=i+1) put: item].
>> copy at: (i:=i+1) put: newElement.
>> ^copy
>>
>> This appears to be even more efficient than the original. I'll attach
>> the CS.
>
> Using the same timing test as above, we have....
>
> old code: 5.5 minutes
> my fix: 5.6 minutes
> your fix: 0.6 seconds
>
> Congrats. I think that qualifies for 'speed-up' of the day (or  
> month, or year,
> or decade ?)
> Cheers,
> Andy