Thursday, May 13, 2010

Scala Stream Fusion and Specialization, Part 2

Note: The full source code for this post can be found here.

Scala specialization is maturing and in Scala 2.8 RC2 some parts of the standard library has been specialized (the function and tuple classes). So, it's time to update the stream fusion tests I wrote about in a previous blog post with proper specialization.

It should be quite straight forward to fully specialize the filter and map iterators used in my previous post. This turns out to not be the case as the current specialization implementation contains a quite severe limitation:

A method is only specialized for a type parameter annotated as specialized if the method type signature contains the type parameter in a "naked" position (or an array of the "naked" type parameter).

See this ticket for more information. Here are some examples of how this limitation affects method specialization:

trait A[@specialized T] {
def m1(t : T) : Boolean // Will be specialized for T
def m2(f : T => Boolean) // Will NOT be specialized for T
def m3[@specialized U](fn : T => U) : T // Will be specialized for T, but NOT for U
def m4() // Will NOT be specialized
}

It easy to see how this will cause some problems when implementing specialized iterators and higher order functions.

The iterator trait from my previous post has to be modified slightly as the next method would not get specialized due to the limitation mentioned above:

trait SIterator[@specialized T] {
def hasNext : Boolean
def next() : T
}

This interface is similar to the Java and Scala iterator interfaces.

The implementations of array and map iterators are straight forward, but the filter iterator is quite tricky:

final class FilterIterator[@specialized T](iter : SIterator[T], pred : T => Boolean) extends SIterator[T] {
private var hasElem = false
private var elem : T = findNext()

def hasNext = hasElem

def next() = {
val r = elem
findNext()
r
}

def findNext() : T = {
while (iter.hasNext) {
elem = iter.next()

if (pred(elem)) {
hasElem = true
return elem
}
}

hasElem = false
elem
}
}

Normally findNext wouldn't return anything, but that would cause it to not be specialized, so the return type must be set to T.

The fold method is awkward to use as a dummy parameter has to be added so that all type parameters appear in "naked" positions:

def fold[@specialized T, @specialized U](iter : SIterator[T], fn : (U, T) => U, v : U, dummy : T) = {
var r = v

while (iter.hasNext) {
r = fn(r, iter.next())
}

r
}

This leaves us with the following code for the map-filter-sum calculation:

def mapFilterSum(a : Array[Int]) = {
val ai = new ArrayIterator(a, 0, a.length)
val s = new FilterIterator[Int](new MapIterator[Int, Int](ai, _ * 3 + 7), _ % 10 == 0)
fold[Int, Int](s, _ + _, 0, 0)
}

Now to the benchmarks. Remember that we want to compare the performance to this while loop:

def mapFilterSumLoop(a : Array[Int]) = {
var i = 0
var r = 0

while (i < a.length) {
val v = a(i) * 3 + 7

if ((v % 10) == 0)
r += v

i += 1
}

r
}

Compiling with -optimize and running with -server gives the following benchmarks times:

Java version: 1.6.0_20
Loop: (4936,-423600172)
Specialized iterators: (5935,-423600172)

So, 4936 microseconds for the while loop compared to 5935 microseconds for the specialized iterators, about 20% performance penalty. This relatively small difference in running times indicates that all boxing/unboxing has been eliminated. Nice indeed.

It would be nice to clean up the syntax a bit for the filter and map operations. This turns out to be harder than expected, again due to the limitation in the specialization implementation. Dummy parameters have to be added to the filter and map methods:

trait SIterator[@specialized T] {
def hasNext : Boolean
def next() : T
def filter(pred : T => Boolean, dummy : T) = new FilterIterator[T](this, pred)
def map[@specialized U](fn : T => U, dummy : T, dummy2 : U) = new MapIterator[T, U](this, fn)
}

Even with the dummy parameters the map method is not specialized correctly which leads to boxing and inferior performance.

In conclusion I would say that specialization still needs some work before it can be useful in a collection library. It's a very powerful feature and hopefully it can be improved to reach its full potential in future Scala releases.

31 comments:

Iulian said...

I agree with you, and we are going to fix the issues with specializing higher-order functions for the next RC. The rule will be that a method is specialized if any of its specialized type parameters appear naked or as arguments to type constructors that are themselves specialized.

I'll have a look at the map example and see what's going on.

文輝 said...

Yo ~ ~ re-fuel efforts............................................................

K910athrinA_Petrin0 said...

不要把生命看得太嚴肅,反正我們不會活著離開。...............................................................

慧玲 said...

本土天堂自拍台灣夫妻自拍做愛自拍照片打炮自拍貼圖夫妻自拍片免費線上直播片銀赫歐美av線上歐美av線上看歐美女自慰歐美成人女星歐美成人片女星歐美成人免費線上歐美成人情色歐美色情圖貼歐美免費成人電影歐美免費成人影片觀看歐美免費自拍歐美免費做愛片歐美免費情色影片模特兒平台標題樣?嫚雪兒免費小說影片avi影片a直播影片下?影片分享fuck影片成人片影片成人免費凹凸色色卡通圖片免費即時通視訊成人論壇巨乳

蕙帆ElmoAc said...

Virtue is a jewel of great price. ............................................................

sdas said...

人不能像動物一樣活著,而應該追求知識和美德..................................................

皇銘 said...

人生不如意事,十常八九。......................................................................

俊偉 said...

來幫推 你個blog影d相真係好靚,係我至愛~.................................................................

江婷 said...

所有的資產,在不被諒解時,都成了負債.................................................................                           

韻枝 said...

死亡是悲哀的,但活得不快樂更悲哀。......................................................................

柯凡豐 said...

一個人的價值,應該看他貢獻了什麼,而不是他取得了什麼............................................................

陳登陽 said...

人有兩眼一舌,是為了觀察倍於說話的緣故。............................................................

原秋原秋 said...

當一個人內心能容納兩樣相互衝突的東西,這個人便開始變得有價值了。............................................................

佳皓佳皓 said...

海鷗要高飛,必先遠退。花蜜要香醇,必先久釀。............................................................

戴昀德 said...

Better late than never...................................................................

楊儀卉 said...

人們不缺少力量,他們缺少意志。.......................................................

廖珮秋廖珮秋 said...

你的部落格很棒,我期待更新喔..................................................................

蕙春蕙春 said...

人生都有不如意的時候~ 但你的BLOG帶給大家愉快的心情..................................................................

王美妹 said...

廢話不多,祝你順心~^^............................................................

童祖如童祖如 said...

當最困難的時候,也就是離成功不遠的時候。.......................................................

Alex Cruise said...

Jesper, have you thought about doing a Ph.D. or postdoc at EPFL? This kind of thing would be a killer language feature. :)

ToryO_Vis建銘 said...

很喜歡你的部落格,來給你加油,幫你推一下喔~期待你的下一個更新,謝謝............................................................

吳林怡廷佳宇 said...

Judge not of men and things at first sight................................................

陳劉嘉韋蓉宣 said...

道歉是人類一定必要的禮節..................................................

罗韬 said...

過去的事早已消失,未來的事更渺不可知,只有現在是真實的................................................

江仁趙雲虹昆 said...

心平氣和~祝你也快樂~~..................................................

麗王王珠 said...

在莫非定律中有項笨蛋定律:「一個組織中的笨蛋,恆大於等於三分之二。」. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

翊翊翊翊張瑜翊翊翊 said...

愛情不是慈善事業,不能隨便施捨。......................................................................

柔于真于真于真林姍 said...

來給你加油打氣!!!保重!!!............................................................

洪勳劉耀德劉耀德華 said...

路過留言支持~~~..................................................

司冯欣 said...

唯有用熱情、用智慧去觀察事物,這事物才會把他的秘密,洩漏給我們......................................................................