debasishg

Cache Oblivious and Cache Aware Data Structure and Algorithms

1. Cache-Oblivious Algorithms and Data Structures - Erik Demaine (One of the earliest papers in cache oblivious data structures and algorithms that introduces the cache oblivious model in detail and examines static and dynamic cache oblivious data structures built between 2000-2003)

2. Cache Oblivious B-Trees - Bender, Demaine, Farch-Colton (This paper presents two dynamic search trees attaining near-optimal performance on any hierarchical memory. One of the fundamental papers in the field where both search trees discussed match the optimal search bound of Θ(1+log (B+1)N) memory transfers)

3. Cache Oblivious Search Trees via Binary Trees of Small Height - Brodal, Fagerberg, Jacob (The data structure discussed in this paper works on the version of [2] but avoids the use o

debasishg

Basics

1. The Log-Structured Merge-Tree (LSM-Tree)
2. B-Tree vs Log-Structured Merge-Tree
3. Modern B-tree techniques
4. More Modern B-Tree Techniques
5. LSM-based Storage Techniques: A Survey

B-trees and CPU Caches

debasishg

package cqrs
package eventstore

import zio.*
import zio.prelude.*
import zio.prelude.fx.*

object BaseSyntax:

  type Program[S, R, E, A] = ZPure[Nothing, S, S, R, E, A]

debasishg

Thinking differently between frameworks with concrete abstractions (ZIO in Scala) and those with algebras and typeclasses (Haskell / cats & cats-effects in Scala) :-

Using Haskell or Scala cats / cats-effect, which offers libraries based on algebras and typeclasses, we think in terms of the algebra and the appropriate typeclass to model the effect. It's always algebra first - in the following example, we fetch an entity to work with in a domain model. We try fetching from the cache first and if we get a cache miss we reach out for a database based query. With Haskell or cats in Scala, the mantra is using the algebra of an Alternative typeclass.

getAccount = runMaybeT $
      MaybeT (AC.fetchCachedAccount ano) 
  <|> MaybeT (AR.queryAccount ano)

debasishg

package zio

case class ZKleisli[-R, +E, -A, +B](
    run: A => ZIO[R, E, B]
) { self =>
  // compose with a ZIO not lifted into a Kleisli
  def mapZIO[R1 <: R, E1 >: E, A1 <: A, C1](bc: B => ZIO[R1, E1, C1]): ZKleisli[R1, E1, A, C1] =
    ZKleisli(self.run(_).flatMap(bc))

  // Modify the output of the Kleisli function with `f`

debasishg

import cats.{Applicative, Functor}
import cats.syntax.all._

/** Is this the proper Scala encoding for the Haskell snippet in comments ? */
/** from : https://doisinkidney.com/pdfs/algebras-for-weighted-search.pdf */

/** with help from @Odomontois */

// newtype Cayley f a = Cayley {runC :: ∀b. f b → f (a, b) }
trait Cayley[F[_], A] {

debasishg

import cats.{ Applicative, Functor }
import cats.syntax.all._

/** Is this the proper Scala encoding for the Haskell snippet in comments ? */
/** from : https://doisinkidney.com/pdfs/algebras-for-weighted-search.pdf */

// newtype Cayley f a = Cayley {runC :: ∀b. f b → f (a, b) }
sealed trait Cayley[F[_], A] {
  def apply[B](fb: F[B]): F[(A, B)]
}

debasishg

package interview

object DominoInterview extends App {
	/**
	|1|2|3|
	|4|5|6|
	|7|8|9|
	|*|0|#|

	Problem:

debasishg

  // Inspired by a tweet from @trautonen 1/13/2016
  // Use Source.unfoldAsync to turn paginated database results into an akka-streams Source
  // unfold is the inverse of fold

  case class Page[T](pageNumber:Long, totalPages:Long, contents:List[T])
  case class Thing(id: Long, name: String = "foo")
  
  val totalPages = 5 // 
  val pageSize = 3

debasishg

import org.scalatest._
import org.scalatest.concurrent.ScalaFutures
import scala.concurrent.Future

// from https://github.com/d6y/scalatest-future-failure/blob/master/src/test/scala/example.scala
class ExampleSpec extends FlatSpec with Matchers with ScalaFutures {

  sealed trait Boom extends Throwable
  final case class ExampleFail() extends Boom