blog

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

a-gemini-browser.md (36720B)


      1 # A Gemini Browser (in C++)
      2 
      3 I've written gemini browsers before, but I never saw them through to completion; a silly proposition for such a simple task, but prior iterations lacked the structure necessary to see the project through. An earlier attempt, in Go, ended with a 500 line main file, some tests, and a bunch of weird state management. This time I'll be using TDD, a sensible object hierarchy, and general sensibilities.
      4 
      5 ## Ncurses
      6 
      7 Ncurses is a great dependency (I know, dependency, yuck). It just makes sense without imposing stupid constraints. I can bind all of the keys I care about in the way I want, what's missing? Honestly, pretty much nothing (except maybe not great support for unicode, but I don't care about unicode, ascii ftw!!!).
      8 
      9 ## Issues
     10 
     11 Redirects -- it's rather hard to find normal redirects. There's a stress test redirect thing, but that redirects to a redirect loop or smt. 
     12 
     13 ## Process
     14 
     15 - First you consider requirements
     16 - Then you make choices
     17 - Then you refine your choices
     18 
     19 When you don't first consider requirements, you make choices like using Go or some other GC language that's slow as fuck, and you end up with something that has performance characteristics of amfora. 
     20 
     21 So, here they are:
     22 
     23 - Every user intereaction must happen exceptionally fast
     24 - Memory overhead should be limited whenever possible, but it should not be traded off for performance
     25 - Minimize the complexity of the codebase
     26 
     27 To minimize complexity, I chose to only depend on a few select, semi-sane, dependencies. One was `uri` for parsing URIs. This is a smallish header file, feels acceptable. Ncurses was another. It's not very magical and just does the thing you expect it to do without being constraining in any ways  I'd find irritating, unlike many TUI frameworks which have notions of how things should be laid out on screen, and how keybindings and such should work -- I wanted full control over keybindings, and this was what put me off of things like tview which I've found to be annoying to make my own keybindings with, so might as well just do my own painting with ncurses.
     28 
     29 ### Implementation
     30 
     31 ----
     32 
     33 TESTING:
     34 
     35 - gcov + lcov
     36     - gnu coverage, lcov for viz
     37 - coverage based testing at commit ff1badfc22b1fde35a018cf6406ec51b4a31fab1
     38     - ~/personal-files/blog/foreseen-coverage-3
     39     - this was after refactoring from the getch looping model for the 'o' menu -> taking inputs to the function
     40         - and returnning instead of blocking. 
     41     - realized I'm not covering backspace / escape cases which are relatively important so added those.
     42     - after fixing:
     43         - (render.cpp:182-212)
     44         - 417a0a3c157bb7849fd1562603b2d655d017245b
     45         - still have cols = 0 so will want to address that with passable cols and rows
     46             - will help to make sure small sizes don't have weird issues I used to have with crashing
     47                 - / infinite loops
     48 - refactored link follow redirecting
     49     - y / n support from input arg
     50     - after:
     51         - ~/personal-files/blog/foreseen-coverage-5
     52         - 6254ff6de2feeee86d3b83d87d121694e6fddb4d
     53         - render coverage:
     54             - 39.8 % 	244 	97 	54.5 % 	11 	6
     55         - (then added no branch coverage)
     56 
     57 - refactored user input for status 1X
     58     - 965b9203d358a9ff145334ffc8b3c38aab7def5a
     59     - ~/personal-files/blog/foreseen-coverage-5
     60     - render coverage:
     61         - 55.2 % 	248 	137 	63.6 % 	11 	7
     62 
     63 - added the ability to edit a page in editor
     64     - 2dce468fc819fcfe39561f195dba111434edf828
     65     - ~/personal-files/blog/foreseen-coverage-6
     66     - render coverage:
     67         - 60.7 % 	257 	156 	63.6 % 	11 	7
     68 
     69 ---
     70 
     71 it's a bit slow though. Let's get benchmarks for that.
     72 
     73 - refactored main loop to accept rows and cols as parameters so I can test that. 
     74     - commit: e357bcbbb0cc23129c1719ae38819fb4a46c0c1e
     75     - testing:
     76         - -O0
     77         - we find these results with a small file:
     78 
     79 
     80 ```
     81 benchmark name                       samples       iterations    est run time
     82                                      mean          low mean      high mean
     83                                      std dev       low std dev   high std dev
     84 -------------------------------------------------------------------------------
     85 All line types - X: 8 Y: 8                     100             1    34.6794 ms
     86                                         314.314 us    308.421 us    324.578 us
     87                                         38.7483 us     26.394 us    65.5161 us
     88 
     89 All line types - X: 8 Y: 9                     100             1     28.572 ms
     90                                         284.577 us     277.58 us    297.826 us
     91                                         47.7262 us    29.1738 us    74.4475 us
     92 
     93 All line types - X: 9 Y: 8                     100             1    27.5064 ms
     94                                          277.78 us    273.851 us    287.784 us
     95                                         29.7422 us    14.0369 us    60.6527 us
     96 
     97 All line types - X: 9 Y: 9                     100             1    27.3251 ms
     98                                         296.212 us    288.637 us    307.774 us
     99                                         46.9271 us    34.7786 us    69.0629 us
    100 ```
    101 the above samples are from commit 59cbaf1b90f4dfde5db35d4c9d474497f9d72e11
    102 
    103 These are all very fast; to be expected considering we are just reading a file from disk and rendering it. I'm  not too concerned about optimizing that, but the case I noticed was slow before was scrolling for large files. 
    104 
    105 let's evaluate that. 
    106 
    107 So we write some code to generate a string of 100_000 chars size, write it to a file, and see how that goes. 
    108 
    109 (the string has \n and ' ' along with al num):
    110 
    111 100 up, 100 down, 100x100 screen size
    112 
    113 ```
    114 
    115 benchmark name                       samples       iterations    est run time
    116                                      mean          low mean      high mean
    117                                      std dev       low std dev   high std dev
    118 -------------------------------------------------------------------------------
    119 100k character file, load, scroll
    120 down 100x, scroll up 100x with
    121 100x100 emulated terminal size                 100             1     6.97173 m
    122                                          4.94128 s     4.79944 s     5.08459 s
    123                                         726.364 ms    660.585 ms    805.704 ms
    124 ```
    125 
    126 why so slow?
    127 
    128 well, we are currently calling breaklines every time we call draw, which is a lot. this means we go through each line each time, using our accumulation logic to breaklines to fit on screen. That logic isn't perfect; but why call it more often than needed instead of focusing on making that bit fast right now. 
    129 
    130 We really only need to break in two cases:
    131 
    132 1) content of page changes
    133 2) screensize changes
    134 
    135 so we handle screensize changes by checking if current cols != prior and same for lines. 
    136 
    137 To check if screen content has changed, we could do a != check, but that'd be basically the same issue as we'd have to scan each line each time. As such, we should have another boolean to track this too. 
    138 
    139 we can just set it as true whenever we might be performing a state transiation between screens. after we update the textrender vector, we then set rebreak to true. 
    140 
    141 (the times it might change are f,b,reload, open (site, link))
    142 
    143 admittedly this make the software a bit more complex, but it is much, much faster for large files.
    144 
    145 ```
    146 benchmark name                       samples       iterations    est run time
    147                                      mean          low mean      high mean
    148                                      std dev       low std dev   high std dev
    149 -------------------------------------------------------------------------------
    150 100k character file, load, scroll
    151 down 100x, scroll up 100x with
    152 100x100 emulated terminal size                 100             1     1.97092 m
    153                                          1.28874 s     1.23349 s     1.35405 s
    154                                         304.981 ms    258.005 ms     373.63 ms
    155 ```
    156 
    157 commit - 70af9dfaf9afa5586109d2c21ba3df7f5f86118f
    158 
    159 alright, so that's 3.53x faster, not terrible for what is a fairly small file. 
    160 
    161 what's taking so much time now?
    162 
    163 let's consult perf!
    164 
    165 +   96.47%     0.02%  bench1.out  bench1.out            [.] draw(DrawState&)                                                               ▒
    166 +   96.42%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Detail::CompleteType<std::remove_reference<std::remove_cv<std▒
    167 +   96.42%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Detail::CompleteType<std::remove_reference<std::remove_cv<std▒
    168 +   96.42%     0.00%  bench1.out  bench1.out            [.] std::vector<std::chrono::duration<double, std::ratio<1l, 1000000000l> >, std::a▒
    169 +   96.42%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Benchmark::run<std::chrono::_V2::steady_clock>()::{lambda()#2▒
    170 +   96.42%     0.00%  bench1.out  bench1.out            [.] std::enable_if<std::is_same<std::chrono::_V2::steady_clock, std::chrono::_V2::s▒
    171 +   96.42%     0.01%  bench1.out  bench1.out            [.] Catch::Benchmark::Detail::run_plan_default(Catch::Benchmark::ExecutionPlan cons▒
    172 +   93.85%     9.90%  bench1.out  bench1.out            [.] sanitizeCharactersToDraw(std::vector<std::pair<std::__cxx11::basic_string<char,▒
    173 +   79.51%     3.76%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    174 +   75.41%     9.64%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    175 +   30.58%     7.91%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    176 +   21.26%    11.97%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    177 +   16.02%     6.88%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    178 +   14.83%     4.53%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    179 +   14.53%     7.35%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    180 +   10.56%     7.06%  bench1.out  bench1.out            [.] unsigned long const& std::min<unsigned long>(unsigned long const&, unsigned lon▒
    181 +    8.21%     1.18%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    182 +    8.02%     5.48%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    183 +    6.70%     3.32%  bench1.out  bench1.out            [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒
    184 +    6.69%     5.21%  bench1.out  bench1.out            [.] std::char_traits<char>::assign(char&, char const&)                             ▒
    185 
    186 I see; so draw is quite slow. specifically though, we notice most of the time is spent in 
    187 
    188 +   93.85%     9.90%  bench1.out  bench1.out            [.] sanitizeCharactersToDraw(std::vector<std::pair<std::__cxx11::basic_string<char,▒
    189 
    190 why is that? well, it goes through the entire list (again), to pull out \r, \t, \v, ... characters and do substitiutions as necessary. seems rather useless to be here in all honesty.
    191 
    192 we can do this as part of the mustrerender process, let's do that. instead.
    193 
    194 now we get:
    195 
    196 ```
    197 benchmark name                       samples       iterations    est run time
    198                                      mean          low mean      high mean
    199                                      std dev       low std dev   high std dev
    200 -------------------------------------------------------------------------------
    201 100k character file, load, scroll
    202 down 100x, scroll up 100x with
    203 100x100 emulated terminal size                 100             1     2.06189 s
    204                                         20.9672 ms    20.8873 ms    21.0798 ms
    205                                         480.389 us    369.924 us    666.694 us
    206 ```
    207 
    208 We went from a mean of 4.94128s to 20.9672 ms, we find this is:
    209 
    210 4941.28ms -> 20.9672ms 
    211 
    212 4941.28ms / 20.9672ms = 235.66713724293183x faster.
    213 
    214 , and this is for a small(ish) file where we are actually doing a relatively small amount of up / down movements. I would've used larger files, but it was originally so slow that I couldn't. 
    215 
    216 ---
    217 
    218 ohh yeah, and we also got a shitload more coverage:
    219 
    220 - render.cpp
    221     - 84.7 % 	275 	233 	81.8 % 	11 	9
    222 
    223 Lines: 	91.0 % 	2067 	1882
    224 Test Date: 	2026-09-30 15:12:43 		Functions: 	94.7 % 	190 	180
    225 
    226 ---
    227 
    228 ok, let's go with 10,000,000 for evaluation to see how the perf stacks up with 1k down, 1k up
    229 
    230 ```
    231 
    232 benchmark name                       samples       iterations    est run time
    233                                      mean          low mean      high mean
    234                                      std dev       low std dev   high std dev
    235 -------------------------------------------------------------------------------
    236 10m character file, load, scroll
    237 down 1000x, scroll up 1000x with
    238 100x100 emulated terminal size                 100             1     5.08277 m
    239                                           2.7127 s     2.61997 s     2.81432 s
    240                                         494.032 ms    444.661 ms    544.078 ms
    241 
    242 ```
    243 
    244 ```
    245 +   99.99%     0.00%  bench1.out  bench1.out            [.] CATCH2_INTERNAL_TEST_0()
    246 +   99.85%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Benchmark& Catch::Benchmark::Benchmark::operator=
    247 +   99.85%     0.00%  bench1.out  bench1.out            [.] void Catch::Benchmark::Benchmark::run<std::chrono::_V2::steady_cloc
    248 +   98.82%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Detail::BenchmarkFunction::model<CATCH2_INTERNAL_
    249 +   98.82%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Detail::BenchmarkFunction::model<CATCH2_INTERNAL_
    250 +   98.82%     0.00%  bench1.out  bench1.out            [.] void Catch::Benchmark::Chronometer::measure<CATCH2_INTERNAL_TEST_0(
    251 +   98.82%     0.00%  bench1.out  bench1.out            [.] void Catch::Benchmark::Chronometer::measure<CATCH2_INTERNAL_TEST_0(
    252 +   98.82%     0.00%  bench1.out  bench1.out            [.] std::enable_if<std::is_same<void, decltype ({parm#1}({parm#2}...))>
    253 +   98.82%     0.00%  bench1.out  bench1.out            [.] CATCH2_INTERNAL_TEST_0()::{lambda(int)#1}::operator()(int) const
    254 +   97.91%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Detail::CompleteType<std::remove_reference<std::r
    255 +   97.91%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Detail::CompleteType<std::remove_reference<std::r
    256 +   97.91%     0.00%  bench1.out  bench1.out            [.] std::vector<std::chrono::duration<double, std::ratio<1l, 1000000000
    257 +   97.91%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Benchmark::run<std::chrono::_V2::steady_clock>():
    258 +   97.91%     0.00%  bench1.out  bench1.out            [.] std::enable_if<std::is_same<std::chrono::_V2::steady_clock, std::ch
    259 +   97.91%     0.00%  bench1.out  bench1.out            [.] Catch::Benchmark::Detail::run_plan_default(Catch::Benchmark::Execut
    260 +   97.72%     0.00%  bench1.out  bench1.out            [.] mainLoop(DrawState&, Browser&, int, int, int)
    261 +   80.38%     0.06%  bench1.out  bench1.out            [.] draw(DrawState&)
    262 +   61.79%     4.26%  bench1.out  bench1.out            [.] breakLines(std::vector<std::pair<std::__cxx11::basic_string<char, s
    263 ```
    264 
    265 so... we are still spending a ton of time on these larger files on breaklines. there's also ~20% time spent on other stuff related to drawing, most of which appears to be 
    266 
    267 ```
    268 +   17.20%     0.00%  bench1.out  bench1.out            [.] Browser::goToSite(std::__cxx11::basic_string<char, std::char_traits
    269 +   17.20%     0.00%  bench1.out  bench1.out            [.] tryVisitSite(DrawState&, Browser&, std::__cxx11::basic_string<char,
    270 +   16.94%     0.12%  bench1.out  bench1.out            [.] Browser::toLines(Site*)
    271 +   14.64%     1.57%  bench1.out  bench1.out            [.] sanitizeCharactersToDraw(std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, TextRender>, std
    272 ```
    273 
    274 so quite a bit of time is spent on 1) toLines, mostly sanitize characters 2) breakLines
    275 
    276 alright, let's focus on breaklines first. 
    277 
    278 ```
    279 std::vector<std::pair<std::string, TextRender>> breakLines(std::vector<std::pair<std::string, TextRender>>& strLs, int width, int cols) {
    280  
    281     std::vector<std::pair<std::string, TextRender>> res {};
    282  
    283     int leftPadAmount = std::max(0, (cols - width) / 2);
    284     std::string leftPadStr (leftPadAmount, ' ');
    285  
    286     if(width <= 0) {
    287         return res;
    288     }
    289  
    290     for(std::size_t i = 0;  i < strLs.size(); ++i) {
    291  
    292         std::string cstr = strLs[i].first;
    293  
    294         if(!strLs[i].second.shouldFold) {
    295             int limit = cols - leftPadAmount;
    296             int w = 0;
    297             std::size_t end = 0;
    298             while(end < cstr.size()) {
    299                 int len = std::min(u8len(cstr[end]), (int)(cstr.size() - end));
    300                 int cw = u8width(cstr, end, len);
    301                 if(w + cw > limit) {
    302                     break;
    303                 }
    304                 w += cw;
    305                 end += len;
    306             }
    307             cstr = cstr.substr(0, end); // otherwise there's some funkiness at the end due to how ncurses renders stuff.
    308             res.push_back(std::pair<std::string,TextRender> {leftPadStr + cstr, strLs[i].second});
    309             continue;
    310         }
    311  
    312         std::string current = "";
    313         int curWidth = 0;
    314         int lastSpace = -1;
    315         int lastSpaceWidth = 0;
    316  
    317         for(int x = 0; x < (int)cstr.size(); ) {
    318             if(cstr[x] == '\n') {
    319                 res.push_back(std::pair<std::string,TextRender> {leftPadStr + current, strLs[i].second});
    320                 current = "";
    321                 curWidth = 0;
    322                 lastSpace = -1;
    323                 ++x;
    324                 continue;
    325             }
    326  
    327             int len = std::min(u8len(cstr[x]), (int)cstr.size() - x);
    328             int w = u8width(cstr, x, len);
    329  
    330             if(w > 0 && curWidth > 0 && curWidth + w > width) {
    331  
    332                 std::string toPush = current;
    333  
    334                 if(lastSpace != -1) {
    335                     toPush = current.substr(0,lastSpace+1);
    336                     current = current.substr(lastSpace+1);
    337                     curWidth = curWidth - lastSpaceWidth;
    338                 } else {
    339                     current = "";
    340                     curWidth = 0;
    341                 }
    342  
    343                 res.push_back(std::pair<std::string,TextRender> {leftPadStr + toPush,strLs[i].second});
    344                 lastSpace = -1;
    345             }
    346  
    347             current.append(cstr, x, len);
    348             curWidth += w;
    349             if(cstr[x] == ' ') {
    350                 lastSpace = current.size() - 1;
    351                 lastSpaceWidth = curWidth;
    352             }
    353             x += len;
    354         }
    355         if(current.size() > 0) {
    356             res.push_back(std::pair<std::string,TextRender> {leftPadStr + current,strLs[i].second});
    357             current = "";
    358         }
    359     }
    360  
    361     return res;
    362 }
    363 
    364 ```
    365 
    366 so we take in strls then break and transfer lines into a new list to return it. We do want this to be the case because strLs may be broken again with different cols so it must be const. 
    367 
    368 first thing we can do is allocate the proper amount of space for res up front. After we do our width check, we know have a lower bound of the size of the strLs, so let's use that.
    369 
    370 ```
    371 res.reserve(strLs.size());
    372 ```
    373 
    374 
    375 we can also make cstr a const reference and then cut down on a few allocations during the !shouldFold branch:
    376 
    377 
    378 ```
    379 const std::string& cstr = strLs[i].first;
    380 ```
    381 
    382 if we look at sanitize characters, 
    383 
    384 ```void sanitizeCharactersToDraw(std::vector<std::pair<std::string, TextRender>>& strLs) {
    385     for(std::size_t i = 0; i < strLs.size(); ++i) {
    386 
    387         std::string& s = strLs[i].first;
    388 
    389         std::string out;
    390         for (int c: s)
    391             if (c == '\r' || c  == '\v' || c == '\b' || c == '\f' || c == '\a' || c == '\0') {
    392                 continue;
    393             } else if (c == '\t') {
    394                 out += "    "; // \t is a larger character and fucks with breaklines.
    395             } else {
    396                 out += c;
    397             }
    398 
    399         strLs[i].first = out;
    400     }
    401     return;
    402 }
    403 ```
    404 
    405 the main issue with this is += has the same reseze issue as our vector did before. 
    406 
    407 since most characters won't be special, it's relatively safe to just do:
    408 
    409 ```
    410 out.reserve(s.size());
    411 ```
    412 
    413 there's other stuff that can be done to make each invocation faster, but I wonder if threads could help with this because this is quite parallelizable. 
    414 
    415 
    416 let's first do this with the sanitize characters to draw because this is quite safe given that it's operating on a vector to permute it instead of constructing a vector to return. 
    417 
    418 ```
    419 void operate(std::vector<std::pair<std::string, TextRender>>& strLs, std::size_t idxStart, std::size_t idxStop) {
    420     for(std::size_t i = idxStart; i < idxStop; ++i) {
    421         std::string& s = strLs[i].first;
    422         std::string out;
    423         out.reserve(s.size());
    424 
    425         for (int c : s)
    426             if (c == '\r' || c  == '\v' || c == '\b' || c == '\f' || c == '\a' || c == '\0') {
    427                 continue;
    428             } else if (c == '\t') {
    429                 out += "    "; // \t is a larger character and fucks with breaklines.
    430             } else {
    431                 out += c;
    432             }
    433 
    434         strLs[i].first = std::move(out);
    435     }
    436     return;
    437 
    438 }
    439 
    440 void sanitizeCharactersToDraw(std::vector<std::pair<std::string, TextRender>>& strLs) {
    441     std::vector<std::thread> threads{};
    442 
    443     if(strLs.size() > 100) {
    444         for(int i = 0; i < 10; ++i) {
    445             threads.emplace_back(&operate, std::ref(strLs), i*strLs.size() / 10, (i+1)*strLs.size() / 10);
    446         }
    447         for(auto& t: threads) {
    448             t.join();
    449         }
    450     } else {
    451         operate(strLs, 0, strLs.size());
    452     }
    453 }
    454 ```
    455 
    456 
    457 before threading, with allocation changes:
    458 
    459 ```
    460 benchmark name                       samples       iterations    est run time
    461                                      mean          low mean      high mean
    462                                      std dev       low std dev   high std dev
    463 -------------------------------------------------------------------------------
    464 10m character file, load, scroll
    465 down 1000x, scroll up 1000x with
    466 100x100 emulated terminal size                 100             1     4.32557 m
    467                                            3.374 s     3.26604 s     3.49725 s
    468                                         589.504 ms    512.778 ms    697.531 ms
    469 ```
    470 
    471 
    472 after threading:
    473 
    474 ```
    475 
    476 10m character file, load, scroll
    477 down 1000x, scroll up 1000x with
    478 100x100 emulated terminal size                 100             1     4.27891 m
    479                                          3.35466 s     3.24084 s      3.4761 s
    480                                         598.993 ms    541.664 ms     678.83 ms
    481 
    482 ```
    483 
    484 ok, probably not worth the added complexity for dubious returns, albeit without calibration for thread count. 
    485 
    486 the other issue with this is the cache friendliness of it. we are storing  a pair for each element when we really just care about the strings. this would require sizeable refactors to fix, but is perhps worth considering in the future as it's a more data-oriented-design thing. 
    487 
    488 
    489 ---
    490 
    491 let's stop and compare olevels for this now. I'll  run each a few times.
    492 
    493 
    494 we perform 5 iterations of reading in the same file, doing the parsing, doing the 1000 down, 1000 up on O0 per iteation. This means we are averaging across iterations where a single iteration is itself 5 iterations of loading the file and doing the movement:
    495 
    496 -O0
    497 
    498 ```
    499 benchmark name                       samples       iterations    est run time
    500                                      mean          low mean      high mean
    501                                      std dev       low std dev   high std dev
    502 -------------------------------------------------------------------------------
    503 5 passes per iteration, 10m
    504 character file, load, scroll down
    505 1000x, scroll up 1000x with 100x100
    506 emulated terminal size                         100             1     22.7922 m
    507                                          17.3735 s     16.9738 s     17.7704 s
    508                                          2.03698 s     1.86856 s     2.23307 s
    509 
    510 ```
    511 
    512 -Ofast
    513 
    514 ```
    515 benchmark name                       samples       iterations    est run time
    516                                      mean          low mean      high mean
    517                                      std dev       low std dev   high std dev
    518 -------------------------------------------------------------------------------
    519 5 passes per iteration, 10m
    520 character file, load, scroll down
    521 1000x, scroll up 1000x with 100x100
    522 emulated terminal size                         100             1     4.61931 m
    523                                          2.43228 s     2.35738 s     2.51318 s
    524                                         399.998 ms     356.84 ms      449.1 ms
    525 
    526 ```
    527 
    528 ohh yeah.
    529 
    530 ---
    531 
    532 memory overhead is rather large though...
    533 
    534 1064kb
    535 
    536 
    537 amfora:
    538 
    539 baseline: 24MB
    540 
    541 andrew@deepthought:~$ du -s 1.1MB.gmi
    542 1064    1.1MB.gmi
    543 
    544 1.1MB file: 49MB
    545 
    546 delta: 25MB
    547 
    548 foreseen:
    549 
    550 baseline: 9.2MB
    551 
    552 1.1MB file: 25MB
    553 
    554 delta: 15.8MB
    555 
    556 most of their optimization appears to come from showing txt where they don't have character coloring, it seems, which really cuts down on memory usage, but when they have gemtext, even without any formatting, it's still way bigger.
    557 
    558 
    559 amfora ~2MB file: 77MB
    560 amfora ~2MB file: 39MB
    561 
    562 get a recording of this shit because it's fucking pathetic.
    563 
    564 we're also storing ~3 copies of the page:
    565 
    566 - Site - this is in cache, containing the body + header
    567 - Preformatted - before breaking lines
    568 - Postformatted - after breaking lines
    569     - we really want these unless we compute these in realtime because 
    570     - screen size changes can unbreak lines which would add additional computation 
    571     - instead of just throwing out prior and starting fresh without folding back lines. 
    572 
    573 we could put the cache on disk. We could also try compressing the cache. 
    574 
    575 the former would make cache accesses way slower; like we see when reading files from disk. 
    576 
    577 ---
    578 
    579 ---
    580 
    581 at what point did we accept that software could just be dogshit slow all the fucking time? I tried using amfora recently and it was absolutely fucking unbearable. Are you serious? You can't open a file bigger than 2MB? Why the fuck not? I have 16, goddamn, gigabytes of memory? Oh, I see, because you are a performance leach and it would be **fucking** embarrassing if I could open larger files because it would show how utterly fucking stupid you are. 
    582 
    583 Let's get to it. 
    584 
    585 ---
    586 
    587 Ok, so let's figure out why amfora is slow; is it stupid algorithmic choices or a stupid language choice?
    588 
    589 ---
    590 
    591 so amfora is slow to open, taking a few frames, but this is inconsequential relative to the time taken to open any file of reasonable size (>1MB), so what's that about?
    592 
    593 I mean, it compiles quickly which is nice, but it's slow as fuck otherwise. 
    594 
    595 ---
    596 
    597 1.3M    count.gmi
    598 
    599 perf record -g  amfora ~/count.gmi
    600 
    601 these are just 262180 lines of number that are <=5 digits long.
    602 
    603 I was going to update the code to stop it when the file had finished rendering, whatever codepath would do that, but it took so fucking long it didn't even matter. 
    604 
    605 > +   99.23%     0.00%  amfora   amfora                [.] 0x0000555f1b69fb41                          ◆
    606 > +   68.33%     0.00%  amfora   amfora                [.] 0x0000555f1b69db67                          ▒
    607 > +   61.24%     0.00%  amfora   amfora                [.] 0x0000555f1b646b45                          ▒
    608 > +   60.22%     0.00%  amfora   amfora                [.] 0x0000555f1b646d69                          ▒
    609 > +   54.87%     0.00%  amfora   amfora                [.] 0x0000555f1b64abf4                          ▒
    610 
    611 good thing perf works great with go binaries! /s
    612 
    613 maybe this is unfair; if I did the same for a real PL like haskell I'd get poor results too so I guess that's fine.
    614 
    615 ---
    616 
    617 go build -ldflags="-compressdwarf=false" -o amfora .
    618 perf record -F 99 -g -o perf.data ./amfora ~/count.gmi
    619 
    620 git clone https://github.com/brendangregg/FlameGraph
    621 perf script -i perf.data | ./FlameGraph/stackcollapse-perf.pl | ./FlameGraph/flamegraph.pl > amfora.svg
    622 
    623 /home/andrew/gitRepos/blog/posts/site/images/amfora-no-info.svg
    624 
    625 ---
    626 
    627 ok so there is some information here I guess. 
    628 
    629 so we see 70% of the time is spent by the GC, nice. 
    630 
    631 we then spend 25% of our computation opening the file and rendering it.
    632 
    633 This is mostly:
    634 
    635 RenderGemini: runtime.concatstring3
    636 
    637 file:///home/andrew/gitRepos/blog/posts/site/images/amfora-no-info.svg?s=render&x=25.9&y=613 (render gemini)
    638 
    639 concat string 3:
    640 
    641 24.34% of the 25.11% that is the rendergemini function.
    642 
    643 14.88% is runtime.memmove and 9.42% is runtime.concatstrings
    644 
    645 ---
    646 
    647 In the go code this is:
    648 
    649 renderer/renderer.go
    650 
    651 per their code comment:
    652 
    653 ```
    654 // RenderGemini converts text/gemini into a cview displayable format.
    655 // It also returns a slice of link URLs.
    656 //
    657 // width is the number of columns to wrap to.
    658 // leftMargin is the number of blank spaces to prepend to each line.
    659 //
    660 // proxied is whether the request is through the gemini:// scheme.
    661 // If it's not a gemini:// page, set this to true.
    662 ```
    663 
    664 the line that takes most of the actual computational time is this:
    665 
    666 
    667 ```
    668 buf += strings.TrimSuffix(lines[i], "\r") + "\r\n"
    669 ```
    670 
    671 what in the actual fuck?
    672 
    673 This is a O(n^2) op.... we yoink the current line and append it to the current line. 
    674 
    675 now in c++ this wouldn't be, but since go strings are immutable, this copies... them... every... single... fucking... time. 
    676 
    677 The fix is actually relatively simple: use a stringbuilder.
    678 
    679 the delta of 22 lines on my part (there is no pr for this because the project is unmaintained) is:
    680 
    681 go build -ldflags="-compressdwarf=false" -o amfora .
    682 perf record -F 99 -g -o perf.data ./amfora ~/count.gmi
    683 
    684 perf script -i perf.data | ./FlameGraph/stackcollapse-perf.pl | ./FlameGraph/flamegraph.pl > amfora.svg
    685 
    686 ~/gitRepos/blog/posts/site/images/amfora-fixed.svg
    687 
    688 ---
    689 
    690 sorry, flamegraphs are relative:
    691 
    692 from perf:
    693 
    694 (before): Event count (approx.): 262436801339
    695 (after): Event count (approx.): 5188060667
    696 
    697 >>> 5188060667 / 262436801339
    698 0.019768800109319945
    699 
    700 this now costs 1.98% of what it did before.... or in other words this is 50x fucking faster for "large" files of this shape. 
    701 
    702 https://github.com/makew0rld/amfora/pull/370
    703 
    704 Ok, I did create a pr for this. 
    705 
    706 ---
    707 
    708 I see, so it's not necessarily go that's slow, and it's not necessarily the GC, it's these  stupid fucking language decisions that bite people in the fucking ass. 
    709 
    710 Perhaps an aside, but it's so fucking annoying when imperative languages impose stupid fucking rules for no damn good reason. Like, it's not mathematically more correct to not mutate state in GO? In declarative / fp langs, I get it, in go? Fuck you.
    711 
    712 Admittedly, c++ has some annoying copy stuff where you'll accidentally copy stuff too often, passing by value some big ass thing, but I guess that's just something you learn, and in c++ you kinda can because that shit's fast as fuck, but like learn not to ig. 
    713 
    714 ---
    715 
    716 alright, let's stick to our own lane; no reason to compare with utter dogshit software. 
    717 
    718 ---
    719 
    720 perf record -g foreseen
    721 
    722 (normal usage for a few minutes)
    723 
    724 ---
    725 
    726 ok, so ~/gitRepos/blog/posts/site/images/foreseen-flamegraph-bench.svg?x=410.3&y=325
    727 
    728 33.77% of time is spent in u8width. 
    729 
    730 this is -Ofast
    731 
    732 Of the time spent in breaklines (45.61%), this makes up the bulk of it. 
    733 
    734 int u8width(const std::string& s, std::size_t i, int len) {
    735     std::mbstate_t st {};
    736     wchar_t wc;
    737     if (std::mbrtowc(&wc, s.data() + i, len, &st) != (std::size_t)len) {
    738         return 1;
    739     }
    740     int w = wcwidth(wc);
    741     if (w < 0) {
    742         return 0;
    743     }
    744     return w;
    745 }
    746 
    747 
    748 well this is kinda overkill because it's probably the case that most of our text is ascii, esp, in our benchmarks, but also in the realworld. So let's special case handle ascii first. 
    749 
    750 ```cpp
    751 unsigned char c = static_cast<unsigned char>(s[i]);
    752 if (len == 1 && c < 0x80) {
    753     return (c >= 0x20 && c != 0x7F) ? 1 : 0;
    754 }
    755 ```
    756 
    757 (we call sanitize characters to draw before this so there are no tabs)
    758 
    759 that's it, then the rest remains for utf-8. This skips the libc calls for ascii, while still being consistent, taking advantage of domain knowledge here to short-circuit computations.
    760 
    761 
    762 (after change)
    763 ```
    764 
    765 -------------------------------------------------------------------------------
    766 Benchmarking huge file scrolling
    767 -------------------------------------------------------------------------------
    768 benchmarking/render-bench.cpp:25
    769 ...............................................................................
    770 
    771 benchmark name                       samples       iterations    est run time
    772                                      mean          low mean      high mean
    773                                      std dev       low std dev   high std dev
    774 -------------------------------------------------------------------------------
    775 5 passes per iteration, 10m
    776 character file, load, scroll down
    777 1000x, scroll up 1000x with 100x100
    778 emulated terminal size                         100             1     2.09376 m
    779                                          1.29688 s     1.28467 s      1.3104 s
    780                                         65.4397 ms    57.5482 ms    75.5631 ms
    781 
    782 ```
    783 
    784 ~/gitRepos/blog/posts/site/images/flamegraph-shortcircuit.svg
    785 
    786 relative to before, we now spend only 21.84% of our time in this function, and only 3.27% of our total time is spent in the utf-8 encoding block, more than 10x less in terms of the portion of our time spent in that function.  that is across all benchmarks though (actually that was just small file + huge file), but just the huge file rendering we had this before:
    787 
    788 (before change)
    789 
    790 ```
    791 benchmark name                       samples       iterations    est run time
    792                                      mean          low mean      high mean
    793                                      std dev       low std dev   high std dev
    794 -------------------------------------------------------------------------------
    795 5 passes per iteration, 10m
    796 character file, load, scroll down
    797 1000x, scroll up 1000x with 100x100
    798 emulated terminal size                         100             1     2.92848 m
    799                                          1.91088 s      1.8952 s     1.93021 s
    800                                         89.0951 ms    71.0092 ms    113.665 ms
    801 ```
    802 
    803 so the one little, tiny, change for shortcircuiting ascii to avoid libc gives us ~47% better performance, on average... one tiny function. all of a flamegraph and a little domain consideration. 
    804 
    805 ---
    806 
    807 can it be faster? obviously, but at this point I'm pleased for large file usage and such. 
    808 
    809 ---
    810 
    811 productionizing:
    812 
    813 1. config files
    814     - utter dog shit
    815 2. editing source code
    816 3. cli arguments
    817 4. env varaibles
    818     - utter dog shit, it's so fucking annoying putting utter bullshit into my .bashrc / other sourced files
    819 
    820 editing source code + cli arguments it is. 
    821 
    822 
    823 ---
    824 
    825 I should've realized I was doing too many copies with cstr before:
    826 
    827 ```
    828 std::string cp = cstr;
    829 current.append(cp, x, len);
    830 ```
    831 
    832 with that perf is this:
    833 
    834 ```
    835 
    836 benchmark name                       samples       iterations    est run time
    837                                      mean          low mean      high mean
    838                                      std dev       low std dev   high std dev
    839 -------------------------------------------------------------------------------
    840 5 passes per iteration, 10m
    841 character file, load, scroll down
    842 1000x, scroll up 1000x with 100x100
    843 emulated terminal size                         100             1     2.02098 m
    844                                          1.27579 s     1.26486 s     1.29325 s
    845                                         69.2992 ms    48.4834 ms    101.668 ms
    846 
    847 ```
    848 
    849 
    850 after fix:
    851 
    852 ```
    853 benchmark name                       samples       iterations    est run time
    854                                      mean          low mean      high mean
    855                                      std dev       low std dev   high std dev
    856 -------------------------------------------------------------------------------
    857 5 passes per iteration, 10m
    858 character file, load, scroll down
    859 1000x, scroll up 1000x with 100x100
    860 emulated terminal size                         100             1     1.18109 m
    861                                         742.083 ms    736.293 ms    749.936 ms
    862                                          34.263 ms    25.8876 ms    47.0647 ms
    863 ```
    864 
    865 dang.
    866 
    867 ---
    868 
    869 argparse next
    870 
    871 done, easily.
    872 
    873 ---
    874 
    875