debasishg

Performance Engineering, Hardware and cache awareness with algorithm and data structures

1. Parallel Computing Course - Stanford CS149, Fall 2023
2. Performance-Aware Programming Series by Casey Muratori
3. Algorithms for Modern Hardware
4. Computer Systems: A Programmer's Perspective, 3/E - by Randal E. Bryant and David R. O'Hallaron, Carnegie Mellon University
5. Performance Engineering Of Software Systems - am MITOCW course
6. Parallel Programming 2020 by NHR@FAU
7. Cpu Caches and Why You Care

debasishg

The error you're encountering seems to occur during the build process for librdkafka, which is being built and linked statically as part of your Rust project that uses the rdkafka crate. Here's a breakdown of possible causes and solutions:

1. Resource temporarily unavailable (make[1]: *** read jobs pipe: Resource temporarily unavailable.)

This error suggests that the build process is hitting some system resource limits, possibly related to the number of parallel jobs make is trying to run. The default behavior of make is to run jobs in parallel, which can sometimes overwhelm system resources.

Solution: Try limiting the number of jobs make runs in parallel by setting the MAKEFLAGS environment variable:

export MAKEFLAGS="-j1"

debasishg

#[derive(Debug)]
enum MyError {
    Io(std::io::Error),
    Parse(pest::error::Error<Rule>),
}

#[derive(Debug)]
struct StoreError(MyError);

impl std::fmt::Display for StoreError {

debasishg

Trait Bounds

Trait bounds in Rust are really powerful and also offers lots of idiomatic ways to constrain your model. Bounds are for enforcing constraints even in other languages like Scala, but Rust offers them at a different level.

Here's one example from the book Rust for Rustaceans (a great book BTW).

Suppose you want to construct a HashMap<K, V, S>, whose keys are some generic type T, value is a usize, you can write bounds like T: Hash + Eq, S: BuildHasher + Default.

pub fn doit<T>(value: T)

debasishg

Abstraction and Parametricity implementing domain models in OCaml

One of my favorite comments on abstraction and parametricity ..

Parametricity can be thought of as the dual to abstraction. Where abstraction hides details about an implementation from the outside world, parametricity hides details about the outside world from an implementation.

When using OCaml as the implementation language, you abstract using ADTs (Abstract Data Types) and make your abstraction parametric using functors. And bind all of the algebras together using Modules.

Abstraction

debasishg

(* Modules - the signature of functions and types with no 
   implementation whatsoever. Pure interfaces. *)
module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

(* Note we don't specify any representation for the implementation of a 
   [heap]. Just the facts that define a heap - an ordered element, an 
   abstract type and a bunch of functions *)

debasishg

(* an abstract signature for instantiations of the existential quantifier *)
module type EXISTS =
sig
  (* the predicate *)
  type 'a phi

  (* the existential type *)
  type t

  (* the introduction rule *)

debasishg

Algebraic Domain Modeling

When we talk about the algebra of an operation, we talk about the signature of the operation, and how, starting from the input, we can just "follow the types" to lead to the implementation of that operation.

Consider the following operation generateTrades as part of a domain service TradingService. The idea is to generate all trades that happened on the day (input to the operation) and executed by the user (input to the operation) in the back-office of a securities trading organization.

In the example below, note the following 2 principles that form the core of the algebraic modeling:

1. The sequence of steps mentioned in the specification of the method as comments and correspond one-to-one to the types of the operations used in implementing generateTrades. I have annotated the steps in the implementation below.
2. The implementation of generateTrades is completely decoupled from the implementation of the operations like queryExecutionsForDate, `getAccountNoF

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