List.foldLeft implementation

[huynhjl]

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

[Rex Kerr]

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

  --Rex

[√iktor Ҡlang]

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)

--
Viktor Klang

Akka Tech Lead

Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang

[Rex Kerr]

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

[huynhjl]

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...

[Rex Kerr]

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

[huynhjl]

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