commit e445c11b428e2a8d24e8767906692a7ded1dcc96 parent 9e213b4acb2ebf46623d3da4638d4f23e95d141a Author: Andrew Laack <andrew@laack.co> Date: Sat, 19 Sep 2026 18:14:16 -0500 Continued working; iterated on my comparison between raylib and pygame Diffstat:
10 files changed, 846 insertions(+), 910 deletions(-)
diff --git a/assets/abg/benchmarking-python/benchmarking/py_v_rlib/avg-times.txt b/assets/abg/benchmarking-python/benchmarking/py_v_rlib/avg-times.txt @@ -0,0 +1 @@ +93918.3376,101433.4116,101713.7572,98654.2084,92696.7232,97360.1532,98689.9556,104551.0432,101502.8576,100549.6796 diff --git a/assets/abg/benchmarking-python/benchmarking/py_v_rlib/prim-rlib.py b/assets/abg/benchmarking-python/benchmarking/py_v_rlib/prim-rlib.py @@ -0,0 +1,144 @@ +import pyray as pr +import statistics +import heapq +import random +import math +import time + +for _ in range(0,10): + VERTICES = 2500 + EDGES = 25000 + RADIUS = 5 + + pr.init_window(5120,1440, "prim") + + class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + def draw_vertex(self): + if self.visited: + pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.WHITE) + else: + pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.GRAY) + class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + def draw_edge(self, c): + pr.draw_line(int(self.v1.x), int(self.v1.y), int(self.v2.x), int(self.v2.y), c) + + def __lt__(self,otr): + return self.dist < otr.dist + + + graph = {} + + for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + + edge_list = [] + keys = list(graph.keys()) + + for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(keys) + k2 = random.choice(keys) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + + edge_heap = [] + visited_vertices = set() + + + start = random.choice(keys) + start.visited = True + visited_vertices.add(start) + for edge in graph[start]: + heapq.heappush(edge_heap, edge) + + + first = True + + to_draw_vert = [] + to_draw_edge = [] + + texture = pr.load_render_texture(5120,1440) + + fts = [] + + while True: + + pr.begin_texture_mode(texture) + + if first: + start = time.monotonic_ns() + pr.clear_background(pr.BLACK) + + for edge in edge_list: + edge.draw_edge(pr.DARKGRAY) + first = False + end = time.monotonic_ns() + print("first frame (ns): ", end - start) + + for vertex in graph: + vertex.draw_vertex() + + start = time.monotonic_ns() + for edge in to_draw_edge: + edge.draw_edge(pr.WHITE) + for vert in to_draw_vert: + vert.draw_vertex() + pr.end_texture_mode() + end = time.monotonic_ns() + fts.append(end - start) + + to_draw_vert = [] + to_draw_edge = [] + + + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + + to_draw_vert.append(new_vertex) + to_draw_edge.append(item) + + for edge in graph[new_vertex]: + if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices: + heapq.heappush(edge_heap, edge) + + source_rec = pr.Rectangle(0, 0, 5120, 1440) + dest_rec = pr.Rectangle(0, 0, 5120,1440) + + pr.begin_drawing() + pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE) + pr.end_drawing() + + + print("Average frame time (ns): " + str(sum(fts) / len(fts))) + print("Std. deviation frame time (ns): " + str(statistics.stdev(fts))) + + pr.unload_render_texture(texture) + pr.close_window() diff --git a/assets/abg/benchmarking-python/benchmarking/py_v_rlib/prim.py b/assets/abg/benchmarking-python/benchmarking/py_v_rlib/prim.py @@ -0,0 +1,128 @@ +import pygame +import heapq +import random +import math + +pygame.init() + +display = pygame.display.set_mode((5120,1440)) + +VERTICES = 10000 +EDGES = 100000 + +white = (255, 255, 255) +red = (255, 0, 0) +black = (0, 0, 0) +grey = (100,100,100) +light_grey = (50,50,50) + + +class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + def draw_vertex(self,display): + if self.visited: + pygame.draw.circle(display, white, (self.x,self.y), 5) + else: + pygame.draw.circle(display, grey, (self.x,self.y), 5) +class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + def draw_edge(self,display, c): + pygame.draw.line(display, c, (self.v1.x,self.v1.y), (self.v2.x,self.v2.y), 1) + + def __lt__(self,otr): + return self.dist < otr.dist + + +graph = {} + +for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + +edge_list = [] +keys = list(graph.keys()) + +for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(keys) + k2 = random.choice(keys) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + +edge_heap = [] +visited_vertices = set() + + +start = random.choice(keys) +start.visited = True +visited_vertices.add(start) +for edge in graph[start]: + heapq.heappush(edge_heap, edge) + + +first = True + +to_draw_vert = [] +to_draw_edge = [] + +while True: + for event in pygame.event.get(): + if event.type == pygame.QUIT: + pygame.quit() + quit() + + if first: + display.fill(black) + + for edge in edge_list: + edge.draw_edge(display, light_grey) + first = False + + for vertex in graph: + vertex.draw_vertex(display) + + for edge in to_draw_edge: + edge.draw_edge(display, white) + for vert in to_draw_vert: + vert.draw_vertex(display) + + to_draw_vert = [] + to_draw_edge = [] + + + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + + to_draw_vert.append(new_vertex) + to_draw_edge.append(item) + + for edge in graph[new_vertex]: + if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices: + heapq.heappush(edge_heap, edge) + + pygame.display.update() diff --git a/assets/abg/benchmarking-python/benchmarking/py_v_rlib/res.txt b/assets/abg/benchmarking-python/benchmarking/py_v_rlib/res.txt @@ -0,0 +1 @@ +23737800,21623742,21875582,22175871,22329912,21842306,22855717,22070161,21947041,22239451 diff --git a/assets/abg/benchmarking-python/benchmarking/py_v_rlib/rlib.txt b/assets/abg/benchmarking-python/benchmarking/py_v_rlib/rlib.txt @@ -0,0 +1,30 @@ +first frame (ns): 23737800 +Average frame time (ns): 93918.3376 +Std. deviation frame time (ns): 27358.70480398966 +first frame (ns): 21623742 +Average frame time (ns): 101433.4116 +Std. deviation frame time (ns): 28772.132168367207 +first frame (ns): 21875582 +Average frame time (ns): 101713.7572 +Std. deviation frame time (ns): 30284.105649615063 +first frame (ns): 22175871 +Average frame time (ns): 98654.2084 +Std. deviation frame time (ns): 29251.17195957408 +first frame (ns): 22329912 +Average frame time (ns): 92696.7232 +Std. deviation frame time (ns): 31224.898743060603 +first frame (ns): 21842306 +Average frame time (ns): 97360.1532 +Std. deviation frame time (ns): 31437.82910904259 +first frame (ns): 22855717 +Average frame time (ns): 98689.9556 +Std. deviation frame time (ns): 30392.119471429018 +first frame (ns): 22070161 +Average frame time (ns): 104551.0432 +Std. deviation frame time (ns): 33696.63139007443 +first frame (ns): 21947041 +Average frame time (ns): 101502.8576 +Std. deviation frame time (ns): 31350.79811678079 +first frame (ns): 22239451 +Average frame time (ns): 100549.6796 +Std. deviation frame time (ns): 32959.51310657718 diff --git a/assets/abg/blog_post_benchmarking/prim-rlib.py b/assets/abg/blog_post_benchmarking/prim-rlib.py @@ -0,0 +1,169 @@ +import pyray as pr +import statistics +import heapq +import random +import math +import time + +fts = [] +first_time = [] + + +pr.init_window(5120,1440, "prim") +texture = pr.load_render_texture(5120,1440) + +for _ in range(0,10): + VERTICES = 2500 + EDGES = 25000 + RADIUS = 5 + + + class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + def draw_vertex(self): + if self.visited: + pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.WHITE) + else: + pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.GRAY) + class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + def draw_edge(self, c): + pr.draw_line(int(self.v1.x), int(self.v1.y), int(self.v2.x), int(self.v2.y), c) + + def __lt__(self,otr): + return self.dist < otr.dist + + + graph = {} + + for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + + edge_list = [] + keys = list(graph.keys()) + + for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(keys) + k2 = random.choice(keys) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + + edge_heap = [] + visited_vertices = set() + + + start = random.choice(keys) + start.visited = True + visited_vertices.add(start) + for edge in graph[start]: + heapq.heappush(edge_heap, edge) + + + first = True + + to_draw_vert = [] + to_draw_edge = [] + + while True: + + + if first: + start = time.monotonic_ns() + pr.begin_texture_mode(texture) + pr.clear_background(pr.BLACK) + + edge_times = [] + vertex_times = [] + + for edge in edge_list: + es = time.monotonic_ns() + edge.draw_edge(pr.DARKGRAY) + ee = time.monotonic_ns() + edge_times.append(ee - es) + for vertex in graph: + vs = time.monotonic_ns() + vertex.draw_vertex() + ve = time.monotonic_ns() + vertex_times.append(ve - vs) + first = False + pr.end_texture_mode() + source_rec = pr.Rectangle(0, 0, 5120, 1440) + dest_rec = pr.Rectangle(0, 0, 5120,1440) + pr.begin_drawing() + pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE) + pr.end_drawing() + end = time.monotonic_ns() + first_time.append(end - start) + + print("Edge time avg: " + str(sum(edge_times) / len(edge_times))) + print("Vertex time avg: " + str(sum(vertex_times) / len(vertex_times))) + + continue + + + if len(to_draw_edge) != 0 or len(to_draw_vert) != 0: + start = time.monotonic_ns() + pr.begin_texture_mode(texture) + for edge in to_draw_edge: + edge.draw_edge(pr.WHITE) + for vert in to_draw_vert: + vert.draw_vertex() + pr.end_texture_mode() + source_rec = pr.Rectangle(0, 0, 5120, 1440) + dest_rec = pr.Rectangle(0, 0, 5120,1440) + + pr.begin_drawing() + pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE) + pr.end_drawing() + end = time.monotonic_ns() + fts.append(end - start) + to_draw_vert = [] + to_draw_edge = [] + + + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + + to_draw_vert.append(new_vertex) + to_draw_edge.append(item) + + for edge in graph[new_vertex]: + if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices: + heapq.heappush(edge_heap, edge) + + +pr.unload_render_texture(texture) +pr.close_window() + +print("Average frame time (ns): " + str(sum(fts) / len(fts))) +print("Std. deviation frame time (ns): " + str(statistics.stdev(fts))) + +print("Average first frame time (ns): " + str(sum(first_time) / len(first_time))) +print("Std. deviation first frame time (ns): " + str(statistics.stdev(first_time))) diff --git a/assets/abg/blog_post_benchmarking/prim.py b/assets/abg/blog_post_benchmarking/prim.py @@ -0,0 +1,162 @@ +import pygame +import time +import heapq +import random +import statistics +import math + +pygame.init() +display = pygame.display.set_mode((5120,1440)) + +fts = [] +first_time = [] + +VERTICES = 2500 +EDGES = 25000 + +white = (255, 255, 255) +red = (255, 0, 0) +black = (0, 0, 0) +grey = (100,100,100) +light_grey = (50,50,50) + + +class Vertex(): + def __init__(self, x, y): + self.x = x + self.y = y + self.visited = False + def draw_vertex(self,display): + if self.visited: + pygame.draw.circle(display, white, (self.x,self.y), 5) + else: + pygame.draw.circle(display, grey, (self.x,self.y), 5) +class Edge(): + def __init__(self, v1, v2): + self.v1 = v1 + self.v2 = v2 + self.dist = math.sqrt(((v1.x - v2.x) ** 2) + ((v1.y - v2.y) ** 2)) + def draw_edge(self,display, c): + pygame.draw.line(display, c, (self.v1.x,self.v1.y), (self.v2.x,self.v2.y), 1) + + def __lt__(self,otr): + return self.dist < otr.dist + +for _ in range(0,10): + + graph = {} + + for i in range(0,VERTICES): + x = random.random() * 5120 + y = random.random() * 1440 + graph[Vertex(x,y)] = [] + + + edge_list = [] + keys = list(graph.keys()) + + for i in range(0,EDGES): + k1 = None + k2 = None + while k1 == k2: + k1 = random.choice(keys) + k2 = random.choice(keys) + + edge = Edge(k1,k2) + graph[k1].append(edge) + graph[k2].append(edge) + edge_list.append(edge) + + + edge_heap = [] + visited_vertices = set() + + + start = random.choice(keys) + start.visited = True + visited_vertices.add(start) + for edge in graph[start]: + heapq.heappush(edge_heap, edge) + + + first = True + + to_draw_vert = [] + to_draw_edge = [] + + while True: + for event in pygame.event.get(): + if event.type == pygame.QUIT: + pygame.quit() + quit() + + if first: + start = time.monotonic_ns() + display.fill(black) + + edge_times = [] + vertex_times = [] + + for edge in edge_list: + se = time.monotonic_ns() + edge.draw_edge(display, light_grey) + ee = time.monotonic_ns() + edge_times.append(ee - se) + + for vertex in graph: + sv = time.monotonic_ns() + vertex.draw_vertex(display) + ev = time.monotonic_ns() + vertex_times.append(ev - sv) + + pygame.display.update() + end = time.monotonic_ns() + first_time.append(end - start) + first = False + print("Edge time avg: " + str(sum(edge_times) / len(edge_times))) + print("Vertex time avg: " + str(sum(vertex_times) / len(vertex_times))) + continue + + item = None + while edge_heap: + candidate = heapq.heappop(edge_heap) + if (candidate.v1 in visited_vertices) != (candidate.v2 in visited_vertices): + item = candidate + break + + if item is None: + break + + new_vertex = item.v2 if item.v1 in visited_vertices else item.v1 + visited_vertices.add(new_vertex) + new_vertex.visited = True + + to_draw_vert.append(new_vertex) + to_draw_edge.append(item) + + for edge in graph[new_vertex]: + if not edge.v1 in visited_vertices or not edge.v2 in visited_vertices: + heapq.heappush(edge_heap, edge) + + start = time.monotonic_ns() + for edge in to_draw_edge: + edge.draw_edge(display, white) + for vert in to_draw_vert: + vert.draw_vertex(display) + pygame.display.update() + end = time.monotonic_ns() + + fts.append(end - start) + + to_draw_vert = [] + to_draw_edge = [] + + + + +print("Average frame time (ns): " + str(sum(fts) / len(fts))) +print("Std. deviation frame time (ns): " + str(statistics.stdev(fts))) + +print("Average first frame time (ns): " + str(sum(first_time) / len(first_time))) +print("Std. deviation first frame time (ns): " + str(statistics.stdev(first_time))) + diff --git a/assets/abg/blog_post_benchmarking/pygame.txt b/assets/abg/blog_post_benchmarking/pygame.txt @@ -0,0 +1,4 @@ +Average frame time (ns): 5593530.846578632 +Std. deviation frame time (ns): 654036.6681470409 +Average first frame time (ns): 323388385.3 +Std. deviation first frame time (ns): 44603039.88315142 diff --git a/assets/abg/blog_post_benchmarking/rlib.txt b/assets/abg/blog_post_benchmarking/rlib.txt @@ -0,0 +1,4 @@ +Average frame time (ns): 2882704.4661864745 +Std. deviation frame time (ns): 1114606.9047266191 +Average first frame time (ns): 29873724.3 +Std. deviation first frame time (ns): 737806.3908848008 diff --git a/posts/wip/pygame-vs-raylib.md b/posts/wip/pygame-vs-raylib.md @@ -1,979 +1,272 @@ # Pygame vs Raylib -I wanted my visualization of [Prim's algorithm](https://cp-algorithms.com/graph/mst_prim.html) to be my background. My original implementation was in Python, so I was curious to see how far I could go with Python rendering libraries, but realized Python was not going to be what I ran in the background all day. Despite this, it gave me an excellent opportunity to compare Pygame and Raylib (from both Python and C++) to see how the two compare in terms of performance, and how the Python bindings for Raylib compare with direct usage from C++. +I implemented [Prim's algorithm](https://cp-algorithms.com/graph/mst_prim.html) for the creation of a MST of a graph in Python. It's an algorithm worth understanding, but as it relates to the task of rendering, the following is true about the visualization I want: -## Saving Screenshots +1. The first rendered frame must draw every edge and vertex of the graph. +2. For each subsequent timestep we have to re-draw one edge, the edge traversed at the timestep, and one vertex, the vertex we are visiting. -My plan is as follows: +Given this, the first frame being rendered will take substantially longer than subsequent frames for most graphs because rendering time is often proportional to the number of components we are rendering. With any sensible rendering program, there's a way to do incremental changes, making use of prior renders. This is true for both Raylib and PyGame. -1. Run one step of the simulation -2. Save a screenshot of the simulation to `/dev/shm` -3. Execute `feh` to set the screenshot as my background -4. Repeat until the MST was induced +## Raylib -This approach is quite janky, but it also stops me from having to dig deep into X11, a nightmare. +### Implementation -### Benchmarking - -My approach to this using Pygame looked something like this: +Raylib has 2D rendered textures which can be persisted across frames, to be rendered as part of the frame. Here's a little Python code that does this: ```python -# ... imports ... - -os.environ["SDL_VIDEODRIVER"] = "dummy" -VERTICES = 1000 # number of vertices in the graph -EDGES = 10000 # number of edges in the graph -# ... pygame initialization ... -# ... mst implementation ... - - now = time.monotonic() - pygame.image.save(display, dir_name + "out.png") - os.system("/usr/bin/feh --no-fehbg --bg-tile '/dev/shm/bg/out.png' ") - after = time.monotonic() - pygame.display.update() -``` +# ... (imports and such) + +pr.init_window(screen_width,screen_height, "prim") + +# ... (other initialization) + +texture = pr.load_render_texture(screen_width,screen_height) + +while !done: + if first: + start = time.monotonic_ns() + pr.begin_texture_mode(texture) + pr.clear_background(pr.BLACK) + + for edge in edge_list: + edge.draw_edge(pr.DARKGRAY) + for vertex in graph: + vertex.draw_vertex() + first = False + pr.end_texture_mode() + source_rec = pr.Rectangle(0, 0, 5120, 1440) + dest_rec = pr.Rectangle(0, 0, 5120,1440) + pr.begin_drawing() + pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE) + pr.end_drawing() + end = time.monotonic_ns() + first_time.append(end - start) + continue + + # ... (perform one step of Prim's algorithm) + + if len(to_draw_edge) != 0 or len(to_draw_vert) != 0: + start = time.monotonic_ns() + pr.begin_texture_mode(texture) + for edge in to_draw_edge: + edge.draw_edge(pr.WHITE) + for vert in to_draw_vert: + vert.draw_vertex() + pr.end_texture_mode() + source_rec = pr.Rectangle(0, 0, 5120, 1440) + dest_rec = pr.Rectangle(0, 0, 5120,1440) + + pr.begin_drawing() + pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE) + pr.end_drawing() + end = time.monotonic_ns() + fts.append(end - start) + to_draw_vert = [] + to_draw_edge = [] -(NOTE: All screenshots are 5120x1440) - -We set the "SDL_VIDEODRIVER" environment variable to dummy, forcing SDL to not try rendering to any screens, because we want screenshots for `feh` to operate on, not an actual window showing the rendering. - -Averaging across ten steps, the amount of time taken to save the screenshot was 0.42 seconds, an eternity. That's not great. Looking at the code for pygame, we can find the file, `src_c/image.c` that contains the save definition, and notably there are some other file formats: - -```c -static PyObject * -image_save(PyObject *self, PyObject *arg) -{ -// ... - else { - const char *name = NULL; - const char *ext = NULL; - if (oencoded == Py_None) { - name = (namehint ? namehint : "tga"); - } - else { - name = PyBytes_AS_STRING(oencoded); - } - - ext = find_extension(name); - if (!strcasecmp(ext, "png") || !strcasecmp(ext, "jpg") || - !strcasecmp(ext, "jpeg")) { - /* If it is .png .jpg .jpeg use the extended module. */ - /* try to get extended formats */ - ret = image_save_extended(self, arg); - result = (ret == NULL ? -2 : 0); - } - else if (oencoded == Py_None) { - SDL_RWops *rw = pgRWops_FromFileObject(obj); - if (rw != NULL) { - if (!strcasecmp(ext, "bmp")) { - // ... -} ``` -Well, that's interesting. It seems like there are four options. Below are the average times for each file format across 10 iterations: - +(TODO: This isn't correct anymore with the code above) -| bmp | jpg | png | tga | -| ---- | ---- | ---- | ---- | -| 0.05 | 0.09 | 0.42 | 0.07 | +Outside of our main iteration loop for Prim's algorithm, we initialize our texture to be the size of our screen, matching the window size we specified, because fullscreen animations are cooler, and we want the texture to fill the entire window. We then call the `draw_init_graph()` function with our texture as input to draw our graph to the texture, and then output the first rendered frame. -Huh, so bmp is probably the best. Very interesting. Also, notice the benchmarking contains the `feh` invocation too because `feh` will take varying amounts of time to set the X11 background depending on the fileformat too. - -Let's compare this with raylib. It looks like this: +Within our main iteration loop, we call the `begin_texture_mode()` function, which updates the Raylib global state, and makes any Raylib calls to render things to be rendered on that texture. Examples of such calls are shown below: ```python -# ... imports, mst, raylib texture initialization and incremental updating -pr.begin_drawing() -pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE) -before = time.monotonic() -pr.take_screenshot("../../../../../../../../../dev/shm/bg/out.png") -os.system("/usr/bin/feh --no-fehbg --bg-tile '/dev/shm/bg/out.jpg' ") -after = time.monotonic() -print(after - before) -pr.end_drawing() +pr.draw_line(int(self.v1.x), int(self.v1.y), int(self.v2.x), int(self.v2.y), c) +pr.draw_circle(int(self.x),int(self.y), RADIUS, pr.WHITE) ``` -We call `begin_drawing()` to initiate frame creation, load in our texture which is the rendered graph and mst, take the screenshot, set the background with `feh`, and print the time elapsed between starting the screenshot and it being set as our background. - -One thing to notice about this is the series of `../`'s. Raylib does not support absolute path specification for screenshots, and it seems like they only have screenshotting for ["convenience"](https://github.com/raysan5/raylib/issues/3530#issuecomment-1808299932). +Notice how we don't have to specify we are rendering to the texture, Raylib stores the global state for what canvas is being rendered to. -| png | jpg | bmp | tga | -| ----- | ----- | ----- | ----- | -| 0.48 | 0.27 | 0.15 | N/A | +Continuing on, we then call `end_texture_mode()` to finalize the render of the texture. This invocation is generally quite slow because it realizes the queue of writes we've sent to Raylib from our `draw_line` and `draw_circle` invocations. In this case though, since each iteration only draws one line and one circle, the overhead cost isn't great, it is merely interesting that this is how Raylib supports batch rendering. -The only other promising option supported by Raylib, not supported by Pygame, as .raw, but this appears to be a file format not understood by feh, to it is omitted. +We then define two rectangles which will be used to map the texture onto the frame. We also call `begin_drawing()` which tells Raylib we are going to start rendering our frame now. Since Raylib makes extensive use of global state, it knows we mean we are rendering to the window we created from our `init_window()` invocation at the beginning. -Interestingly, writing the bmp from Raylib is 3x slower than Pygame, with comparable performance on PNGs, and poor results on JPGs. +The rest is fairly obvious. -### Finding +## PyGame -Raylib's lack of prioritization for screenshotting appears to have resulted in worse performance relative to Pygame for screenshotting. So if I was planning to stick with this approach of screenshotting, I likely would've favored Pygame because screenshotting at the aspect ratio I use (5120x1440), was taking the bulk of the processing time. +### Implementation -## Rendering comparison +PyGame frames are persisted from frame-to-frame, so we don't have to mess with rendered textures like we did with Raylib! Here's a little code that does the PyGame rendering: -As I said before, the bulk of the time per frame was often spent on screenshotting because the cost of screenshotting was only loosely impacted by the complexity of the graph being rendered, but what if we scale up the size of the graph? Our baseline before was using 1,000 vertices and 10,000 edges in the graph. Once the screenshotting is removed we find one iteration takes: +```python -rlib: 0.0032 seconds +# ... (imports and such) -pygame: 0.0057 seconds +pygame.init() +display = pygame.display.set_mode((screen_width,screen_height)) +# ... (other initialization) -So raylib is ~1.75x faster? Let's see with larger values. We'll use 1,000,000 edges and 100,000 vertices for this: +while !done: + if first: + start = time.monotonic_ns() + display.fill(black) + for edge in edge_list: + edge.draw_edge(display, light_grey) -rlib: 0.0029 seconds -pygame: 0.0056 + for vertex in graph: + vertex.draw_vertex(display) + pygame.display.update() + end = time.monotonic_ns() + first_time.append(end - start) + first = False + continue -Huh. Why's that? Let's look at the code for the Pygame version: + # ... (perform one step of Prim's algorithm) -```python -# ... -to_draw_vert = [] -to_draw_edge = [] + start = time.monotonic_ns() + for edge in to_draw_edge: + edge.draw_edge(display, white) + for vert in to_draw_vert: + vert.draw_vertex(display) + pygame.display.update() + end = time.monotonic_ns() -# ... + to_draw_vert = [] + to_draw_edge = [] +``` -for edge in to_draw_edge: - edge.draw_edge(display, white) -for vert in to_draw_vert: - vert.draw_vertex(display) +That's a bit nicer than the Raylib variant because we don't have to mess with a standalone texture, and I like the way writing to a display works in PyGame: -to_draw_vert = [] -to_draw_edge = [] +```python +pygame.draw.circle(display, white, (self.x,self.y), 5) +pygame.draw.line(display, white, (self.v1.x,self.v1.y), (self.v2.x,self.v2.y), 1) +``` -# ... +This feels much more explicit to write directly to the display instead of writing to the Raylib global state. Despite this, the final: +```python pygame.display.update() - -# ... ``` -A lot is removed from the code, but what we see here is an approach that mitigates step-wise overdrawing, only drawing one edge between any two frames. This larger evaluation thus shows that the number of elements on screen is functionaly irrelevant for render times, dictating that render times are almost entirely constrained by the addition of new elements with both approaches. Despite this, we still say raylib is ~1.75x faster than Pygame for this task of rendering. +Is still over-using global state in my opinion. All that being said, PyGame does feel more pythonic. -## Takeaways - -You can expect better performance using Raylib than Pygame for most rendering tasks, excluding screenshotting due to it seemingly being a lesser priority for the Raylib team. Raylib uses OpenGL for rendering while PyGame uses SDL which in turn uses OpenGL for rendering. This added layer of overhead, likely also coupled with heavier Python ecosystem baggage, makes the rendering performance for PyGame fall short of Raylib. - - -## Time to go lower +## Benchmarking -Raylib is at its core a C library. Raylib from Python uses a [Python package](https://pypi.org/project/raylib/) to call this library. This begs the question: Should we go lower? +These benchmarks are performed with the following parameters: -To evaluate this, I'm going to be comparing calling Raylib directly from C++ with what we've shown previously, invoking Raylib from Python. +- Vertex count: 2,500 +- Edge count: 25,000 +- Screen dimensions: 5120x1440 -### Benchmarking +Averaging across 10 full graph traversals. For each of the times we are tracking, these are as close to just render time as possible, removing all of the graph traversal logic time from the measured times. +### Raylib -1_000_000 edges and 100_000 vertices: +Average frame time (ns): 2882704.4661864745 +Std. deviation frame time (ns): 1114606.9047266191 +Average first frame time (ns): 29873724.3 +Std. deviation first frame time (ns): 737806.3908848008 -rlib: 0.00295373 -rlibcpp: 0.00294624 +### PyGame -both of these were across 30_000 frames. We find rlibcpp is 1.0025x faster than the python version. This is .25%. Very impressive. +Average frame time (ns): 5593530.846578632 +Std. deviation frame time (ns): 654036.6681470409 +Average first frame time (ns): 323388385.3 +Std. deviation first frame time (ns): 44603039.88315142 +### Deltas ---- +- Raylib's average frame render time was 1.94x faster than PyGame's. +- Raylib's average first frame render time was 10.83x faster than PyGame's. +### Why So Slow? +Well, let's add some more time track to our PyGame code to find out why: +```python +if first: + start = time.monotonic_ns() + display.fill(black) -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? - -## MST - -IMPLEMENTATION DETAILS + edge_times = [] + vertex_times = [] -## Background making + for edge in edge_list: + se = time.monotonic_ns() + edge.draw_edge(display, light_grey) + ee = time.monotonic_ns() + edge_times.append(ee - se) -[https://github.com/python-xlib/python-xlib](https://github.com/python-xlib/python-xlib.md) + for vertex in graph: + sv = time.monotonic_ns() + vertex.draw_vertex(display) + ev = time.monotonic_ns() + vertex_times.append(ev - sv) -```python3 -os.environ["SDL_VIDEODRIVER"] = "dummy" + pygame.display.update() + end = time.monotonic_ns() + first_time.append(end - start) + first = False + print("Edge time avg: " + str(sum(edge_times) / len(edge_times))) + print("Vertex time avg: " + str(sum(vertex_times) / len(vertex_times))) + continue ``` -why not just use screenshots in a shared location? - -indeed, why not? - -## fuck you and your bullshit. - -Benchmarking - -## c -> c++ - -realized I needed a heap. - -## bmp vs png vs jpg - -bmp is crazy fucking fast (benchmark) - -(looked in the code for supported file formats, looked in feh -> lib(whatever) for support) - -note larger file size. - -this is interesting, look further. - -### patched upstream xl - -### x11 - -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. - -(should learn more about this) - -### Benchmarking - -uhhh... is it actually that fast? - -wait; did this just optimize all of my code? - -Well yes, but actually no. - -adding: - -std::cout << g.toString() << std::endl; - -gives ~ the same perf (minus the amount of time it takes to send so much data to stdout) - -(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). - -(fixed a bug in the python code slowing it down) - -see no_render_2_fixed_itr. - -## C++ benchmarking - -330 ms for init stuff w/ graph -1405 ms for iteration - -broken further down: - -average iteration time is ~0ms, reaching ~20ms for later stages. Over time the percentage of valid edges declines. - -added getUnvisitedEdges function to return only non-traversed edges - -Init time: 332 -Loop time: 1344 -Init time: 327 -Loop time: 1350 -Init time: 322 -Loop time: 1374 - -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. - -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. - -such a refactor though is likely irrelevant right now due to the added cost of - -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. - -Init time: 389 -Loop time: 706 -Init time: 315 -Loop time: 671 -Init time: 337 -Loop time: 692 - -now we're cooking with gas. - -tests now fail. bc snapshots. updated and everything seems right again. - -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. - -Init time: 334 -Loop time: 694 -Init time: 321 -Loop time: 668 -Init time: 323 -Loop time: 701 - -now we find this: - -(see benchmarking/no_render_v_100000_e_1000000_s_0/out1.csv) - -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$ - -at this point it's worth worrying about the return for the get untraversed edges for vertices not traversed. after that: - -Init time: 314 -Loop time: 678 -Init time: 312 -Loop time: 671 -Init time: 311 -Loop time: 680 - -and with the optimization for edge ordering: - -Init time: 311 -Loop time: 659 -Init time: 333 -Loop time: 673 -Init time: 320 -Loop time: 709 -Init time: 311 -Loop time: 674 - -this is still too fucking slow. - -what's making the graph induction so incredibly slow? - -just graph creation: - -graph create: 317 -Loop time: 691 -graph create: 314 -Loop time: 657 -graph create: 311 -Loop time: 665 - -reserving instead of pushing: - -graph create: 314 -Loop time: 636 -graph create: 324 -Loop time: 688 -graph create: 315 -Loop time: 693 - -replaced map with vector where we were using indices to index into the map (dumb): - -graph create: 174 -Loop time: 654 -graph create: 179 -Loop time: 610 -graph create: 184 -Loop time: 618 -graph create: 185 -Loop time: 622 - -ok, let's now run the full benchmarks again: - -benchmarking/no_render_only_grab_unvisited_edges_vector_instead_of_map_v_100000_e_1000000_s_0/out1.csv - -0.04,0.79,0.84 -0.03,0.79,0.84 -0.04,0.77,0.82 - -this was kind of just stalling though becaus I'm out of my depth as it relates to rendering, the larger perf issue. - -back to that. - -here are where this stands w/ 1000 v and 10_000 edges - -prior was ~34s per iteration (final col) - -this is basically the same: - -benchmarking/better_render_v_1000_e_10000_s_0/out1.csv - -(snippet from above file) - -0.26,10.71,34.22 -0.29,10.64,33.24 -0.31,10.62,33.57 -0.28,10.53,33.56 - -fine. we'll fix the raylib shit. (queue montage) - -make debug-build && time ./abg.out -s 0 --edges 2000 --vertices 200 - -real 0m1.948s -user 0m0.529s -sys 0m0.060s - -~20 milliseconds per render call w/ make debug-build && time ./abg.out -s 0 --edges 20000 --vertices 2000 - -Total single iteration cost: 65 -Amount of time calling render: 18 -Total single iteration cost: 65 -Amount of time calling render: 18 -Total single iteration cost: 65 -Amount of time calling render: 18 -Total single iteration cost: 65 -Amount of time calling render: 18 -Total single iteration cost: 65 -Amount of time calling render: 19 -Total single iteration cost: 65 -Amount of time calling render: 18 -Total single iteration cost: 65 -Amount of time calling render: 18 -Total single iteration cost: 65 - -huh; what's the other iteration cost? - - - while (!WindowShouldClose() && toVisit.size() != 0) { - auto startLoop = std::chrono::steady_clock::now(); - BeginDrawing(); - ClearBackground(BLACK); - auto startRender = std::chrono::steady_clock::now(); - g.render(); - auto endRender = std::chrono::steady_clock::now(); - auto diff = std::chrono::duration_cast<std::chrono::milliseconds>(endRender - startRender); - std::cout << "Amount of time calling render: " << diff.count() << std::endl; - EndDrawing(); - - // since we wait sleepTime here, the bg render has a render delta of - // at minimum sleepTime when switching tags in dwm, this is rather - // annoying because the screen doesn't repaint until the sleep time - // passes, which results in artifacts on screen. - - // despite this, calling render a lot of times is rather intensive - // (at least on my hardware) and so this tradeoff is accepted for - // now, unless there's a simple approach that allows for preemption - - //usleep((int)(sleepTime * 1000000)); - - oneStepPrim(toVisit, visitedIndices, g); - auto endLoop = std::chrono::steady_clock::now(); - auto loopDiff = std::chrono::duration_cast<std::chrono::milliseconds>(endLoop - startLoop); - std::cout << "Total single iteration cost: " << loopDiff.count() << std::endl; - - } - -so it's somewhere in that first block; in the render area. the actual computation cost at the end is inconsequential. - -begindrawing is ~free. - -clear background is ~free. - -~46 of 65ms are spent on enddrawing. - -so two things: - -19ms on render -46ms on enddrawing - -what about when the numbers are much bigger (100_000 edges, 10_000 vertices)? - -Render time: 56 -End Drawing time: 237 -Total single iteration cost: 316 - -the other 23 ms is the prim step + begin drawing / clear background. - -can we just not clear the screen? does that help? nope. doesn't do anything. - -target 60 fps? - -nope. - -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. - -what happens if I use the better single time render method? - -before: - -Render time: 62 -End Drawing time: 244 -Total single iteration cost: 306 -Render time: 60 -End Drawing time: 245 -Total single iteration cost: 305 -Render time: 60 -End Drawing time: 245 -Total single iteration cost: 305 -Render time: 55 -End Drawing time: 252 -Total single iteration cost: 307 -Render time: 60 -End Drawing time: 245 -Total single iteration cost: 305 -Render time: 58 -End Drawing time: 247 -Total single iteration cost: 306 - -after: - -Total single iteration cost: 158 -Render time: 46 -End Drawing time: 112 -Total single iteration cost: 159 -Render time: 46 -End Drawing time: 112 -Total single iteration cost: 159 -Render time: 45 -End Drawing time: 113 -Total single iteration cost: 159 -Render time: 46 -End Drawing time: 111 -Total single iteration cost: 158 -Render time: 46 -End Drawing time: 112 -Total single iteration cost: 158 -Render time: 46 -End Drawing time: 113 - -hell yeah. +Here are some sample outputs of this: -why so slow still? - -Like this is only ~100_000 and ~10_000 vertices so like why so slow? - -benchmarked now: - -benchmarking/simpler_render_v_1000_e_10000_s_0/out1.csv -0.29,7.77,18.96 -0.27,7.80,19.17 -0.29,7.90,19.17 -0.31,7.76,19.05 -0.29,7.72,18.68 -0.30,7.90,18.56 -0.27,7.78,18.80 -0.27,7.77,18.74 -0.29,7.69,18.77 -0.32,7.67,18.85 - -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. - -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? - -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. - -std::thread t(endDrawing); -t.join(); - -vs endDrawing() - -result in entirely different outcomes. - -the second sort of renders some stuff, but gets totally fucked up and then just black screens. - -due to an import? no this shit's just fucked. - -opengl affinity. - -can prebake the graph though and then only render additions. - -after: - -0.19,1.77,3.86 -0.17,1.76,3.81 -0.19,1.76,3.82 -0.18,1.75,3.85 -0.18,1.71,3.86 -0.19,1.68,3.83 -0.18,1.72,3.83 - -holy shit. can we make this faster? - -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. - -benchmarking/cache_first_use_blank_graph_v_1000_e_10000_s_0/out1.csv - -0.17,0.65,3.06 -0.18,0.63,3.05 -0.18,0.66,3.05 -0.18,0.64,3.05 -0.18,0.64,3.04 -0.17,0.63,3.02 -0.18,0.62,3.04 -0.19,0.64,3.05 -0.17,0.65,3.04 -0.17,0.66,3.03 -0.18,0.62,3.04 -0.17,0.63,3.03 - -this is too boring; let's turn this shit up. - -how fast are we relative to the python bloatware webshit? - -benchmarking/cache_first_use_blank_graph_v_10000_e_100000_s_0/out1.csv - -1.40,28.92,35.76 -1.53,29.30,35.95 - -(notice the edges and vertices) - -vs python: - -1.33,10730.71,10772.74 - -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. - -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. - -after doing this we find: - -benchmarking/track_to_render_v_10000_e_100000_s_0/out1.csv - -1.50,3.12,29.43 -1.51,3.20,29.67 -1.57,3.08,30.00 -1.57,3.04,30.07 - -35.855000000000004 / 29.7925 = 1.2034908114458338 - -okay, so 20 percent faster. still too fucking slow. - -i'm also getting sick of this bs chrono / time shit. time to bring in perf. - - 3.20% 395 abg.out libraylib.so.6.0.0 [.] rlVertex3f - 2.08% 338 abg.out abg.out [.] Edge::operator>(Edge const&) const - 1.55% 245 abg.out abg.out [.] oneStepPrim(std::priority_queue<Edge, std::vector<Edge, st> - 1.41% 255 abg.out libraylib.so.6.0.0 [.] rlDrawRenderBatch - 1.22% 225 abg.out libc.so.6 [.] 0x0000000000185dde - 0.85% 129 abg.out libraylib.so.6.0.0 [.] DrawCircleSector - 0.79% 136 abg.out libc.so.6 [.] pthread_mutex_lock - 0.74% 133 abg.out libc.so.6 [.] ioctl - 0.64% 115 abg.out libgallium-26.2.2-arch1.1.so [.] 0x00000000007f8138 - 0.62% 113 abg.out libraylib.so.6.0.0 [.] PollInputEvents - 0.57% 91 abg.out libc.so.6 [.] cfree - 0.56% 95 abg.out libc.so.6 [.] malloc - 0.54% 27 abg.out libc.so.6 [.] 0x00000000001866c9 - 0.53% 99 abg.out libgallium-26.2.2-arch1.1.so [.] 0x000000000180c45c - -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. - -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. - -looking at the call stack: - -|--14.80%--EndTextureMode -|--58.02%--EndDrawing ---1.62%--Graph::render() - -well. huh. end texture mode is where I add things though the function itself is just clearing the queue. - -It's a bit surprising enddrawing is more expensive since it just loads in the texture I've baked. - ---- - -I shall call this ~done. final findings with - -rendered below is using vertices = 10_000, edges = 100_000 - -unrendered below is using vertices = 200_000, edges = 2_000_000 - -- python (with overdraw mostly fixing + texture map) - - rendered - - 58.758 seconds - - unrendered - - 20.253333333333334 seconds - -- c++ (with overdraw fixing + texture map) - - rendered - - - 29.7925 seconds - - - unrendered - - 2.118 seconds - - -benchmarking/final_no_render_v_200000_e_2000000_s_0/ - -takeaway: - -the rendered python implementation w/ 10_000 v and 100_000 edges using perf: - -Performance counter stats for 'python3 prim.py': - - 0 context-switches:u # 0.0 cs/sec cs_per_second - 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second - 14,233 page-faults:u # 252.0 faults/sec page_faults_per_second - 56,487.57 msec task-clock:u # nan CPUs CPUs_utilized - 30,763,483 branch-misses:u # 0.7 % branch_miss_rate (88.90%) - 4,305,442,939 branches:u # 76.2 M/sec branch_frequency (88.90%) - 128,137,043,750 cpu-cycles:u # 2.3 GHz cycles_frequency (88.90%) - 18,736,054,409 instructions:u # 0.1 instructions insn_per_cycle (88.85%) - TopdownL1 # 0.1 % tma_backend_bound - # 98.9 % tma_bad_speculation (88.87%) - # 0.5 % tma_frontend_bound (77.81%) - # 0.5 % tma_retiring (88.92%) - - 59.936596362 seconds time elapsed - - 52.628026000 seconds user - 1.492521000 seconds sys - -gpu constrained though. - -the rendered c++ implementation w/ 10_000 v and 100_000 edges using perf: - - Performance counter stats for './abg.out -s 0 --vertices 10000 --edges 100000': - - 0 context-switches:u # 0.0 cs/sec cs_per_second - 0 cpu-migrations:u # 0.0 migrations/sec migrations_per_second - 9,363 page-faults:u # 1819.4 faults/sec page_faults_per_second - 5,146.21 msec task-clock:u # nan CPUs CPUs_utilized - 28,144,835 branch-misses:u # 5.9 % branch_miss_rate (89.55%) - 473,319,266 branches:u # 92.0 M/sec branch_frequency (88.64%) - 3,973,233,282 cpu-cycles:u # 0.8 GHz cycles_frequency (88.55%) - 2,925,854,560 instructions:u # 0.7 instructions insn_per_cycle (89.12%) - TopdownL1 # 2.7 % tma_backend_bound - # 93.6 % tma_bad_speculation (88.66%) - # 0.9 % tma_frontend_bound (77.75%) - # 2.8 % tma_retiring (88.67%) - - 29.577542431 seconds time elapsed - - 2.925597000 seconds user - 2.094917000 seconds sys - -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. - -gpu constrained too. - -memory overhead? - -c++ rendered sits at ~171mb-175mb. it's not great, hasn't been optimized, def room for improvement. - -python rendered sits at ~240mb-248mb - -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... - -huh... after 2 hours it's chilling at 163mb (TODO). - -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.) - -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. - -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. - -before: - -benchmarking/final_no_render_v_200000_e_2000000_s_0/ - -0.08,2.03,2.12 -0.09,2.02,2.12 -0.09,2.00,2.11 -0.09,2.00,2.11 -0.08,1.99,2.09 -0.07,1.99,2.08 -0.10,2.00,2.11 -0.09,2.00,2.11 -0.09,2.07,2.18 -0.06,2.08,2.15 - - -after: - -benchmarking/final_min_no_render_v_200000_e_2000000_s_0/out.csv - -0.06,0.97,1.04 -0.06,0.93,1.00 -0.07,0.95,1.03 -0.09,0.92,1.02 -0.08,0.94,1.02 -0.08,0.94,1.03 -0.08,0.94,1.03 -0.06,0.95,1.02 -0.08,0.93,1.02 -0.07,0.95,1.02 -0.07,0.95,1.03 -0.07,0.95,1.03 -0.08,0.95,1.04 -0.09,0.93,1.03 -0.07,0.98,1.06 -0.07,0.95,1.04 -0.08,0.94,1.03 -0.07,0.96,1.04 -0.07,0.95,1.04 -0.07,1.00,1.08 - -this doesn't really impact time wrt rendered because that is basically all spent on rendering not computation. - -do I have a memory leak? - - - -> time valgrind --tool=memcheck abg - -==944657== Process terminating with default action of signal 2 (SIGINT) -==944657== at 0x50D3952: __syscall_cancel_arch (syscall_cancel.S:56) -==944657== by 0x5117AEC: internal_syscall_cancel (sysdep-cancel.h:53) -==944657== by 0x5117AEC: clock_nanosleep@@GLIBC_2.17 (clock_nanosleep.c:48) -==944657== by 0x5123F26: nanosleep (nanosleep.c:25) -==944657== by 0x51532E9: usleep (usleep.c:31) -==944657== by 0x40065B8: main (in /usr/local/bin/abg) -==944657== -==944657== HEAP SUMMARY: -==944657== in use at exit: 11,776,171 bytes in 27,368 blocks -==944657== total heap usage: 86,922 allocs, 59,554 frees, 29,848,973 bytes allocated -==944657== -==944657== LEAK SUMMARY: -==944657== definitely lost: 0 bytes in 0 blocks -==944657== indirectly lost: 0 bytes in 0 blocks -==944657== possibly lost: 6,876,540 bytes in 3,237 blocks -==944657== still reachable: 4,899,631 bytes in 24,131 blocks -==944657== suppressed: 0 bytes in 0 blocks -==944657== Rerun with --leak-check=full to see details of leaked memory -==944657== -==944657== For lists of detected and suppressed errors, rerun with: -s -==944657== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) - - -real 12m18.560s -user 0m23.848s -sys 0m0.969s - -andrew@deepthought:~$ time valgrind --tool=memcheck abg -==947393== Memcheck, a memory error detector -==947393== Copyright (C) 2002-2024, and GNU GPL'd, by Julian Seward et al. -==947393== Using Valgrind-3.25.1 and LibVEX; rerun with -h for copyright info -==947393== Command: abg -==947393== -^C==947393== -==947393== Process terminating with default action of signal 2 (SIGINT) -==947393== at 0x50D3952: __syscall_cancel_arch (syscall_cancel.S:56) -==947393== by 0x5117AEC: internal_syscall_cancel (sysdep-cancel.h:53) -==947393== by 0x5117AEC: clock_nanosleep@@GLIBC_2.17 (clock_nanosleep.c:48) -==947393== by 0x5123F26: nanosleep (nanosleep.c:25) -==947393== by 0x51532E9: usleep (usleep.c:31) -==947393== by 0x40065B8: main (in /usr/local/bin/abg) -==947393== -==947393== HEAP SUMMARY: -==947393== in use at exit: 11,656,499 bytes in 27,404 blocks -==947393== total heap usage: 64,820 allocs, 37,416 frees, 24,650,054 bytes allocated -==947393== -==947393== LEAK SUMMARY: -==947393== definitely lost: 0 bytes in 0 blocks -==947393== indirectly lost: 0 bytes in 0 blocks -==947393== possibly lost: 6,744,916 bytes in 3,235 blocks -==947393== still reachable: 4,911,583 bytes in 24,169 blocks -==947393== suppressed: 0 bytes in 0 blocks -==947393== Rerun with --leak-check=full to see details of leaked memory -==947393== -==947393== For lists of detected and suppressed errors, rerun with: -s -==947393== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) - - -real 0m53.077s -user 0m20.121s -sys 0m0.750s - -andrew@deepthought:~$ time valgrind --leak-check=full --tool=memcheck abg -s 0 - -==948338== -==948338== LEAK SUMMARY: -==948338== definitely lost: 0 bytes in 0 blocks -==948338== indirectly lost: 0 bytes in 0 blocks -==948338== possibly lost: 6,948,380 bytes in 3,271 blocks -==948338== still reachable: 4,899,399 bytes in 24,179 blocks -==948338== suppressed: 0 bytes in 0 blocks -==948338== Reachable blocks (those to which a pointer was found) are not shown. -==948338== To see them, rerun with: --leak-check=full --show-leak-kinds=all -==948338== -==948338== For lists of detected and suppressed errors, rerun with: -s -==948338== ERROR SUMMARY: 2838 errors from 2838 contexts (suppressed: 0 from 0) - - -real 21m9.471s -user 19m30.601s -sys 1m12.207s - -seems like this was just me not closing the window. fixed that. - ---- - -profiling: - -start: 121mb (time 5:15pm after running for ~a minute) -check-in: 121mb (time 8:55pm) -- this is just the default `abg` cmd so not a ton of churn -stopped: 121mb (9:11pm) - -running again w/ s=0: - ---- - -(recompile) - -start: 123mb (time 9:13pm) -end: 123mb (time: 11:00pm) - ---- - -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: - -- It's unlikely there's an optimization for my hardware that'd improve performance by 2x -- 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. -- These further optimizations are probably not worth it - - They could make this faster but two things: - 1. They would decrease code readability and extensibility a non-trivial amount - - sometimes worth it - 2. The improvements wouldn't be meaningful for average usage - - 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 - - ---- - -Pygame vs raylib: - -- Not a super great comparison -- SDL (pygame) will basically always be slower than opengl (raylib) - ---- - -okay, so, this is a comparison between pygame, rlib w/ python, rlib from c++: - -these are all only rendering deltas, using a texture with rlib, and just doing incremental writes with pygame (functionally the same amount of computation) - - -each is running one iteration of prim, rendering each step, with 100000 edges and 10000 vertices - -(kept each render in the foreground as that makes it slower, disabled picom) - -sleep 1 for each - -max memory is me running /usr/bin/time -v {command}, taking the max resident set size - -py rlib: - -- (render_rlib) - - 24.347371951736843 seconds avg - - 7,884,780,154.947369 avg cycles -- (render_rlib/mem) - - 160.2857894736842 MiB avg - -py pygame: - -- (render_pygame/v...) - - 52.71620356077778 seconds avg - - 12,353,392,498.666666 avg cycles -- (render_pygame/mem) - - 201.89875 MiB avg - -c++ rlib: - -- (benchmarking/final_render/out.txt) - - 23.859886112999998 seconds avg - - 3,796,753,782.428571 avg cycles -- (benchmarking/final_render_mem/out.txt) - - 137.27142857142857 MiB avg - -summary: - -this is strictly rendering information. - -raylib and pygame, with the same algorithm / write count, albeit randomized so not technically the same graphs, but each with multiple runs, we find: - -- pygame used ~1.25x the memory of raylib -- pygame ran ~2.15x slower than raylib - -python vs c++ (normalized with raylib) - -- 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) -- python version ran ~1.02x slower than c++ version - - the overhead of computation for the graph is trivial relative to the rendering, which was gpu bound in both -- python spent ~3.25x more cpu cycles than the c++ version - - 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 +``` +Edge time avg: 9504.15048 +Vertex time avg: 686.6508 +Edge time avg: 9479.576 +Vertex time avg: 684.0856 +Edge time avg: 10398.7096 +Vertex time avg: 689.1952 +``` -without rendering: +That's interesting. Let's compare this to our Raylib code: -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. +```python +if first: + start = time.monotonic_ns() + pr.begin_texture_mode(texture) + pr.clear_background(pr.BLACK) + + edge_times = [] + vertex_times = [] + + for edge in edge_list: + es = time.monotonic_ns() + edge.draw_edge(pr.DARKGRAY) + ee = time.monotonic_ns() + edge_times.append(ee - es) + for vertex in graph: + vs = time.monotonic_ns() + vertex.draw_vertex() + ve = time.monotonic_ns() + vertex_times.append(ve - vs) + first = False + pr.end_texture_mode() + source_rec = pr.Rectangle(0, 0, 5120, 1440) + dest_rec = pr.Rectangle(0, 0, 5120,1440) + pr.begin_drawing() + pr.draw_texture_pro(texture.texture, source_rec, dest_rec, pr.Vector2(0, 0), 0, pr.WHITE) + pr.end_drawing() + end = time.monotonic_ns() + first_time.append(end - start) + + print("Edge time avg: " + str(sum(edge_times) / len(edge_times))) + print("Vertex time avg: " + str(sum(vertex_times) / len(vertex_times))) + continue +``` -- benchmarking/final_no_render_v_200000_e_2000000_s_0/ - - 2.118 seconds -- no_render_final/v200000e2000000 - - 20.253333333333334 seconds +``` +Edge time avg: 944.15884 +Vertex time avg: 3016.1852 +Edge time avg: 961.17092 +Vertex time avg: 3076.4524 +``` -- c++ ran ~9.56x faster +Huh. We see PyGame is faster at rendering vertices (circles), but slower drawing edges (lines). If we consider the PyGame source code, this actually makes some amount of sense. PyGame uses SDL where we have to walk the lines pixel by pixel on CPU, costing a lot of cycles, while Raylib writes the edge ends to a geometry batch to be asynchronously rendered on GPU lessening the amount of time spent in this loop. -takeaway: +If we consider the vertices, the Python Raylib bindings call out to `DrawCircleSector()`, and this in turn appends geometries to the GPU geometries batch, but for every circle there are a bunch of discrete geometries which have to be appended to the batch, costing cycles. Contrasting this with the PyGame approach where PyGame simply has a draw some pixels onto the screen. -- the overhead for the python raylib bindings aren't that encumbering. The default pygame ones are (pygame -> sdl -> opengl), instead of raylib -> opengl. -- rendering performance is excellerated greatly by re-using texture maps -- raylib -> screenshot is far faster when going -> bmp instead of other image file formats +There are ways to make PyGame utilize the GPU more, but these approaches are much more complex, and not something an average person who just wants to render some graphs would do. ---- +## Takeaways -headline: +For most use cases, you'll likely have better rendering performance if you use Raylib. Raylib is slightly more complex to work with, requiring explicit texture manipulation to achieve comparable performance on incremental renders, and making use of more global state, how the underlying C library is designed. Despite this, PyGame also makes use of some global state that can be a bit annoying, but slightly less so. Additionally, if you want to utilize GPU rendering more fully, Raylib will be better.