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