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