search

elh / feynman-781

⚛️ Simple, performant graph generator for Feynman diagrams*
MIT License
2 stars 0 forks source link

Documenting: Optimizing the brute force #16

Open elh opened 1 year ago

elh commented 1 year ago

Improvements made in PRs for N=16. Normalized for debug v. release builds. Measured using release build on a 2020 i5 Macbook Pro (and then later on a 2023 M2 Pro Macbook Pro)

Run                                  ms       X faster    graphs/sec
--------------------------------------------------------------------
Initial run                          34112                356K/sec
Remove is_solution check (#3)        3449     9.8x        3.5M/sec
Check fewer undirected edges (#4)    1310     2.7x        9.3M/sec
Assign cell by cell (#5)             1294     ~1x         9.4M/sec
Tightly pack array (#7)              1310     ~1x         9.3M/sec
j_0 and k_0 cursors (#12)            930      1.4x        13.1M/sec
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
UPDATE: ^ on 2023 M2 Pro             482      1.9x        25.2M/sec

Using a tightly packed multidimensional array instead of a vector of arrays was a meaningful performance improvement in debug mode but does not matter in release mode. Perhaps Rust compiler is already optimizing!

. . .

Runs Run N=16

elh commented 10 months ago

Out of curiosity, ran this on my new 2023 M2 Pro Macbook and it was almost twice as fast at 480ms 😮