FilesExpand file tree

 main

/

benchmark.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

136 lines (104 loc) · 4.28 KB

 main

/

benchmark.py

Copy path

Top

File metadata and controls

• Code
• Blame

136 lines (104 loc) · 4.28 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

"""

Generate performance comparison figure for Tier 1 documentation.

Compares naive O(n²) vs KDTree O(n log n) implementations.

Usage (from backend directory):

python benchmark.py

Outputs:

benchmark_results.png - Performance comparison figure

"""

import numpy as np

import matplotlib.pyplot as plt

import time

from boids.flock import Flock, SimulationParams

from boids.flock_optimized import FlockOptimized

def run_benchmark():

"""Run benchmark and return results."""

results = {

'n': [],

'naive_ms': [],

'optimized_ms': []

}

flock_sizes = [50, 100, 150, 200, 300, 400, 500]

num_steps = 100

for n in flock_sizes:

print(f"Benchmarking N={n}...")

np.random.seed(42)

params = SimulationParams()

# Create flocks

naive_flock = Flock(num_boids=n, params=params)

np.random.seed(42)

optimized_flock = FlockOptimized(num_boids=n, params=params)

# Warm up

for _ in range(10):

naive_flock.update()

optimized_flock.update()

# Time naive

start = time.perf_counter()

for _ in range(num_steps):

naive_flock.update()

naive_time = (time.perf_counter() - start) / num_steps * 1000

# Time optimized

start = time.perf_counter()

for _ in range(num_steps):

optimized_flock.update()

optimized_time = (time.perf_counter() - start) / num_steps * 1000

results['n'].append(n)

results['naive_ms'].append(naive_time)

results['optimized_ms'].append(optimized_time)

return results

def create_figure(results):

"""Generate performance comparison figure."""

fig, axes = plt.subplots(1, 2, figsize=(12, 5))

n = results['n']

naive = results['naive_ms']

optimized = results['optimized_ms']

speedup = [naive[i] / optimized[i] for i in range(len(n))]

# Plot 1: Execution time comparison

ax1 = axes[0]

ax1.plot(n, naive, 'o-', label='Naive O(n²)', linewidth=2, markersize=8, color='#e74c3c')

ax1.plot(n, optimized, 's-', label='KDTree O(n log n)', linewidth=2, markersize=8, color='#27ae60')

ax1.set_xlabel('Number of Boids', fontsize=12)

ax1.set_ylabel('Frame Time (ms)', fontsize=12)

ax1.set_title('Execution Time vs Flock Size', fontsize=14)

ax1.legend(fontsize=11)

ax1.grid(True, alpha=0.3)

ax1.set_xlim(0, max(n) + 50)

ax1.set_ylim(0, max(naive) * 1.1)

# Add 60fps and 30fps reference lines

ax1.axhline(y=16.67, color='gray', linestyle='--', alpha=0.7, label='60 FPS')

ax1.axhline(y=33.33, color='gray', linestyle=':', alpha=0.7, label='30 FPS')

ax1.text(max(n) - 30, 18, '60 FPS', fontsize=9, color='gray')

ax1.text(max(n) - 30, 35, '30 FPS', fontsize=9, color='gray')

# Plot 2: Speedup factor

ax2 = axes[1]

bars = ax2.bar(n, speedup, color='#3498db', width=30, edgecolor='black')

ax2.set_xlabel('Number of Boids', fontsize=12)

ax2.set_ylabel('Speedup Factor (x)', fontsize=12)

ax2.set_title('KDTree Speedup vs Naive Implementation', fontsize=14)

ax2.grid(True, alpha=0.3, axis='y')

# Add value labels on bars

for bar, s in zip(bars, speedup):

ax2.text(bar.get_x() + bar.get_width()/2, bar.get_height() + 0.2,

f'{s:.1f}x', ha='center', fontsize=10)

plt.tight_layout()

plt.savefig('benchmark_results.png', dpi=150, bbox_inches='tight')

print("Figure saved to benchmark_results.png")

return fig

def print_table(results):

"""Print markdown table for documentation."""

print("\n### Performance Results\n")

print("| Boids | Naive (ms) | KDTree (ms) | Speedup |")

print("|------:|-----------:|------------:|--------:|")

for i in range(len(results['n'])):

n = results['n'][i]

naive = results['naive_ms'][i]

opt = results['optimized_ms'][i]

speedup = naive / opt

print(f"| {n} | {naive:.2f} | {opt:.2f} | {speedup:.2f}x |")

if __name__ == "__main__":

print("Running performance benchmark...")

print("This compares Naive O(n²) vs KDTree O(n log n) implementations.\n")

results = run_benchmark()

print("\nGenerating figure...")

create_figure(results)

print_table(results)