notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

commit 5394387cee560ce703cd239d4d30e39e265d9753
parent 2465551bbb0e3a700fab5061d88ba4108b6014ba
Author: Andrew Laack <andrew@laack.co>
Date:   Thu,  8 Oct 2026 21:28:35 -0500

Performance / asm notes

Co-authored-by: Vim

Diffstat:
Adocs/8086.md | 7+++++++
Mdocs/Algorithms.md | 3+++
Adocs/BentleyRules.md | 60++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Adocs/BitBlit.md | 5+++++
Adocs/CGI.md | 7+++++++
Mdocs/CS3110.md | 2++
Ddocs/CodeVerification.md | 18------------------
Mdocs/ComputerScience.md | 5+++++
Adocs/HalsteadMetrics.md | 35+++++++++++++++++++++++++++++++++++
Adocs/HindleyMilnerTypeSystem.md | 24++++++++++++++++++++++++
Adocs/MerkleTree.md | 7+++++++
Adocs/Mov.md | 7+++++++
Adocs/Optimization.md | 8++++++++
Adocs/PerformanceAwareProgramming.md | 31+++++++++++++++++++++++++++++++
Mdocs/PerformanceEngineering.md | 2++
Adocs/RISC.md | 10++++++++++
Mdocs/Software.md | 1+
Adocs/SoftwareStability.md | 23+++++++++++++++++++++++
Adocs/SuccessorGraph.md | 15+++++++++++++++
Adocs/VanityMetrics.md | 9+++++++++
Adocs/Variants.md | 14++++++++++++++
Adocs/Work.md | 18++++++++++++++++++
22 files changed, 293 insertions(+), 18 deletions(-)

diff --git a/docs/8086.md b/docs/8086.md @@ -0,0 +1,7 @@ +# 8086 (ISA) + +**Source:** Performance Aware Programming + +**Definition:** The 8086 ISA from Intel is a CISC instruction set with variable width instructions and 16 bit words. + +8086 was a precursor to x86. Its variable width instrutions, allowing 1, 2, 3, or 4 byte instructions, results in complex boundary decoding, a choice that adds hardware complexity. This does however support more complex instructions than a [RISC](RISC.md) architecture would, allowing memory accesses relative to registers in a singular instruction. diff --git a/docs/Algorithms.md b/docs/Algorithms.md @@ -4,6 +4,9 @@ This is an index for links to notes taken about algorithms. These are CS related ## Links +- [Merkle Tree](MerkleTree.md) +- [Bit Blit](BitBlit.md) +- [Successor Graph](SuccessorGraph.md) - [Quickselect](Quickselect.md) - [Monte Carlo Method](MonteCarloMethod.md) - [Las Vegas Method](LasVegasMethod.md) diff --git a/docs/BentleyRules.md b/docs/BentleyRules.md @@ -0,0 +1,60 @@ +# Bentley Rules for Optimizing Work + +**Source:** MIT 6.172 Performance Engineering of Software Systems, Fall 2018 + +**Definition:** Bentley rules are rules for optimizing the work performed by computer programs, from his book "Writing Efficient Programs". + +Some of the original rules are no longer applicable due to computer architecture changes, but these won't be included in these notes. + +## Rules + +- Datastructures + 1. Packing and encoding + - Compressed representations increase the likelihood for cache hits + 2. Augmentation + - Augment data structures to make specific operations perform less work + - Ex. reference to tail for singly linked lists + 3. Precomputation / compile-time initialization + - Perform calculations in advanced to decrease work during critical sections + - Ex. Meta-programming to precompute tables at compile-time + 4. Caching + - Store previous results to decrease repeated work + 5. Lazy evaluation + - Sparsity + - Compress representations of data + - Ex. compressed sparse row matrix representation +- Logic + 1. Constant folding an propagation + - Evaluate constant expressions and substitute their results into further expressions at compile time + 2. Common-subexpression elimination + - Evaluate an expression and store it for reuse + - This is a specific case of caching + 3. Algebraic identities + - Using identities to replace more costly operations with equivalent cheaper ones + 4. Short-circuiting + - When performing a series of tests, stop evaluating once an answer is found + 5. Creating a fast path + - Perform cheaper tests before performing full tests to evaluate invariants + - Ex. Before checking euclidean distance check Manhattan distance + 6. Combining tests + - Replace a sequence of tests with one test or switch +- Loops + 1. Hoisting + - Avoid recomputing loop-invariant code + 2. Sentinels + - Dummy values to simplify logic of boundary conditions + 3. Loop unrolling + - Combining consecutive iterations of the loop into a single iteration + - Partial unrolling + - Decreased number of loop iterations + - Full unrolling + - No loop + 4. Loop fusion + - Combine multiple loops when they have the same index ranges + 5. Eliminate wasted iterations +- Functions + 1. Inlining + - Replaces the overhead of a function call + 2. Tail recursion elimination + 3. Coarsening recursion + - Make base case larger to decrease recursion depth diff --git a/docs/BitBlit.md b/docs/BitBlit.md @@ -0,0 +1,5 @@ +# Bit Blit + +**Source**: [https://en.wikipedia.org/wiki/Bit_blit](https://en.wikipedia.org/wiki/Bit_blit) + +**Definition:** A bit blit is a BIt bLock Transfer, a predominantly graphics programming data operation where multiple bitmaps are combined using a boolean function. diff --git a/docs/CGI.md b/docs/CGI.md @@ -0,0 +1,7 @@ +# CGI + +**Definition:** CGI is the Common Gateway Interface which specified how web servers may execute programs to process HTTP(S) requests. + +## Details + +CGI specifies the invocation of executables, where context about the web request is passed to the exectuable via environment variables or stdin, and the stdout of the program is to be returned to the caller. Stdin is used for POST request bodies while get request parameters are passed via environment variables. diff --git a/docs/CS3110.md b/docs/CS3110.md @@ -7,3 +7,5 @@ This is the index for my CS 3110 (Data Structures and Functional Programming) no ## Links - [OCaml](OCaml.md) +- [Variants](Variants.md) +- [Hindley Milner Type System](HindleyMilnerTypeSystem.md) diff --git a/docs/CodeVerification.md b/docs/CodeVerification.md @@ -1,18 +0,0 @@ -# Code Verification - -Notes related to correctness verification of code - -## Links - -- [Code Sanitizer](CodeSanitizer.md) -- [Cyclomatic Complexity](CyclomaticComplexity.md) -- [Orion](Orion.md) -- [Where To Fuzz.md](WhereToFuzz.md) -- [PromptFuzz](PromptFuzz.md) -- [NDCG](NDCG.md) -- [Directed Fuzzer](DirectedFuzzer.md) -- [PropertyBasedTesting](PropertyBasedTesting.md) -- [JANUS](JANUS.md) -- [Fuzzing Information Theoretic Perspective](FuzzingInformationTheoreticPerspective.md) -- [Atheris](Atheris.md) -- [ELFuzz](ELFuzz.md) diff --git a/docs/ComputerScience.md b/docs/ComputerScience.md @@ -2,6 +2,11 @@ This is the index for my Computer Science related notes. +## Actively Working On + +- [Optimization](Optimization.md) +- [Software Stability](SoftwareStability.md) + ## Course Notes - [CS 202](CS202.md) diff --git a/docs/HalsteadMetrics.md b/docs/HalsteadMetrics.md @@ -0,0 +1,35 @@ +# Halstead Metrics + +**Source:** [https://en.wikipedia.org/wiki/Halstead_complexity_measures/](https://en.wikipedia.org/wiki/Halstead_complexity_measures/) + +**Definition:** Halstead metrics are a set of simple, measurable, software metrics, intended to be platform and language independent. + +## Metrics + +We have four basic computed values: + +- $n_1$ := the number of distinct operators +- $N_1$ := the total number of operators +- $n_2$ := the number of distinct operands +- $N_2$ := the total number of operands + +Using these numbers we can compute the following: + +- Program vocabulary + - $n_1 + n_2$ +- Program length + - $N_1 + N_2$ +- Calculated estimated program length + - $n_1 * \text{log}_2(n_1) + n_2 \* \text{log}_2(n_2)$ +- Volume + - $N \* \text{log}_2(\text{vocabulary})$ +- Difficulty + - $D = \frac{n_1}{2} \* \frac{N_2}{n_2}$ +- Effort + - $E = D \* V$ + +- Difficulty attempts to describe how difficult a program is to understand. +- Effort has a translation to coding time using the relation: + - $T = \frac{E}{18}$ seconds +- Volume has a translation to delivered bugs + - $B = \frac{V}{3000}$ diff --git a/docs/HindleyMilnerTypeSystem.md b/docs/HindleyMilnerTypeSystem.md @@ -0,0 +1,24 @@ +# Hindley-Milner Type System + +**Source:** [https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system](https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system) + +**Definition:** Hindley-Milner type systems are type systems with parametric poymorphism based on the lambda calculus where types can be checked without the programmer supplying any information about variable typing. + +## Example + +```OCaml +let lt x y = x < y;; + +val lt : a' -> a' -> bool = <fun> + +let () = print_endline (string_of_bool (lt 10 100));; + +true + +let () = print_endline (string_of_bool (lt "andrew" " bob"));; + +false + +``` + +In this context, the `lt` function is a function with the type a' -> a' -> bool where a' informs us that the function is parametrically polymorphic. diff --git a/docs/MerkleTree.md b/docs/MerkleTree.md @@ -0,0 +1,7 @@ +# Merkle Tree + +**Source:** [https://en.wikipedia.org/wiki/Merkle_tree](https://en.wikipedia.org/wiki/Merkle_tree) + +**Definition:** A merkle tree is a tree data structure where each leaf node is labeled with a hash of it's stored data, and each non-leaf node is labeled with a hash of the hashes of its child nodes. + +This data structure is useful for comparing multiple trees against each other. Assuming the same induction strategy, if the root node hashes match, all nodes in the trees match (with an asterisk about hash collisions). If they don't match, you can traverse downwards, following hashes that don't match, to find precisely which elements have changed. diff --git a/docs/Mov.md b/docs/Mov.md @@ -0,0 +1,7 @@ +# Mov + +**Source:** [https://edge.edx.org/c4x/BITSPilani/EEE231/asset/8086_family_Users_Manual_1_.pdf](https://edge.edx.org/c4x/BITSPilani/EEE231/asset/8086_family_Users_Manual_1_.pdf) + +**Definition:** Mov is an 8086 (and ARM, but implementations vary) instruction for moving data from a source to a destination where the source remains the same. + +The 8086 mov instruction can perform a mov on combination of registers and memory addresses. Additional bytes (up to two additional bytes) may be used in some cases. There are also different opcodes for some combinations of registers and memory under the mov mnemonic. diff --git a/docs/Optimization.md b/docs/Optimization.md @@ -0,0 +1,8 @@ +# Optimization + +This is the index for my optimization related course notes. + +## Courses + +- [PerformanceAwareProgramming](PerformanceAwareProgramming.md) +- [PerformanceEngineering](PerformanceEngineering.md) diff --git a/docs/PerformanceAwareProgramming.md b/docs/PerformanceAwareProgramming.md @@ -0,0 +1,31 @@ +# Performance-Aware Programming + +**Source:** [https://www.computerenhance.com/p/table-of-contents](https://www.computerenhance.com/p/table-of-contents) + +## Links + +- SIMD + - SSE - 4 + - streaming simd extensions + - PADDD + - Pack (wide) add + - takes in 4 inputs and outputs + - just 4 adds, but only have to take in one instruction + - each of the inputs are aligned as before + - AVX - 8 + - AXV512 - 16 +- IPC/ILP +- x64 +- [8086](8086.md) +- [RISC](RISC.md) +- LoopUnrolling +- VectorComputing +- Register file +- L1,L2,L3 (dedicated,dedictated,shared) + - times: 3-4, 14, 80 + - sizes: 64kb, 256kb, 8mb +- Mainmemory + - 250 cycles +- Haversine distance + - dist on surface of sphere +- [Mov](Mov.md) diff --git a/docs/PerformanceEngineering.md b/docs/PerformanceEngineering.md @@ -4,3 +4,5 @@ ## Links +- [Work](Work.md) +- [BentleyRules](BentleyRules.md) diff --git a/docs/RISC.md b/docs/RISC.md @@ -0,0 +1,10 @@ +# RISC + +**Definition:** RISC stands for Reduced Instruction Set Computer, describing the ISA of a given computer. + +## Specifics of RISC + +- Tend to have fixed length instructions +- Load and store procedures are how memory is manipulated, never directly + +Early on, it seems RISC also meant a smaller instruction set, but this is generally no longer the case, as many modern RISC ISAs are as complex as early CISC ISAs. diff --git a/docs/Software.md b/docs/Software.md @@ -6,6 +6,7 @@ Software and software related concepts. Focused on free software and primitives. - [Flatpak](Flatpak.md) - [Homebrew](Homebrew.md) +- [CGI](CGI.md) ## Note Taking diff --git a/docs/SoftwareStability.md b/docs/SoftwareStability.md @@ -0,0 +1,23 @@ +# Software Stability + +An index for notes related to the stability and development of robust software. + +### Metrics Notes + +- [Halstead Metrics](HalsteadMetrics.md) +- [Vanity Metrics](VanityMetrics.md) +- [Cyclomatic Complexity](CyclomaticComplexity.md) +- [NDCG](NDCG.md) + +### Code Correctness Notes + +- [Code Sanitizer](CodeSanitizer.md) +- [Orion](Orion.md) +- [Where To Fuzz.md](WhereToFuzz.md) +- [PromptFuzz](PromptFuzz.md) +- [Directed Fuzzer](DirectedFuzzer.md) +- [PropertyBasedTesting](PropertyBasedTesting.md) +- [JANUS](JANUS.md) +- [Fuzzing Information Theoretic Perspective](FuzzingInformationTheoreticPerspective.md) +- [Atheris](Atheris.md) +- [ELFuzz](ELFuzz.md) diff --git a/docs/SuccessorGraph.md b/docs/SuccessorGraph.md @@ -0,0 +1,15 @@ +# Successor Graph + +**Source:** Competitive Programmer's Handbook Ch 16 + +**Definition:** A successor graph is a directed graph where the out-degree of every node is exactly 1. + +## Implication + +Since each node has an out-degree of 1, a successor graph with $n$ vertices has $n$ edges. This means the graph must have at least one cycle. Specifically, successor graphs must have one cycle per connected component. + +Since each vertex has one edge, there's a function $f: V \to V$ where V is the set of all vertices, and $f(v_i) = v_j$ where $v_j$ is the successor to $v_i$. For this reason, successor graphs are sometimes called functional graphs. + +Additionally, we may also define a function $s: V \times \mathbb{N} \to V$ such that $s(v_i,k)$ is the vertex that will be reached from $v_i$ after walking $k$ steps forwards. + +This successor function may be naively evaluated by performing a walk, with a worst case asymptotic time complexity of $O(k)$, but a better approach that involves pre-processing is in the complexity class of $O(\text{log}(n))$. diff --git a/docs/VanityMetrics.md b/docs/VanityMetrics.md @@ -0,0 +1,9 @@ +# Vanity Metrics + +**Definition:** Vanity metrics are metrics that aren't necessarily aligned an underlying target. + +## Examples + +- Code coverage in software testing relative to software stability / robustness +- LoC as a metric for software developer productivity +- Likes on social media as a proxy for social approval diff --git a/docs/Variants.md b/docs/Variants.md @@ -0,0 +1,14 @@ +# Variants + +**Source:** CS3110 Efficient OCaml + +**Chapter:** 3.2 + +**Definition:** Variants are OCaml's analog to enums, allowing the definition of a type with several possible values. + +```ocaml +type day = Sun | Mon | Tue | Wed | Thu | Fri | Sat +let d = Tue +``` + +Each element of the variant is called a constructor. diff --git a/docs/Work.md b/docs/Work.md @@ -0,0 +1,18 @@ +# Work + +**Source:** MIT 6.172 Performance Engineering of Software Systems, Fall 2018 L2 + +**Definition:** The total number of operations performed on a given input. + +Work, as a term, may be applied to functions, code-blocks, or entire programs. + +## Reducing Work + +- Algorithmic design for asymptotic time complexity +- [BentleyRules](BentleyRules.md) + - most of these are related to decreasing work without asymptotic time complexity changes + +## Improving Work Efficiency + +- [BentleyRules](BentleyRules.md) + - packing and encoding mostly