commit 03d8d43a469e29226ae89b494a8ce23ac032afeb
parent e21c8d96e525812e09085f21692a3e308d016940
Author: Andrew Laack <andrew@laack.co>
Date: Wed, 16 Sep 2026 19:07:18 -0500
Benchmarking + perf fix
Diffstat:
8 files changed, 302 insertions(+), 88 deletions(-)
diff --git a/graph/benchmarking/no_render_1_itr/info.txt b/graph/benchmarking/no_render_1_itr/info.txt
@@ -0,0 +1 @@
+this has a copying issue where k1 = random.choice... which creates an array every iteration, bunch of copies. not good.
diff --git a/graph/benchmarking/no_render_2_fixed_itr/bench.sh b/graph/benchmarking/no_render_2_fixed_itr/bench.sh
@@ -0,0 +1,5 @@
+while [ 1 ]; do
+ /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1
+ cat out | tee -a v100000e1000000nosc
+ sleep 1
+done
diff --git a/graph/benchmarking/no_render_2_fixed_itr/out b/graph/benchmarking/no_render_2_fixed_itr/out
@@ -0,0 +1,2 @@
+Command terminated by signal 2
+0.08,10.23,10.35
diff --git a/graph/benchmarking/no_render_2_fixed_itr/prim.py b/graph/benchmarking/no_render_2_fixed_itr/prim.py
@@ -0,0 +1,82 @@
+import heapq
+import random
+import math
+
+VERTICES = 100000
+EDGES = 1000000
+
+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
+
+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 __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()
+
+mst = []
+
+start = random.choice(list(graph.keys()))
+start.visited = True
+visited_vertices.add(start)
+for edge in graph[start]:
+ heapq.heappush(edge_heap, edge)
+
+while True:
+ 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
+ mst.append(item)
+ for edge in graph[new_vertex]:
+ heapq.heappush(edge_heap, edge)
diff --git a/graph/benchmarking/no_render_2_fixed_itr/v100000e1000000nosc b/graph/benchmarking/no_render_2_fixed_itr/v100000e1000000nosc
@@ -0,0 +1,208 @@
+0.06,12.10,12.21
+0.08,12.22,12.35
+0.08,12.16,12.29
+0.09,12.00,12.13
+0.09,11.89,12.02
+0.06,11.92,12.01
+0.06,11.87,11.97
+0.06,12.07,12.16
+0.08,11.84,11.98
+0.07,11.87,12.02
+0.06,11.80,11.89
+0.09,11.84,11.96
+0.07,11.86,11.97
+0.07,11.93,12.04
+0.07,11.97,12.10
+0.07,12.02,12.13
+0.05,12.01,12.11
+0.06,11.80,11.90
+0.06,11.71,11.82
+0.08,11.99,12.11
+0.06,12.02,12.12
+0.06,12.00,12.11
+0.07,11.95,12.06
+0.06,12.08,12.18
+0.07,11.81,11.92
+0.08,12.00,12.12
+0.06,11.88,11.98
+0.06,11.96,12.07
+0.06,11.99,12.09
+0.07,11.84,11.97
+0.07,11.99,12.10
+0.06,12.05,12.15
+0.08,11.91,12.03
+0.08,11.81,11.93
+0.08,11.83,11.94
+0.07,11.87,12.01
+0.07,11.80,11.94
+0.08,12.11,12.24
+0.08,11.87,12.00
+0.07,11.85,11.96
+0.07,11.97,12.08
+0.06,12.10,12.20
+0.06,11.86,11.96
+0.06,11.88,11.98
+0.07,11.95,12.06
+0.07,11.88,11.98
+0.07,11.85,11.97
+0.06,11.86,11.97
+0.08,11.98,12.10
+0.07,11.79,11.90
+0.07,12.03,12.16
+0.06,11.86,11.97
+0.06,11.94,12.03
+0.06,11.91,12.01
+0.06,11.96,12.06
+0.06,12.13,12.22
+0.07,12.00,12.11
+0.06,12.00,12.10
+0.07,12.02,12.14
+0.06,11.85,11.95
+0.08,11.94,12.06
+0.08,11.76,11.88
+0.07,11.89,12.00
+0.05,12.06,12.15
+0.07,11.94,12.05
+0.06,11.92,12.02
+0.08,11.85,11.97
+0.07,11.93,12.06
+0.08,11.75,11.87
+0.06,11.75,11.86
+0.07,11.89,11.99
+0.06,11.89,12.02
+0.06,11.81,11.93
+0.07,11.82,11.93
+0.07,12.03,12.14
+0.06,11.84,11.94
+0.08,12.22,12.34
+0.07,11.89,12.00
+0.08,12.03,12.14
+0.07,12.06,12.17
+0.08,11.74,11.86
+0.07,11.90,12.01
+0.06,11.82,11.93
+0.08,11.84,11.96
+0.07,11.78,11.88
+0.08,12.31,12.44
+0.08,11.87,11.99
+0.08,12.04,12.17
+0.06,12.02,12.12
+0.08,11.85,11.96
+0.05,11.93,12.03
+0.07,11.67,11.79
+0.07,11.82,11.92
+0.08,11.83,11.95
+0.07,11.86,11.97
+0.06,11.98,12.10
+0.07,12.05,12.16
+0.07,11.84,11.94
+0.07,11.91,12.02
+0.07,11.88,11.99
+0.07,11.89,12.00
+0.07,11.94,12.06
+0.07,11.84,11.95
+0.07,11.88,11.99
+0.08,11.85,11.98
+0.07,11.99,12.10
+0.08,11.85,11.97
+0.07,12.12,12.23
+0.08,11.86,11.98
+0.08,11.89,12.00
+0.07,12.05,12.15
+0.07,11.89,11.99
+0.07,11.93,12.05
+0.07,11.82,11.94
+0.06,11.94,12.05
+0.07,11.86,11.98
+0.07,11.76,11.87
+0.07,11.96,12.07
+0.07,11.89,12.00
+0.07,12.16,12.27
+0.07,11.91,12.02
+0.07,11.83,11.94
+0.05,11.85,11.94
+0.07,11.92,12.03
+0.06,11.79,11.90
+0.07,11.76,11.87
+0.07,11.92,12.03
+0.06,11.86,11.96
+0.07,11.81,11.93
+0.07,11.90,12.01
+0.07,11.89,12.00
+0.07,11.91,12.02
+0.07,11.87,11.98
+0.08,11.87,11.99
+0.07,11.83,11.96
+0.06,11.88,11.99
+0.07,11.79,11.90
+0.06,11.84,11.95
+0.06,11.85,11.96
+0.06,11.83,11.95
+0.07,11.85,11.99
+0.07,11.94,12.05
+0.05,11.97,12.07
+0.07,11.90,12.01
+0.06,11.93,12.03
+0.07,11.89,12.00
+0.06,11.91,12.01
+0.06,11.83,11.93
+0.06,11.92,12.02
+0.05,11.88,11.97
+0.08,11.91,12.03
+0.07,11.89,12.00
+0.07,11.83,11.95
+0.09,11.89,12.02
+0.07,11.85,11.97
+0.06,11.82,11.92
+0.07,11.85,11.96
+0.06,11.98,12.08
+0.07,11.79,11.93
+0.07,12.01,12.12
+0.08,11.87,12.01
+0.06,11.85,11.98
+0.07,11.76,11.89
+0.06,11.86,11.97
+0.07,11.88,11.99
+0.08,11.79,11.94
+0.07,11.81,11.96
+0.07,11.90,12.01
+0.06,11.84,11.97
+0.08,11.83,11.98
+0.07,11.93,12.07
+0.07,11.84,11.99
+0.07,11.82,11.94
+0.07,11.96,12.09
+0.07,11.84,11.95
+0.08,11.94,12.09
+0.06,11.83,11.94
+0.06,11.90,12.00
+0.06,11.87,11.98
+0.06,12.04,12.14
+0.05,12.01,12.13
+0.07,11.84,11.98
+0.06,11.80,11.93
+0.05,11.89,12.02
+0.06,11.84,11.94
+0.06,12.11,12.21
+0.06,12.06,12.17
+0.07,11.76,11.89
+0.07,11.93,12.07
+0.08,11.91,12.03
+0.07,11.85,11.96
+0.07,11.95,12.06
+0.09,12.01,12.13
+0.06,11.97,12.07
+0.06,11.97,12.07
+0.07,11.86,11.97
+0.06,11.84,11.94
+0.07,11.98,12.09
+0.07,11.93,12.04
+0.07,12.19,12.30
+0.06,11.88,11.98
+0.07,11.88,11.99
+0.07,11.90,12.00
+0.06,11.99,12.10
+0.06,11.85,11.95
+0.07,11.93,12.04
+0.07,11.96,12.07
+0.07,11.86,11.97
diff --git a/graph/benchmarking/no_render_2_itr/bench.sh b/graph/benchmarking/no_render_2_itr/bench.sh
@@ -1,5 +0,0 @@
-while [ 1 ]; do
- /usr/bin/time -o out -f '%S,%U,%e' python3 prim.py >/dev/null 2>&1
- cat out | tee -a v100000e1000000nosc
- sleep 10
-done
diff --git a/graph/benchmarking/no_render_2_itr/prim.py b/graph/benchmarking/no_render_2_itr/prim.py
@@ -1,80 +0,0 @@
-import heapq
-import random
-import math
-
-VERTICES = 100000
-EDGES = 1000000
-
-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
-
-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 __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 = []
-for i in range(0,EDGES):
- k1 = None
- k2 = None
- while k1 == k2:
- k1 = random.choice(list(graph.keys()))
- k2 = random.choice(list(graph.keys()))
-
- edge = Edge(k1,k2)
- graph[k1].append(edge)
- graph[k2].append(edge)
- edge_list.append(edge)
-
-
-edge_heap = []
-visited_vertices = set()
-
-mst = []
-
-start = random.choice(list(graph.keys()))
-start.visited = True
-visited_vertices.add(start)
-for edge in graph[start]:
- heapq.heappush(edge_heap, edge)
-
-while True:
- 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
- mst.append(item)
- for edge in graph[new_vertex]:
- heapq.heappush(edge_heap, edge)
diff --git a/graph/prim.py b/graph/prim.py
@@ -56,12 +56,13 @@ while True:
edge_list = []
+ keys = list(graph.keys())
for i in range(0,EDGES):
k1 = None
k2 = None
while k1 == k2:
- k1 = random.choice(list(graph.keys()))
- k2 = random.choice(list(graph.keys()))
+ k1 = random.choice(keys)
+ k2 = random.choice(keys)
edge = Edge(k1,k2)
graph[k1].append(edge)
@@ -74,7 +75,7 @@ while True:
mst = []
- start = random.choice(list(graph.keys()))
+ start = random.choice(keys)
start.visited = True
visited_vertices.add(start)
for edge in graph[start]:
