This page is no longer maintained — Please continue to the home page at www.scala-lang.org

immutable ArrayBuffer

7 replies
stepancheg
Joined: 2009-01-12,
User offline. Last seen 3 years 32 weeks ago.

Hi.

I haven't found an immutable ArrayBuffer counterpart. Only thing I've
found is Vector.Impl that is a wrapper of mutable.ArrayBuffer and have
a note "todo: insert better vector implementation here". So it is yet
to be done before 2.8 release, I hope?

I'd like to have a class, say immutable.ArrayBuffer, that has fields:

===
class immutable.ArrayBuffer(array: Array[AnyRef], offset: Int, length: Int) {
...
}
===

offset field is important for the fast "drop" operation:

===
def drop(count) =
if (count >= length) immutable.ArrayBuffer.empty
else new immutable.ArrayBuffer(array, offset - count, length - count)
===

Fast "drop" is important for the sequence pattern matching:

===
val seq = very very big sequence based on immutable.ArrayBuffer
seq match {
case Seq(1, rest) => ...
case Seq() => ...
}
===

And, one important thing: mutable.ArrayBuffer should have destructive:
convertToImmutable operation:

===
class mutable.ArrayBuffer {
var array: Array[AnyRef]
var length: Int

def convertToImmutable = {
val r = new immutable.ArrayBuffer(array, 0, length)
array = null
r
}
}
===

So immutable.ArrayBuffer becomes lighter and faster then current
Vector.Impl with the same cost of construction.

S.

odersky
Joined: 2008-07-29,
User offline. Last seen 45 weeks 6 days ago.
Re: immutable ArrayBuffer

On Wed, Sep 23, 2009 at 2:56 AM, Stepan Koltsov wrote:
> Hi.
>
> I haven't found an immutable ArrayBuffer counterpart. Only thing I've
> found is Vector.Impl that is a wrapper of mutable.ArrayBuffer and have
> a note "todo: insert better vector implementation here". So it is yet
> to be done before 2.8 release, I hope?
>
We are working on something like that yes. Whether it comes in time
for the 2.8 release, not sure yet.
And once it exists it can indeed be the default implementation of Sequence.

Cheers

stepancheg
Joined: 2009-01-12,
User offline. Last seen 3 years 32 weeks ago.
Re: immutable ArrayBuffer

On Wed, Sep 23, 2009 at 11:25, martin odersky wrote:
> On Wed, Sep 23, 2009 at 2:56 AM, Stepan Koltsov wrote:
>> I haven't found an immutable ArrayBuffer counterpart. Only thing I've
>> found is Vector.Impl that is a wrapper of mutable.ArrayBuffer and have
>> a note "todo: insert better vector implementation here". So it is yet
>> to be done before 2.8 release, I hope?
>>
> We are working on something like that yes. Whether it comes in time
> for the 2.8 release, not sure yet.

Is there any catch? Implementing immutable ArrayBuffer seems to be
easy and straightforward.

S.

stepancheg
Joined: 2009-01-12,
User offline. Last seen 3 years 32 weeks ago.
Re: immutable ArrayBuffer

On Thu, Sep 24, 2009 at 15:21, Stepan Koltsov wrote:
> On Wed, Sep 23, 2009 at 11:25, martin odersky wrote:
>> On Wed, Sep 23, 2009 at 2:56 AM, Stepan Koltsov wrote:
>>> I haven't found an immutable ArrayBuffer counterpart. Only thing I've
>>> found is Vector.Impl that is a wrapper of mutable.ArrayBuffer and have
>>> a note "todo: insert better vector implementation here". So it is yet
>>> to be done before 2.8 release, I hope?
>>>
>> We are working on something like that yes. Whether it comes in time
>> for the 2.8 release, not sure yet.
>
> Is there any catch? Implementing immutable ArrayBuffer seems to be
> easy and straightforward.

One maillist reader pointed in private mail that such immutable
ArrayBuffer will have slow "create copy with single element changed"
operation. That is acceptable to me. Scala, unlike Haskell, allows
mutable data structures, and such mutable structures can be used to
build immutables. I'd even reduce immutable.HashMap to standard hash
map implementation without copy-on-write magic.

> S.
>

Colin Bullock
Joined: 2009-01-23,
User offline. Last seen 42 years 45 weeks ago.
Re: immutable ArrayBuffer

One maillist reader pointed in private mail that such immutable
ArrayBuffer will have slow "create copy with single element changed"
operation. That is acceptable to me. Scala, unlike Haskell, allows
mutable data structures, and such mutable structures can be used to
build immutables. I'd even reduce immutable.HashMap to standard hash
map implementation without copy-on-write magic.


I don't think there's a silver bullet here; one must choose the appropriate data structures and performance trade-offs based upon the specific situation and usage. For instance, if I were creating an immutable random-access list of 100 elements only once, but subsequently accessing it millions of times, I'd be more than happy to accept O(n) writes in exchange for O(1) reads. I can imagine plenty of other situations where the exact opposite may be the case.

That being said, there are plenty of immutable and persistent data structures that find a happy middle ground. There are a number implementations of random-access data structures which provide at least O(log n) updates (many of which retain constant-time list-like operations at the same time); search for "skew binary random access list" for a good example.

Finally, I'd love to see an immutable data structure, implemented on top of a mutable one, that doesn't require copy-on-write semantics of some form and still manages to stay fully persistent. I think you'll find a good immutable implementation will often copy far less data to maintain these guarantees (again, depending on the intended usage).

- Colin
Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: immutable ArrayBuffer

Colin,
Take a look at Chris Okasaki: Purely Functional Data Structures. Scalaz
has a difference list and will soon have a 2-3 finger tree backed
sequence. These might help.

Colin Bullock wrote:
>
> One maillist reader pointed in private mail that such immutable
> ArrayBuffer will have slow "create copy with single element changed"
> operation. That is acceptable to me. Scala, unlike Haskell, allows
> mutable data structures, and such mutable structures can be used to
> build immutables. I'd even reduce immutable.HashMap to standard hash
> map implementation without copy-on-write magic.
>
>
> I don't think there's a silver bullet here; one must choose the
> appropriate data structures and performance trade-offs based upon the
> specific situation and usage. For instance, if I were creating an
> immutable random-access list of 100 elements only once, but
> subsequently accessing it millions of times, I'd be more than happy to
> accept O(n) writes in exchange for O(1) reads. I can imagine plenty of
> other situations where the exact opposite may be the case.
>
> That being said, there are plenty of immutable and persistent data
> structures that find a happy middle ground. There are a number
> implementations of random-access data structures which provide at
> least O(log n) updates (many of which retain constant-time list-like
> operations at the same time); search for "skew binary random access
> list" for a good example.
>
> Finally, I'd love to see an immutable data structure, implemented on
> top of a mutable one, that doesn't require copy-on-write semantics of
> some form and still manages to stay fully persistent. I think you'll
> find a good immutable implementation will often copy far less data to
> maintain these guarantees (again, depending on the intended usage).
>
> - Colin

stepancheg
Joined: 2009-01-12,
User offline. Last seen 3 years 32 weeks ago.
Re: immutable ArrayBuffer

On Fri, Sep 25, 2009 at 01:54, Tony Morris wrote:
> Take a look at Chris Okasaki: Purely Functional Data Structures. Scalaz
> has a difference list and will soon have a 2-3 finger tree backed
> sequence. These might help.

Lists based on 2-3 finger tree allow log(N) access, while plain
ArrayBuffer has very fast O(1) access. 2-3 finger trees are cool, but
they don't replace readonly ArrayBuffer, that is much faster in many
of operations (map, filter, take, drop, apply). (I wrote this for
people, how started to think that 2-3 finger trees are silver bullet).

S.

> Colin Bullock wrote:
>>
>>     One maillist reader pointed in private mail that such immutable
>>     ArrayBuffer will have slow "create copy with single element changed"
>>     operation. That is acceptable to me. Scala, unlike Haskell, allows
>>     mutable data structures, and such mutable structures can be used to
>>     build immutables. I'd even reduce immutable.HashMap to standard hash
>>     map implementation without copy-on-write magic.
>>
>>
>> I don't think there's a silver bullet here; one must choose the
>> appropriate data structures and performance trade-offs based upon the
>> specific situation and usage. For instance, if I were creating an
>> immutable random-access list of 100 elements only once, but
>> subsequently accessing it millions of times, I'd be more than happy to
>> accept O(n) writes in exchange for O(1) reads. I can imagine plenty of
>> other situations where the exact opposite may be the case.
>>
>> That being said, there are plenty of immutable and persistent data
>> structures that find a happy middle ground. There are a number
>> implementations of random-access data structures which provide at
>> least O(log n) updates (many of which retain constant-time list-like
>> operations at the same time); search for "skew binary random access
>> list" for a good example.
>>
>> Finally, I'd love to see an immutable data structure, implemented on
>> top of a mutable one, that doesn't require copy-on-write semantics of
>> some form and still manages to stay fully persistent. I think you'll
>> find a good immutable implementation will often copy far less data to
>> maintain these guarantees (again, depending on the intended usage).
>>
>> - Colin
>
> --
> Tony Morris
> http://tmorris.net/
>
>
>

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: immutable ArrayBuffer

I'm just suggesting an possible alternative. I think there should be an
immutable array projection too (with O(1) access) for situations that
require it.
Just like Haskell (see Data.Array), Scala allows mutable data structures
from which to project immutable ones. Someone ought to write it.

Stepan Koltsov wrote:
> On Fri, Sep 25, 2009 at 01:54, Tony Morris wrote:
>
>> Take a look at Chris Okasaki: Purely Functional Data Structures. Scalaz
>> has a difference list and will soon have a 2-3 finger tree backed
>> sequence. These might help.
>>
>
> Lists based on 2-3 finger tree allow log(N) access, while plain
> ArrayBuffer has very fast O(1) access. 2-3 finger trees are cool, but
> they don't replace readonly ArrayBuffer, that is much faster in many
> of operations (map, filter, take, drop, apply). (I wrote this for
> people, how started to think that 2-3 finger trees are silver bullet).
>
> S.
>
>
>> Colin Bullock wrote:
>>
>>> One maillist reader pointed in private mail that such immutable
>>> ArrayBuffer will have slow "create copy with single element changed"
>>> operation. That is acceptable to me. Scala, unlike Haskell, allows
>>> mutable data structures, and such mutable structures can be used to
>>> build immutables. I'd even reduce immutable.HashMap to standard hash
>>> map implementation without copy-on-write magic.
>>>
>>>
>>> I don't think there's a silver bullet here; one must choose the
>>> appropriate data structures and performance trade-offs based upon the
>>> specific situation and usage. For instance, if I were creating an
>>> immutable random-access list of 100 elements only once, but
>>> subsequently accessing it millions of times, I'd be more than happy to
>>> accept O(n) writes in exchange for O(1) reads. I can imagine plenty of
>>> other situations where the exact opposite may be the case.
>>>
>>> That being said, there are plenty of immutable and persistent data
>>> structures that find a happy middle ground. There are a number
>>> implementations of random-access data structures which provide at
>>> least O(log n) updates (many of which retain constant-time list-like
>>> operations at the same time); search for "skew binary random access
>>> list" for a good example.
>>>
>>> Finally, I'd love to see an immutable data structure, implemented on
>>> top of a mutable one, that doesn't require copy-on-write semantics of
>>> some form and still manages to stay fully persistent. I think you'll
>>> find a good immutable implementation will often copy far less data to
>>> maintain these guarantees (again, depending on the intended usage).
>>>
>>> - Colin
>>>
>> --
>> Tony Morris
>> http://tmorris.net/
>>
>>
>>
>>
>
>

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland