Process the list of different types - is using scala (or functional programming) more expensive than Java?

Question

First of all, let me be clear that I am very new to Scala and functional programming, so my understanding and implementation may be incorrect or inefficient.

Given a file look like this:

type1 param11 param12 ...
type2 param21 param22 ...
type2 param31 param32 ...
type1 param41 param42 ...
...

Basically, each line starts with the type of an object which can be created by the following parameters in the same line. I'm working an application which goes through each line, creates an object of a given type and returns the list of lists of all the objects.

In Java, my implementation is like this:

public void parse(List[Type1] type1s, List[Type2] type2s, List[String] lines) {
    for (String line in lines) {
        if (line.startsWith("type1")) {
            Type1 type1 = Type1.createObj(line);
            type1s.add(type1)l
        } else if (line.startsWith("type2")) {
            Type2 type2 = Type2.createObj(line);
            type2s.add(type2)l
        } else { throw new Exception("Unknown type %s".format(line)) }
    }
}

In order to do the same thing in Scala, I do this:

def parse(lines: List[String]): (List[Type1], List[Type2]) = {
    val type1Lines = lines filter (x => x.startsWith("type1"))
    val type2Lines = lines filter (x => x.startsWith("type2"))

    val type1s = type1Lines map (x => Type1.createObj(x))
    val type2s = type2Lines map (x => Type2.createObj(x))

    (type1s, type2s)
}

As I understand, while my Java implementation only goes through the list once, the Scala one has to do it three times: to filter type1, to filter type2 and to create objects from them. Which means the Scala implementation should be slower than the Java one, right? Moreover, the Java implementation is also more memory saving as it only has 3 instances: type1s, type2s and lines. On the other hand, the Scala one has 5: lines, type1Lines, type2Lines, type1s and type2s.

So my questions are:

Is there a better way to re-write my Scala implementation so that the list is iterated only once?
Using immutable object means a new object is create every time, does it mean functional programming requires more memory than others?

Updated: I create a simple test to demonstrate that the Scala program is slower: a program receives a list of String with size = 1000000. It iterate through a list and check each item, if an item starts with "type1", it adds 1 to a list named type1s, otherwise, it adds 2 to another list named type2s.

Java implementation:

public static void test(List<String> lines) {
    System.out.println("START");
    List<Integer> type1s = new ArrayList<Integer>();
    List<Integer> type2s = new ArrayList<Integer>();
    long start = System.currentTimeMillis();
    for (String l : lines) {
        if (l.startsWith("type1")) {
            type1s.add(1);
        } else {
            type2s.add(2);
        }
    }
    long end = System.currentTimeMillis();

    System.out.println(String.format("END after %s milliseconds", end - start));
}

Scala implementation:

def test(lines: List[String]) = {
    println("START")
    val start = java.lang.System.currentTimeMillis()
    val type1Lines = lines filter (x => x.startsWith("type1"))
    val type2Lines = lines filter (x => x.startsWith("type2"))

    val type1s = type1Lines map (x => 1)
    val type2s = type2Lines map (x => 2)
    val end = java.lang.System.currentTimeMillis()

    println("END after %s milliseconds".format(end - start))
  }
}

Averagely, the Java application took 44 milliseconds while the Scala one needed 200 milliseconds.

I think you should just benchmark whether it is fast enough. If you find out that the Scala version is too slow, you can try using a single fold instead of four. And if that's still to slow, you can always write that one method in Java and the rest of the program in Scala. Obviously pure data structures have a certain overhead, but usually you don't care about that as much as about the productivity gain it gets you when writing code and the possibility to more easily transform programms into a parallel design — Niklas B.
– Niklas B., Commented Mar 16, 2014 at 2:33
@NiklasB. Hi, I'm not trying to benchmark my programs or compare their performance, my point is to ask whether using Scala may result in more collection iteration than using Java. — Long Thai
– Long Thai, Commented Mar 16, 2014 at 2:35
Well it seems like you are concerned with performance. But why are you concerned with performance when it has not proven to be a problem? Also, technically you didn't ask about whether it results in multiple passes, but whether you can do it in one pass, which you can, but which makes your code harder to read and thus is probably not worth the effort — Niklas B.
– Niklas B., Commented Mar 16, 2014 at 2:36
IMO wanting to iterate over a file or list of arbitrary size once instead of four times is a reasonable desire regardless of absolute performance. — Dave Newton
– Dave Newton, Commented Mar 16, 2014 at 2:43

Mitrakov Artem · Accepted Answer · 2014-03-16 08:48:33Z

object ScalaTester extends App {
  val random = new Random
  test((0 until 1000000).toList map {_ => s"type${random nextInt 10}"})

  def test(lines: List[String]) {
    val start = Platform.currentTime
    val m = lines groupBy {
      case s if s startsWith "type1" => "type1"
      case s if s startsWith "type2" => "type2"
      case _ => ""
    }
    println(s"Total type1: ${m("type1").size}; Total type2: ${m("type2").size}; time=${Platform.currentTime - start}")
  }
}

The real advantage of Scala (and functional programming in general) is the ability to process data transforming one structures into another.
Of course you can combine mappings, flatMappings, filters, groups and so forth in a single code line. It results to a single data collection.
You may do it one after another creating new collections each time. And this produces a little overhead indeed. But does one care about it? Even though you create excessive collections Scala-style programming helps you design parallel oriented code (as Niklas already mentioned) and prevents you from very elusive side-effects errors that imperative-style programming is prone to

Hi, thank you very much, look like your code performs a lot better than mine :) However, I don't really understand your conclusion. Does it mean using functional programming language introduces the trade-off between safety/scalability gain and performance cost?
Of course it doesn't. You can gain perfect safe and scalable code with a perfect performance. It depends only on a programmer! )) Though in general imperative code is considered to be a bit faster because of imperative nature of processors. You know that cycles are faster than recursion, iterative mutable collections handling is faster than functional immutable lists traversing and so on...

Collectives™ on Stack Overflow

Process the list of different types - is using scala (or functional programming) more expensive than Java?

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related