blog

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

a-gemini-browser.html (38775B)


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