Cache locality, son!

cache-localtiy-son.scala

final class SegmentSumBuffer(val size: Int) {

  private val segmentBits = 12 // 4096 elemets per segmen (n * 8 bytes must fit in L1 cache)
  private val segments = size / (1 << segmentBits) + 1
  private val segmentSize = 8192 // arbitrary number

  private val keySegments = Array.fill(segments) { new Array[Int](segmentSize) }
  private val valSegments = Array.fill(segments) { new Array[Double](segmentSize) }
  private val positions = new Array[Int](segments) // next pos

  private val res = new Array[Double](size)

  def sumSegment(segment: Int) {
    val pos = positions(segment)

    val ks = keySegments(segment)
    val vs = valSegments(segment)

    var i = 0
    while (i < pos) {
      res(ks(i)) += vs(i)
      i += 1
    }

    positions(segment) = 0
  }

  @inline def add(key: Int, value: Double) {
    val segment = key >> segmentBits
    val pos = positions(segment)
    keySegments(segment)(pos) = key
    valSegments(segment)(pos) = value
    positions(segment) += 1

    if (pos+1 == segmentSize) sumSegment(segment)
  }

  def result(): Array[Double] = {
    for (s <- 0 until segments)
      sumSegment(s)

    res
  }

}

why.scala

val scores = new Array[Double](400000) // data ~ 3.2 MB, L1 cache ~ 64KB
for {
  (items, score) <- scoredItems
  item           <- items
} scores(item) += score // cache miss on every read/write

val sumBuffer = new SegmentSumBuffer(400000)
for {
  (items, score) <- scoredItems
  item           <- items
} sumBuffer.add(item, score) // possibly more cache-friendly

val scores = sumBuffer.result()