About linkedlist

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
26 messages Options
12
Reply | Threaded
Open this post in threaded view
|

About linkedlist

Stéphane Ducasse
Hi

I was thinking that linkedList is really not to be used by something else than the scheduler (remember the
problem we got with change == into something else).

So I was wondering if it would not be simpler/safer to design a generalPurpose fast/robust LinkedList too?

Stef
Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Lukas Renggli
See below for an alternative collection implementation:

   http://jenkins.lukas-renggli.ch/job/Container/

Also contains a nice double-linked-list, as well as many other
standard containers that are missing in standard Smalltalk.

Lukas

On 3 February 2012 07:52, Stéphane Ducasse <[hidden email]> wrote:
> Hi
>
> I was thinking that linkedList is really not to be used by something else than the scheduler (remember the
> problem we got with change == into something else).
>
> So I was wondering if it would not be simpler/safer to design a generalPurpose fast/robust LinkedList too?
>
> Stef



--
Lukas Renggli
www.lukas-renggli.ch

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Sven Van Caekenberghe

On 03 Feb 2012, at 09:26, Lukas Renggli wrote:

> See below for an alternative collection implementation:
>
>   http://jenkins.lukas-renggli.ch/job/Container/
>
> Also contains a nice double-linked-list, as well as many other
> standard containers that are missing in standard Smalltalk.

Lukas,

Very interesting !
I already saw that you were working on this ;-)

Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
It is one thing to browse the code, but the why/how is important as a guide.

It seems that although you introduce iterators, they are less annoying then expected, which is great.
Also, a certain level of backwards compatibility seems to be present, looking at message names.

Sven
Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Stéphane Ducasse
In reply to this post by Lukas Renggli
Lukas this is cool. Do you have a list of class/comment?

Stef

On Feb 3, 2012, at 9:26 AM, Lukas Renggli wrote:

> See below for an alternative collection implementation:
>
>   http://jenkins.lukas-renggli.ch/job/Container/
>
> Also contains a nice double-linked-list, as well as many other
> standard containers that are missing in standard Smalltalk.
>
> Lukas
>
> On 3 February 2012 07:52, Stéphane Ducasse <[hidden email]> wrote:
>> Hi
>>
>> I was thinking that linkedList is really not to be used by something else than the scheduler (remember the
>> problem we got with change == into something else).
>>
>> So I was wondering if it would not be simpler/safer to design a generalPurpose fast/robust LinkedList too?
>>
>> Stef
>
>
>
> --
> Lukas Renggli
> www.lukas-renggli.ch
>


Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Stéphane Ducasse
In reply to this post by Lukas Renggli
what is the diff between arrayList and vectorList ?
I have plenty of other questions. :)

Stef


On Feb 3, 2012, at 9:26 AM, Lukas Renggli wrote:

> See below for an alternative collection implementation:
>
>   http://jenkins.lukas-renggli.ch/job/Container/
>
> Also contains a nice double-linked-list, as well as many other
> standard containers that are missing in standard Smalltalk.
>
> Lukas
>
> On 3 February 2012 07:52, Stéphane Ducasse <[hidden email]> wrote:
>> Hi
>>
>> I was thinking that linkedList is really not to be used by something else than the scheduler (remember the
>> problem we got with change == into something else).
>>
>> So I was wondering if it would not be simpler/safer to design a generalPurpose fast/robust LinkedList too?
>>
>> Stef
>
>
>
> --
> Lukas Renggli
> www.lukas-renggli.ch
>


Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Lukas Renggli
This is all very much at an experimental phase.

> what is the diff between arrayList and vectorList ?

ArrayList is double ended (very much like OrderedCollection),
VectorList is single ended. I was just experimenting to see if it
makes a difference.

> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.

The core idea is to split iteration from containment; I think a
horrible design mistake in the Smalltalk-80 collections.

> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
> It is one thing to browse the code, but the why/how is important as a guide.

Another idea is to split the backing store from the container and
allow the composition of collection properties:

 - uniqueness: yes, no
 - order: natural, custom, indexed
 - access: indexed, keyed
 - structure: hashed, treed, linked
 - weakness: yes, no (not even touched yet)

> It seems that although you introduce iterators, they are less annoying then expected, which is great.

The goal here is to be as lazy as possible and avoid unnecessary loops
over the collections.

Also iterators avoid the explosion of selector combinations like (#do:
and #withIndexDo: and #withIndexCollect:, etc) by utilizing objects.

> Also, a certain level of backwards compatibility seems to be present, looking at message names.

I like the existing names, but then this is not a goal. Also I am not
sure if methods like #add: and #at:put: should really return the
argument.

Essentially the goal is to provide an alternative to the Smalltalk-80
collections by adopting some ideas from modern collection libraries in
Java, C++, Scala, Haskell, etc.

Lukas

On 3 February 2012 10:07, Stéphane Ducasse <[hidden email]> wrote:

> what is the diff between arrayList and vectorList ?
> I have plenty of other questions. :)
>
> Stef
>
>
> On Feb 3, 2012, at 9:26 AM, Lukas Renggli wrote:
>
>> See below for an alternative collection implementation:
>>
>>   http://jenkins.lukas-renggli.ch/job/Container/
>>
>> Also contains a nice double-linked-list, as well as many other
>> standard containers that are missing in standard Smalltalk.
>>
>> Lukas
>>
>> On 3 February 2012 07:52, Stéphane Ducasse <[hidden email]> wrote:
>>> Hi
>>>
>>> I was thinking that linkedList is really not to be used by something else than the scheduler (remember the
>>> problem we got with change == into something else).
>>>
>>> So I was wondering if it would not be simpler/safer to design a generalPurpose fast/robust LinkedList too?
>>>
>>> Stef
>>
>>
>>
>> --
>> Lukas Renggli
>> www.lukas-renggli.ch
>>
>
>



--
Lukas Renggli
www.lukas-renggli.ch

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Nicolas Cellier
2012/2/3 Lukas Renggli <[hidden email]>:

> This is all very much at an experimental phase.
>
>> what is the diff between arrayList and vectorList ?
>
> ArrayList is double ended (very much like OrderedCollection),
> VectorList is single ended. I was just experimenting to see if it
> makes a difference.
>
>> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
>
> The core idea is to split iteration from containment; I think a
> horrible design mistake in the Smalltalk-80 collections.
>
>> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
>> It is one thing to browse the code, but the why/how is important as a guide.
>
> Another idea is to split the backing store from the container and
> allow the composition of collection properties:
>
>  - uniqueness: yes, no
>  - order: natural, custom, indexed
>  - access: indexed, keyed
>  - structure: hashed, treed, linked
>  - weakness: yes, no (not even touched yet)
>
>> It seems that although you introduce iterators, they are less annoying then expected, which is great.
>
> The goal here is to be as lazy as possible and avoid unnecessary loops
> over the collections.
>
> Also iterators avoid the explosion of selector combinations like (#do:
> and #withIndexDo: and #withIndexCollect:, etc) by utilizing objects.
>
>> Also, a certain level of backwards compatibility seems to be present, looking at message names.
>
> I like the existing names, but then this is not a goal. Also I am not
> sure if methods like #add: and #at:put: should really return the
> argument.
>

These two are convenient for enabling this kind of DSL instructions

A[i] := B[j] := c

But of course, a dup bytecode would also do the trick...

Nicolas

> Essentially the goal is to provide an alternative to the Smalltalk-80
> collections by adopting some ideas from modern collection libraries in
> Java, C++, Scala, Haskell, etc.
>
> Lukas
>
> On 3 February 2012 10:07, Stéphane Ducasse <[hidden email]> wrote:
>> what is the diff between arrayList and vectorList ?
>> I have plenty of other questions. :)
>>
>> Stef
>>
>>
>> On Feb 3, 2012, at 9:26 AM, Lukas Renggli wrote:
>>
>>> See below for an alternative collection implementation:
>>>
>>>   http://jenkins.lukas-renggli.ch/job/Container/
>>>
>>> Also contains a nice double-linked-list, as well as many other
>>> standard containers that are missing in standard Smalltalk.
>>>
>>> Lukas
>>>
>>> On 3 February 2012 07:52, Stéphane Ducasse <[hidden email]> wrote:
>>>> Hi
>>>>
>>>> I was thinking that linkedList is really not to be used by something else than the scheduler (remember the
>>>> problem we got with change == into something else).
>>>>
>>>> So I was wondering if it would not be simpler/safer to design a generalPurpose fast/robust LinkedList too?
>>>>
>>>> Stef
>>>
>>>
>>>
>>> --
>>> Lukas Renggli
>>> www.lukas-renggli.ch
>>>
>>
>>
>
>
>
> --
> Lukas Renggli
> www.lukas-renggli.ch
>

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Stéphane Ducasse

On Feb 3, 2012, at 12:20 PM, Nicolas Cellier wrote:

> 2012/2/3 Lukas Renggli <[hidden email]>:
>> This is all very much at an experimental phase.
>>
>>> what is the diff between arrayList and vectorList ?
>>
>> ArrayList is double ended (very much like OrderedCollection),
>> VectorList is single ended. I was just experimenting to see if it
>> makes a difference.

ok. I like to see such kind of experiment.
Was the name based on something that people use?

>>> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
>>
>> The core idea is to split iteration from containment; I think a
>> horrible design mistake in the Smalltalk-80 collections.

I thought about that when I read the Iterator.
I would not say that this is horrible. I think that for default case this is not that bad.
Now when you want to navigate a large graph and control the navigation then you should have an iterator.

I'm curious to see what you will get.

>>
>>> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
>>> It is one thing to browse the code, but the why/how is important as a guide.
>>
>> Another idea is to split the backing store from the container and
>> allow the composition of collection properties:
>>
>>  - uniqueness: yes, no
>>  - order: natural, custom, indexed
>>  - access: indexed, keyed
>>  - structure: hashed, treed, linked
>>  - weakness: yes, no (not even touched yet)

Yes I as to see that because I often want uniqueOrdered (not clear what you do when you add twice the same)

>>
>>> It seems that although you introduce iterators, they are less annoying then expected, which is great.
>>
>> The goal here is to be as lazy as possible and avoid unnecessary loops
>> over the collections.
>>
>> Also iterators avoid the explosion of selector combinations like (#do:
>> and #withIndexDo: and #withIndexCollect:, etc) by utilizing objects.
>>
>>> Also, a certain level of backwards compatibility seems to be present, looking at message names.
>>
>> I like the existing names, but then this is not a goal. Also I am not
>> sure if methods like #add: and #at:put: should really return the
>> argument.

:)
If I would know :)

Stef

>>
>
> These two are convenient for enabling this kind of DSL instructions
>
> A[i] := B[j] := c
>
> But of course, a dup bytecode would also do the trick...
>
> Nicolas
>
>> Essentially the goal is to provide an alternative to the Smalltalk-80
>> collections by adopting some ideas from modern collection libraries in
>> Java, C++, Scala, Haskell, etc.
>>
>> Lukas
>>
>> On 3 February 2012 10:07, Stéphane Ducasse <[hidden email]> wrote:
>>> what is the diff between arrayList and vectorList ?
>>> I have plenty of other questions. :)
>>>
>>> Stef
>>>
>>>
>>> On Feb 3, 2012, at 9:26 AM, Lukas Renggli wrote:
>>>
>>>> See below for an alternative collection implementation:
>>>>
>>>>   http://jenkins.lukas-renggli.ch/job/Container/
>>>>
>>>> Also contains a nice double-linked-list, as well as many other
>>>> standard containers that are missing in standard Smalltalk.
>>>>
>>>> Lukas
>>>>
>>>> On 3 February 2012 07:52, Stéphane Ducasse <[hidden email]> wrote:
>>>>> Hi
>>>>>
>>>>> I was thinking that linkedList is really not to be used by something else than the scheduler (remember the
>>>>> problem we got with change == into something else).
>>>>>
>>>>> So I was wondering if it would not be simpler/safer to design a generalPurpose fast/robust LinkedList too?
>>>>>
>>>>> Stef
>>>>
>>>>
>>>>
>>>> --
>>>> Lukas Renggli
>>>> www.lukas-renggli.ch
>>>>
>>>
>>>
>>
>>
>>
>> --
>> Lukas Renggli
>> www.lukas-renggli.ch
>>
>


Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Igor Stasenko
On 3 February 2012 13:33, Stéphane Ducasse <[hidden email]> wrote:

>
> On Feb 3, 2012, at 12:20 PM, Nicolas Cellier wrote:
>
>> 2012/2/3 Lukas Renggli <[hidden email]>:
>>> This is all very much at an experimental phase.
>>>
>>>> what is the diff between arrayList and vectorList ?
>>>
>>> ArrayList is double ended (very much like OrderedCollection),
>>> VectorList is single ended. I was just experimenting to see if it
>>> makes a difference.
>
> ok. I like to see such kind of experiment.
> Was the name based on something that people use?
>
>>>> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
>>>
>>> The core idea is to split iteration from containment; I think a
>>> horrible design mistake in the Smalltalk-80 collections.
>
> I thought about that when I read the Iterator.
> I would not say that this is horrible. I think that for default case this is not that bad.
> Now when you want to navigate a large graph and control the navigation then you should have an iterator.
>
> I'm curious to see what you will get.
>
>>>
>>>> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
>>>> It is one thing to browse the code, but the why/how is important as a guide.
>>>
>>> Another idea is to split the backing store from the container and
>>> allow the composition of collection properties:
>>>
>>>  - uniqueness: yes, no
>>>  - order: natural, custom, indexed
>>>  - access: indexed, keyed
>>>  - structure: hashed, treed, linked
>>>  - weakness: yes, no (not even touched yet)
>
> Yes I as to see that because I often want uniqueOrdered (not clear what you do when you add twice the same)
>
>>>
>>>> It seems that although you introduce iterators, they are less annoying then expected, which is great.
>>>
>>> The goal here is to be as lazy as possible and avoid unnecessary loops
>>> over the collections.
>>>
>>> Also iterators avoid the explosion of selector combinations like (#do:
>>> and #withIndexDo: and #withIndexCollect:, etc) by utilizing objects.
>>>
>>>> Also, a certain level of backwards compatibility seems to be present, looking at message names.
>>>
>>> I like the existing names, but then this is not a goal. Also I am not
>>> sure if methods like #add: and #at:put: should really return the
>>> argument.
>
> :)
> If I would know :)
>

it is somewhat convenient, because you can do things like:

newItem := coll at: index ifAbsentPut: [ MyItem new ].

and other such forms...

> Stef
>


--
Best regards,
Igor Stasenko.

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Lukas Renggli
In reply to this post by Stéphane Ducasse
>>>> what is the diff between arrayList and vectorList ?
>>>
>>> ArrayList is double ended (very much like OrderedCollection),
>>> VectorList is single ended. I was just experimenting to see if it
>>> makes a difference.
>
> ok. I like to see such kind of experiment.
> Was the name based on something that people use?

No, it is a randomly chosen and meaningless name. I guess in the end
there will only be one named ArrayList, but I am not sure which
implementation is better.

Just a note to the VM developers: The primitive
Array>>#replaceFrom:to:with:startingAt: is absolutely central to the
implementation of efficient collections. While it works well if you
copy from one array to the other, it is broken if source and
destination array are the same and the areas overlap. Would it be
possible to fix this. Even "memmove(void*, void*, size_t)" in C can
handle this situation correctly.

>>>> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
>>>
>>> The core idea is to split iteration from containment; I think a
>>> horrible design mistake in the Smalltalk-80 collections.
>
> I thought about that when I read the Iterator.
> I would not say that this is horrible. I think that for default case this is not that bad.
> Now when you want to navigate a large graph and control the navigation then you should have an iterator.

I think it is pretty horrible. I can think of at least 4 meaningful
ways to iterate over an simple array (for other collections there are
even more ways):

    1. forward: #do:, #collect:, #select:, #detect:, #inject:into:, ...
    2. forward with index: #keysAndValuesDo:, #collectWithIndex:,
everything else is not possible
    3. backward: #reverseDo:, everything else is not possible
    4. backward with index: not possible

If you split the iterator into a separate object, suddenly all of this
becomes trivial. A #collect: remains a #collect: no matter if you are
going forward or backward, or with or without index.

Lukas

--
Lukas Renggli
www.lukas-renggli.ch

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Ben Coman
Lukas Renggli wrote:

>>>>> what is the diff between arrayList and vectorList ?
>>>>>          
>>>> ArrayList is double ended (very much like OrderedCollection),
>>>> VectorList is single ended. I was just experimenting to see if it
>>>> makes a difference.
>>>>        
>> ok. I like to see such kind of experiment.
>> Was the name based on something that people use?
>>    
>
> No, it is a randomly chosen and meaningless name. I guess in the end
> there will only be one named ArrayList, but I am not sure which
> implementation is better.
>
>  
I wasn't sure what double-ended versus single-ended meant, and found
some answer at the obvious place [1]
which mentions Ada.Containers.Vectors is a dynamic array implementation
which seems consistent with C++ [2].

While looking around I happened to bump into [3] which was too much for
me but may be of interest to anyone playing with data structres.  
Skimming this shows it discussing efficiency of data structures in
functional languages together with lazy variants of imperative language
data structures.  Would such apply to Smalltalk or is the
object-oriented style of Smalltalk considered imperative rather than
functional?

[1] http://en.wikipedia.org/wiki/Double-ended_queue
[2] http://en.wikipedia.org/wiki/Sequence_container_%28C%2B%2B%29
[3] http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Frank Shearar-3
On 3 February 2012 15:44, Ben Coman <[hidden email]> wrote:

> Lukas Renggli wrote:
>>>>>>
>>>>>> what is the diff between arrayList and vectorList ?
>>>>>>
>>>>>
>>>>> ArrayList is double ended (very much like OrderedCollection),
>>>>> VectorList is single ended. I was just experimenting to see if it
>>>>> makes a difference.
>>>>>
>>>
>>> ok. I like to see such kind of experiment.
>>> Was the name based on something that people use?
>>>
>>
>>
>> No, it is a randomly chosen and meaningless name. I guess in the end
>> there will only be one named ArrayList, but I am not sure which
>> implementation is better.
>>
>>
>
> I wasn't sure what double-ended versus single-ended meant, and found some
> answer at the obvious place [1]
> which mentions Ada.Containers.Vectors is a dynamic array implementation
> which seems consistent with C++ [2].
> While looking around I happened to bump into [3] which was too much for me
> but may be of interest to anyone playing with data structres.  Skimming this
> shows it discussing efficiency of data structures in functional languages
> together with lazy variants of imperative language data structures.  Would
> such apply to Smalltalk or is the object-oriented style of Smalltalk
> considered imperative rather than functional?

The standard tool set - OrderedCollection, Array, etc., are not
functional at all - (myArray at: 1 put: 2) mutates myArray, - so I'd
put them firmly on the "imperative" side of the fence.

There's nothing stopping one from writing functional data structures -
Levente Uzonyi's written some persistent data structures, as have I.
("Persistent" means you get new versions of a data structure; if you
hang onto those old versions you can roll back your changes.)
http://www.squeaksource.com/Nutcracker/ is my own play area for these
sorts of structures - PersistentUnionFind looks like a functional data
structure while internally massively using side effects.
http://www.lshift.net/blog/2011/12/31/translating-a-persistent-union-find-from-ml-to-smalltalk
has references to the original papers I used for my translation.

Okasaki's book is really good reading, if a bit advanced. It also has
a bunch of stuff beyond just showing functional data structures. (Note
that the red-black tree implementation is _incomplete_ - he leaves
deleting nodes as an exercise for the reader. (See
http://matt.might.net/articles/red-black-delete/))

frank

> [1] http://en.wikipedia.org/wiki/Double-ended_queue
> [2] http://en.wikipedia.org/wiki/Sequence_container_%28C%2B%2B%29
> [3] http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
>

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Nicolas Cellier
In reply to this post by Lukas Renggli
2012/2/3 Lukas Renggli <[hidden email]>:

>>>>> what is the diff between arrayList and vectorList ?
>>>>
>>>> ArrayList is double ended (very much like OrderedCollection),
>>>> VectorList is single ended. I was just experimenting to see if it
>>>> makes a difference.
>>
>> ok. I like to see such kind of experiment.
>> Was the name based on something that people use?
>
> No, it is a randomly chosen and meaningless name. I guess in the end
> there will only be one named ArrayList, but I am not sure which
> implementation is better.
>
> Just a note to the VM developers: The primitive
> Array>>#replaceFrom:to:with:startingAt: is absolutely central to the
> implementation of efficient collections. While it works well if you
> copy from one array to the other, it is broken if source and
> destination array are the same and the areas overlap. Would it be
> possible to fix this. Even "memmove(void*, void*, size_t)" in C can
> handle this situation correctly.
>

+1, I already asked for this one, this would be useful also for
Xtreams, and would remove the need for some preconditions
http://permalink.gmane.org/gmane.comp.lang.smalltalk.squeak.general/152057.

Nicolas

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Eliot Miranda-2
In reply to this post by Lukas Renggli


On Fri, Feb 3, 2012 at 6:18 AM, Lukas Renggli <[hidden email]> wrote:
>>>> what is the diff between arrayList and vectorList ?
>>>
>>> ArrayList is double ended (very much like OrderedCollection),
>>> VectorList is single ended. I was just experimenting to see if it
>>> makes a difference.
>
> ok. I like to see such kind of experiment.
> Was the name based on something that people use?

No, it is a randomly chosen and meaningless name. I guess in the end
there will only be one named ArrayList, but I am not sure which
implementation is better.

Just a note to the VM developers: The primitive
Array>>#replaceFrom:to:with:startingAt: is absolutely central to the
implementation of efficient collections. While it works well if you
copy from one array to the other, it is broken if source and
destination array are the same and the areas overlap. Would it be
possible to fix this. Even "memmove(void*, void*, size_t)" in C can
handle this situation correctly.

The problems are that the primitive is defined to be destructive, and code could be depending on the destructive update behaviour.  Would it be feasible to use a new primitive that did the right thing in the case of overlap, or do you definitely want to change primitive 105?


>>>> Do you have some kind of high level description of Container explaining the rationale, ideas and approach.
>>>
>>> The core idea is to split iteration from containment; I think a
>>> horrible design mistake in the Smalltalk-80 collections.
>
> I thought about that when I read the Iterator.
> I would not say that this is horrible. I think that for default case this is not that bad.
> Now when you want to navigate a large graph and control the navigation then you should have an iterator.

I think it is pretty horrible. I can think of at least 4 meaningful
ways to iterate over an simple array (for other collections there are
even more ways):

   1. forward: #do:, #collect:, #select:, #detect:, #inject:into:, ...
   2. forward with index: #keysAndValuesDo:, #collectWithIndex:,
everything else is not possible
   3. backward: #reverseDo:, everything else is not possible
   4. backward with index: not possible

If you split the iterator into a separate object, suddenly all of this
becomes trivial. A #collect: remains a #collect: no matter if you are
going forward or backward, or with or without index.

Lukas

--
Lukas Renggli
www.lukas-renggli.ch




--
best,
Eliot

Reply | Threaded
Open this post in threaded view
|

Re: [Vm-dev] Re: About linkedlist

Lukas Renggli
>> >>>> what is the diff between arrayList and vectorList ?
>> >>>
>> >>> ArrayList is double ended (very much like OrderedCollection),
>> >>> VectorList is single ended. I was just experimenting to see if it
>> >>> makes a difference.
>> >
>> > ok. I like to see such kind of experiment.
>> > Was the name based on something that people use?
>>
>> No, it is a randomly chosen and meaningless name. I guess in the end
>> there will only be one named ArrayList, but I am not sure which
>> implementation is better.
>>
>> Just a note to the VM developers: The primitive
>> Array>>#replaceFrom:to:with:startingAt: is absolutely central to the
>> implementation of efficient collections. While it works well if you
>> copy from one array to the other, it is broken if source and
>> destination array are the same and the areas overlap. Would it be
>> possible to fix this. Even "memmove(void*, void*, size_t)" in C can
>> handle this situation correctly.
>
> The problems are that the primitive is defined to be destructive, and code could be depending on the destructive update behaviour.  Would it be feasible to use a new primitive that did the right thing in the case of overlap, or do you definitely want to change primitive 105?

A new primitive would be prefect. Like this we can even have a nice
fallback in case the VM doesn't have the primitive yet.

Lukas

--
Lukas Renggli
www.lukas-renggli.ch

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Stéphane Ducasse
In reply to this post by Frank Shearar-3
>>>
>>
>> I wasn't sure what double-ended versus single-ended meant, and found some
>> answer at the obvious place [1]
>> which mentions Ada.Containers.Vectors is a dynamic array implementation
>> which seems consistent with C++ [2].
>> While looking around I happened to bump into [3] which was too much for me
>> but may be of interest to anyone playing with data structres.  Skimming this
>> shows it discussing efficiency of data structures in functional languages
>> together with lazy variants of imperative language data structures.  Would
>> such apply to Smalltalk or is the object-oriented style of Smalltalk
>> considered imperative rather than functional?
>
> The standard tool set - OrderedCollection, Array, etc., are not
> functional at all - (myArray at: 1 put: 2) mutates myArray, - so I'd
> put them firmly on the "imperative" side of the fence.
>
> There's nothing stopping one from writing functional data structures -
> Levente Uzonyi's written some persistent data structures, as have I.
> ("Persistent" means you get new versions of a data structure; if you
> hang onto those old versions you can roll back your changes.)

Can you explain a bit more Persistent?

Tx


> http://www.squeaksource.com/Nutcracker/ is my own play area for these
> sorts of structures - PersistentUnionFind looks like a functional data
> structure while internally massively using side effects.
> http://www.lshift.net/blog/2011/12/31/translating-a-persistent-union-find-from-ml-to-smalltalk
> has references to the original papers I used for my translation.
>
> Okasaki's book is really good reading, if a bit advanced. It also has
> a bunch of stuff beyond just showing functional data structures. (Note
> that the red-black tree implementation is _incomplete_ - he leaves
> deleting nodes as an exercise for the reader. (See
> http://matt.might.net/articles/red-black-delete/))
>
> frank
>
>> [1] http://en.wikipedia.org/wiki/Double-ended_queue
>> [2] http://en.wikipedia.org/wiki/Sequence_container_%28C%2B%2B%29
>> [3] http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
>>
>


Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Stéphane Ducasse
In reply to this post by Nicolas Cellier
lukas may be you should send that to the vm mailing-list.
If you need we can ask igor :) (even if he is busy right now).

Stef


On Feb 3, 2012, at 5:35 PM, Nicolas Cellier wrote:

>>
>> Just a note to the VM developers: The primitive
>> Array>>#replaceFrom:to:with:startingAt: is absolutely central to the
>> implementation of efficient collections. While it works well if you
>> copy from one array to the other, it is broken if source and
>> destination array are the same and the areas overlap. Would it be
>> possible to fix this. Even "memmove(void*, void*, size_t)" in C can
>> handle this situation correctly.
>>
>


Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Igor Stasenko
On 3 February 2012 21:42, Stéphane Ducasse <[hidden email]> wrote:
> lukas may be you should send that to the vm mailing-list.
> If you need we can ask igor :) (even if he is busy right now).
>
implementing it wont be a big deal.

i just trying to understand, what is "destructive" vs
"non-destructive" behavior in
replaceFrom:to:with:startingAt:

is it right in my understanding that you want to always meet a
following criteria:

receiver replaceFrom: a to: b with: replacement startingAt: c.

a to: b do: [:i |
  self assert: (receiver at: i) == (replacement at: c + i - 1) ]

? (irrespectible, of course if receiver == replacement or not )


> Stef
>
>
> On Feb 3, 2012, at 5:35 PM, Nicolas Cellier wrote:
>
>>>
>>> Just a note to the VM developers: The primitive
>>> Array>>#replaceFrom:to:with:startingAt: is absolutely central to the
>>> implementation of efficient collections. While it works well if you
>>> copy from one array to the other, it is broken if source and
>>> destination array are the same and the areas overlap. Would it be
>>> possible to fix this. Even "memmove(void*, void*, size_t)" in C can
>>> handle this situation correctly.
>>>
>>
>
>



--
Best regards,
Igor Stasenko.

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Igor Stasenko
oh, wait.. a test should be like following:


rCopy := replacement copy.
receiver replaceFrom: a to: b with: replacement startingAt: c.

a to: b do: [:i |
  self assert: (receiver at: i) == (rCopy at: c + i - 1) ]





--
Best regards,
Igor Stasenko.

Reply | Threaded
Open this post in threaded view
|

Re: About linkedlist

Igor Stasenko
btw, i doubt that there's code which relying on destructive behavior
of that prim.
because in order to use such "destructive behavior" for own benefit it
requires a bit of thought effort :)

if you need such "erasing" (can't even find a proper term for it)
replacement, then it is more
natural that developer will write it by hand, instead of using a
primitive with elusive (and perhaps unintended) behavior.

from other side, making a new prim is better, because then image-side
can do a workarounds if it not there.

and i think we don't even need to implement that prim twice. what we
can do is to fix the implementation of old one and then put it in
additional slot of primitiveTable.


--
Best regards,
Igor Stasenko.

12