A six bit adding machine, storing state with marbles.
Tuesday, June 26, 2007
Monday, June 25, 2007
Friday, June 22, 2007
Performance with Scala Arrays and Lists
As I continue to tinker with Scala, I was wondering about the performance differences between an Array and List. This post will detail what I've found, but as always YMMV and I could be doing it all wrong. If there's a better (in this case, better == faster) way to do this in Scala, please let me know.
My application performs a lot of collection iteration as it combines the values of two collections into a new collection by addition. For instance, I need to combine
Intuition tells me that the Array will perform better, but this is Scala, and Lists reign supreme. So we'll go head to head.
For each test, I wanted to write a function that combined the two collections using tail recursion.
First up, I am adding two lists together while forming a third. One problem here is, due to the way the algorithm is structured, the resulting list is built backwards. So there's a call to
To call it:
Next up, I add two Arrays into a List. The guess here is that accessing the arrays by index will help speed it up.
To call it:
This should be the fastest.
To call it:
I ran each function 1 million times and captured the times with
The results are in, and sure enough, on average, the third option (pure Arrays) is the fastest.
* Test 1 - 1172 ms
* Test 2 - 781 ms
* Test 3 - 687 ms
So, for my purposes, using Arrays results in faster execution. However, if you are looking to do traditional functional programming, you should write your methods to create zero side effects. Using Arrays like this seems anti-functional programming.
My application performs a lot of collection iteration as it combines the values of two collections into a new collection by addition. For instance, I need to combine
[1,2] and [3,4] into [4,6]. I wanted to find out if the collections should be an Array or List.Intuition tells me that the Array will perform better, but this is Scala, and Lists reign supreme. So we'll go head to head.
For each test, I wanted to write a function that combined the two collections using tail recursion.
Test One - Two Lists Into a Third
First up, I am adding two lists together while forming a third. One problem here is, due to the way the algorithm is structured, the resulting list is built backwards. So there's a call to
reverse at the end. (Question: How to rewrite this using normal List methods such as :: without having to call reverse at the end?)
def add(x: List[Long], y: List[Long],
agg: List[Long]): List[Long] = x match {
case Nil => agg.reverse
case x1 :: xs => y match {
case y1 :: ys => add(xs, ys, x1 + y1 :: agg)
}
}
To call it:
add(List(1,2), List(3,4), Nil)Test Two - Two Arrays Into a List
Next up, I add two Arrays into a List. The guess here is that accessing the arrays by index will help speed it up.
def add2(x: Array[Long], y: Array[Long], agg: List[Long],
counter: Int): List[Long] = {
if (counter == 0) agg
else add2(x, y, x(counter-1) + y(counter-1) :: agg, counter-1)
}
To call it:
add2(Array(1,2), Array(3,4), Nil, 2)Test Three - Two Arrays Into a Third Array
This should be the fastest.
def add3(x: Array[Long], y: Array[Long], agg: Array[Long],
i: Int): Array[Long] = {
if (i == x.length) agg
else {
agg(i) = x(i) + y(i)
add3(x, y, agg, i+1)
}
}
To call it:
add3(Array(1,2), Array(3,4), new Array(2), 0)Methodology
I ran each function 1 million times and captured the times with
System.currentTimeMillis. I ran the entire test suite five times to generate an average. I am running Scala 2.5.1 on Java 1.6 on Windows XP. I have a Pentium 4 2.8GHz with 2GB RAM.Results
The results are in, and sure enough, on average, the third option (pure Arrays) is the fastest.
* Test 1 - 1172 ms
* Test 2 - 781 ms
* Test 3 - 687 ms
So, for my purposes, using Arrays results in faster execution. However, if you are looking to do traditional functional programming, you should write your methods to create zero side effects. Using Arrays like this seems anti-functional programming.
Thursday, June 21, 2007
links for 2007-06-22
Why interact with real humans when you can order your food via a big ass table. Take that, Apple.
Wednesday, June 20, 2007
Converting Array to List in Scala
Now, this has to have a built-in somewhere in Scala, because it just seems too common. So, how to convert an Array to a List in Scala?
Why do I need this? I needed to drop to Java for some functionality, which in this case returns an Array. I wanted to get that Array into a List to practice my functional programming skillz.
**Update**: I figured out how to convert Arrays to Lists the Scala way. Turns out it's a piece of cake.
val myList = List.fromArray(Array("one", "two", "three"))
or
val myList = Array("one","two","three").elements.toList
The call to
Because my first version wasn't actually tail recursive, what follows is a true tail recursive solution, if I were to implement this by hand. The above, built in mechanism is much better, though.
The above code is interesting because it demonstrates a nested function. The
*What follows is my original attempt.* Left here for a historical, "what not to do" perspective.
Here's my implementation of it, but if you know if there's a built-in function already implemented, please let me know.
To quickly explain this, an
Why do I need this? I needed to drop to Java for some functionality, which in this case returns an Array. I wanted to get that Array into a List to practice my functional programming skillz.
**Update**: I figured out how to convert Arrays to Lists the Scala way. Turns out it's a piece of cake.
val myList = List.fromArray(Array("one", "two", "three"))
or
val myList = Array("one","two","three").elements.toList
The call to
elements returns an Iterator, and from there you can convert to a List via toList. Nice.Because my first version wasn't actually tail recursive, what follows is a true tail recursive solution, if I were to implement this by hand. The above, built in mechanism is much better, though.
object ArrayUtil {
def toList[a](array: Array[a]): List[a] = {
def convert(arr: Array[a], aggregator: List[a]): List[a] = {
if (arr == null || arr.length == 0) aggregator
else convert(arr.slice(0, arr.length-1), arr(arr.length-1) :: aggregator)
}
convert(array, Nil)
}
}
The above code is interesting because it demonstrates a nested function. The
convert function is nested inside toList. Scala encourages the decomposition of your problem into smaller and smaller functions.*What follows is my original attempt.* Left here for a historical, "what not to do" perspective.
Here's my implementation of it, but if you know if there's a built-in function already implemented, please let me know.
object ArrayUtil {
def toList[a](array: Array[a]): List[a] = {
if (array == null || array.length == 0) Nil
else if (array.length == 1) List(array(0))
else array(0) :: toList(array.slice(1, array.length))
}
}
To quickly explain this, an
object in Scala is a singleton instance of its class. The method toList is parameterized with type a. This is similar to generics in Java. Lastly, the :: operator (pronouned cons in Scala) creates a new List from a single item (the head, on the left) and another List (the tail, on the right). Oh, and Nil represents an empty List.
Tuesday, June 19, 2007
That’s a Lot of Actors
As I continue to explore Scala, I wondered just how many (react based) actors I could create in a single JVM. The answer, apparently, is a lot.
Before I canceled it, the count was up to 13,500,000 actors. This is on an old Centrino laptop running the Sun 1.6 JVM. I did have to turn up the memory limit a bit, but I never saw memory go above 20MB. Also, I wasn't doing anything inside the Actors.
Still, that's enough for me to not have to worry about it.
Scala: It's as if Java and Erlang had a baby. Fun stuff.
Before I canceled it, the count was up to 13,500,000 actors. This is on an old Centrino laptop running the Sun 1.6 JVM. I did have to turn up the memory limit a bit, but I never saw memory go above 20MB. Also, I wasn't doing anything inside the Actors.
Still, that's enough for me to not have to worry about it.
Scala: It's as if Java and Erlang had a baby. Fun stuff.
links for 2007-06-20
A helpful mapping between Java and Scala syntax and idioms.
In this article, you'll follow twelve steps that are designed to help you understand and gain some basic skills in the Scala programming language.
Monday, June 18, 2007
Sunday, June 17, 2007
RESTifying a Real World J2EE Application
RESTify DayTrader, in which Joe Gregorio converts a real world J2EE application's interface into a REST interface.
Perfect example of how to do REST with real life requirements.
Perfect example of how to do REST with real life requirements.
Wednesday, June 13, 2007
A brief history of Consensus, 2PC and Transaction Commit.
A brief history of Consensus, 2PC and Transaction Commit, in which Mark Mc Keown attempts to keep us all in sync with the history of consensus across processes in a distributed system.
Excellent read. Thanks Mark!
Excellent read. Thanks Mark!
Tuesday, June 12, 2007
links for 2007-06-13
Converting a Rails application to a Scala on lift application.
A hilarious soundtrack to the hardest levels of Super Mario Brothers. Warning, not for virgin ears.
Thursday, June 7, 2007
Wednesday, June 6, 2007
Friday, June 1, 2007
Interview and Book Excerpt from RESTful Web Services
InfoQ has an Interview and Book Excerpt from the book RESTful Web Services, the new book published by O'Reilly. I've ordered my copy from Amazon already, and I'm looking forward to reading it.
The interview also links to a sample chapter from the book, titled The Resource Oriented Architecture.
A great quote from the interview, by Sam Ruby:
Congrats to Leonard and Sam on their book!
The interview also links to a sample chapter from the book, titled The Resource Oriented Architecture.
A great quote from the interview, by Sam Ruby:
I also wanted a book that rose above the “we are 733T, WS are the Sux0rs” zealotry that, sadly, one too often hears.
Congrats to Leonard and Sam on their book!
Subscribe to:
Posts (Atom)
Disclaimer
