blog

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

abg.md (26781B)


      1 # Notes
      2 
      3 Originally, I was going to post something called "to make a cool background", but realized the pygame / raylib findings were more interesting. I'll probably add some of this information into a subsequent post.
      4 
      5 # abg
      6 
      7 this is associated with the preliminary post titled: "to make a cool background"
      8 
      9 # To Make a Cool Background
     10 
     11 I wrote a visualization program for prim's algorithm that induces a minimum spanning tree (MST) on a procedurally generated graph. How does one go about making this their background and screensaver with X11 / dwm?
     12 
     13 ## MST
     14 
     15 IMPLEMENTATION DETAILS
     16 
     17 ## Background making
     18 
     19 [https://github.com/python-xlib/python-xlib](https://github.com/python-xlib/python-xlib.md)
     20 
     21 ```python3
     22 os.environ["SDL_VIDEODRIVER"] = "dummy"
     23 ```
     24 
     25 why not just use screenshots in a shared location? 
     26 
     27 indeed, why not?
     28 
     29 ## fuck you and your bullshit.
     30 
     31 Benchmarking
     32 
     33 ## c -> c++
     34 
     35 realized I needed a heap.
     36 
     37 ## bmp vs png vs jpg
     38 
     39 bmp is crazy fucking fast (benchmark)
     40 
     41 (looked in the code for supported file formats, looked in feh -> lib(whatever) for support)
     42 
     43 note larger file size.
     44 
     45 this is interesting, look further.
     46 
     47 ### patched upstream xl
     48 
     49 ### x11
     50 
     51 x11 is weird with this because they are kind hacky in that they just put up a window and take away your inputs, forcing them to go to that window.
     52 
     53 (should learn more about this)
     54 
     55 ### Benchmarking
     56 
     57 uhhh... is it actually that fast?
     58 
     59 wait; did this just optimize all of my code?
     60 
     61 Well yes, but actually no. 
     62 
     63 adding:
     64 
     65 std::cout << g.toString() << std::endl;
     66 
     67 gives ~ the same perf (minus the amount of time it takes to send so much data to stdout)
     68 
     69 (this would require the full traversal because toString is dependent upon prior prim algo steps being performed otherwise the traversal status for edges and vertices would be incorrect).
     70 
     71 (fixed a bug in the python code slowing it down)
     72 
     73 see no_render_2_fixed_itr.
     74 
     75 ## C++ benchmarking
     76 
     77 330 ms for init stuff w/ graph
     78 1405 ms for iteration
     79 
     80 broken further down:
     81 
     82 average iteration time is ~0ms, reaching ~20ms for later stages. Over time the percentage of valid edges declines.
     83 
     84 added getUnvisitedEdges function to return only non-traversed edges
     85 
     86 Init time: 332
     87 Loop time: 1344
     88 Init time: 327
     89 Loop time: 1350
     90 Init time: 322
     91 Loop time: 1374
     92 
     93 still has a similar issue as before; degredation in perf towards the end bc things are pushed earlier on and then get invalidated later on.
     94 
     95 that's basically all I could squeeze out without changes to the algo to be eager instead of lazy wrt tracking vertices. Basically, what's the shortest distance to a given vertex instead of what's the edge that we have that's shortest. 
     96 
     97 such a refactor though is likely irrelevant right now due to the added cost of 
     98 
     99 ope; realized my function for get edges with unvisited vertices above was wrong. I was just not pushing visited edges, but we really care about vertices that haven't been visited so refactored the edge generation and stuff to get a stable ref to v2index and then push only if that hasn't been visited.
    100 
    101 Init time: 389
    102 Loop time: 706
    103 Init time: 315
    104 Loop time: 671
    105 Init time: 337
    106 Loop time: 692
    107 
    108 now we're cooking with gas.
    109 
    110 tests now fail. bc snapshots. updated and everything seems right again.
    111 
    112 actually the stable things isn't really necessary as this approach that's unstable is functionally the same, but safer in case there are changes to the IR of edges.
    113 
    114 Init time: 334
    115 Loop time: 694
    116 Init time: 321
    117 Loop time: 668
    118 Init time: 323
    119 Loop time: 701
    120 
    121 now we find this:
    122 
    123 (see benchmarking/no_render_v_100000_e_1000000_s_0/out1.csv)
    124 
    125 same optimization performed for python code so that's then down to 8.6 seconds ~~~ see andrew@deepthought:no_render_3_fixed_itr_fixed_check$
    126 
    127 at this point it's worth worrying about the return for the get untraversed edges for vertices not traversed. after that:
    128 
    129 Init time: 314
    130 Loop time: 678
    131 Init time: 312
    132 Loop time: 671
    133 Init time: 311
    134 Loop time: 680
    135 
    136 and with the optimization for edge ordering:
    137 
    138 Init time: 311
    139 Loop time: 659
    140 Init time: 333
    141 Loop time: 673
    142 Init time: 320
    143 Loop time: 709
    144 Init time: 311
    145 Loop time: 674
    146 
    147 this is still too fucking slow.
    148 
    149 what's making the graph induction so incredibly slow?
    150 
    151 just graph creation:
    152 
    153 graph create: 317
    154 Loop time: 691
    155 graph create: 314
    156 Loop time: 657
    157 graph create: 311
    158 Loop time: 665
    159 
    160 reserving instead of pushing:
    161 
    162 graph create: 314
    163 Loop time: 636
    164 graph create: 324
    165 Loop time: 688
    166 graph create: 315
    167 Loop time: 693
    168 
    169 replaced map with vector where we were using indices to index into the map (dumb):
    170 
    171 graph create: 174
    172 Loop time: 654
    173 graph create: 179
    174 Loop time: 610
    175 graph create: 184
    176 Loop time: 618
    177 graph create: 185
    178 Loop time: 622
    179 
    180 ok, let's now run the full benchmarks again:
    181 
    182 benchmarking/no_render_only_grab_unvisited_edges_vector_instead_of_map_v_100000_e_1000000_s_0/out1.csv
    183 
    184 0.04,0.79,0.84
    185 0.03,0.79,0.84
    186 0.04,0.77,0.82
    187 
    188 this was kind of just stalling though becaus I'm out of my depth as it relates to rendering, the larger perf issue.
    189 
    190 back to that. 
    191 
    192 here are where this stands w/ 1000 v and 10_000 edges
    193 
    194 prior was ~34s per iteration (final col)
    195 
    196 this is basically the same:
    197 
    198 benchmarking/better_render_v_1000_e_10000_s_0/out1.csv
    199 
    200 (snippet from above file)
    201 
    202 0.26,10.71,34.22
    203 0.29,10.64,33.24
    204 0.31,10.62,33.57
    205 0.28,10.53,33.56
    206 
    207 fine. we'll fix the raylib shit. (queue montage)
    208 
    209 make debug-build && time ./abg.out -s 0 --edges 2000 --vertices 200
    210 
    211 real    0m1.948s
    212 user    0m0.529s
    213 sys     0m0.060s
    214 
    215 ~20 milliseconds per render call w/ make debug-build && time ./abg.out -s 0 --edges 20000 --vertices 2000
    216 
    217 Total single iteration cost: 65
    218 Amount of time calling render: 18
    219 Total single iteration cost: 65
    220 Amount of time calling render: 18
    221 Total single iteration cost: 65
    222 Amount of time calling render: 18
    223 Total single iteration cost: 65
    224 Amount of time calling render: 18
    225 Total single iteration cost: 65
    226 Amount of time calling render: 19
    227 Total single iteration cost: 65
    228 Amount of time calling render: 18
    229 Total single iteration cost: 65
    230 Amount of time calling render: 18
    231 Total single iteration cost: 65
    232 
    233 huh; what's the other iteration cost?
    234 
    235 
    236     while (!WindowShouldClose() && toVisit.size() != 0) {
    237         auto startLoop = std::chrono::steady_clock::now();
    238         BeginDrawing();
    239         ClearBackground(BLACK);
    240         auto startRender = std::chrono::steady_clock::now();
    241         g.render();
    242         auto endRender = std::chrono::steady_clock::now();
    243         auto diff = std::chrono::duration_cast<std::chrono::milliseconds>(endRender - startRender);
    244         std::cout << "Amount of time calling render: " << diff.count() << std::endl;
    245         EndDrawing();
    246 
    247         // since we wait sleepTime here, the bg render has a render delta of
    248         // at minimum sleepTime when switching tags in dwm, this is rather
    249         // annoying because the screen doesn't repaint until the sleep time
    250         // passes, which results in artifacts on screen.
    251 
    252         // despite this, calling render a lot of times is rather intensive
    253         // (at least on my hardware) and so this tradeoff is accepted for
    254         // now, unless there's a simple approach that allows for preemption
    255 
    256         //usleep((int)(sleepTime * 1000000));
    257 
    258         oneStepPrim(toVisit, visitedIndices, g);
    259         auto endLoop = std::chrono::steady_clock::now();
    260         auto loopDiff = std::chrono::duration_cast<std::chrono::milliseconds>(endLoop - startLoop);
    261         std::cout << "Total single iteration cost: " << loopDiff.count() << std::endl;
    262 
    263     }
    264 
    265 so it's somewhere in that first block; in the render area. the actual computation cost at the end is inconsequential. 
    266 
    267 begindrawing is ~free.
    268 
    269 clear background is ~free.
    270 
    271 ~46 of 65ms are spent on enddrawing. 
    272 
    273 so two things:
    274 
    275 19ms on render
    276 46ms on enddrawing
    277 
    278 what about when the numbers are much bigger (100_000 edges, 10_000 vertices)?
    279 
    280 Render time: 56
    281 End Drawing time: 237
    282 Total single iteration cost: 316
    283 
    284 the other 23 ms is the prim step + begin drawing / clear background.
    285 
    286 can we just not clear the screen? does that help? nope. doesn't do anything.
    287 
    288 target 60 fps?
    289 
    290 nope.
    291 
    292 ahh; the slowness is being realized later on. while render is cool with me double calling on edges; this is felt when enddrawing is called as the gpu does the rendering and stuff at that point. 
    293 
    294 what happens if I use the better single time render method?
    295 
    296 before:
    297 
    298 Render time: 62
    299 End Drawing time: 244
    300 Total single iteration cost: 306
    301 Render time: 60
    302 End Drawing time: 245
    303 Total single iteration cost: 305
    304 Render time: 60
    305 End Drawing time: 245
    306 Total single iteration cost: 305
    307 Render time: 55
    308 End Drawing time: 252
    309 Total single iteration cost: 307
    310 Render time: 60
    311 End Drawing time: 245
    312 Total single iteration cost: 305
    313 Render time: 58
    314 End Drawing time: 247
    315 Total single iteration cost: 306
    316 
    317 after:
    318 
    319 Total single iteration cost: 158
    320 Render time: 46
    321 End Drawing time: 112
    322 Total single iteration cost: 159
    323 Render time: 46
    324 End Drawing time: 112
    325 Total single iteration cost: 159
    326 Render time: 45
    327 End Drawing time: 113
    328 Total single iteration cost: 159
    329 Render time: 46
    330 End Drawing time: 111
    331 Total single iteration cost: 158
    332 Render time: 46
    333 End Drawing time: 112
    334 Total single iteration cost: 158
    335 Render time: 46
    336 End Drawing time: 113
    337 
    338 hell yeah.
    339 
    340 why so slow still?
    341 
    342 Like this is only ~100_000 and ~10_000 vertices so like why so slow?
    343 
    344 benchmarked now:
    345 
    346 benchmarking/simpler_render_v_1000_e_10000_s_0/out1.csv
    347 0.29,7.77,18.96
    348 0.27,7.80,19.17
    349 0.29,7.90,19.17
    350 0.31,7.76,19.05
    351 0.29,7.72,18.68
    352 0.30,7.90,18.56
    353 0.27,7.78,18.80
    354 0.27,7.77,18.74
    355 0.29,7.69,18.77
    356 0.32,7.67,18.85
    357 
    358 alright then. unfortunately, we're only calling the draw function once per vertex and edge now. we could change the rendering to only render connections, this would increase speed a lot, but it also makes the animation look less cool so fuck that. 
    359 
    360 could we draw in the background? like create a new thread that doesn't block us and then wait until that's done once we get back?
    361 
    362 well maybe, but the issue is I don't know how well this handles drawing while there's a queue of messages still being sent. 
    363 
    364 std::thread t(endDrawing);
    365 t.join();
    366 
    367 vs endDrawing()
    368 
    369 result in entirely different outcomes.
    370 
    371 the second sort of renders some stuff, but gets totally fucked up and then just black screens.
    372 
    373 due to an import? no this shit's just fucked.
    374 
    375 opengl affinity.
    376 
    377 can prebake the graph though and then only render additions.
    378 
    379 after:
    380 
    381 0.19,1.77,3.86
    382 0.17,1.76,3.81
    383 0.19,1.76,3.82
    384 0.18,1.75,3.85
    385 0.18,1.71,3.86
    386 0.19,1.68,3.83
    387 0.18,1.72,3.83
    388 
    389 holy shit. can we make this faster?
    390 
    391 of fucking course we can. track if a traversed state has been rendered and skip it if it has, using this to update our incremental texture. we then render that. 
    392 
    393 benchmarking/cache_first_use_blank_graph_v_1000_e_10000_s_0/out1.csv
    394 
    395 0.17,0.65,3.06
    396 0.18,0.63,3.05
    397 0.18,0.66,3.05
    398 0.18,0.64,3.05
    399 0.18,0.64,3.04
    400 0.17,0.63,3.02
    401 0.18,0.62,3.04
    402 0.19,0.64,3.05
    403 0.17,0.65,3.04
    404 0.17,0.66,3.03
    405 0.18,0.62,3.04
    406 0.17,0.63,3.03
    407 
    408 this is too boring; let's turn this shit up.
    409 
    410 how fast are we relative to the python bloatware webshit?
    411 
    412 benchmarking/cache_first_use_blank_graph_v_10000_e_100000_s_0/out1.csv
    413 
    414 1.40,28.92,35.76
    415 1.53,29.30,35.95
    416 
    417 (notice the edges and vertices)
    418 
    419 vs python:
    420 
    421 1.33,10730.71,10772.74
    422 
    423 that's only >300x slower for the python code so the average python developer would totally be cool with shipping it. Job done, webshit: built. 
    424 
    425 alright then. enough messing around. We really should have a queue for items that are to be rendered so we don't have to iterate over all vertices and edges, checking if they have the 'rendered' flag set. 
    426 
    427 after doing this we find:
    428 
    429 benchmarking/track_to_render_v_10000_e_100000_s_0/out1.csv
    430 
    431 1.50,3.12,29.43
    432 1.51,3.20,29.67
    433 1.57,3.08,30.00
    434 1.57,3.04,30.07
    435 
    436 35.855000000000004 / 29.7925 = 1.2034908114458338
    437 
    438 okay, so 20 percent faster. still too fucking slow.
    439 
    440 i'm also getting sick of this bs chrono / time shit. time to bring in perf.
    441 
    442  3.20%           395  abg.out  libraylib.so.6.0.0            [.] rlVertex3f
    443  2.08%           338  abg.out  abg.out                       [.] Edge::operator>(Edge const&) const
    444  1.55%           245  abg.out  abg.out                       [.] oneStepPrim(std::priority_queue<Edge, std::vector<Edge, st>
    445  1.41%           255  abg.out  libraylib.so.6.0.0            [.] rlDrawRenderBatch
    446  1.22%           225  abg.out  libc.so.6                     [.] 0x0000000000185dde
    447  0.85%           129  abg.out  libraylib.so.6.0.0            [.] DrawCircleSector
    448  0.79%           136  abg.out  libc.so.6                     [.] pthread_mutex_lock
    449  0.74%           133  abg.out  libc.so.6                     [.] ioctl
    450  0.64%           115  abg.out  libgallium-26.2.2-arch1.1.so  [.] 0x00000000007f8138
    451  0.62%           113  abg.out  libraylib.so.6.0.0            [.] PollInputEvents
    452  0.57%            91  abg.out  libc.so.6                     [.] cfree
    453  0.56%            95  abg.out  libc.so.6                     [.] malloc
    454  0.54%            27  abg.out  libc.so.6                     [.] 0x00000000001866c9
    455  0.53%            99  abg.out  libgallium-26.2.2-arch1.1.so  [.] 0x000000000180c45c
    456 
    457 alright so raylib is spending a decent amount of time on Vertex3f though not a crazy amount. Comparisons between edges are common; not surprising as we are using a heap with lots of elements towards the end, as we've seen. prim's algorithm generally taking some time, makes sense.
    458 
    459 render drawing is rather low, but within reason. This is rather disappointing. It's nice when it's like, no, dude, you spent 99.95% of your time in one function. 
    460 
    461 looking at the call stack:
    462 
    463 |--14.80%--EndTextureMode
    464 |--58.02%--EndDrawing
    465 --1.62%--Graph::render()
    466 
    467 well. huh. end texture mode is where I add things though the function itself is just clearing the queue. 
    468 
    469 It's a bit surprising enddrawing is more expensive since it just loads in the texture I've baked. 
    470 
    471 ---
    472 
    473 I shall call this ~done. final findings with 
    474 
    475 rendered below is using     vertices = 10_000, edges = 100_000
    476 
    477 unrendered below is using   vertices = 200_000, edges = 2_000_000 
    478 
    479 - python (with overdraw mostly fixing + texture map)
    480     - rendered 
    481         - 58.758 seconds
    482     - unrendered
    483         - 20.253333333333334 seconds
    484 
    485 - c++ (with overdraw fixing + texture map)
    486     - rendered
    487         - - 29.7925 seconds
    488 
    489     - unrendered
    490         - 2.118 seconds
    491 
    492 
    493 benchmarking/final_no_render_v_200000_e_2000000_s_0/
    494 
    495 takeaway:
    496 
    497 the rendered python implementation w/ 10_000 v and 100_000 edges using perf:
    498 
    499 Performance counter stats for 'python3 prim.py':
    500 
    501                  0      context-switches:u               #      0.0 cs/sec  cs_per_second
    502                  0      cpu-migrations:u                 #      0.0 migrations/sec  migrations_per_second
    503             14,233      page-faults:u                    #    252.0 faults/sec  page_faults_per_second
    504          56,487.57 msec task-clock:u                     #      nan CPUs  CPUs_utilized
    505         30,763,483      branch-misses:u                  #      0.7 %  branch_miss_rate         (88.90%)
    506      4,305,442,939      branches:u                       #     76.2 M/sec  branch_frequency     (88.90%)
    507    128,137,043,750      cpu-cycles:u                     #      2.3 GHz  cycles_frequency       (88.90%)
    508     18,736,054,409      instructions:u                   #      0.1 instructions  insn_per_cycle  (88.85%)
    509             TopdownL1 #      0.1 %  tma_backend_bound
    510                                                          #     98.9 %  tma_bad_speculation      (88.87%)
    511                                                          #      0.5 %  tma_frontend_bound       (77.81%)
    512                                                          #      0.5 %  tma_retiring             (88.92%)
    513 
    514       59.936596362 seconds time elapsed
    515 
    516       52.628026000 seconds user
    517        1.492521000 seconds sys
    518 
    519 gpu constrained though. 
    520 
    521 the rendered c++ implementation w/ 10_000 v and 100_000 edges using perf:
    522 
    523  Performance counter stats for './abg.out -s 0 --vertices 10000 --edges 100000':
    524 
    525                  0      context-switches:u               #      0.0 cs/sec  cs_per_second
    526                  0      cpu-migrations:u                 #      0.0 migrations/sec  migrations_per_second
    527              9,363      page-faults:u                    #   1819.4 faults/sec  page_faults_per_second
    528           5,146.21 msec task-clock:u                     #      nan CPUs  CPUs_utilized
    529         28,144,835      branch-misses:u                  #      5.9 %  branch_miss_rate         (89.55%)
    530        473,319,266      branches:u                       #     92.0 M/sec  branch_frequency     (88.64%)
    531      3,973,233,282      cpu-cycles:u                     #      0.8 GHz  cycles_frequency       (88.55%)
    532      2,925,854,560      instructions:u                   #      0.7 instructions  insn_per_cycle  (89.12%)
    533             TopdownL1 #      2.7 %  tma_backend_bound
    534                                                          #     93.6 %  tma_bad_speculation      (88.66%)
    535                                                          #      0.9 %  tma_frontend_bound       (77.75%)
    536                                                          #      2.8 %  tma_retiring             (88.67%)
    537 
    538       29.577542431 seconds time elapsed
    539 
    540        2.925597000 seconds user
    541        2.094917000 seconds sys
    542 
    543 32x less instructions than the python version. Neither is cpu constrained, but this is a non-trivial amount of overhead from the python version; c++ version also had 7x higher instructions per cycle. 
    544 
    545 gpu constrained too.
    546 
    547 memory overhead?
    548 
    549 c++ rendered sits at ~171mb-175mb. it's not great, hasn't been optimized, def room for improvement. 
    550 
    551 python rendered sits at ~240mb-248mb
    552 
    553 the default invocation method for the c++ implementation I use as my lock screen is running at 160mb. This is rather annoying, but also, it's doing a bunch of rendering stuff so IG that's fine, and this does improve the computational cost in terms of cycles so...
    554 
    555 huh... after 2 hours it's chilling at 163mb (TODO).
    556 
    557 bc it's always holding onto at least one frame which is 5120x1440 pixels which is ~21mb minimum (assuming r g and b bytes per pixel.)
    558 
    559 an eager approach for this would be better, but c++ stl doesn't have an indexed priority queue, so I'll just retcon what I have. 
    560 
    561 basically, I just want to minimize the useless things I push to the queue. One way to do this is to track the minimum weighted edge with an untraversed vertex and then updating this and only pushing edges with it when they are < that weight. 
    562 
    563 before:
    564 
    565 benchmarking/final_no_render_v_200000_e_2000000_s_0/
    566 
    567 0.08,2.03,2.12
    568 0.09,2.02,2.12
    569 0.09,2.00,2.11
    570 0.09,2.00,2.11
    571 0.08,1.99,2.09
    572 0.07,1.99,2.08
    573 0.10,2.00,2.11
    574 0.09,2.00,2.11
    575 0.09,2.07,2.18
    576 0.06,2.08,2.15
    577 
    578 
    579 after:
    580 
    581 benchmarking/final_min_no_render_v_200000_e_2000000_s_0/out.csv
    582 
    583 0.06,0.97,1.04
    584 0.06,0.93,1.00
    585 0.07,0.95,1.03
    586 0.09,0.92,1.02
    587 0.08,0.94,1.02
    588 0.08,0.94,1.03
    589 0.08,0.94,1.03
    590 0.06,0.95,1.02
    591 0.08,0.93,1.02
    592 0.07,0.95,1.02
    593 0.07,0.95,1.03
    594 0.07,0.95,1.03
    595 0.08,0.95,1.04
    596 0.09,0.93,1.03
    597 0.07,0.98,1.06
    598 0.07,0.95,1.04
    599 0.08,0.94,1.03
    600 0.07,0.96,1.04
    601 0.07,0.95,1.04
    602 0.07,1.00,1.08
    603 
    604 this doesn't really impact time wrt rendered because that is basically all spent on rendering not computation. 
    605 
    606 do I have a memory leak?
    607 
    608 
    609 
    610 > time valgrind --tool=memcheck abg
    611 
    612 ==944657== Process terminating with default action of signal 2 (SIGINT)
    613 ==944657==    at 0x50D3952: __syscall_cancel_arch (syscall_cancel.S:56)
    614 ==944657==    by 0x5117AEC: internal_syscall_cancel (sysdep-cancel.h:53)
    615 ==944657==    by 0x5117AEC: clock_nanosleep@@GLIBC_2.17 (clock_nanosleep.c:48)
    616 ==944657==    by 0x5123F26: nanosleep (nanosleep.c:25)
    617 ==944657==    by 0x51532E9: usleep (usleep.c:31)
    618 ==944657==    by 0x40065B8: main (in /usr/local/bin/abg)
    619 ==944657==
    620 ==944657== HEAP SUMMARY:
    621 ==944657==     in use at exit: 11,776,171 bytes in 27,368 blocks
    622 ==944657==   total heap usage: 86,922 allocs, 59,554 frees, 29,848,973 bytes allocated
    623 ==944657==
    624 ==944657== LEAK SUMMARY:
    625 ==944657==    definitely lost: 0 bytes in 0 blocks
    626 ==944657==    indirectly lost: 0 bytes in 0 blocks
    627 ==944657==      possibly lost: 6,876,540 bytes in 3,237 blocks
    628 ==944657==    still reachable: 4,899,631 bytes in 24,131 blocks
    629 ==944657==         suppressed: 0 bytes in 0 blocks
    630 ==944657== Rerun with --leak-check=full to see details of leaked memory
    631 ==944657==
    632 ==944657== For lists of detected and suppressed errors, rerun with: -s
    633 ==944657== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
    634 
    635 
    636 real    12m18.560s
    637 user    0m23.848s
    638 sys     0m0.969s
    639 
    640 andrew@deepthought:~$ time valgrind --tool=memcheck abg
    641 ==947393== Memcheck, a memory error detector
    642 ==947393== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al.
    643 ==947393== Using Valgrind-3.25.1 and LibVEX; rerun with -h for copyright info
    644 ==947393== Command: abg
    645 ==947393==
    646 ^C==947393==
    647 ==947393== Process terminating with default action of signal 2 (SIGINT)
    648 ==947393==    at 0x50D3952: __syscall_cancel_arch (syscall_cancel.S:56)
    649 ==947393==    by 0x5117AEC: internal_syscall_cancel (sysdep-cancel.h:53)
    650 ==947393==    by 0x5117AEC: clock_nanosleep@@GLIBC_2.17 (clock_nanosleep.c:48)
    651 ==947393==    by 0x5123F26: nanosleep (nanosleep.c:25)
    652 ==947393==    by 0x51532E9: usleep (usleep.c:31)
    653 ==947393==    by 0x40065B8: main (in /usr/local/bin/abg)
    654 ==947393==
    655 ==947393== HEAP SUMMARY:
    656 ==947393==     in use at exit: 11,656,499 bytes in 27,404 blocks
    657 ==947393==   total heap usage: 64,820 allocs, 37,416 frees, 24,650,054 bytes allocated
    658 ==947393==
    659 ==947393== LEAK SUMMARY:
    660 ==947393==    definitely lost: 0 bytes in 0 blocks
    661 ==947393==    indirectly lost: 0 bytes in 0 blocks
    662 ==947393==      possibly lost: 6,744,916 bytes in 3,235 blocks
    663 ==947393==    still reachable: 4,911,583 bytes in 24,169 blocks
    664 ==947393==         suppressed: 0 bytes in 0 blocks
    665 ==947393== Rerun with --leak-check=full to see details of leaked memory
    666 ==947393==
    667 ==947393== For lists of detected and suppressed errors, rerun with: -s
    668 ==947393== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
    669 
    670 
    671 real    0m53.077s
    672 user    0m20.121s
    673 sys     0m0.750s
    674 
    675 andrew@deepthought:~$ time valgrind --leak-check=full --tool=memcheck abg -s 0
    676 
    677 ==948338==
    678 ==948338== LEAK SUMMARY:
    679 ==948338==    definitely lost: 0 bytes in 0 blocks
    680 ==948338==    indirectly lost: 0 bytes in 0 blocks
    681 ==948338==      possibly lost: 6,948,380 bytes in 3,271 blocks
    682 ==948338==    still reachable: 4,899,399 bytes in 24,179 blocks
    683 ==948338==         suppressed: 0 bytes in 0 blocks
    684 ==948338== Reachable blocks (those to which a pointer was found) are not shown.
    685 ==948338== To see them, rerun with: --leak-check=full --show-leak-kinds=all
    686 ==948338==
    687 ==948338== For lists of detected and suppressed errors, rerun with: -s
    688 ==948338== ERROR SUMMARY: 2838 errors from 2838 contexts (suppressed: 0 from 0)
    689 
    690 
    691 real    21m9.471s
    692 user    19m30.601s
    693 sys     1m12.207s
    694 
    695 seems like this was just me not closing the window. fixed that.
    696 
    697 ---
    698 
    699 profiling:
    700 
    701 start: 121mb (time 5:15pm after running for ~a minute)
    702 check-in: 121mb (time 8:55pm) -- this is just the default `abg` cmd so not a ton of churn
    703 stopped: 121mb (9:11pm)
    704 
    705 running again w/ s=0:
    706 
    707 ---
    708 
    709 (recompile)
    710 
    711 start: 123mb (time 9:13pm)
    712 end: 123mb (time: 11:00pm)
    713 
    714 ---
    715 
    716 seems good; calling it here. further refactors can be done that'd improve perf, mostly be improving cache utilization by removing unnecessary bits. This is what I'd say:
    717 
    718 - It's unlikely there's an optimization for my hardware that'd improve performance by 2x
    719 - It's unlikely there's an optimization for my hardware that'd improve performance by 5x across the workloads I've evaluated. There are ways to make prim's algorithm much faster on much larger graphs, but given what I care about, this is likely inconsequential.
    720 - These further optimizations are probably not worth it
    721     - They could make this faster but two things:
    722         1. They would decrease code readability and extensibility a non-trivial amount
    723             - sometimes worth it
    724         2. The improvements wouldn't be meaningful for average usage
    725             - most ppl will be draw constrained. I believe I'm close to what is optimal as it relates to using raylib, without diving straight into opengl
    726 
    727 
    728 ---
    729 
    730 Pygame vs raylib:
    731 
    732 - Not a super great comparison
    733 - SDL (pygame) will basically always be slower than opengl (raylib)
    734 
    735 ---
    736 
    737 okay, so, this is a comparison between pygame, rlib w/ python, rlib from c++:
    738 
    739 these are all only rendering deltas, using a texture with rlib, and just doing incremental writes with pygame (functionally the same amount of computation)
    740 
    741 
    742 each is running one iteration of prim, rendering each step, with 100000 edges and 10000 vertices
    743 
    744 (kept each render in the foreground as that makes it slower, disabled picom)
    745 
    746 sleep 1 for each
    747 
    748 max memory is me running /usr/bin/time -v {command}, taking the max resident set size
    749 
    750 py rlib:
    751 
    752 - (render_rlib)
    753     - 24.347371951736843 seconds avg
    754     - 7,884,780,154.947369 avg cycles
    755 - (render_rlib/mem)
    756     - 160.2857894736842 MiB avg
    757 
    758 py pygame:
    759 
    760 - (render_pygame/v...)
    761     - 52.71620356077778 seconds avg
    762     - 12,353,392,498.666666 avg cycles
    763 - (render_pygame/mem)
    764     - 201.89875 MiB avg
    765 
    766 c++ rlib:
    767 
    768 - (benchmarking/final_render/out.txt)
    769     - 23.859886112999998 seconds avg
    770     - 3,796,753,782.428571 avg cycles
    771 - (benchmarking/final_render_mem/out.txt)
    772     - 137.27142857142857 MiB avg
    773 
    774 summary:
    775 
    776 this is strictly rendering information.
    777 
    778 raylib and pygame, with the same algorithm / write count, albeit randomized so not technically the same graphs, but each with multiple runs, we find:
    779 
    780 - pygame used ~1.25x the memory of raylib
    781 - pygame ran ~2.15x slower than raylib
    782 
    783 python vs c++ (normalized with raylib)
    784 
    785 - python used 1.15x more memory than c++ (c++ not really optimized for memory as it used OO paradigm that increasde overhead relative to python, but still better)
    786 - python version ran ~1.02x slower than c++ version
    787     - the overhead of computation for the graph is trivial relative to the rendering, which was gpu bound in both
    788 - python spent ~3.25x more cpu cycles than the c++ version
    789     - again, gpu bound, so this doesn't change max fps, but does increase energy usage, espeically when considering this is to run in the background for a long time
    790 
    791 without rendering:
    792 
    793 since I didn't do the heap-push optimization in the python code, I'll compare the comparable c++ implementation without that optimization which improved perf by ~2x.
    794 
    795 - benchmarking/final_no_render_v_200000_e_2000000_s_0/
    796     - 2.118 seconds
    797 - no_render_final/v200000e2000000
    798     - 20.253333333333334 seconds
    799 
    800 - c++ ran ~9.56x faster
    801 
    802 takeaway:
    803 
    804 - the overhead for the python raylib bindings aren't that encumbering. The default pygame ones are (pygame -> sdl -> opengl), instead of raylib -> opengl.
    805 - rendering performance is excellerated greatly by re-using texture maps
    806 - raylib -> screenshot is far faster when going -> bmp instead of other image file formats
    807 
    808 ---
    809 
    810 headline:
    811