OrderedCollection growing

Hi,

I've made a small change in OrderedCollection in growBy:shift:
I use the primitive VMpr_OrderedCollection_replaceFromToWithStartingAt.
I guess it should be possible to tweak again a bit the behavior:
   In addLast or addFirst if we have any free rooms but first is <= 1 or
last >= n we could move instead of allocating a new collection.

Gwen

_______________________________________________
help-smalltalk mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-smalltalk

On Fri, Jun 24, 2011 at 08:17, Gwenael Casaccio <[hidden email]> wrote:
> Hi,
>
> I've made a small change in OrderedCollection in growBy:shift:
> I use the primitive VMpr_OrderedCollection_replaceFromToWithStartingAt.
> I guess it should be possible to tweak again a bit the behavior:

That's very nice, you could also implement all of
#replaceFrom:to:with:startingAt: with the primitive instead?  The
primitive would be #primReplaceFrom:to:with:startingAt:.  Then you
don't need a change in #growBy:shift:, I think.

>  In addLast or addFirst if we have any free rooms but first is <= 1 or last
>>= n we could move instead of allocating a new collection.

Is it really helpful?

Paolo

_______________________________________________
help-smalltalk mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-smalltalk

I think it can be helpfull consider the situtation:
  we have enough room but first <= 1 we cannot decrease (if adding item first)
what happen know a new orderedcollection is allocated and items are moved,
in the new behavior the items are just moved ("less" impact on the gc)

Gwen

On Fri, Jun 24, 2011 at 12:17 PM, Paolo Bonzini <[hidden email]> wrote:
_______________________________________________
help-smalltalk mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-smalltalk

On Fri, Jun 24, 2011 at 13:57, Gwenaël Casaccio <[hidden email]> wrote:
> I think it can be helpfull consider the situtation:
>  we have enough room but first <= 1 we cannot decrease (if adding item first)
> what happen know a new orderedcollection is allocated and items are moved,
> in the new behavior the items are just moved ("less" impact on the gc)

Yes, that's true.  Especially if the old collection is in old-space
and it keeps old objects alive after they are removed from the OC.
But I would limit the number of slots by which you move.  In
particular, you need to ensure that only the first attempt results in
a move, the second should result in a grow.  I'm not sure if this is
possible, but it would be necessary to avoid quadratic behavior.

The problem is that the most common scenario where this helps (a FIFO
queue with addFirst: / removeLast) will not result in optimal behavior
anyway due to shrinking.

Perhaps an alternative approach is this: remove shrinking, and only do
the move if the OrderedCollection is at most 33% full, or something like
that.  WDYT?

Paolo

_______________________________________________
help-smalltalk mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-smalltalk

On 06/24/2011 12:17 PM, Paolo Bonzini wrote: So here is the patch. I've changed OrederedCollection to use
#replaceFrom:to:with:startingAt, SortedCollection uses the Smalltalk
implementation but for growing I call the primitive. And OrderedSet uses
the St implementation.

>
>>   In addLast or addFirst if we have any free rooms but first is<= 1 or last
>>> = n we could move instead of allocating a new collection.
>
> Is it really helpful?
>
> Paolo


_______________________________________________
help-smalltalk mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-smalltalk

On 07/04/2011 12:05 PM, Gwenael Casaccio wrote:
> So here is the patch.

This is not a patch, it is 10 patches including multiple reverts of
pieces that you have already submitted.

You should have grouped the patches in two, one for #beConsistent and
one squashing everything else.

> I've changed OrederedCollection to use
> #replaceFrom:to:with:startingAt, SortedCollection uses the Smalltalk
> implementation but for growing I call the primitive. And OrderedSet uses
> the St implementation.

Why?  Is it just because the ordered_set_class is not available?  I
believe this rather shows that class checks are too specific.

I pulled some changes in stable-3.2 and others in master only.  Please
test master and see how performance compares with your code.

Paolo

_______________________________________________
help-smalltalk mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-smalltalk

On 07/04/2011 01:14 PM, Paolo Bonzini wrote: Hi,

here is a new patch:

  - #replaceFrom: cannot be called in SortedCollection
  - add basicFirstIndex which return the position of the first object

make check is green

Gwen

_______________________________________________
help-smalltalk mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-smalltalk