<commit_before>package io.reactors.common.concurrent



import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.ConcurrentSkipListMap
import org.scalameter.api._
import org.scalameter.execution.LocalExecutor
import org.scalameter.japi.JBench
import org.scalatest.FunSuite
import scala.collection.concurrent.TrieMap
import scala.util.Random



class CacheTrieFootprintBenches extends JBench.OfflineReport {
  override def measurer = new Executor.Measurer.MemoryFootprint

  override def defaultConfig = Context(
    exec.benchRuns -> 8,
    exec.independentSamples -> 1,
    verbose -> true
  )

  val sizes = Gen.range("size")(100000, 100000, 100000)

  case class Wrapper(value: Int) extends Comparable[Wrapper] {
    def compareTo(that: Wrapper): Int = that.value - this.value
  }

  val elems = (0 until 2000000).map(i => Wrapper(i)).toArray

  @gen("sizes")
  @benchmark("cache-trie.size")
  @curve("chm")
  def chmSize(size: Int) = {
   val chm = new ConcurrentHashMap[Wrapper, Wrapper]
   var i = 0
   while (i < size) {
     val v = elems(i)
     chm.put(v, v)
     i += 1
   }
   chm
  }

  @gen("sizes")
  @benchmark("cache-trie.size")
  @curve("skiplist")
  def skipListSize(size: Int) = {
   val skiplist = new ConcurrentSkipListMap[Wrapper, Wrapper]
   var i = 0
   while (i < size) {
     val v = elems(i)
     skiplist.put(v, v)
     i += 1
   }
   skiplist
  }

  @gen("sizes")
  @benchmark("cache-trie.size")
  @curve("ctrie")
  def ctrieSize(size: Int) = {
   val trie = new TrieMap[Wrapper, Wrapper]
   var i = 0
   while (i < size) {
     val v = elems(i)
     trie.put(v, v)
     i += 1
   }
   trie
  }

  @gen("sizes")
  @benchmark("cache-trie.size")
  @curve("cachetrie")
  def cachetrieSize(size: Int) = {
    val trie = new CacheTrie[Wrapper, Wrapper]
    var i = 0
    while (i < size) {
      val v = elems(i)
      trie.insert(v, v)
      i += 1
    }
    i = 0
    while (i < size) {
      val v = elems(i)
      trie.lookup(v)
      i += 1
    }
    trie
  }
}


class CacheTrieBenches extends JBench.OfflineReport {
  override def historian =
    org.scalameter.reporting.RegressionReporter.Historian.Complete()

  override def defaultConfig = Context(
    exec.minWarmupRuns -> 40,
    exec.maxWarmupRuns -> 80,
    exec.independentSamples -> 1,
    exec.jvmflags -> List("-server", "-verbose:gc", "-Xmx4048m", "-Xms4048m"),
    verbose -> true
  )

  case class Wrapper(value: Int) extends Comparable[Wrapper] {
    def compareTo(that: Wrapper) = this.value - that.value
  }

  val maxElems = 4000000

  @transient
  lazy val elems = Random.shuffle((0 until maxElems).toVector)
    .map(i => Wrapper(i)).toArray
    .sorted

  val sizes = Gen.range("size")(100000, maxElems, 500000)

  val chms = for (size <- sizes) yield {
    val chm = new ConcurrentHashMap[Wrapper, Wrapper]
    for (i <- 0 until size) chm.put(elems(i), elems(i))
    (size, chm)
  }

  val skiplists = for (size <- sizes) yield {
    val skiplist = new ConcurrentSkipListMap[Wrapper, Wrapper]
    for (i <- 0 until size) skiplist.put(elems(i), elems(i))
    (size, skiplist)
  }

  val ctries = for (size <- sizes) yield {
    val trie = new TrieMap[Wrapper, Wrapper]
    for (i <- 0 until size) trie.put(elems(i), elems(i))
    (size, trie)
  }

  val cachetries = for (size <- sizes) yield {
    val trie = new CacheTrie[Wrapper, Wrapper]
    for (i <- 0 until size) {
      trie.insert(elems(i), elems(i))
    }
    for (i <- 0 until size) {
      trie.lookup(elems(i))
    }
    for (i <- 0 until size) {
      trie.lookup(elems(i))
    }
    (size, trie)
  }

  val artificialCachetries = for (size <- sizes) yield {
    val trie = new CacheTrie[Wrapper, Wrapper]
    //trie.debugCachePopulate(20, elems(0), elems(0))
    //trie.debugCachePopulateTwoLevel(20, elems, elems)
    trie.debugCachePopulateOneLevel(24, elems, elems, true)
    (size, trie)
  }

  // @gen("chms")
  // @benchmark("cache-trie.apply")
  // @curve("CHM")
  // def chmLookup(sc: (Int, ConcurrentHashMap[Wrapper, Wrapper])): Int = {
  //  val (size, chm) = sc
  //  var i = 0
  //  var sum = 0
  //  while (i < size) {
  //    sum += chm.get(elems(i)).value
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("skiplists")
  // @benchmark("cache-trie.apply")
  // @curve("skiplist")
  // def skiplistLookup(sc: (Int, ConcurrentSkipListMap[Wrapper, Wrapper])): Int = {
  //  val (size, skiplist) = sc
  //  var i = 0
  //  var sum = 0
  //  while (i < size) {
  //    sum += skiplist.get(elems(i)).value
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("cachetries")
  // @benchmark("cache-trie.apply")
  // @curve("cachetrie-slow-path")
  // def cachetrieSlowLookup(sc: (Int, CacheTrie[Wrapper, Wrapper])): Int = {
  //  val (size, trie) = sc
  //  var i = 0
  //  var sum = 0
  //  while (i < size) {
  //    sum += trie.slowLookup(elems(i)).value
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("ctries")
  // @benchmark("cache-trie.apply")
  // @curve("ctrie")
  // def ctrie(sc: (Int, TrieMap[Wrapper, Wrapper])): Int = {
  //  val (size, trie) = sc
  //  var i = 0
  //  var sum = 0
  //  while (i < size) {
  //    sum += trie.lookup(elems(i)).value
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("artificialCachetries")
  // @benchmark("cache-trie.apply")
  // @curve("cachetrie-fast-path")
  // def cachetrieFastLookup(sc: (Int, CacheTrie[Wrapper, Wrapper])): Int = {
  //  val (size, trie) = sc
  //  var i = 0
  //  var sum = 0
  //  io.reactors.test.delayTest(this.getClass)
  //  while (i < size) {
  //    val x = trie.fastLookup(elems(i))
  //    sum += (if (x != null) x.value else 0)
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("cachetries")
  // @benchmark("cache-trie.apply")
  // @curve("cachetrie")
  // def cachetrieLookup(sc: (Int, CacheTrie[Wrapper, Wrapper])): Int = {
  //   val (size, trie) = sc
  //   var i = 0
  //   var sum = 0
  //   while (i < size) {
  //     sum += trie.lookup(elems(i)).value
  //     i += 1
  //   }
  //   //println(trie.debugPerLevelDistribution)
  //   println(trie.debugCacheStats)
  //   sum
  // }

  // @gen("sizes")
  // @benchmark("cache-trie.insert")
  // @curve("chm")
  // def chmInsert(size: Int) = {
  //   val chm = new ConcurrentHashMap[Wrapper, Wrapper]
  //   var i = 0
  //   while (i < size) {
  //     val v = elems(i)
  //     chm.put(v, v)
  //     i += 1
  //   }
  //   chm
  // }

  // @gen("sizes")
  // @benchmark("cache-trie.insert")
  // @curve("skiplist")
  // def skiplistInsert(size: Int) = {
  //   val skiplist = new ConcurrentSkipListMap[Wrapper, Wrapper]
  //   var i = 0
  //   while (i < size) {
  //     val v = elems(i)
  //     skiplist.put(v, v)
  //     i += 1
  //   }
  //   skiplist
  // }

  // @gen("sizes")
  // @benchmark("cache-trie.insert")
  // @curve("ctrie")
  // def ctrieInsert(size: Int) = {
  //   val trie = new TrieMap[Wrapper, Wrapper]
  //   var i = 0
  //   while (i < size) {
  //     val v = elems(i)
  //     trie.put(v, v)
  //     i += 1
  //   }
  //   trie
  // }

  @gen("sizes")
  @benchmark("cache-trie.insert")
  @curve("cachetrie")
  def cachetrieInsert(size: Int) = {
    val trie = new CacheTrie[Wrapper, Wrapper]
    var i = 0
    while (i < size) {
      if (i == size / 4 || i == size / 2) {
        println(trie.debugCacheStats)
      }
      val v = elems(i)
      trie.insert(v, v)
      i += 1
    }
    println(trie.debugCacheStats)
    trie
  }
}


class BirthdaySimulations extends FunSuite {
  test("run birthday simulations") {
    birthday(4, 1)
    birthday(16, 1)
    birthday(16, 2)
    birthday(32, 1)
    birthday(32, 2)
    birthday(256, 1)
    birthday(4096, 1)
    birthday(4096, 2)
    birthday(1 << 16, 1)<commit_msg>Increase heap size.<commit_after>package io.reactors.common.concurrent



import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.ConcurrentSkipListMap
import org.scalameter.api._
import org.scalameter.execution.LocalExecutor
import org.scalameter.japi.JBench
import org.scalatest.FunSuite
import scala.collection.concurrent.TrieMap
import scala.util.Random



class CacheTrieFootprintBenches extends JBench.OfflineReport {
  override def measurer = new Executor.Measurer.MemoryFootprint

  override def defaultConfig = Context(
    exec.benchRuns -> 8,
    exec.independentSamples -> 1,
    verbose -> true
  )

  val sizes = Gen.range("size")(100000, 100000, 100000)

  case class Wrapper(value: Int) extends Comparable[Wrapper] {
    def compareTo(that: Wrapper): Int = that.value - this.value
  }

  val elems = (0 until 2000000).map(i => Wrapper(i)).toArray

  @gen("sizes")
  @benchmark("cache-trie.size")
  @curve("chm")
  def chmSize(size: Int) = {
   val chm = new ConcurrentHashMap[Wrapper, Wrapper]
   var i = 0
   while (i < size) {
     val v = elems(i)
     chm.put(v, v)
     i += 1
   }
   chm
  }

  @gen("sizes")
  @benchmark("cache-trie.size")
  @curve("skiplist")
  def skipListSize(size: Int) = {
   val skiplist = new ConcurrentSkipListMap[Wrapper, Wrapper]
   var i = 0
   while (i < size) {
     val v = elems(i)
     skiplist.put(v, v)
     i += 1
   }
   skiplist
  }

  @gen("sizes")
  @benchmark("cache-trie.size")
  @curve("ctrie")
  def ctrieSize(size: Int) = {
   val trie = new TrieMap[Wrapper, Wrapper]
   var i = 0
   while (i < size) {
     val v = elems(i)
     trie.put(v, v)
     i += 1
   }
   trie
  }

  @gen("sizes")
  @benchmark("cache-trie.size")
  @curve("cachetrie")
  def cachetrieSize(size: Int) = {
    val trie = new CacheTrie[Wrapper, Wrapper]
    var i = 0
    while (i < size) {
      val v = elems(i)
      trie.insert(v, v)
      i += 1
    }
    i = 0
    while (i < size) {
      val v = elems(i)
      trie.lookup(v)
      i += 1
    }
    trie
  }
}


class CacheTrieBenches extends JBench.OfflineReport {
  override def historian =
    org.scalameter.reporting.RegressionReporter.Historian.Complete()

  override def defaultConfig = Context(
    exec.minWarmupRuns -> 40,
    exec.maxWarmupRuns -> 80,
    exec.independentSamples -> 1,
    exec.jvmflags -> List("-server", "-verbose:gc", "-Xmx6092m", "-Xms6092m"),
    verbose -> true
  )

  case class Wrapper(value: Int) extends Comparable[Wrapper] {
    def compareTo(that: Wrapper) = this.value - that.value
  }

  val maxElems = 4000000

  @transient
  lazy val elems = Random.shuffle((0 until maxElems).toVector)
    .map(i => Wrapper(i)).toArray
    .sorted

  val sizes = Gen.range("size")(100000, maxElems, 500000)

  val chms = for (size <- sizes) yield {
    val chm = new ConcurrentHashMap[Wrapper, Wrapper]
    for (i <- 0 until size) chm.put(elems(i), elems(i))
    (size, chm)
  }

  val skiplists = for (size <- sizes) yield {
    val skiplist = new ConcurrentSkipListMap[Wrapper, Wrapper]
    for (i <- 0 until size) skiplist.put(elems(i), elems(i))
    (size, skiplist)
  }

  val ctries = for (size <- sizes) yield {
    val trie = new TrieMap[Wrapper, Wrapper]
    for (i <- 0 until size) trie.put(elems(i), elems(i))
    (size, trie)
  }

  val cachetries = for (size <- sizes) yield {
    val trie = new CacheTrie[Wrapper, Wrapper]
    for (i <- 0 until size) {
      trie.insert(elems(i), elems(i))
    }
    for (i <- 0 until size) {
      trie.lookup(elems(i))
    }
    for (i <- 0 until size) {
      trie.lookup(elems(i))
    }
    (size, trie)
  }

  val artificialCachetries = for (size <- sizes) yield {
    val trie = new CacheTrie[Wrapper, Wrapper]
    //trie.debugCachePopulate(20, elems(0), elems(0))
    //trie.debugCachePopulateTwoLevel(20, elems, elems)
    trie.debugCachePopulateOneLevel(24, elems, elems, true)
    (size, trie)
  }

  // @gen("chms")
  // @benchmark("cache-trie.apply")
  // @curve("CHM")
  // def chmLookup(sc: (Int, ConcurrentHashMap[Wrapper, Wrapper])): Int = {
  //  val (size, chm) = sc
  //  var i = 0
  //  var sum = 0
  //  while (i < size) {
  //    sum += chm.get(elems(i)).value
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("skiplists")
  // @benchmark("cache-trie.apply")
  // @curve("skiplist")
  // def skiplistLookup(sc: (Int, ConcurrentSkipListMap[Wrapper, Wrapper])): Int = {
  //  val (size, skiplist) = sc
  //  var i = 0
  //  var sum = 0
  //  while (i < size) {
  //    sum += skiplist.get(elems(i)).value
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("cachetries")
  // @benchmark("cache-trie.apply")
  // @curve("cachetrie-slow-path")
  // def cachetrieSlowLookup(sc: (Int, CacheTrie[Wrapper, Wrapper])): Int = {
  //  val (size, trie) = sc
  //  var i = 0
  //  var sum = 0
  //  while (i < size) {
  //    sum += trie.slowLookup(elems(i)).value
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("ctries")
  // @benchmark("cache-trie.apply")
  // @curve("ctrie")
  // def ctrie(sc: (Int, TrieMap[Wrapper, Wrapper])): Int = {
  //  val (size, trie) = sc
  //  var i = 0
  //  var sum = 0
  //  while (i < size) {
  //    sum += trie.lookup(elems(i)).value
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("artificialCachetries")
  // @benchmark("cache-trie.apply")
  // @curve("cachetrie-fast-path")
  // def cachetrieFastLookup(sc: (Int, CacheTrie[Wrapper, Wrapper])): Int = {
  //  val (size, trie) = sc
  //  var i = 0
  //  var sum = 0
  //  io.reactors.test.delayTest(this.getClass)
  //  while (i < size) {
  //    val x = trie.fastLookup(elems(i))
  //    sum += (if (x != null) x.value else 0)
  //    i += 1
  //  }
  //  sum
  // }

  // @gen("cachetries")
  // @benchmark("cache-trie.apply")
  // @curve("cachetrie")
  // def cachetrieLookup(sc: (Int, CacheTrie[Wrapper, Wrapper])): Int = {
  //   val (size, trie) = sc
  //   var i = 0
  //   var sum = 0
  //   while (i < size) {
  //     sum += trie.lookup(elems(i)).value
  //     i += 1
  //   }
  //   //println(trie.debugPerLevelDistribution)
  //   println(trie.debugCacheStats)
  //   sum
  // }

  // @gen("sizes")
  // @benchmark("cache-trie.insert")
  // @curve("chm")
  // def chmInsert(size: Int) = {
  //   val chm = new ConcurrentHashMap[Wrapper, Wrapper]
  //   var i = 0
  //   while (i < size) {
  //     val v = elems(i)
  //     chm.put(v, v)
  //     i += 1
  //   }
  //   chm
  // }

  // @gen("sizes")
  // @benchmark("cache-trie.insert")
  // @curve("skiplist")
  // def skiplistInsert(size: Int) = {
  //   val skiplist = new ConcurrentSkipListMap[Wrapper, Wrapper]
  //   var i = 0
  //   while (i < size) {
  //     val v = elems(i)
  //     skiplist.put(v, v)
  //     i += 1
  //   }
  //   skiplist
  // }

  // @gen("sizes")
  // @benchmark("cache-trie.insert")
  // @curve("ctrie")
  // def ctrieInsert(size: Int) = {
  //   val trie = new TrieMap[Wrapper, Wrapper]
  //   var i = 0
  //   while (i < size) {
  //     val v = elems(i)
  //     trie.put(v, v)
  //     i += 1
  //   }
  //   trie
  // }

  @gen("sizes")
  @benchmark("cache-trie.insert")
  @curve("cachetrie")
  def cachetrieInsert(size: Int) = {
    val trie = new CacheTrie[Wrapper, Wrapper]
    var i = 0
    while (i < size) {
      val v = elems(i)
      trie.insert(v, v)
      i += 1
    }
    // println(trie.debugCacheStats)
    trie
  }
}


class BirthdaySimulations extends FunSuite {
  test("run birthday simulations") {
    birthday(4, 1)
    birthday(16, 1)
    birthday(16, 2)
    birthday(32, 1)
    birthday(32, 2)
    birthday(256, 1)
    birthday(4096, 1)
    birthday(4096, 2)
    birthday(1 << 16, 1)
{'fraction_non_alphanumeric': 0.17145099064931668, 'fraction_numerical': 0.01896292421369254, 'mean_word_length': 2.2728439974320565, 'pattern_counts': {'":': 0, '<': 59, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7664938', 'n_tokens_mistral': 6348, 'n_tokens_neox': 5969, 'n_words': 1289}