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 -> 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&) ▒</li> 190 <li>96.42% 0.00% bench1.out bench1.out [.] Catch::Benchmark::Detail::CompleteType<std::remove_reference<std::remove_cv<std▒</li> 191 <li>96.42% 0.00% bench1.out bench1.out [.] Catch::Benchmark::Detail::CompleteType<std::remove_reference<std::remove_cv<std▒</li> 192 <li>96.42% 0.00% bench1.out bench1.out [.] std::vector<std::chrono::duration<double, std::ratio<1l, 1000000000l> >, 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<std::is_same<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<std::pair<std::__cxx11::basic_string<char,▒</li> 197 <li>79.51% 3.76% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 198 <li>75.41% 9.64% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 199 <li>30.58% 7.91% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 200 <li>21.26% 11.97% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 201 <li>16.02% 6.88% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 202 <li>14.83% 4.53% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 203 <li>14.53% 7.35% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 204 <li>10.56% 7.06% bench1.out bench1.out [.] unsigned long const& std::min<unsigned long>(unsigned long const&, unsigned lon▒</li> 205 <li>8.21% 1.18% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 206 <li>8.02% 5.48% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 207 <li>6.70% 3.32% bench1.out bench1.out [.] std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >▒</li> 208 <li>6.69% 5.21% bench1.out bench1.out [.] std::char_traits<char>::assign(char&, char const&) ▒</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<std::pair<std::__cxx11::basic_string<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 -> 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& Catch::Benchmark::Benchmark::operator= 254 + 99.85% 0.00% bench1.out bench1.out [.] void Catch::Benchmark::Benchmark::run<std::chrono::_V2::steady_cloc 255 + 98.82% 0.00% bench1.out bench1.out [.] Catch::Benchmark::Detail::BenchmarkFunction::model<CATCH2_INTERNAL_ 256 + 98.82% 0.00% bench1.out bench1.out [.] Catch::Benchmark::Detail::BenchmarkFunction::model<CATCH2_INTERNAL_ 257 + 98.82% 0.00% bench1.out bench1.out [.] void Catch::Benchmark::Chronometer::measure<CATCH2_INTERNAL_TEST_0( 258 + 98.82% 0.00% bench1.out bench1.out [.] void Catch::Benchmark::Chronometer::measure<CATCH2_INTERNAL_TEST_0( 259 + 98.82% 0.00% bench1.out bench1.out [.] std::enable_if<std::is_same<void, decltype ({parm#1}({parm#2}...))> 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<std::remove_reference<std::r 262 + 97.91% 0.00% bench1.out bench1.out [.] Catch::Benchmark::Detail::CompleteType<std::remove_reference<std::r 263 + 97.91% 0.00% bench1.out bench1.out [.] std::vector<std::chrono::duration<double, std::ratio<1l, 1000000000 264 + 97.91% 0.00% bench1.out bench1.out [.] Catch::Benchmark::Benchmark::run<std::chrono::_V2::steady_clock>(): 265 + 97.91% 0.00% bench1.out bench1.out [.] std::enable_if<std::is_same<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&, Browser&, int, int, int) 268 + 80.38% 0.06% bench1.out bench1.out [.] draw(DrawState&) 269 + 61.79% 4.26% bench1.out bench1.out [.] breakLines(std::vector<std::pair<std::__cxx11::basic_string<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<char, std::char_traits 272 + 17.20% 0.00% bench1.out bench1.out [.] tryVisitSite(DrawState&, Browser&, std::__cxx11::basic_string<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<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, TextRender>, 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<std::pair<std::string, TextRender>> breakLines(std::vector<std::pair<std::string, TextRender>>& strLs, int width, int cols) { 278 279 std::vector<std::pair<std::string, TextRender>> res {}; 280 281 int leftPadAmount = std::max(0, (cols - width) / 2); 282 std::string leftPadStr (leftPadAmount, ' '); 283 284 if(width <= 0) { 285 return res; 286 } 287 288 for(std::size_t i = 0; i < 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 < 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 > limit) { 300 break; 301 } 302 w += cw; 303 end += len; 304 } 305 cstr = cstr.substr(0, end); // otherwise there's some funkiness at the end due to how ncurses renders stuff. 306 res.push_back(std::pair<std::string,TextRender> {leftPadStr + cstr, strLs[i].second}); 307 continue; 308 } 309 310 std::string current = ""; 311 int curWidth = 0; 312 int lastSpace = -1; 313 int lastSpaceWidth = 0; 314 315 for(int x = 0; x < (int)cstr.size(); ) { 316 if(cstr[x] == '\n') { 317 res.push_back(std::pair<std::string,TextRender> {leftPadStr + current, strLs[i].second}); 318 current = ""; 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 > 0 && curWidth > 0 && curWidth + w > 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 = ""; 338 curWidth = 0; 339 } 340 341 res.push_back(std::pair<std::string,TextRender> {leftPadStr + toPush,strLs[i].second}); 342 lastSpace = -1; 343 } 344 345 current.append(cstr, x, len); 346 curWidth += w; 347 if(cstr[x] == ' ') { 348 lastSpace = current.size() - 1; 349 lastSpaceWidth = curWidth; 350 } 351 x += len; 352 } 353 if(current.size() > 0) { 354 res.push_back(std::pair<std::string,TextRender> {leftPadStr + current,strLs[i].second}); 355 current = ""; 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& cstr = strLs[i].first;</code></pre> 367 <p>if we look at sanitize characters,</p> 368 <p>```void sanitizeCharactersToDraw(std::vector<std::pair<std::string, TextRender>>& strLs) { for(std::size_t i = 0; i < strLs.size(); ++i) {</p> 369 <pre><code> std::string& s = strLs[i].first; 370 371 std::string out; 372 for (int c: s) 373 if (c == '\r' || c == '\v' || c == '\b' || c == '\f' || c == '\a' || c == '\0') { 374 continue; 375 } else if (c == '\t') { 376 out += " "; // \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't be special, it's relatively safe to just do: 389 </code></pre> 390 <p>out.reserve(s.size());</p> 391 <pre><code> 392 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. 393 394 395 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. 396 </code></pre> 397 <p>void operate(std::vector<std::pair<std::string, TextRender>>& strLs, std::size_t idxStart, std::size_t idxStop) { for(std::size_t i = idxStart; i < idxStop; ++i) { std::string& s = strLs[i].first; std::string out; out.reserve(s.size());</p> 398 <pre><code> for (int c : s) 399 if (c == '\r' || c == '\v' || c == '\b' || c == '\f' || c == '\a' || c == '\0') { 400 continue; 401 } else if (c == '\t') { 402 out += " "; // \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<std::pair<std::string, TextRender>>& strLs) { std::vector<std::thread> threads{};</p> 412 <pre><code>if(strLs.size() > 100) { 413 for(int i = 0; i < 10; ++i) { 414 threads.emplace_back(&operate, std::ref(strLs), i*strLs.size() / 10, (i+1)*strLs.size() / 10); 415 } 416 for(auto& 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's a more data-oriented-design thing. 437 438 439 --- 440 441 let's stop and compare olevels for this now. I'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'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. 483 484 485 amfora ~2MB file: 77MB 486 amfora ~2MB file: 39MB 487 488 get a recording of this shit because it's fucking pathetic. 489 490 we'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'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's get to it. 510 511 --- 512 513 Ok, so let'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 (>1MB), so what's that about? 518 519 I mean, it compiles quickly which is nice, but it'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 <=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't even matter. 530 531 > + 99.23% 0.00% amfora amfora [.] 0x0000555f1b69fb41 ◆ 532 > + 68.33% 0.00% amfora amfora [.] 0x0000555f1b69db67 ▒ 533 > + 61.24% 0.00% amfora amfora [.] 0x0000555f1b646b45 ▒ 534 > + 60.22% 0.00% amfora amfora [.] 0x0000555f1b646d69 ▒ 535 > + 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'd get poor results too so I guess that's fine. 540 541 --- 542 543 go build -ldflags="-compressdwarf=false" -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 > 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&x=25.9&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'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="-compressdwarf=false" -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 > 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 >>> 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 "large" 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'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. 624 625 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. 626 627 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. 628 629 --- 630 631 alright, let'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&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& s, std::size_t i, int len) { 650 std::mbstate_t st {}; 651 wchar_t wc; 652 if (std::mbrtowc(&wc, s.data() + i, len, &st) != (std::size_t)len) { 653 return 1; 654 } 655 int w = wcwidth(wc); 656 if (w < 0) { 657 return 0; 658 } 659 return w; 660 } 661 662 663 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. 664 665 ```cpp 666 unsigned char c = static_cast<unsigned char>(s[i]); 667 if (len == 1 && c < 0x80) { 668 return (c >= 0x20 && 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>