- About Scala
- Documentation
- Code Examples
- Software
- Scala Developers
immutable var vs. mutable val
Mon, 2010-02-22, 06:20
I understand that vals are preferred to vars, and immutable objects are preferred to mutable objects. But if something needs to be modified and an immutable val won't work, which is prefereable in general: an immutable var or a mutable val?
When building strings, for example, you can use += on a String and create a new string every time to add something, or you can use StringBuilder and keep working with the same object, then convert to a String when you are done. The latter seems more efficient to me, but I'm just guessing. The same issue comes up with Maps, Lists, etc. Any guidance will be appreciated. Thanks.
Russ P.
--
http://RussP.us
When building strings, for example, you can use += on a String and create a new string every time to add something, or you can use StringBuilder and keep working with the same object, then convert to a String when you are done. The latter seems more efficient to me, but I'm just guessing. The same issue comes up with Maps, Lists, etc. Any guidance will be appreciated. Thanks.
Russ P.
--
http://RussP.us
Mon, 2010-02-22, 12:47
#2
Re: immutable var vs. mutable val
There are advantages and disadvantages to immutable data structures. The
disadvantages however seem to be apropriate e. g. in concurrency contexts.
It also depends on what Kind of datastructures you are refering to, if you
google: persistent datastructures you will find some nice explainations
which might Be helpfull.
Regards andreas
Mon, 2010-02-22, 13:07
#3
RE: immutable var vs. mutable val
I asked a question about the appropriate immutable.Map structure to use in Scala in the use-case of a very large (100k+ entries), high-throughput (around a 1m insertions/updates as fast as they can be processed) immutable Map because the default HashMap looked to me like a very expensive structure to use. This was in the case where I had a private Map and didn't care about concurrency (the Map was the internal, private state of an actor).
The consensus seemed to be that using an immutable structure in the case was a poor design decision and the default immutable HashMap in particular is a "broken" class. I was advised to use a mutable structure instead.
See more here: http://stackoverflow.com/questions/2298046/immutable-map-implementation-...
Chris
> From: tonymorris@gmail.com
>
> In the very few cases where something does in fact need to be modified
> use a var to the immutable structure. I'm betting you don't have one
> of those cases based on your given example.
>
> Tony Morris
> http://tmorris.net/
Do you have a story that started on Hotmail? Tell us now
The consensus seemed to be that using an immutable structure in the case was a poor design decision and the default immutable HashMap in particular is a "broken" class. I was advised to use a mutable structure instead.
See more here: http://stackoverflow.com/questions/2298046/immutable-map-implementation-...
Chris
> From: tonymorris@gmail.com
>
> In the very few cases where something does in fact need to be modified
> use a var to the immutable structure. I'm betting you don't have one
> of those cases based on your given example.
>
> Tony Morris
> http://tmorris.net/
Do you have a story that started on Hotmail? Tell us now
Mon, 2010-02-22, 17:17
#4
Re: immutable var vs. mutable val
On Mon, Feb 22, 2010 at 12:20 AM, Russ Paielli <russ.paielli@gmail.com> wrote:
You're right: the latter is more efficient. It's also potentially more misleading: the "var" token is a clear indication that the value might change, whereas "xBuilder" is a little less obvious.
As a practical matter, performance is often a significant concern. There are many cases where the performance hit of immutable data structures is overstated, irrelevant, or nonexistent. But sometimes mutability is the most effective way to solve a problem.
In that case, the question I usually ask is: can I isolate all of my mutation to a single code block? If yes, it's a "var". If not, it's a "val" that gets passed around. I try not to have mutable vals flying around all over the code, but it's often very useful to avoid code duplication by having a common routine (e.g. to manipulate some values and stuff them into a StringBuilder) that takes a mutable class as input.
For example, one very common pattern I use for high-performance code is an array-wrapping iterator. Suppose, for instance, I have a long list (i.e. millions) of Short x,y coordinates and I need to manipulate them. Assuming some 2-ary Vector class, I could, in 2.8, do something like
list.grouped(2).map( _ match { case x::y::Nil => Vector(x,y); case _ => Vector.zero })
but here, every short is boxed, every pair is stuck into list objects, and then into a vector object. If you add it all up, it's something like 10-20x overhead in both space and time (at least if you're mostly doing simple operations like adding and multiplying the coordinates).
Rather than throw up my hands and revert to vars and while loops over arrays, however, I switch to using a wrapper class that looks something like
class VecWrap(data: Array[Short]) extends Vector with Iterator[Vector] {
var index = -1
def hasNext = index+1 < data.length
def next = { index += 1; this }
// Presumably have inherited math operations from Vector
}
Now I get all the advantages of map and filter and foreach and whatnot with a minimal performance hit. It is still mutable, hairy, and potentially dangerous, but it is less so than groping around with raw arrays. Now, when I need to do work on these giant coordinate lists, I have the option of passing VecWraps around.
But now that I have these less-safe operations going on, I try to hide them well from the rest of my code that doesn't need to know about the details of array access; if I end up writing a few points to the screen, for instance, I'll call a method that will return an immutable copy rather than relying on a dangerous mutable VecWrap.
This sort of approach (if not that exact pattern) works well for things like mutable HashMaps, giant string-building routines, heavy-duty file parsing, and so on.
--Rex
I understand that vals are preferred to vars, and immutable objects are preferred to mutable objects. But if something needs to be modified and an immutable val won't work, which is prefereable in general: an immutable var or a mutable val?
When building strings, for example, you can use += on a String and create a new string every time to add something, or you can use StringBuilder and keep working with the same object, then convert to a String when you are done. The latter seems more efficient to me, but I'm just guessing. The same issue comes up with Maps, Lists, etc. Any guidance will be appreciated. Thanks.
You're right: the latter is more efficient. It's also potentially more misleading: the "var" token is a clear indication that the value might change, whereas "xBuilder" is a little less obvious.
As a practical matter, performance is often a significant concern. There are many cases where the performance hit of immutable data structures is overstated, irrelevant, or nonexistent. But sometimes mutability is the most effective way to solve a problem.
In that case, the question I usually ask is: can I isolate all of my mutation to a single code block? If yes, it's a "var". If not, it's a "val" that gets passed around. I try not to have mutable vals flying around all over the code, but it's often very useful to avoid code duplication by having a common routine (e.g. to manipulate some values and stuff them into a StringBuilder) that takes a mutable class as input.
For example, one very common pattern I use for high-performance code is an array-wrapping iterator. Suppose, for instance, I have a long list (i.e. millions) of Short x,y coordinates and I need to manipulate them. Assuming some 2-ary Vector class, I could, in 2.8, do something like
list.grouped(2).map( _ match { case x::y::Nil => Vector(x,y); case _ => Vector.zero })
but here, every short is boxed, every pair is stuck into list objects, and then into a vector object. If you add it all up, it's something like 10-20x overhead in both space and time (at least if you're mostly doing simple operations like adding and multiplying the coordinates).
Rather than throw up my hands and revert to vars and while loops over arrays, however, I switch to using a wrapper class that looks something like
class VecWrap(data: Array[Short]) extends Vector with Iterator[Vector] {
var index = -1
def hasNext = index+1 < data.length
def next = { index += 1; this }
// Presumably have inherited math operations from Vector
}
Now I get all the advantages of map and filter and foreach and whatnot with a minimal performance hit. It is still mutable, hairy, and potentially dangerous, but it is less so than groping around with raw arrays. Now, when I need to do work on these giant coordinate lists, I have the option of passing VecWraps around.
But now that I have these less-safe operations going on, I try to hide them well from the rest of my code that doesn't need to know about the details of array access; if I end up writing a few points to the screen, for instance, I'll call a method that will return an immutable copy rather than relying on a dangerous mutable VecWrap.
This sort of approach (if not that exact pattern) works well for things like mutable HashMaps, giant string-building routines, heavy-duty file parsing, and so on.
--Rex
Tue, 2010-02-23, 02:27
#5
Re: immutable var vs. mutable val
On Mon, Feb 22, 2010 at 2:27 AM, Tony Morris <tonymorris@gmail.com> wrote:
I don't doubt that you know what you're talking about, but I'm curious to know why an immutable var is preferable to a mutable val. I'm guessing it has something to do with concurrency and threads. Am I right?
As for the mutable StringBuilder, I find myself using it for toString methods. It is nearly interchangable with the immutable String, since they both support +=. With String, however, you end up creating a new object every time you add characters to the string. I'm no efficiency freak, but that seems grossly inefficient to me (but since toString is usually not called at a super high rate, it probably doesn't matter much anyway). Are you saying StringBuilder should be avoided? If so, why? Is it concurrency again?
--Russ P.
In the very few cases where something does in fact need to be modified use a var to the immutable structure. I'm betting you don't have one of those cases based on your given example.
I don't doubt that you know what you're talking about, but I'm curious to know why an immutable var is preferable to a mutable val. I'm guessing it has something to do with concurrency and threads. Am I right?
As for the mutable StringBuilder, I find myself using it for toString methods. It is nearly interchangable with the immutable String, since they both support +=. With String, however, you end up creating a new object every time you add characters to the string. I'm no efficiency freak, but that seems grossly inefficient to me (but since toString is usually not called at a super high rate, it probably doesn't matter much anyway). Are you saying StringBuilder should be avoided? If so, why? Is it concurrency again?
--Russ P.
On Feb 22, 2010, at 15:20, Russ Paielli <russ.paielli@gmail.com> wrote:
I understand that vals are preferred to vars, and immutable objects are preferred to mutable objects. But if something needs to be modified and an immutable val won't work, which is prefereable in general: an immutable var or a mutable val?
When building strings, for example, you can use += on a String and create a new string every time to add something, or you can use StringBuilder and keep working with the same object, then convert to a String when you are done. The latter seems more efficient to me, but I'm just guessing. The same issue comes up with Maps, Lists, etc. Any guidance will be appreciated. Thanks.
Russ P.
Tue, 2010-02-23, 02:37
#6
Re: immutable var vs. mutable val
Russ Paielli wrote:
> On Mon, Feb 22, 2010 at 2:27 AM, Tony Morris wrote:
>
>
>> In the very few cases where something does in fact need to be modified use
>> a var to the immutable structure. I'm betting you don't have one of those
>> cases based on your given example.
>>
>
>
> I don't doubt that you know what you're talking about, but I'm curious to
> know why an immutable var is preferable to a mutable val. I'm guessing it
> has something to do with concurrency and threads. Am I right?
>
> As for the mutable StringBuilder, I find myself using it for toString
> methods. It is nearly interchangable with the immutable String, since they
> both support +=. With String, however, you end up creating a new object
> every time you add characters to the string. I'm no efficiency freak, but
> that seems grossly inefficient to me (but since toString is usually not
> called at a super high rate, it probably doesn't matter much anyway). Are
> you saying StringBuilder should be avoided? If so, why? Is it concurrency
> again?
>
> --Russ P.
>
>
>
>
>>
>> On Feb 22, 2010, at 15:20, Russ Paielli wrote:
>>
>> I understand that vals are preferred to vars, and immutable objects are
>>
>>> preferred to mutable objects. But if something needs to be modified and an
>>> immutable val won't work, which is prefereable in general: an immutable var
>>> or a mutable val?
>>>
>>> When building strings, for example, you can use += on a String and create
>>> a new string every time to add something, or you can use StringBuilder and
>>> keep working with the same object, then convert to a String when you are
>>> done. The latter seems more efficient to me, but I'm just guessing. The same
>>> issue comes up with Maps, Lists, etc. Any guidance will be appreciated.
>>> Thanks.
>>>
>>> Russ P.
>>>
>>> --
>>> http://RussP.us
>>>
>>>
>
>
>
It's mostly in keeping with the thesis of functional programming and
receiving the subsequent benefits i.e. code that is easier to reason
about, better compositionality. In this case, the "movement of the
side-effect to the outer layer" is so minimal that the impact is likely
to be same. In other words, you get a very minor improvement at no expense.
Tue, 2010-02-23, 06:37
#7
Re: immutable var vs. mutable val
Russ Paielli wrote:
> On Mon, Feb 22, 2010 at 2:27 AM, Tony Morris wrote:
>
>
>> In the very few cases where something does in fact need to be modified use
>> a var to the immutable structure. I'm betting you don't have one of those
>> cases based on your given example.
>>
>
>
> I don't doubt that you know what you're talking about, but I'm curious to
> know why an immutable var is preferable to a mutable val. I'm guessing it
> has something to do with concurrency and threads. Am I right?
>
> As for the mutable StringBuilder, I find myself using it for toString
> methods. It is nearly interchangable with the immutable String, since they
> both support +=. With String, however, you end up creating a new object
> every time you add characters to the string. I'm no efficiency freak, but
> that seems grossly inefficient to me (but since toString is usually not
> called at a super high rate, it probably doesn't matter much anyway). Are
> you saying StringBuilder should be avoided? If so, why? Is it concurrency
> again?
>
> --Russ P.
>
>
>
>
>>
>> On Feb 22, 2010, at 15:20, Russ Paielli wrote:
>>
>> I understand that vals are preferred to vars, and immutable objects are
>>
>>> preferred to mutable objects. But if something needs to be modified and an
>>> immutable val won't work, which is prefereable in general: an immutable var
>>> or a mutable val?
>>>
>>> When building strings, for example, you can use += on a String and create
>>> a new string every time to add something, or you can use StringBuilder and
>>> keep working with the same object, then convert to a String when you are
>>> done. The latter seems more efficient to me, but I'm just guessing. The same
>>> issue comes up with Maps, Lists, etc. Any guidance will be appreciated.
>>> Thanks.
>>>
>>> Russ P.
>>>
>>> --
>>> http://RussP.us
>>>
>>>
>
>
>
To answer your second question, String is the wrong data type for
displaying objects. Instead, prefer List[Char] or FingerTree[Char] in
which case, the problems of having to perform side-effects to achieve
reasonable (but still relatively poor) performance disappear. There is
more than one reason not to use Object.toString; this is one of them.
All of those reasons put together makes a compelling case to avoid it
altogether, which is precisely what I (and others) do. In other words,
you are right about having to use StringBuilder to achieve performance
compared to += in a loop (and I would encourage to keep doing so), but
only to the extent that you are right to use toString returning
java.lang.String, for which Scala provides syntactical benefits (I'll
let you decide where to trade on this contention).
Tue, 2010-02-23, 06:47
#8
Re: immutable var vs. mutable val
If you want a not-broken immutable Map in Scala, TreeHashMap is not a bad choice.
Supposedly there will be a not-broken persistent immutable HashMap for 2.8.
That said, in a high-throughput, private Map, it will almost certainly more efficient to use a mutable Map than any immutable structure.
--j
On Mon, Feb 22, 2010 at 4:05 AM, christopher marshall <oxbow_lakes@hotmail.com> wrote:
Supposedly there will be a not-broken persistent immutable HashMap for 2.8.
That said, in a high-throughput, private Map, it will almost certainly more efficient to use a mutable Map than any immutable structure.
--j
On Mon, Feb 22, 2010 at 4:05 AM, christopher marshall <oxbow_lakes@hotmail.com> wrote:
I asked a question about the appropriate immutable.Map structure to use in Scala in the use-case of a very large (100k+ entries), high-throughput (around a 1m insertions/updates as fast as they can be processed) immutable Map because the default HashMap looked to me like a very expensive structure to use. This was in the case where I had a private Map and didn't care about concurrency (the Map was the internal, private state of an actor).
The consensus seemed to be that using an immutable structure in the case was a poor design decision and the default immutable HashMap in particular is a "broken" class. I was advised to use a mutable structure instead.
See more here: http://stackoverflow.com/questions/2298046/immutable-map-implementation-for-huge-maps
Chris
> From: tonymorris@gmail.com
>
> In the very few cases where something does in fact need to be modified
> use a var to the immutable structure. I'm betting you don't have one
> of those cases based on your given example.
>
> Tony Morris
> http://tmorris.net/
Do you have a story that started on Hotmail? Tell us now
Tue, 2010-02-23, 17:07
#9
Re: immutable var vs. mutable val
On Tue, Feb 23, 2010 at 12:19 AM, Tony Morris <tonymorris@gmail.com> wrote:
The "problems" would only disappear because you're _always_ stuck with relatively poor performance. Even if @specialized, List requires one layer of boxing (without specialization, it needs two) to wrap the "next" pointer. If performance matters, either in terms of speed or size, this is only marginally less wasteful than the O(n^2) accumulation time for Strings being built a character at a time. You'll have the same O(n^2) if you aren't able to build your entire List[Char] at once or in reverse order, as you'll spend all your time reversing and/or traversing the list; Finger Trees (not currently in the main Scala library, by the way) avoid this problem at the expense of even more per-item overhead, and still don't solve the problem of compositing if kept balanced as they usually are (i.e. you build the answer for A and B and have to _copy_ (not refer to) those answers to print C that contains those two).
An _un_balanced tree structure would be a good choice for output as it would composite well.
But if you bring in all of that heavy-duty algorithmic complexity, and put in all the work required to wrap it nicely in some easy-to-use library, you _still_ are a constant factor of 10 or so behind something like StringBuilder. You'd need to composite ~10 layers deep before you saw a performance improvement. (With JVM improvments, this probably could be cut in half, but still....)
Now, if you're going to try for fast output without using toString, you can replace it with a text injector that sticks the output in the right spot into an array class that does expansions by adding arrays rather than recopying. This is algorithmically simple, low-overhead, and necessarily way faster than any method that does not simply use characters to build up the text.
Using higher-order data structures like Finger Trees have some great advantages when it comes to data processing, but speed is _not_ one of them when compared to something like StringBuilder. Finger Trees lessen the cost of a functional approach, but it's still expensive.
The question to ask is: do the benefits I gain from a non-String (not even StringBuilder) approach make the performance and loss-of-ease-of-Java-interoperability costs worth it? If your program is designed to spit out massive amounts of text with very little processing, the answer will probably be "no". If it's designed to do anything else, it's worth thinking about it.
--Rex
To answer your second question, String is the wrong data type for
displaying objects. Instead, prefer List[Char] or FingerTree[Char] in
which case, the problems of having to perform side-effects to achieve
reasonable (but still relatively poor) performance disappear
The "problems" would only disappear because you're _always_ stuck with relatively poor performance. Even if @specialized, List requires one layer of boxing (without specialization, it needs two) to wrap the "next" pointer. If performance matters, either in terms of speed or size, this is only marginally less wasteful than the O(n^2) accumulation time for Strings being built a character at a time. You'll have the same O(n^2) if you aren't able to build your entire List[Char] at once or in reverse order, as you'll spend all your time reversing and/or traversing the list; Finger Trees (not currently in the main Scala library, by the way) avoid this problem at the expense of even more per-item overhead, and still don't solve the problem of compositing if kept balanced as they usually are (i.e. you build the answer for A and B and have to _copy_ (not refer to) those answers to print C that contains those two).
An _un_balanced tree structure would be a good choice for output as it would composite well.
But if you bring in all of that heavy-duty algorithmic complexity, and put in all the work required to wrap it nicely in some easy-to-use library, you _still_ are a constant factor of 10 or so behind something like StringBuilder. You'd need to composite ~10 layers deep before you saw a performance improvement. (With JVM improvments, this probably could be cut in half, but still....)
Now, if you're going to try for fast output without using toString, you can replace it with a text injector that sticks the output in the right spot into an array class that does expansions by adding arrays rather than recopying. This is algorithmically simple, low-overhead, and necessarily way faster than any method that does not simply use characters to build up the text.
Using higher-order data structures like Finger Trees have some great advantages when it comes to data processing, but speed is _not_ one of them when compared to something like StringBuilder. Finger Trees lessen the cost of a functional approach, but it's still expensive.
The question to ask is: do the benefits I gain from a non-String (not even StringBuilder) approach make the performance and loss-of-ease-of-Java-interoperability costs worth it? If your program is designed to spit out massive amounts of text with very little processing, the answer will probably be "no". If it's designed to do anything else, it's worth thinking about it.
--Rex
Tue, 2010-02-23, 23:47
#10
Re: immutable var vs. mutable val
Rex Kerr wrote:
> On Tue, Feb 23, 2010 at 12:19 AM, Tony Morris wrote:
>
>
>> To answer your second question, String is the wrong data type for
>> displaying objects. Instead, prefer List[Char] or FingerTree[Char] in
>> which case, the problems of having to perform side-effects to achieve
>> reasonable (but still relatively poor) performance disappear
>>
>
>
> The "problems" would only disappear because you're _always_ stuck with
> relatively poor performance. Even if @specialized, List requires one layer
> of boxing (without specialization, it needs two) to wrap the "next"
> pointer. If performance matters, either in terms of speed or size, this is
> only marginally less wasteful than the O(n^2) accumulation time for Strings
> being built a character at a time. You'll have the same O(n^2) if you
> aren't able to build your entire List[Char] at once or in reverse order, as
> you'll spend all your time reversing and/or traversing the list; Finger
> Trees (not currently in the main Scala library, by the way) avoid this
> problem at the expense of even more per-item overhead, and still don't solve
> the problem of compositing if kept balanced as they usually are (i.e. you
> build the answer for A and B and have to _copy_ (not refer to) those answers
> to print C that contains those two).
>
> An _un_balanced tree structure would be a good choice for output as it would
> composite well.
>
> But if you bring in all of that heavy-duty algorithmic complexity, and put
> in all the work required to wrap it nicely in some easy-to-use library, you
> _still_ are a constant factor of 10 or so behind something like
> StringBuilder. You'd need to composite ~10 layers deep before you saw a
> performance improvement. (With JVM improvments, this probably could be cut
> in half, but still....)
>
> Now, if you're going to try for fast output without using toString, you can
> replace it with a text injector that sticks the output in the right spot
> into an array class that does expansions by adding arrays rather than
> recopying. This is algorithmically simple, low-overhead, and necessarily
> way faster than any method that does not simply use characters to build up
> the text.
>
> Using higher-order data structures like Finger Trees have some great
> advantages when it comes to data processing, but speed is _not_ one of them
> when compared to something like StringBuilder. Finger Trees lessen the cost
> of a functional approach, but it's still expensive.
>
> The question to ask is: do the benefits I gain from a non-String (not even
> StringBuilder) approach make the performance and
> loss-of-ease-of-Java-interoperability costs worth it? If your program is
> designed to spit out massive amounts of text with very little processing,
> the answer will probably be "no". If it's designed to do anything else,
> it's worth thinking about it.
>
> --Rex
>
>
A cons list will have the same performance as String in terms of its
construction. I mentioned finger-trees only to appease the common
tendency to "append" to a list. There are also difference lists:
trait DList[+A] {
def apply(a: List[A]): List[A]
}
I realise none of this is in the standard library, but that can be said
for a lot of useful things.
In the very few cases where something does in fact need to be modified
use a var to the immutable structure. I'm betting you don't have one
of those cases based on your given example.
Tony Morris
http://tmorris.net/
On Feb 22, 2010, at 15:20, Russ Paielli wrote:
> I understand that vals are preferred to vars, and immutable objects
> are preferred to mutable objects. But if something needs to be
> modified and an immutable val won't work, which is prefereable in
> general: an immutable var or a mutable val?
>
> When building strings, for example, you can use += on a String and
> create a new string every time to add something, or you can use
> StringBuilder and keep working with the same object, then convert to
> a String when you are done. The latter seems more efficient to me,
> but I'm just guessing. The same issue comes up with Maps, Lists,
> etc. Any guidance will be appreciated. Thanks.
>
> Russ P.
>