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

Should/Can scalac optimize immutable code?

23 replies
Antoras
Joined: 2010-05-23,
User offline. Last seen 1 year 19 weeks ago.

Hello,

see following code:

val xs = (0 to 100)
xs.sum*xs.sum

This can be really inefficient since xs is large. The alternative to
this code is to introduce a temporary value which holds the result of
xs.sum:

val xs = (0 to 100)
val sum = xs.sum
sum*sum

But in my opinion sometimes this is not as readable as the first code
example.

The JVM did not optimize this after running the first code thousands of
times. Probably for the JVM it is hard to optimize because it doesn't
know that this code is completely immutable and doesn't change its behavior.
But the Scala compiler should be able to optimize this because it can
know that this code is immutable. For example it can transform the first
code to the second one.

Can it be useful to introduce such optimizing strategy to scalac? Does
someone know if there are already such optimizing strategies planned?

Antoras

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Should/Can scalac optimize immutable code?
What you're basically asking for is a Scala Effect System, a term that will find you many hits through a web search engine of your choice.
Such a system would allow the compiler to optimize far more extensively than it currently can, due to the ever-present risk of side effects
Needless to say, the desire for such a thing is almost universal for such a thing.  If time and developers were in unlimited supply, you can be certain that we'd have it by now :)

On 28 May 2011 14:35, Antoras <mail [at] antoras [dot] de> wrote:
Hello,

see following code:

       val xs = (0 to 100)
       xs.sum*xs.sum

This can be really inefficient since xs is large. The alternative to this code is to introduce a temporary value which holds the result of xs.sum:

       val xs = (0 to 100)
       val sum = xs.sum
       sum*sum

But in my opinion sometimes this is not as readable as the first code example.

The JVM did not optimize this after running the first code thousands of times. Probably for the JVM it is hard to optimize because it doesn't know that this code is completely immutable and doesn't change its behavior.
But the Scala compiler should be able to optimize this because it can know that this code is immutable. For example it can transform the first code to the second one.

Can it be useful to introduce such optimizing strategy to scalac? Does someone know if there are already such optimizing strategies planned?

Antoras




--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] comkev [dot] lee [dot] wright [at] gmail [dot] commail: kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wrightquora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra
Randall R Schulz
Joined: 2008-12-16,
User offline. Last seen 1 year 29 weeks ago.
Re: Should/Can scalac optimize immutable code?

On Saturday May 28 2011, Kevin Wright wrote:
> What you're basically asking for is a Scala Effect System, a term
> that will find you many hits through a web search engine of your
> choice.
>
> Such a system would allow the compiler to optimize far more
> extensively than it currently can, due to the ever-present risk of
> side effects
>
> Needless to say, the desire for such a thing is almost universal for
> such a thing. If time and developers were in unlimited supply, you
> can be certain that we'd have it by now :)

You're saying it's a solved problem and an SMOP?

> ...

Randall Schulz

Kevin Wright 2
Joined: 2010-05-30,
User offline. Last seen 26 weeks 4 days ago.
Re: Should/Can scalac optimize immutable code?


On 28 May 2011 15:07, Randall R Schulz <rschulz [at] sonic [dot] net> wrote:
On Saturday May 28 2011, Kevin Wright wrote:
> What you're basically asking for is a Scala Effect System, a term
> that will find you many hits through a web search engine of your
> choice.
>
> Such a system would allow the compiler to optimize far more
> extensively than it currently can, due to the ever-present risk of
> side effects
>
> Needless to say, the desire for such a thing is almost universal for
> such a thing.  If time and developers were in unlimited supply, you
> can be certain that we'd have it by now :)

You're saying it's a solved problem and an SMOP?


Of course not, that's why I specified unlimited resources - to allow enough slack for fixing the unresolved issues :) 

> ...


Randall Schulz




Antoras
Joined: 2010-05-23,
User offline. Last seen 1 year 19 weeks ago.
Re: Should/Can scalac optimize immutable code?
On 28.05.2011 15:48, Kevin Wright wrote:
1-3-QU5sNqMyQMsw [at] mail [dot] gmail [dot] com" type="cite">What you're basically asking for is a Scala Effect System, a term that will find you many hits through a web search engine of your choice.
Yes, I found some interesting discussions about this topic.
1-3-QU5sNqMyQMsw [at] mail [dot] gmail [dot] com" type="cite">
Such a system would allow the compiler to optimize far more extensively than it currently can, due to the ever-present risk of side effects
Needless to say, the desire for such a thing is almost universal for such a thing.  If time and developers were in unlimited supply, you can be certain that we'd have it by now :)
Maybe, one day we will have it. Exists such an effect system still in theory or are there already some languages which contain it?

1-3-QU5sNqMyQMsw [at] mail [dot] gmail [dot] com" type="cite">

On 28 May 2011 14:35, Antoras <mail [at] antoras [dot] de" rel="nofollow">mail [at] antoras [dot] de> wrote:
Hello,

see following code:

       val xs = (0 to 100)
       xs.sum*xs.sum

This can be really inefficient since xs is large. The alternative to this code is to introduce a temporary value which holds the result of xs.sum:

       val xs = (0 to 100)
       val sum = xs.sum
       sum*sum

But in my opinion sometimes this is not as readable as the first code example.

The JVM did not optimize this after running the first code thousands of times. Probably for the JVM it is hard to optimize because it doesn't know that this code is completely immutable and doesn't change its behavior.
But the Scala compiler should be able to optimize this because it can know that this code is immutable. For example it can transform the first code to the second one.

Can it be useful to introduce such optimizing strategy to scalac? Does someone know if there are already such optimizing strategies planned?

Antoras




--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com" target="_blank" rel="nofollow">kev [dot] lee [dot] wright [at] gmail [dot] com mail: kevin [dot] wright [at] scalatechnology [dot] com" target="_blank" rel="nofollow">kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wright quora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

Antoras
Joined: 2010-05-23,
User offline. Last seen 1 year 19 weeks ago.
Re: Should/Can scalac optimize immutable code?
Ok, I can answer my question by myself. Haskell for example does contain an effect system in the form of IO Monads.

Thanks for your reply.
Antoras


On 28.05.2011 22:34, Antoras wrote:
4DE15C57 [dot] 30802 [at] antoras [dot] de" type="cite"> On 28.05.2011 15:48, Kevin Wright wrote:
1-3-QU5sNqMyQMsw [at] mail [dot] gmail [dot] com" type="cite">What you're basically asking for is a Scala Effect System, a term that will find you many hits through a web search engine of your choice.
Yes, I found some interesting discussions about this topic.
1-3-QU5sNqMyQMsw [at] mail [dot] gmail [dot] com" type="cite">
Such a system would allow the compiler to optimize far more extensively than it currently can, due to the ever-present risk of side effects
Needless to say, the desire for such a thing is almost universal for such a thing.  If time and developers were in unlimited supply, you can be certain that we'd have it by now :)
Maybe, one day we will have it. Exists such an effect system still in theory or are there already some languages which contain it?

1-3-QU5sNqMyQMsw [at] mail [dot] gmail [dot] com" type="cite">

On 28 May 2011 14:35, Antoras <mail [at] antoras [dot] de" rel="nofollow">mail [at] antoras [dot] de> wrote:
Hello,

see following code:

       val xs = (0 to 100)
       xs.sum*xs.sum

This can be really inefficient since xs is large. The alternative to this code is to introduce a temporary value which holds the result of xs.sum:

       val xs = (0 to 100)
       val sum = xs.sum
       sum*sum

But in my opinion sometimes this is not as readable as the first code example.

The JVM did not optimize this after running the first code thousands of times. Probably for the JVM it is hard to optimize because it doesn't know that this code is completely immutable and doesn't change its behavior.
But the Scala compiler should be able to optimize this because it can know that this code is immutable. For example it can transform the first code to the second one.

Can it be useful to introduce such optimizing strategy to scalac? Does someone know if there are already such optimizing strategies planned?

Antoras




--
Kevin Wright

gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com" target="_blank" rel="nofollow">kev [dot] lee [dot] wright [at] gmail [dot] com mail: kevin [dot] wright [at] scalatechnology [dot] com" target="_blank" rel="nofollow">kevin [dot] wright [at] scalatechnology [dot] com
vibe / skype: kev.lee.wright quora: http://www.quora.com/Kevin-Wright
twitter: @thecoda

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra


Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Should/Can scalac optimize immutable code?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 28/05/11 23:48, Kevin Wright wrote:
> Needless to say, the desire for such a thing is almost universal
> for such a thing. If time and developers were in unlimited supply,
> you can be certain that we'd have it by now :)
We have it. See scalaz.effects package.

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Should/Can scalac optimize immutable code?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 29/05/11 06:38, Antoras wrote:
> Ok, I can answer my question by myself. Haskell for example does
> contain an effect system in the form of IO Monads.
Your question had little to do with effect-tracking directly and more
to do with sharing. It's that the compiler must know that your sum
method does not side-effect in order to "optimise." However, sharing
is not an optimisation -- it costs space -- and in languages like
haskell, altering the program universally where sharing were possible
would result in massive, unreasonable space costs.

>
> Thanks for your reply. Antoras
>
>
> On 28.05.2011 22:34, Antoras wrote:
>> On 28.05.2011 15:48, Kevin Wright wrote:
>>> What you're basically asking for is a Scala Effect System, a
>>> term that will find you many hits through a web search engine
>>> of your choice.
>> Yes, I found some interesting discussions about this topic.
>>>
>>> Such a system would allow the compiler to optimize far more
>>> extensively than it currently can, due to the ever-present risk
>>> of side effects
>>>
>>> Needless to say, the desire for such a thing is almost
>>> universal for such a thing. If time and developers were in
>>> unlimited supply, you can be certain that we'd have it by now
>>> :)
>> Maybe, one day we will have it. Exists such an effect system
>> still in theory or are there already some languages which contain
>> it?
>>
>>>
>>>
>>> On 28 May 2011 14:35, Antoras >> > wrote:
>>>
>>> Hello,
>>>
>>> see following code:
>>>
>>> val xs = (0 to 100) xs.sum*xs.sum
>>>
>>> This can be really inefficient since xs is large. The
>>> alternative to this code is to introduce a temporary value
>>> which holds the result of xs.sum:
>>>
>>> val xs = (0 to 100) val sum = xs.sum sum*sum
>>>
>>> But in my opinion sometimes this is not as readable as the
>>> first code example.
>>>
>>> The JVM did not optimize this after running the first code
>>> thousands of times. Probably for the JVM it is hard to
>>> optimize because it doesn't know that this code is completely
>>> immutable and doesn't change its behavior. But the Scala
>>> compiler should be able to optimize this because it can know
>>> that this code is immutable. For example it can transform the
>>> first code to the second one.
>>>
>>> Can it be useful to introduce such optimizing strategy to
>>> scalac? Does someone know if there are already such optimizing
>>> strategies planned?
>>>
>>> Antoras
>>>
>>>
>>>
>>>
>>> -- Kevin Wright
>>>
>>> gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
>>> mail:
>>> kevin [dot] wright [at] scalatechnology [dot] com
>>> vibe / skype:
>>> kev.lee.wright quora: http://www.quora.com/Kevin-Wright
>>> twitter: @thecoda
>>>
>>> "My point today is that, if we wish to count lines of code, we
>>> should not regard them as "lines produced" but as "lines
>>> spent": the current conventional wisdom is so foolish as to
>>> book that count on the wrong side of the ledger" ~ Dijkstra
>>>
>>
>
>

Antoras
Joined: 2010-05-23,
User offline. Last seen 1 year 19 weeks ago.
Re: Should/Can scalac optimize immutable code?

But scalaz is a library not a compiler extension. There is no chance
that it will be optimized.

On 29.05.2011 00:29, Tony Morris wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 28/05/11 23:48, Kevin Wright wrote:
>> Needless to say, the desire for such a thing is almost universal
>> for such a thing. If time and developers were in unlimited supply,
>> you can be certain that we'd have it by now :)
> We have it. See scalaz.effects package.
>
> - --
> Tony Morris
> http://tmorris.net/
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAk3hd0EACgkQmnpgrYe6r62S6ACguwLcEC2LDxAABlUif1KQ6H7e
> RnIAoJWQ/iYm5kFUklNgS+GrayIFebFl
> =nYfJ
> -----END PGP SIGNATURE-----
>
>
>

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Should/Can scalac optimize immutable code?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Scalaz has effect-tracking. There is no optimisation to be made.
Sharing is not an optimisation -- it's a space/time trade.

On 29/05/11 20:36, Antoras wrote:
> But scalaz is a library not a compiler extension. There is no
> chance that it will be optimized.
>
>
> On 29.05.2011 00:29, Tony Morris wrote: On 28/05/11 23:48, Kevin
> Wright wrote:
>>>> Needless to say, the desire for such a thing is almost
>>>> universal for such a thing. If time and developers were in
>>>> unlimited supply, you can be certain that we'd have it by
>>>> now :)
> We have it. See scalaz.effects package.
>
> -- Tony Morris http://tmorris.net/
>
>>
>>
>>

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk3iJGsACgkQmnpgrYe6r60DSACfVBqysFsVIqQG/WOMgmByzsJy
abIAnjiEl1JJ0DkPUA1A3NlHwtG0FRzv
=8YxG
-----END PGP SIGNATURE-----

Antoras
Joined: 2010-05-23,
User offline. Last seen 1 year 19 weeks ago.
Re: Should/Can scalac optimize immutable code?

Yes, it is a problem when the shared content would use a lot of space.
It should possible to develop algorithms which can deal with this
problem. But it can take long time to develop such an algorithm...

On 29.05.2011 00:35, Tony Morris wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 29/05/11 06:38, Antoras wrote:
>> Ok, I can answer my question by myself. Haskell for example does
>> contain an effect system in the form of IO Monads.
> Your question had little to do with effect-tracking directly and more
> to do with sharing. It's that the compiler must know that your sum
> method does not side-effect in order to "optimise." However, sharing
> is not an optimisation -- it costs space -- and in languages like
> haskell, altering the program universally where sharing were possible
> would result in massive, unreasonable space costs.
>
>> Thanks for your reply. Antoras
>>
>>
>> On 28.05.2011 22:34, Antoras wrote:
>>> On 28.05.2011 15:48, Kevin Wright wrote:
>>>> What you're basically asking for is a Scala Effect System, a
>>>> term that will find you many hits through a web search engine
>>>> of your choice.
>>> Yes, I found some interesting discussions about this topic.
>>>> Such a system would allow the compiler to optimize far more
>>>> extensively than it currently can, due to the ever-present risk
>>>> of side effects
>>>>
>>>> Needless to say, the desire for such a thing is almost
>>>> universal for such a thing. If time and developers were in
>>>> unlimited supply, you can be certain that we'd have it by now
>>>> :)
>>> Maybe, one day we will have it. Exists such an effect system
>>> still in theory or are there already some languages which contain
>>> it?
>>>
>>>>
>>>> On 28 May 2011 14:35, Antoras>>> > wrote:
>>>>
>>>> Hello,
>>>>
>>>> see following code:
>>>>
>>>> val xs = (0 to 100) xs.sum*xs.sum
>>>>
>>>> This can be really inefficient since xs is large. The
>>>> alternative to this code is to introduce a temporary value
>>>> which holds the result of xs.sum:
>>>>
>>>> val xs = (0 to 100) val sum = xs.sum sum*sum
>>>>
>>>> But in my opinion sometimes this is not as readable as the
>>>> first code example.
>>>>
>>>> The JVM did not optimize this after running the first code
>>>> thousands of times. Probably for the JVM it is hard to
>>>> optimize because it doesn't know that this code is completely
>>>> immutable and doesn't change its behavior. But the Scala
>>>> compiler should be able to optimize this because it can know
>>>> that this code is immutable. For example it can transform the
>>>> first code to the second one.
>>>>
>>>> Can it be useful to introduce such optimizing strategy to
>>>> scalac? Does someone know if there are already such optimizing
>>>> strategies planned?
>>>>
>>>> Antoras
>>>>
>>>>
>>>>
>>>>
>>>> -- Kevin Wright
>>>>
>>>> gtalk / msn : kev [dot] lee [dot] wright [at] gmail [dot] com
>>>> mail:
>>>> kevin [dot] wright [at] scalatechnology [dot] com
>>>> vibe / skype:
>>>> kev.lee.wright quora: http://www.quora.com/Kevin-Wright
>>>> twitter: @thecoda
>>>>
>>>> "My point today is that, if we wish to count lines of code, we
>>>> should not regard them as "lines produced" but as "lines
>>>> spent": the current conventional wisdom is so foolish as to
>>>> book that count on the wrong side of the ledger" ~ Dijkstra
>>>>
>>
>
> - --
> Tony Morris
> http://tmorris.net/
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAk3heLkACgkQmnpgrYe6r62pPQCgn4Hs2IJzruTRP5n45h4N3tYp
> xCoAn3/zWQWXeGIGw80UBa5fqy5Bwm34
> =l2gW
> -----END PGP SIGNATURE-----
>
>
>

Antoras
Joined: 2010-05-23,
User offline. Last seen 1 year 19 weeks ago.
Re: Should/Can scalac optimize immutable code?

You mean it internally saves the calculated values when it is useful
(e.g. with lazy vals)?

On 29.05.2011 12:48, Tony Morris wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Scalaz has effect-tracking. There is no optimisation to be made.
> Sharing is not an optimisation -- it's a space/time trade.
>
> On 29/05/11 20:36, Antoras wrote:
> > But scalaz is a library not a
> compiler extension. There is no
>
> > chance that it will be optimized.
>
> >
>
> >
>
> > On 29.05.2011 00:29, Tony Morris wrote: On 28/05/11 23:48,
> Kevin
>
> > Wright wrote:
>
> >>>> Needless to say, the desire for such a thing is
> almost
>
> >>>> universal for such a thing. If time and
> developers were in
>
> >>>> unlimited supply, you can be certain that we'd
> have it by
>
> >>>> now :)
>
> > We have it. See scalaz.effects package.
>
> >
>
> > -- Tony Morris http://tmorris.net/
>
> >
>
> >>
>
> >>
>
> >>
>
> - --
> Tony Morris
> http://tmorris.net/
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.10 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAk3iJGsACgkQmnpgrYe6r60DSACfVBqysFsVIqQG/WOMgmByzsJy
> abIAnjiEl1JJ0DkPUA1A3NlHwtG0FRzv
> =8YxG
> -----END PGP SIGNATURE-----
>

Tony Morris 2
Joined: 2009-03-20,
User offline. Last seen 42 years 45 weeks ago.
Re: Should/Can scalac optimize immutable code?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Sharing with call-by-need would do this sure. Haskell for example.

For example:

let x = sum y in x + x

In Scala:

{
lazy val x = sum(y)
x + x
}

On 29/05/11 21:12, Antoras wrote:
> You mean it internally saves the calculated values when it is
> useful (e.g. with lazy vals)?
>
>
> On 29.05.2011 12:48, Tony Morris wrote:
>>
> Scalaz has effect-tracking. There is no optimisation to be made.
> Sharing is not an optimisation -- it's a space/time trade.
>
> On 29/05/11 20:36, Antoras wrote:
>> But scalaz is a library not a
> compiler extension. There is no
>
>> chance that it will be optimized.
>
>
>
>
>
>> On 29.05.2011 00:29, Tony Morris wrote: On 28/05/11 23:48,
> Kevin
>
>> Wright wrote:
>
>>>>> Needless to say, the desire for such a thing is
> almost
>
>>>>> universal for such a thing. If time and
> developers were in
>
>>>>> unlimited supply, you can be certain that we'd
> have it by
>
>>>>> now :)
>
>> We have it. See scalaz.effects package.
>
>
>
>> -- Tony Morris http://tmorris.net/
>
>
>
>
>
>
>
>
>
> -- Tony Morris http://tmorris.net/
>
>>

- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk3iKyEACgkQmnpgrYe6r60GfgCgoCAFOfx80bZddDdmqiH311U6
VxIAn3Gb44q2kHldrlNerF/UMHVwIJDn
=rjjt
-----END PGP SIGNATURE-----

soc
Joined: 2010-02-07,
User offline. Last seen 34 weeks 5 days ago.
Re: Should/Can scalac optimize immutable code?

Hi,

I couldn't seriously believe that Range doesn't override sum with a more
sensible implementation (like "not going through the whole thing and
accumulating the results"), but after checking, it seems it does.

Range inherits sum from TraversableOnce:

def sum[B >: A](implicit num: Numeric[B]): B =
foldLeft(num.zero)(num.plus)

Imho it would make sense to optimize the two most common operations, 0
to n and 1 to n.

My implementation of sum would look like:

final def sum: Int =
if (step == 1) {
if (start == 0) euler(end) + 1
else if (start == 1) euler(end)
} else sum()

@inline private def euler(end: Int) = (end+1)*end/2

I imagine that this faster by orders of magnitude, but I haven't
benchmarked yet.

Bye,

Simon

H-star Development
Joined: 2010-04-14,
User offline. Last seen 2 years 26 weeks ago.
Re: Should/Can scalac optimize immutable code?

keep in mind that "+1" is not the only possible increment

-------- Original-Nachricht --------
> Datum: Mon, 30 May 2011 11:54:30 +0200
> Von: Simon Ochsenreither
> An: scala-debate [at] googlegroups [dot] com
> Betreff: Re: [scala-debate] Should/Can scalac optimize immutable code?

> Hi,
>
> I couldn't seriously believe that Range doesn't override sum with a more
> sensible implementation (like "not going through the whole thing and
> accumulating the results"), but after checking, it seems it does.
>
> Range inherits sum from TraversableOnce:
>
> def sum[B >: A](implicit num: Numeric[B]): B =
> foldLeft(num.zero)(num.plus)
>
>
> Imho it would make sense to optimize the two most common operations, 0
> to n and 1 to n.
>
> My implementation of sum would look like:
>
> final def sum: Int =
> if (step == 1) {
> if (start == 0) euler(end) + 1
> else if (start == 1) euler(end)
> } else sum()
>
> @inline private def euler(end: Int) = (end+1)*end/2
>
> I imagine that this faster by orders of magnitude, but I haven't
> benchmarked yet.
>
> Bye,
>
> Simon

ichoran
Joined: 2009-08-14,
User offline. Last seen 2 years 3 weeks ago.
Re: Should/Can scalac optimize immutable code?
On Mon, May 30, 2011 at 6:05 AM, Dennis Haupt <h-star [at] gmx [dot] de> wrote:
keep in mind that "+1" is not the only possible increment

And that ranges can be either inclusive or exclusive.
 


-------- Original-Nachricht --------
> Datum: Mon, 30 May 2011 11:54:30 +0200
> Von: Simon Ochsenreither <simon [at] ochsenreither [dot] de>
> An: scala-debate [at] googlegroups [dot] com
> Betreff: Re: [scala-debate] Should/Can scalac optimize immutable code?
> Imho it would make sense to optimize the two most common operations, 0
> to n and 1 to n.

Goodness, why not optimize all of them?

def sum(r: Range): Int = {
  val L = r.length
  val least = if (r.step>0) r.start else r.start+(L-1)*r.step
  val sq = if ((L&0x1) == 0) (L-1)*(L/2) else ((L-1)/2)*L
  math.abs(r.step)*sq + least*L
}

Note the if statement to handle overflow the same way that summing the elements does (division in rings is pesky).

Actually, maybe I should submit this as a patch.

  --Rex


dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Should/Can scalac optimize immutable code?

On Mon, May 30, 2011 at 13:32, Rex Kerr wrote:
>
> Goodness, why not optimize all of them?
>
> def sum(r: Range): Int = {
>   val L = r.length
>   val least = if (r.step>0) r.start else r.start+(L-1)*r.step
>   val sq = if ((L&0x1) == 0) (L-1)*(L/2) else ((L-1)/2)*L
>   math.abs(r.step)*sq + least*L
> }

def sum(r: Range): Int = r.length * (r.head + r.last) / 2

dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Should/Can scalac optimize immutable code?

On Mon, May 30, 2011 at 14:43, Daniel Sobral wrote:
> On Mon, May 30, 2011 at 13:32, Rex Kerr wrote:
>>
>> Goodness, why not optimize all of them?
>>
>> def sum(r: Range): Int = {
>>   val L = r.length
>>   val least = if (r.step>0) r.start else r.start+(L-1)*r.step
>>   val sq = if ((L&0x1) == 0) (L-1)*(L/2) else ((L-1)/2)*L
>>   math.abs(r.step)*sq + least*L
>> }
>
> def sum(r: Range): Int = r.length * (r.head + r.last) / 2

Though, granted, it can suffer from overflow. One could move it to
Long and back to Int to make sure it doesn't do so unnecessarily,
which would still keep it way faster than the default implementation.

ichoran
Joined: 2009-08-14,
User offline. Last seen 2 years 3 weeks ago.
Re: Should/Can scalac optimize immutable code?
On Mon, May 30, 2011 at 1:43 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
On Mon, May 30, 2011 at 13:32, Rex Kerr <ichoran [at] gmail [dot] com> wrote:
>
> Goodness, why not optimize all of them?
>
> def sum(r: Range): Int = {
>   val L = r.length
>   val least = if (r.step>0) r.start else r.start+(L-1)*r.step
>   val sq = if ((L&0x1) == 0) (L-1)*(L/2) else ((L-1)/2)*L
>   math.abs(r.step)*sq + least*L
> }

def sum(r: Range): Int = r.length * (r.head + r.last) / 2

Okay, that's a lot better (with the .toLong/.toInt wrapper)--I wasn't sure last was O(1), but I checked and it is.

  --Rex

Jim Powers
Joined: 2011-01-24,
User offline. Last seen 36 weeks 2 days ago.
Re: Should/Can scalac optimize immutable code?
On Mon, May 30, 2011 at 1:43 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
def sum(r: Range): Int = r.length * (r.head + r.last) / 2

Only works if the step is 1 
--
Jim Powers
ichoran
Joined: 2009-08-14,
User offline. Last seen 2 years 3 weeks ago.
Re: Should/Can scalac optimize immutable code?
On Mon, May 30, 2011 at 11:00 PM, Jim Powers <jim [at] casapowers [dot] com> wrote:
On Mon, May 30, 2011 at 1:43 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
def sum(r: Range): Int = r.length * (r.head + r.last) / 2

Only works if the step is 1 

It's a good idea to try these things before assuming the math is wrong.

  --Rex

Jim Powers
Joined: 2011-01-24,
User offline. Last seen 36 weeks 2 days ago.
Re: Should/Can scalac optimize immutable code?
On Mon, May 30, 2011 at 11:12 PM, Rex Kerr <ichoran [at] gmail [dot] com> wrote:
On Mon, May 30, 2011 at 11:00 PM, Jim Powers <jim [at] casapowers [dot] com> wrote:
On Mon, May 30, 2011 at 1:43 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
def sum(r: Range): Int = r.length * (r.head + r.last) / 2

Only works if the step is 1 

It's a good idea to try these things before assuming the math is wrong.

HA! Or at least read the code instead of what I wanted to see. ;-)
Have a closed-form solution to this for Project Euler problems, read 'length' as (max - min), my bad. 
Nothing to see here. 
--
Jim Powers
dcsobral
Joined: 2009-04-23,
User offline. Last seen 38 weeks 5 days ago.
Re: Should/Can scalac optimize immutable code?

On Tue, May 31, 2011 at 00:00, Jim Powers wrote:
> On Mon, May 30, 2011 at 1:43 PM, Daniel Sobral wrote:
>>
>> def sum(r: Range): Int = r.length * (r.head + r.last) / 2
>
> Only works if the step is 1

Not true.

scala> val r1 = 1 to 10 by 4
r1: scala.collection.immutable.Range = Range(1, 5, 9)

scala> r1.sum
res59: Int = 15

scala> sum(r1)
res60: Int = 15

scala> val r2 = 547 to -2048 by -56
r2: scala.collection.immutable.Range = Range(547, 491, 435, 379, 323,
267, 211, 155, 99, 43, -13, -69, -125, -181, -237, -293, -349, -405,
-461, -517, -573, -629, -685, -741, -797, -853, -909, -965, -1021,
-1077, -1133, -1189, -1245, -1301, -1357, -1413, -1469, -1525, -1581,
-1637, -1693, -1749, -1805, -1861, -1917, -1973, -2029)

scala> r2.sum
res61: Int = -34827

scala> sum(r2)
res62: Int = -34827

It only works for non-empty ranges, but a simple if (length > 0) fixes that.

Jim Powers
Joined: 2011-01-24,
User offline. Last seen 36 weeks 2 days ago.
Re: Should/Can scalac optimize immutable code?
On Tue, May 31, 2011 at 10:31 AM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
On Tue, May 31, 2011 at 00:00, Jim Powers <jim [at] casapowers [dot] com> wrote:
> On Mon, May 30, 2011 at 1:43 PM, Daniel Sobral <dcsobral [at] gmail [dot] com> wrote:
>>
>> def sum(r: Range): Int = r.length * (r.head + r.last) / 2
>
> Only works if the step is 1

Not true.

Rex already called me out on this.  My bad, sorry.
-- Jim Powers

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