List.foldLeft implementation

How is the match version more efficient than the head/tail equivalent in LinearSeqOptimized?  Did you benchmark it, or are you assuming?

  --Rex

On Tue, Dec 27, 2011 at 12:02 PM, huynhjl <huynhjl@gmail.com> wrote:

Hi All,

I just noticed while exploring various implementations of foldRight at
http://stackoverflow.com/questions/8549433/is-it-possible-to-use-continuations-to-make-foldright-tail-recursive
that List.foldLeft is implemented in terms of LinearSeqOptimized. It
does not seem as efficient as the tail recursive version along this
line:

 def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
   list match {
     case x :: xs => foldLeft2(xs, f(x, acc))(f)
     case Nil => acc
   }
 }

Without specific knowledge, I would have assumed that the
List.foldLeft implementation was the typical tail recursive one. Was
this a conscious choice/trade off? Or maybe my benchmark is flawed?

Jean-Laurent

Challenge accepted:

@tailrec final def foldLeft2[T, U](list: List[T], acc: U)(f: (T, U) => U): U =
  if (list eq Nil) acc else foldLeft2(list.tail, f(list.head, acc))(f)

On Tue, Dec 27, 2011 at 6:02 PM, huynhjl <huynhjl@gmail.com> wrote:

Hi All,

I just noticed while exploring various implementations of foldRight at
http://stackoverflow.com/questions/8549433/is-it-possible-to-use-continuations-to-make-foldright-tail-recursive
that List.foldLeft is implemented in terms of LinearSeqOptimized. It
does not seem as efficient as the tail recursive version along this
line:

 def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
   list match {
     case x :: xs => foldLeft2(xs, f(x, acc))(f)
     case Nil => acc
   }
 }

Without specific knowledge, I would have assumed that the
List.foldLeft implementation was the typical tail recursive one. Was
this a conscious choice/trade off? Or maybe my benchmark is flawed?

Jean-Laurent

--
Viktor Klang

Akka Tech LeadTypesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

You're just measuring the overhead of being in the collections hierarchy.  If you extract the library method into your own function, you find that the times are identical.

(In fact, Viktor's seems exactly identical to the library version in speed, while yours is perhaps 3-4% slower.)

There does seem to be a ~15% performance penalty from being part of the collections hierarchy.

  --Rex

On Tue, Dec 27, 2011 at 12:02 PM, huynhjl <huynhjl@gmail.com> wrote:

Hi All,

I just noticed while exploring various implementations of foldRight at
http://stackoverflow.com/questions/8549433/is-it-possible-to-use-continuations-to-make-foldright-tail-recursive
that List.foldLeft is implemented in terms of LinearSeqOptimized. It
does not seem as efficient as the tail recursive version along this
line:

 def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
   list match {
     case x :: xs => foldLeft2(xs, f(x, acc))(f)
     case Nil => acc
   }
 }

Without specific knowledge, I would have assumed that the
List.foldLeft implementation was the typical tail recursive one. Was
this a conscious choice/trade off? Or maybe my benchmark is flawed?

Jean-Laurent

Hi Rex,

I'm not able to reproduce timings by pulling them in. Here is the
code:

https://gist.github.com/1524670

Results are:

[info] Running C
tailrec match foldLeft2: warming...
Elapsed: 0.024
tailrec if/else foldLeft3: warming...
Elapsed: 0.045
lib foldLeft: warming...
Elapsed: 0.068
pulled-in foldLeft: warming...
Elapsed: 0.069

Implementation of lots and time implementation may seem familiar, I
took them from one of your stackoverflow post.

Victor's is slower which is really odd. Probably my methodology is
flawed...

Jean-Laurent

On Dec 27, 9:33 am, Rex Kerr wrote:
> You're just measuring the overhead of being in the collections hierarchy.
> If you extract the library method into your own function, you find that the
> times are identical.
>
> (In fact, Viktor's seems exactly identical to the library version in speed,
> while yours is perhaps 3-4% slower.)
>
> There does seem to be a ~15% performance penalty from being part of the
> collections hierarchy.
>
>   --Rex
>
>
>
>
>
>
>
> On Tue, Dec 27, 2011 at 12:02 PM, huynhjl wrote:
> > Hi All,
>
> > I just noticed while exploring various implementations of foldRight at
>
> >http://stackoverflow.com/questions/8549433/is-it-possible-to-use-cont...
> > that List.foldLeft is implemented in terms of LinearSeqOptimized. It
> > does not seem as efficient as the tail recursive version along this
> > line:
>
> >  def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
> >    list match {
> >      case x :: xs => foldLeft2(xs, f(x, acc))(f)
> >      case Nil => acc
> >    }
> >  }
>
> > Without specific knowledge, I would have assumed that the
> > List.foldLeft implementation was the typical tail recursive one. Was
> > this a conscious choice/trade off? Or maybe my benchmark is flawed?
>
> > Jean-Laurent

I'm not sure what's going on with your timings, but your benchmark is too short.  You should run through the list multiple times or otherwise do something to take more time.  (Maybe it's a memory issue due to boxing all those ints?)

If I change bench to use time(what, lots(n,f)), and then change warm to 100, I get nice even times for all methods (all of them, even the library version; the JVM seems to have elided the overhead here).

  --Rex

On Tue, Dec 27, 2011 at 1:20 PM, huynhjl <huynhjl@gmail.com> wrote:

Hi Rex,

I'm not able to reproduce timings by pulling them in. Here is the
code:

https://gist.github.com/1524670

Results are:

[info] Running C
tailrec match foldLeft2: warming...
Elapsed: 0.024
tailrec if/else foldLeft3: warming...
Elapsed: 0.045
lib foldLeft: warming...
Elapsed: 0.068
pulled-in foldLeft: warming...
Elapsed: 0.069

Implementation of lots and time implementation may seem familiar, I
took them from one of your stackoverflow post.

Victor's is slower which is really odd. Probably my methodology is
flawed...

Jean-Laurent

On Dec 27, 9:33 am, Rex Kerr <icho...@gmail.com> wrote:
> You're just measuring the overhead of being in the collections hierarchy.
> If you extract the library method into your own function, you find that the
> times are identical.
>
> (In fact, Viktor's seems exactly identical to the library version in speed,
> while yours is perhaps 3-4% slower.)
>
> There does seem to be a ~15% performance penalty from being part of the
> collections hierarchy.
>
>   --Rex
>
>
>
>
>
>
>
> On Tue, Dec 27, 2011 at 12:02 PM, huynhjl <huyn...@gmail.com> wrote:
> > Hi All,
>
> > I just noticed while exploring various implementations of foldRight at
>
> >http://stackoverflow.com/questions/8549433/is-it-possible-to-use-cont...
> > that List.foldLeft is implemented in terms of LinearSeqOptimized. It
> > does not seem as efficient as the tail recursive version along this
> > line:
>
> >  def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
> >    list match {
> >      case x :: xs => foldLeft2(xs, f(x, acc))(f)
> >      case Nil => acc
> >    }
> >  }
>
> > Without specific knowledge, I would have assumed that the
> > List.foldLeft implementation was the typical tail recursive one. Was
> > this a conscious choice/trade off? Or maybe my benchmark is flawed?
>
> > Jean-Laurent

Hi Rex,

I found out that the timing behavior is specific to my Core 2 Duo
1.5GHz. Using a more recent computer, the timings are nearly identical
for all implementations. I guess I'll have to be more suspicious of my
old laptop.

Jean-Laurent

On Dec 27, 10:59 am, Rex Kerr wrote:
> I'm not sure what's going on with your timings, but your benchmark is too
> short.  You should run through the list multiple times or otherwise do
> something to take more time.  (Maybe it's a memory issue due to boxing all
> those ints?)
>
> If I change bench to use time(what, lots(n,f)), and then change warm to
> 100, I get nice even times for all methods (all of them, even the library
> version; the JVM seems to have elided the overhead here).
>
>   --Rex
>
>
>
>
>
>
>
> On Tue, Dec 27, 2011 at 1:20 PM, huynhjl wrote:
> > Hi Rex,
>
> > I'm not able to reproduce timings by pulling them in. Here is the
> > code:
>
> >https://gist.github.com/1524670
>
> > Results are:
>
> > [info] Running C
> > tailrec match foldLeft2: warming...
> > Elapsed: 0.024
> > tailrec if/else foldLeft3: warming...
> > Elapsed: 0.045
> > lib foldLeft: warming...
> > Elapsed: 0.068
> > pulled-in foldLeft: warming...
> > Elapsed: 0.069
>
> > Implementation of lots and time implementation may seem familiar, I
> > took them from one of your stackoverflow post.
>
> > Victor's is slower which is really odd. Probably my methodology is
> > flawed...
>
> > Jean-Laurent
>
> > On Dec 27, 9:33 am, Rex Kerr wrote:
> > > You're just measuring the overhead of being in the collections hierarchy.
> > > If you extract the library method into your own function, you find that
> > the
> > > times are identical.
>
> > > (In fact, Viktor's seems exactly identical to the library version in
> > speed,
> > > while yours is perhaps 3-4% slower.)
>
> > > There does seem to be a ~15% performance penalty from being part of the
> > > collections hierarchy.
>
> > >   --Rex
>
> > > On Tue, Dec 27, 2011 at 12:02 PM, huynhjl wrote:
> > > > Hi All,
>
> > > > I just noticed while exploring various implementations of foldRight at
>
> > > >http://stackoverflow.com/questions/8549433/is-it-possible-to-use-cont.
> > ..
> > > > that List.foldLeft is implemented in terms of LinearSeqOptimized. It
> > > > does not seem as efficient as the tail recursive version along this
> > > > line:
>
> > > >  def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
> > > >    list match {
> > > >      case x :: xs => foldLeft2(xs, f(x, acc))(f)
> > > >      case Nil => acc
> > > >    }
> > > >  }
>
> > > > Without specific knowledge, I would have assumed that the
> > > > List.foldLeft implementation was the typical tail recursive one. Was
> > > > this a conscious choice/trade off? Or maybe my benchmark is flawed?
>
> > > > Jean-Laurent