Optimization roadmap

[Yomguithereal]

• possible to do attraction & repulsion in same loop to avoid double write to out?
• multithreading
• SoA for autovectorization
• SoA for the BarnesHut itself
• rten_simd
• simd gravity etc.
• cache friendly barnes hut (dfs sorting)
• barnes hut with leaf bucket
• use an enum for leaf or non leaf
• merging attraction into repulsion for parallelization
• numerical optimizations everywhere
• branchless whenever possible
• sorted csr for edges
• niche optim for barnes hut options, use nonmax crate
• document design choices
• single consolidated loop node-wise for parallelization (must sort edges into CSR)
• moving node masses into SoA layout for barnes hut tree?
• find insights: https://github.com/gephi/gephi/tree/master/modules/LayoutPlugin/src/main/java/org/gephi/layout/plugin/forceAtlas2
• weight scaling could happen when building the algorithm
• try to parallelize force application also

[Yomguithereal]

If CSR order, layout must expose current position but not allow to take your data back.

[Yomguithereal]

• leaf bucket 8 nodes
• DFS
• compact tag array
• check offset computation (/2 or /4)
• document what was tried (enum, niche optim, SoA layout), note that adaptative, optimized for f32
• root size squared + depth for barnes?
• consolidation de tout dans la boucle parallèle (need CSR)

[Yomguithereal]

The consolidated version is now the crux of what can be done to improve parallel barnes-hut and avoid sync stalling for gravity, attraction and force application.

[Yomguithereal]

Gephi insights:

• 8 nodes as a parallel task instead of a single one (might be moot against rayon work-stealing)
• track total swinging along with movement?

[Yomguithereal]

• parallel force application (needs to par_iter_mut convergences and over x & y).
• force optimization
• chunking
• simd attraction
• time tree construction and force application
• positions packed with edges (grouped by SIMD)
• k-means repulsion
• flamegraphing
• parallel barnes hut trees

[Yomguithereal]

Barnes-Hut tree construction is 70% of total runtime for skyblogs.