FingerTreeBench.scala

FingerTreeBench.scala

// a few finger tree operations benchmarked on large
// trees, 22-mar-2012, using scala 2.9.1 / java 1.6.0_20 64-bit server.
// each test series performs from fresh 'sbt console'

// -------- preliminaries --------

def t() = System.currentTimeMillis()

def runOp( warmUp: Int, main: Int )( op: => Unit ) : Long = { var i = 0; while( i < warmUp ) { op; i += 1 }; val t1 = t(); i = 0; while( i < main ) { op; i += 1 }; val t2 = t(); t2 - t1 }

// -------- fingertree : indexed+summed --------
// https://github.com/Sciss/FingerTree (head)

def randomTree( n: Int ) : IndexedSummedSeq[ Int, Long ] = { val r = new util.Random( 0L ); var tr = IndexedSummedSeq.emptyIntLong; var i = 0; while( i < n ) { tr +:= r.nextInt(); i += 1 }; tr }

runOp( 10, 10 )( randomTree( 1000000 ))
// --> ca. 6 seconds

def accessAll( t: IndexedSummedSeq[ _, _ ]) { val sz = t.size; var i = 0; while( i < sz ) { t( i ); i += 1 }}

val tr = randomTree( 1000000 )
runOp( 10, 10 )( accessAll( tr ))
// --> ca. 13 seconds

def splitAll( t: IndexedSummedSeq[ _, _ ]) { val sz = t.size; var i = 0; while( i < sz ) { t.take( i ); i += 1 }}

runOp( 3, 3 )( splitAll( tr ))
// --> ca. 15 seconds

// -------- fingertree : indexed --------

def randomTree( n: Int ) : IndexedSeq[ Int ] = { val r = new util.Random( 0L ); var tr = IndexedSeq.empty[ Int ]; var i = 0; while( i < n ) { tr +:= r.nextInt(); i += 1 }; tr }

runOp( 10, 10 )( randomTree( 1000000 ))
// --> ca. 4 seconds

def accessAll( t: IndexedSeq[ _ ]) { val sz = t.size; var i = 0; while( i < sz ) { t( i ); i += 1 }}

val tr = randomTree( 1000000 )
runOp( 10, 10 )( accessAll( tr ))
// --> ca. 11 seconds

def splitAll( t: IndexedSeq[ _ ]) { val sz = t.size; var i = 0; while( i < sz ) { t.take( i ); i += 1 }}

runOp( 3, 3 )( splitAll( tr ))
// --> ca. 14 seconds

// -------- vector : indexed --------

import scala.collection.immutable.IndexedSeq
def randomTree( n: Int ) : IndexedSeq[ Int ] = { val r = new util.Random( 0L ); var tr = IndexedSeq.empty[ Int ]; var i = 0; while( i < n ) { tr +:= r.nextInt(); i += 1 }; tr }

runOp( 10, 10 )( randomTree( 1000000 ))
// --> ca. 3 seconds (note that there might be more efficient ways to construct a Vector)

def accessAll( t: IndexedSeq[ _ ]) { val sz = t.size; var i = 0; while( i < sz ) { t( i ); i += 1 }}

val tr = randomTree( 1000000 )
runOp( 10, 10 )( accessAll( tr ))
// --> ca. 0.1 seconds !

def splitAll( t: IndexedSeq[ _ ]) { val sz = t.size; var i = 0; while( i < sz ) { t.take( i ); i += 1 }}

runOp( 3, 3 )( splitAll( tr ))
// --> ca. 3 seconds

// -------- scalaz : indexed+summed --------
// https://github.com/Sciss/FingerTree/tree/f6c630fdd69841808831e598a6aa4b3e584364fa

import de.sciss.fingertree.FingerTree.IndexedSummed
def randomTree( n: Int ) : IndexedSummed[ Int, Long ] = { val r = new util.Random( 0L ); var tr = IndexedSummed.emptyWithView[Int, Long]; var i = 0; while( i < n ) { tr +:= r.nextInt(); i += 1 }; tr }

runOp( 10, 10 )( randomTree( 1000000 ))
// --> ca 35 seconds

def accessAll( t: IndexedSummed[ _, _ ]) { val sz = t.size; var i = 0; while( i < sz ) { t( i ); i += 1 }}
val tr = randomTree( 1000000 )
runOp( 10, 10 )( accessAll( tr ))
// --> ca. 308 seconds
// Note that in the new finger tree version, `apply` uses `find1` which doesn't produce intermediate tree splittings,
// this is not supported by the Scalaz based version which simply uses `split`. It this therefore expected that this
// runs way slower. Indeed, it is virtually the same operation as `splitAll` below, hence the results are coherent
// (99 * 20/6 = 330)

def splitAll( t: IndexedSummed[ _, _ ]) { val sz = t.size; var i = 0; while( i < sz ) { t.take( i ); i += 1 }}

runOp( 3, 3 )( splitAll( tr ))
// --> ca. 99 seconds