blog

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

commit 825ef17628a4d0c3ceec6482b33ebbffd447fc9e
parent a7b971b987afe0a37ac929cf3df81baca50ab986
Author: Andrew Laack <andrew@laack.co>
Date:   Sat, 10 Oct 2026 20:18:01 -0500

Refactoring + work on constrained software

Diffstat:
Aperf/fifo/Makefile | 6++++++
Aperf/fifo/naive.cpp | 19+++++++++++++++++++
Aperf/fifo/naive.txt | 21+++++++++++++++++++++
Aperf/fifo/ring.cpp | 16++++++++++++++++
Aperf/fifo/ring.txt | 21+++++++++++++++++++++
Rperf/Makefile -> perf/gemini-protocol/Makefile | 0
Rperf/amfora-after.svg -> perf/gemini-protocol/amfora-after.svg | 0
Rperf/amfora-before.svg -> perf/gemini-protocol/amfora-before.svg | 0
Rperf/ex1.cpp -> perf/gemini-protocol/ex1.cpp | 0
Rperf/ex1.svg -> perf/gemini-protocol/ex1.svg | 0
Rperf/gen.py -> perf/gemini-protocol/gen.py | 0
Aposts/wip/array-buffer-fifo.md | 7+++++++
Mposts/wip/basic-software-profiling-cpu-usage.md | 106+++++++++++++++++++++++++++++++++++++------------------------------------------
Aposts/wip/boundary-between-vector-and-hashmap.md | 5+++++
Mposts/wip/constrained-software-revolution.md | 41++++++++++++++++++++++++++++++++++-------
15 files changed, 179 insertions(+), 63 deletions(-)

diff --git a/perf/fifo/Makefile b/perf/fifo/Makefile @@ -0,0 +1,6 @@ +build: + g++ -O0 naive.cpp -o fifo-n + g++ -O0 ring.cpp -o fifo-r +run: build + perf stat ./fifo-n 10000000 &> naive.txt + perf stat ./fifo-r 10000000 &> ring.txt diff --git a/perf/fifo/naive.cpp b/perf/fifo/naive.cpp @@ -0,0 +1,19 @@ +#include <vector> +#include <string> + +int main(int argc, char** argv) { + + if(argc != 2) { + return -1; + } + + int sz = std::stoi(argv[1]); + std::vector<int> vec {}; + vec.resize(sz); + + for(int i = 0; i < sz; ++i) { + vec.push_back(i); + } + + return 0; +} diff --git a/perf/fifo/naive.txt b/perf/fifo/naive.txt @@ -0,0 +1,21 @@ + + Performance counter stats for './fifo-n 10000000': + + 0 context-switches:u # 0.0 cs/sec cs_per_second + 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second + 812 page-faults:u # 4247.0 faults/sec page_faults_per_second + 191.20 msec task-clock:u # nan CPUs CPUs_utilized + 603 branch-misses:u # 0.0 % branch_miss_rate (28.35%) + 116,749,300 branches:u # 610.6 M/sec branch_frequency (28.87%) + 511,175,902 cpu-cycles:u # 2.7 GHz cycles_frequency (43.52%) + 829,537,724 instructions:u # 1.8 instructions insn_per_cycle (43.44%) + 350,354,991 stalled-cycles-frontend:u # 0.75 frontend_cycles_idle (42.92%) + 104,021,883 stalled-cycles-backend:u # 0.20 backend_cycles_idle (28.21%) + 79,706,640 stalled-cycles-backend:u # 0.32 stalled_cycles_per_instruction (28.21%) + + 0.191698746 seconds time elapsed + + 0.162680000 seconds user + 0.026613000 seconds sys + + diff --git a/perf/fifo/ring.cpp b/perf/fifo/ring.cpp @@ -0,0 +1,16 @@ +#include <string> + +int main(int argc, char** argv) { + + if(argc != 2) { + return -1; + } + + int sz = std::stoi(argv[1]); + int* ls = (int*)malloc(sizeof(int)*sz); + + for(int i = 0; i < sz; ++i) { + ls[i] = i; + } + return 0; +} diff --git a/perf/fifo/ring.txt b/perf/fifo/ring.txt @@ -0,0 +1,21 @@ + + Performance counter stats for './fifo-r 10000000': + + 0 context-switches:u # 0.0 cs/sec cs_per_second + 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second + 186 page-faults:u # 5483.4 faults/sec page_faults_per_second + 33.92 msec task-clock:u # nan CPUs CPUs_utilized + 786 branch-misses:u # 0.0 % branch_miss_rate (26.32%) + 10,108,121 branches:u # 298.0 M/sec branch_frequency (27.06%) + 65,974,627 cpu-cycles:u # 1.9 GHz cycles_frequency (41.82%) + 107,813,682 instructions:u # 1.6 instructions insn_per_cycle (44.21%) + 68,657,312 stalled-cycles-frontend:u # 1.02 frontend_cycles_idle (44.27%) + 32,064,508 stalled-cycles-backend:u # 0.45 backend_cycles_idle (29.47%) + 29,954,548 stalled-cycles-backend:u # 0.56 stalled_cycles_per_instruction (28.67%) + + 0.034601306 seconds time elapsed + + 0.022345000 seconds user + 0.011677000 seconds sys + + diff --git a/perf/Makefile b/perf/gemini-protocol/Makefile diff --git a/perf/amfora-after.svg b/perf/gemini-protocol/amfora-after.svg diff --git a/perf/amfora-before.svg b/perf/gemini-protocol/amfora-before.svg diff --git a/perf/ex1.cpp b/perf/gemini-protocol/ex1.cpp diff --git a/perf/ex1.svg b/perf/gemini-protocol/ex1.svg diff --git a/perf/gen.py b/perf/gemini-protocol/gen.py diff --git a/posts/wip/array-buffer-fifo.md b/posts/wip/array-buffer-fifo.md @@ -0,0 +1,7 @@ +# Array Buffer FIFO + +Compare this with the deque approach. + +Discuss comp. complexity vs work optimization and such. + +woah; this is like a lot faster. diff --git a/posts/wip/basic-software-profiling-cpu-usage.md b/posts/wip/basic-software-profiling-cpu-usage.md @@ -1,23 +1,30 @@ +TODOS: +- since we support http(s) we mustn't hardcode file paths. +- is my statement abt perf_events being collected true? + - like the call graph samples aren't perf_events.... +- foreseen results for file w/ python header + + # Basic Software Profiling: CPU Usage -I have wasted many CPU cycles because I didn't understand software profiling. +Collectively, we waste trillions of CPU cycles every day because software isn't profiled frequently. I believe this is an educational problem. -By reading this blog post you will understand the process of identifying which parts of a program are taking the most CPU time. I'll be focusing on compiled CPU-bound programs in this post, but many of these ideas generalize to interpreted programs that have other bottlenecks. +This post will explain how you can find the parts of a program hogging the most CPU time. The post will focus on compiled programs, but the core ideas can be applied to interpreted programs. ## Tools -[Perf](https://en.wikipedia.org/wiki/Perf_%28Linux%29) is the DevTools of Linux. +[Perf](https://en.wikipedia.org/wiki/Perf_%28Linux%29) is a suite of tools for program profiling on Linux. We will mainly use it to collect aggregate performance metrics and call stack information. Analogous tools exist for other Free operating systems, and dedicated tools exist for many interpreted languages to collect call stack information. -You might also want a visualization tool. I'll be showing [flamegraph](https://github.com/brendangregg/FlameGraph). Normally I just use perf because it is very powerful, but having pleasing visuals is useful for demonstrations (newer versions of `perf` can generate flamegraphs directly, but I prefer Brendan's implementation). +[Flamegraph](https://github.com/brendangregg/FlameGraph) is a suite of tools for generating flamegraphs, a type of graph designed for the visualization of performance data. -## Reading a flamegraph +## Reading a Flamegraph -Let's start with something easy, how do you read a flamegraph? Take a look at the following flamegraph and, without my help, try to understand what's being shown: +Take a look at the flamegraph below and try to understand the performance characteristics of the program: <object data="https://blog.laack.co/images/ex1-fg.svg" type="image/svg+xml" width="100%"></object> <details> -<summary>Source code that generated this flamegraph</summary> +<summary>Source code for the program that generated this flamegraph</summary> ```cpp uint32_t square(uint32_t input) { @@ -61,33 +68,29 @@ int main() { </details> -The amount of time spent with the `main` function on the stack is represented by the width of its bar. +The amount of time spent with the `main` function on the call stack is represented by the width of its bar. -Notice how there are multiple bars that say `square`. This is because we execute `square` at different stack depths, and the width of each bar is dictated by the amount of time we spent with `square` on the call stack at a given stack depth. +Notice how there are multiple bars that say `square`. This is because we execute `square` at different call stack depths, and the width of each bar is dictated by the amount of time we spent with `square` on the call stack at a given stack depth. Given how the widths are calculated, we can deduce the top-down width of a bar is how much time the program spent executing a specific function. In the case of `squareHelper` and `square`, we see we spent more time executing `squareHelper` than `square`, evidenced by the fact that from a top-down view, `squareHelper` is wider. -The astute among you might've noticed that `square` and `squareHelper` appear to sometimes be executed outside of the main loop. This is due to how stack depth is calculated, and that's a bit more technical than I'll be able to discuss here. +The astute among you might've noticed `square` and `squareHelper` seem to have been executed a few times outside of the main loop. This is due to how `perf` calculates the stack depth. The specifics of this are more in the weeds than we'll discuss here, but it shouldn't meaningfully impact the high level information that can be obtained from a flamegraph. ## Perf -I've been a little loose with my words thus far in describing flamegraphs. The command I've been using with perf to generate the data for flamegraphs isn't tracking the amount of time spent with a function on the stack at a given depth, we are instead tracking the number of on-CPU samples taken with the function on the top of the call stack. This distinction is important because things like blocking I/O will not be reflected in our timings. Additionally, since perf is interrupt based, it may miss some data, but it gives a good enough approximation of CPU utilization. +I've been loose with my words in terms of the specific data being displayed by the flamegraph. The command I used to generate the data for the flamegraph doesn't track the amount of time spent with a function on the stack at a given depth, we are instead tracking the number of on-CPU samples taken with the function on the top of the call stack. This distinction is important because things like blocking I/O will not be reflected in our timings. -``` +This is the command I ran to generate the data: + +```bash perf record -g ./ex1 ``` -This is the command I ran to generate the data for the flamegraph. The `record` command is used to record events that will be written to the `perf.data` file. By default, `perf record` will sample at 1000Hz. The final option, `-g`, is used to specify we are interested in having the call stack included in our data. +The `record` command is used to record `perf_events` and other statistics. These are written to the `perf.data` file. By default, `perf record` will sample at 1000Hz while the program is on-CPU. The final option, `-g`, is used to specify we are interested in having the call stack included in our data. -If you want to generate a flamegraph right away, you can run the following command: +To view aggregate information about the data in the `perf.data` file we can run: -``` -perf script report flamegraph -``` - -This isn't how the flamegraph above was generated because I prefer Brendan's FlameGraph program, but both are fairly similar, and in a pinch, `perf script report flamegraph` will work. A command I use more often to view performance is: - -``` +```bash perf report -g ``` @@ -103,9 +106,9 @@ perf report -g ... ``` -or if I'm curious to see function calling information: +If you are interested in information about which functions are calling each other, and the resulting on-CPU times therein, you can run this command: -``` +```bash perf report -g --stdio ``` @@ -129,9 +132,9 @@ perf report -g --stdio ... ``` -In many cases, I find the `--stdio` command a bit difficult to read because the report can get exceptionally wide for any non-trivial program (there are additional CLI options that can help with this), and such navigation in the terminal is difficult. +In many cases, I find the `--stdio` command a bit difficult to read because the report can get wide for non-trivial programs (there are additional CLI options that can help with this), and horizontal navigation in the terminal is unergonomic. -The final thing I wanted to mention is if you just want high level information about your program's performance, this is a useful command: +The final command worth mentioning is: ``` perf stat ./ex1 @@ -159,28 +162,30 @@ perf stat ./ex1 0.002939000 seconds sys ``` -This is the command I run most frequently when validating optimizations where the optimization is targeting a portion of the codebase with an outsized footprint. If the program is more uniformly expensive, `perf stat` is likely less useful than a full report / flamegraph. +Which provides high level information about the program's entire execution. + +This is the command I run most frequently when validating optimizations when the optimization is aimed at improving the performance of a function that contributes a lot to the total program runtime. If the program is more uniformly expensive across many functions, `perf stat` is less useful than a full report / flamegraph. -## What to optimize +## What to Optimize -Start with the functions that are costing the most CPU time. Often a very small number of functions take up the majority of the computation, and these are the ones worth optimizing. As it relates to optimization in this context, I don't expect most people to be hand coding assembly, and if you are, you already know all of this anyways. This is for the people just building normal software, consider what's costly and ask yourself two questions: +Start with functions using lots of CPU time that you wouldn't expect to. Often a small number of functions do the majority of computation, and these are the ones worth optimizing in the average case. To make these functions run faster, you should consider the following: -1. Would it be possible to call this function less often -2. Would it be possible to make each call of this function perform less work +1. Can we call this function less often +2. Can each call perform less work via algorithmic improvements -Work is key for most optimization; cache friendliness is important, but what I really want from software I use is for it to not leave tons of performance on the table by using bad algorithms, performing unexpected / unnecessary copies, or calling functions (like draw functions) when they don't have to. +Both of these questions are about decreasing work, not making the work faster. Making work faster can be complex, and it's often easier to improve performance by decreasing wasted work and algorithmic improvements. -## Amfora +## Case Study -Something useful to understand when profiling is the ideal case. Without a conception of how long (roughly) reading a file should take, transferring data, or drawing text, it's hard to understand if performance is to be expected or abnormal. This is very contextual, so I can't answer every question that's relevant for this, but something I've found useful is comparing what I have with something that's similar in ways I'd anticipate that result in similar performance to see where each implementation is spending a disproportionate amount of cycles. +### Amfora -To this end, when I was working on my Gemini protocol browser I wanted to compare it against a well known browser. Amfora states in the readme that it "aims to be the best looking Gemini client with the most features", and while I absotlutely detest the idea that more features means slower in all cases, they do have some features that make it slower*. Specifically, they have syntax highlighting and per character coloring, neither of which my browser has, instead opting for a simpler line based coloring approach which I believe still results in nice looking gemtext because it's all line based at the end of the day. +Amfora is a fancy terminal-based Gemini protocol browser with syntax highlighting. When I start profiling software in a well-trodden domain, I find it useful to use an oracle to understand what's possible. An oracle in this context is a program that performs comparable tasks with sensible performance. -(* They could've done coloring as a second pass perhaps to improve perceived performance, but I'd imagine that'd be more complex, and it would increase the time to having the finalized text displayed) +For Amfora I chose Foreseen (my Gemini protocol browser) as the oracle as it has adequate performance, and performs a sensible subset of the tasks performed by Amfora, notably without the inclusion of syntax highlighting or character addressable coloring. -I decided the first benchmark I was going to perform was a comparison between their performances when opening large files on my filesystem. This was quickly stopped when I realized amfora has a max file size limit of 2097152 bytes or ~2MB. That's curious, but alright then. Let's just make a file that's bigger than 1MB. +I normally start by testing out what I think will be the worst cases. I've found worst cases are often amplifications of average cases, so by improving worst case performance you can improve average case performance as well. -This is a first pass at a direct comparison so I'm not going to make it the max size, and I'm not going to use a representative text, just a bunch of numbers. +Let's evaluating the worst case for just rendering. We'll load a large text file from disk into both browsers, ending execution once text is drawn. I used this code to generate the file: ```python with open("lf.txt", "w") as f: @@ -188,9 +193,9 @@ with open("lf.txt", "w") as f: f.write(str(i) + "\n") ``` -That should be good enough, the resulting file is ~1.3MB in size. +The resulting file is ~1.3MB in size, less than the ~2MB max file size for Amfora, and the 5MB truncation size for foreseen. -I then ran following command: +I then ran both programs killing each program with Ctrl-C at first draw of the text from the file: ``` perf stat amfora lf.txt @@ -217,8 +222,6 @@ Performance counter stats for 'amfora lf.txt': ``` -This is quite unscientific because I simply Ctrl-C'd out once the first characters had rendered. Here's the same for foreseen: - ``` perf stat foreseen lf.txt @@ -243,9 +246,9 @@ perf stat foreseen lf.txt 0.021186000 seconds sys ``` -Of these metrics, the most comparable one is CPU cycles because they aren't spinning during the time it took me to react to the text having been rendered, but even so, this isn't a very good benchmark, and it's not something I'd post about. +This is very unscientific, but that's how I like to start profiling. Given how unscientific this methodology is, we can't conclude anything from this as the timings are within margin of error. It might be worth looking into this further in the future if nothing obvious is found. -Since Amfora can highlight code, let's see how the performance comparse if we just add our python code block to the top of that file, and rename it to lf.gmi: +Since Amfora can highlight code, let's see how the performance changes when we add our python code block from above to the top of the file and rename the file to lf.gmi: ``` perf stat amfora lf.gmi @@ -271,7 +274,7 @@ perf stat amfora lf.gmi 8.207151000 seconds sys ``` -Woah, that's a lot slower. With foreseen there shouldn't be any difference because each line is treated ~ the same, so something's up here. Let's look at a flamegraph for this. +That's a lot slower for Amfora (TODO). Let's look at a flamegraph for this. <object data="https://blog.laack.co/images/amfora-before.svg" type="image/svg+xml" width="100%"></object> @@ -299,7 +302,6 @@ buf += strings.TrimSuffix(lines[i], "\r") + "\r\n" Well, there's our problem; each of these seemingly innocuous appends is actually very costly. Unlike sensible OO / procedural programming languages, Go strings are immutable so each of these operations will create an entirely new string each time, and since we accumulate into `buf` until reaching a preformatted text switch line ("```" lines), the file we were trying to open has to re-create the full string 200,000 times, since we only have the tail 200,000 lines in the file don't have a format switcher. - This is relatively trivial to solve by using a strings.Builder which doesn't have this issue, and that's [what I did](https://github.com/makew0rld/amfora/pull/370/changes)*. After this change, we can perform our profiling again to find: (NOTE: The profiling I did to find this differed slightly from what's shown here, hence the difference in numbers between what we see now, and what's seen in the PR, but they're similar enough) @@ -332,21 +334,13 @@ Much better, that's now using 32x less cycles, and is far faster than before. <object data="https://blog.laack.co/images/amfora-after.svg" type="image/svg+xml" width="100%"></object> - Looking again at the flamegraph, we see the RenderGemini function is now mostly performing word wrapping, and the GC is only utilizing the CPU during 16.48% of our samples, much better. We can go deeper into this if we'd like, but there are now 3 ~equally costly groupings, and as performance becomes more diffuse, optimizations will generally have a smaller amount of impact on perf, so we can leave this where it is. -## Refutations - -I think everything above paints a picture that you don't have to put in that much effort to, in many cases, make things a lot better, and you don't have to be that well versed in optimization either. - -I often hear arguments about how we should just let other people make software and we'll just use it and be happy because they're smarter / better than us at it, this is often the case with libraries, and I so vehemently disagree with this idea. Amfora is a piece of software with 1.4K Github stars, that's existed for > 6 years with 54 contributors; it's not tiny, and yet a glaring issue took this long to find and solve. - -While I do think there is blame in this situation, I don't think there should be any shame in writing bad software, but it's all of our jobs to make our software a little less bad over time, hopefully you can do the same, and help others with that too. - ## What's Next -Consider learning memory profiling next. I didn't directly discuss the topic because 1) it's more complex and 2) memory related performance issues often manifest, like we saw in the go example, as CPU performance issues too. I also didn't discuss anything related to instrumented profiling; everything I've shown with perf can be done without changing any code. When you can change the code, you have the ability to get more granular than just getting metrics on the basis of functions. Despite the upsides of instrumented profiling, I rarely do it because it often takes more time. The main context where I do it is to get shareable information with others, in a working context, and for intra-function profiling. +This post only focused on on-CPU time. There are two additional metrics worth profiling I'll discuss in the future: -Memory stuff is also more complex across languages, where they do weird stuff like go not using malloc. +1. Off CPU profiling +2. Memory profiling diff --git a/posts/wip/boundary-between-vector-and-hashmap.md b/posts/wip/boundary-between-vector-and-hashmap.md @@ -0,0 +1,5 @@ +# Boundary Between Hashmap and Vector (C++) + +At what size is it faster to use a hashmap than a vector? + +THere's a subquestion here of access patterns. That is, if I am inserting a lot, reading a lot, etc., when should I do each? diff --git a/posts/wip/constrained-software-revolution.md b/posts/wip/constrained-software-revolution.md @@ -1,8 +1,35 @@ # Constrained Software Revolution -Software has been atrophying for some time now. Every release of Firefox is slower than the last, every release of Chromium is slower than the last, new websites from tech companies today are slower than they were last month, year, and decade. +[constrained.net](constrained.net) -For all of the claims about caring about inclusion, people seem to not notice how exclusive they are being. When you make software that's slow, buggy, and complicated you're excluding people. People who have slower computers, who use different operating systems, who have disabilities, and who want to make their own standard compliant software. Slow down and consider this: Is you're click-jacking website harming or helping people? Is adding that ill considered feature to Firefox that only slows down startup time by 5ms (on your computer) really worth adding? Every choice in this process leads to the atrophying of software, and leads to the here and now. +--- + +General flow: + +1. explain the issues today + - slow software + - buggy software + - abusive software +2. explain the reasons +3. introduce constrained software + - definition + - examples +4. why not just xyz + - suckless + - too focused on advanced usage + - minimalist + - minimalist is synonymous as long as it's extended to computational minimalism. While less features / complexity is good, a python program with few features is still often not constrained +5. moving forwards, how to contribute, stuff like that + - is foreseen constrained software + - it works from a termainal so accessible + - it works on low end devices + - I think distribution wise it's limited, but that's a nice to have not a requirement + +--- + +Software has been atrophying for years. Every release of Firefox is more bloated and complex than the last, every release of Chromium the same. New websites from today are slower than they were last month, year, and decade. + +For all of the claims about caring about inclusion, people seem to not notice how exclusive they are being. When you make software that's slow, buggy, and complicated you're excluding people. People who have slower computers, who use different operating systems, who have disabilities, and who want to make their own standards-compliant software. Slow down and consider this: Is you're click-jacking website harming or helping people? Is adding that ill considered feature to Firefox that only slows down startup time by 5ms (on your computer) really worth adding? Every choice in this process leads to the atrophying of software, and leads to the here and now. In some ways, software is better now than it's ever been before. My text editor, vim, is marginally better than it was 20 years ago, and if it wasn't, I'd just build that version instead, but when people treat their software like milk that spoils quickly, we don't have the luxury to go back in time and use what we had. Most people, misguidedly, interact with computing systems via the internet, a transient, spoiling, slow, inaccessible hellscape. @@ -12,18 +39,18 @@ It doesn't have to be like this. Definition: -1. Performs a small set of cohesive functions well -2. Respects the user -3. Simple +1. Performs a constrained set of functions +2. Is usable on constrained systems This is the entire definition. Let's break these down. -> Performs a small set of cohesive functions well +> Performs a constrained set of functions. -A small set of cohesive functions. A few things that come to mind: +A cohesive functions. A few things that come to mind: 1. Dillo 2. Mpv +3. Lagrange Dillo is designed to browse the web, with plugins to browse alternative protocols too. This is cohesive. It is for browsing, and the additional features aid in this.