notes

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

commit fd9e47084a5d54f6f6d26bee6e9c9996258bcd56
parent adb08ff93774c81fabb335b3c72e110319e53b5a
Author: Andrew Laack <andrew@laack.co>
Date:   Mon, 19 Oct 2026 11:25:28 -0500

Notes on perf programming and some algorithmic work

Diffstat:
Mdocs/8086.md | 22+++++++++++++++++++++-
Mdocs/AES.md | 1-
Mdocs/Algorithms.md | 1+
Mdocs/ComputerScience.md | 1+
Adocs/CraftingInterpreters.md | 58++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Adocs/InstructionPointer.md | 29+++++++++++++++++++++++++++++
Adocs/MinimumSwapsToSort.md | 107+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Mdocs/PerformanceAwareProgramming.md | 87+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
Mdocs/Stack.md | 60++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Dscratch/scheduling.md | 53-----------------------------------------------------
10 files changed, 362 insertions(+), 57 deletions(-)

diff --git a/docs/8086.md b/docs/8086.md @@ -4,4 +4,24 @@ **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. +8086 was a precursor to x86. Its variable width instrutions 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. + +## Registers + +8086 has the following registers in the register file: + +- ax +- bx +- cx +- dx +- sp +- bp +- si +- di + +Of these, only the '.x' registers are top and bottom byte addressable. As such: + +- ax := ah,al +- bx := bh,bl +- cx := ch,cl +- dx := dh,dl diff --git a/docs/AES.md b/docs/AES.md @@ -9,4 +9,3 @@ ## Performing AES Encryption/Decryption Decryption is done by reversing the order of encryption and thus I will only take notes on the encryption portion of AES. - diff --git a/docs/Algorithms.md b/docs/Algorithms.md @@ -4,6 +4,7 @@ This is an index for links to notes taken about algorithms. These are CS related ## Links +- [Minimum Swaps To Sort](MinimumSwapsToSort.md) - [Merkle Tree](MerkleTree.md) - [Bit Blit](BitBlit.md) - [Successor Graph](SuccessorGraph.md) diff --git a/docs/ComputerScience.md b/docs/ComputerScience.md @@ -19,6 +19,7 @@ This is the index for my Computer Science related notes. - [Operating Systems](OperatingSystems.md) - [Performance Engineering](PerformanceEngineering.md) - [Cryptography](Cryptography.md) +- [Crafting Interpreters](CraftingInterpreters.md) ## Personal Interest diff --git a/docs/CraftingInterpreters.md b/docs/CraftingInterpreters.md @@ -0,0 +1,58 @@ +# Crafting Interpreters + +**Source:** [craftinginterpreters.com](https://craftinginterpreters.com) + +## Links + +- Lox +- Lexing + - scanning + - lexical analysis +- Lexer + - A lexer takes a stream of characters and groups them together into tokens +- Token + - Chunk of characters with syntactic meaning in the language +- Parsing + - We go from syntax to grammar by generating an AST +- Static Analysis + - The above two steps are fairly consistent across languages, this one is not + - Some common static analysis steps + - binding / resolution + - find identifier definitions and associate them + - this has to consider scopes, and in statically typed languages we'd perform type checking here +- all of the above are considered the "frontend". below is the "middle end" (an addition at some point as compilers got more complex, making frontend and backend unsatisfactory). + - The middle end is focused on intermediate representations, not tied to the source or destination forms +- optimization + - constant folding + - at compile time compute computable values + - u32Max = (2**32) - 1 + - -> u32Max = 4294967295 + - ctr = (7 - 12) * (20 + 29) + - -> ctr = -245 +- backend + - code generation + - this is the final step of compilation, where we generate the target code + - asm + - timeless + - bytecode + - named as so due to these instructions frequently being one byte in size + - options + - vm + - run the code on a vm that supports the bytecode as it's isa + - specifically these are process or language virtual machines, not to be confused with system virtual machines + - small compiler to go directly to machine + +- runtime + - in the context of compiled languages, like go, the runtime would be stuff like the gc which is baked into the executable + - for interpreted languages, this is often something like the python interpreter, which manages some program state + - broadly, the runtime is the set of things provided by the language that help out during execution time +- single pass compilers + - category of compiler that doesn't generate an ast, instead parsing and code gening in one pass + - this is actually something that dictated design decisions for c, causing it to have things like only allowing references to functions defined above the current function +- tree walk interpreter + - simple interpreter approach that generates an ast, and than walks it while executing the program +- transpiler + - disagree with the word because it is just a compiler with a specific target, but this is basically the general idea of using IRs as an easy exit without doing the hard work in the backend +- jit + - this is what the jvm is, clr (common language runtime from MS), and js (in browsers) use + - quite complex, considers hotspots during execution to determine if further optimizations are warranted to generated code diff --git a/docs/InstructionPointer.md b/docs/InstructionPointer.md @@ -0,0 +1,29 @@ +# Instruction Pointer (IP) + +**Source:** Performance Aware Programming + +**Definition:** The instruction pointer is a register that points to the next instruction byte to decode. + +## 8086 + +In 8086, IP would work like this: + +1. IP == 0 +2. read 3 bytes (mov, reg r/m, dist) + - The number of bytes can vary on 8086 +3. IP += 3 + - Or however many bytes the instruction is +4. Execute mov instruction + - Or whatever instruction was decoded +5. go to step 2, repeat until instructions cease + +## Jumps + +Step 4 above may be a jumping instruction, like JNZ, which can set the IP directly. In such cases, we set the IP relative to our current position. Additionally, since the jump instruction has been decoded by the time it is being executed, and IP has been incremented by then, our relative reference must account for that too. + +```asm +cmp bx, ax +jne -4 +``` + +This will either loop forever if bx != ax or it will just pass through. diff --git a/docs/MinimumSwapsToSort.md b/docs/MinimumSwapsToSort.md @@ -0,0 +1,107 @@ +# Minimum Swaps To Sort + +## Intuition + +We have an unsorted array. We want to first create a sorted array copy of this array. We'll use this as the final destination, computing the number of swaps to make them equivalent. + +To compute the swap number, we first want a way to index into our unsorted array by value. Thusly, we want a hashmap where the keys are the array's values, and the values are the indices. + +Once we have our hashmap for lookups, we then iterate over each index of our array. If the value in our unsorted array doesn't match the sorted array, we know a swap must be done. Specifically, we want to swap the current element in the array element that matches the one in the sorted array at that index. To find this we simple check our hashmap for the index that contains sorted[i]. We then perform a swap of these two elements in both our array, and in our hashmap so they stay synchronized. We also increment the swap count by one as we have performed a swap. We do this for each element of arr. + +Once done, arr will match sorted, and we will have the minimum swap count to sort as well. The time complexity of this algorithm is O(n log n), dominated by the initial sort. Each swap takes constant time, and we only perform at most n swaps. + +## Definition + +Input: int[] arr +Output: int swapCount + +1. Create sorted copy of arr +2. Create hashmap addressed by array value, storing index in arr + - For each element in arr, h[arr[i]] = i +3. swapCount = 0 +4. For each index in arr + - if sorted[i] != arr[i] + - index = h[sorted[i]] + - swap(arr[i], arr[index]) + - h[arr[i]] = i + - h[arr[ind]] = ind + - swapCount++ +5. Return swapCount + +## Implementation in C++ + +### Leetcode Problem + +Leetcode #3551, Minimum Swaps to Sort by Digit Sum + +Given an array nums of distinct positive integers. Sort the array in increasing order based on the sum of the digits of each number. If two numbers have the same digit sum, the smaller number appears first in the sorted order. + +Return the minimum number of swaps required to rearrange nums into this sorted order. + +A swap is defined as exchanging the values at two distinct positions in the array. + +### Solution + +NOTE: There are implementation improvements to aid in runtime, but asymptotically it's optimal. + +```c++ +int sumDigits(int input) { + int res = 0; + + while(input > 0) { + res += (input % 10); + input /= 10; + } + return res; +} + +std::string encodePair(std::pair<int,int> pr) { + return std::to_string(pr.first) + ":" + std::to_string(pr.second); +} + +class Solution { +public: + int minSwaps(vector<int>& nums) { + + std::vector<std::pair<int,int>> pairs {}; + std::vector<std::pair<int,int>> sortedPairs {}; + + + for(int i = 0; i < nums.size(); ++i) { + pairs.push_back({sumDigits(nums[i]), nums[i]}); + sortedPairs.push_back({sumDigits(nums[i]), nums[i]}); + } + + std::sort(sortedPairs.begin(), sortedPairs.end()); + + std::unordered_map<std::string,int> h {}; + + for(int i = 0; i < pairs.size(); ++i) { + h[encodePair(pairs[i])] = i; + } + + int swapCount = 0; + for(int i = 0; i < pairs.size(); ++i) { + + if(pairs[i] != sortedPairs[i]) { + std::string encodedBase = encodePair(pairs[i]); + std::string encodedTarget = encodePair(sortedPairs[i]); + + int swapIndex = h[encodedTarget]; + + auto temp = pairs[i]; + pairs[i] = pairs[swapIndex]; + pairs[swapIndex] = temp; + + h[encodedTarget] = i; + h[encodedBase] = swapIndex; + + swapCount += 1; + } + } + + + return swapCount; + } +}; +``` diff --git a/docs/PerformanceAwareProgramming.md b/docs/PerformanceAwareProgramming.md @@ -22,9 +22,9 @@ - VectorComputing - Register file - L1,L2,L3 (dedicated,dedictated,shared) - - times: 3-4, 14, 80 + - times (cycles): 3-4, 14, 80 - sizes: 64kb, 256kb, 8mb -- Mainmemory +- MainMemory - 250 cycles - Haversine distance - dist on surface of sphere @@ -34,3 +34,86 @@ - mind blown - [Jump Table](JumpTable.md) - SingleTranslationUnitBuild +- StackPointer (SP) + - Points to the top of the stack +- BasePointer (BP) + - Points to the base of the current stack frame + - often this is used along with an offset to maintain a consistent + - reference to values on the stack (given that it doesn't move + - except when pushing more frames) + - Base pointers may be removed for optimization (to use that register for other stuff), which is called frame pointer optimization + - disable this in gcc with -fomit-frame-pointer + - frame pointer is the base pointer +- [Instruction Pointer](InstructionPointer.md) +- Flags Register + - Register that tracks information about execution, like the output of a cmp / sub, including things like zero, negative, and things like that. +- cmp / sub relation -- cmp is just sub without updating the destination because they both set flags the same way (in 8086) +- Segmented Addressing + - Not common anymore, but is used when there are more addresses than the word size can accommodate. +- Loop + - Instruction that's a decrement and then jnz + - This is generally not used because it's often slower than dec / jnz + - One diff is the loop instruction doesn't set flags +- shr + - shift right + - logical / bitwise shift +- sar + - arithmetic shift right + - maintains signedness + - shifts everything right except the leftmost bit (signed bit) +- shl + - shift left +- sal + - arithmetic shift left + - this is the same as shl due to two's complement +- test + - is equivalent to and, but doesn't write back + - similar to how cmp is sub without writing +- lea + - load effective address + - calculates effective address and writes it to a register + - can be more efficient if the effective address is reused +- inc, dec + - increment, decrement +- push / pop + - push and pop from the [Stack](Stack.md) +- instruction performance characteristics +- 8086 vs x86_64 + - 8086 register addressing is a subset of x86_64 + - to extend registers to 32 bits, we use e{register} such as eax to say the extended ax register + - registers are now 64 bits though so we also have r{register} like rax + - additional 8 registers called: + - R8,R9,R10,...,R15 + - these are addressable in their lonesome or with B, W, and D. + - e.g. R15D -- first 32 bits + - We aren't constrained to the lookup table for effective address calcuation, instead we can use any register additions + disp + - We can also multiply the second register value by 1, 2, 4, or 8 + - e.g. [eax + esi*8] + +--- + +- Haversine distance +- json parsing + - general recommendations about how to do things often result in un-necessary complexity and performance degradations + - json parsers can be relatively complex and slow relative to a binary approach + - it's overcomplicated in part because it's too general purpose +- rdtsc + - read timestamp counter + - this gives us a 64-bit value (half in two different registers) which is how much time the processor believes has elapsed since it started + - this just counts up, and ppl can touch it and it'll just count from there + - if >64-bits, it'll wrap around + - every cycle causes an increment + - this is based on the crystal that modulates clock speed + - main reasons why this isn't perfect + - rdtsc may take some time itself + - the value can be changed + - since its inception, multi-core systems have become more popular + - each core may have a different frequency and for some reason rdtsc started measuring invariant tsc, which is where the tsc is consistent across all cores (even if boosting / sleeping). + - so basically, rdtsc is now some sort of ~ analog for clocks, but not actually + - this allows cross core timing, which is nice, but that's the extent of the goodness as the tsc now isn't for counting cycles + - invariant tsc is probably base clock, not necessarily our core + - so it's just a precise wall clock now + - added in 586 (before x86_64, after 8086) + - while rdtsc is annoying, it is basically always there, whereas alternatives may not be +- rdtscp + - nice out of order execution properties diff --git a/docs/Stack.md b/docs/Stack.md @@ -13,3 +13,63 @@ pop: remove from top This can be implemented as a [SinglyLinkedList](SinglyLinkedList.md) See [Queue](Queue.md) for information about the fifo implementation. + +--- + +# ASM Stack + +**Source:** Performance Aware Programming + +"The Stack" in ASM + +The stack is a region of memory allocated to the task of storing relatively small amounts of scoped variables. Additionally, the stack grows downwards in terms of memory addresses. + +In 8086, somewhere early on in the program there will be an instruction like `mov sp 40000` which will set the stack pointer to the logical bottom of the stack (note, this grows by decrementing the address). + +Then to push to the stack we may do something like this: + +```asm +sub sp, -2 +mov [sp], ax +``` + +And to pop from the stack we may: + +```asm +mov ax, [sp] +add sp, 2 +``` + +This is one way, bad but illustrative, to do this. The other way is as follows: + +```asm +push ax +``` + +```asm +pop ax +``` + +This is often used with functions, and either the function or calling code could push / pop. + +To store the IP register so functions may return from where they're called from we can do this: + +```asm +call interesting_function +``` + +This will push the IP to the stack and then jump. + +To pop the IP register we may use: + +```asm +ret +``` + +## Calling Conventions + +Pushing registers to the stack introduces the concept of "calling conventions" which dictate who performs what operations. + +There are also conventions about how to pass parameters and how to return parameters. These are arbitrarily defined, but must be agreed upon. + +This is also where the idea of an "ABI" comes from. Executables and shared libraries have to adhere to these conventions. diff --git a/scratch/scheduling.md b/scratch/scheduling.md @@ -1,53 +0,0 @@ -priority-based scheduler with preemption. - -| Task | Arrival Time | Exec Time | Priority | -| ---- | ------------ | --------- | -------- | -| T1 | 5 | 3 | 1 | -| T2 | 3 | 4 | 2 | -| T3 | 0 | 4 | 3 | - - -0-3 T3 - -T3 has 1 second left then preempted - -3-5 T2 - -T2 has 2 seconds left then preempted - -5-8 T1 completes - -8-10 T2 completes - -10-11 T3 completes - ---- - -T1 finishes at 8 - -T2 finishes at 10 - -T3 finishes at 11 - ---- - -single cpu; 10 i/o bound tasks 1 cpu bound -i/o bound tasks issue i/o every 1ms -i/o operations always take 10ms -context switching is .1ms -all tasks are long running - - -1ms timeslice: - -91% cpu utilization - -10ms timeslice: - -95% total utilization then. - ---- - -This is because of the .1 ms context switching - -1ms / 1ms + .1 ms = .91