General Performance Improvements

[JBloss1517]

The goal of this issue is to improve the over all performance of pynite. This would close #251 and #189. When I was profiling the usage of largish models, it was clear there were a handful of bottlenecks that slowed the whole thing down. As an example, if you see @angelmusonda profile in #251, you will see PhysMember.descritize takes up 16.6s of the total 25.9 secs.

My plan would include:

• Introduce a KD tree as a second node storage used for faster near node queries.
• Use the KD tree to improve the performance of FEModel3D.merge_duplicate_nodes method
• Use the KD tree to improve the performance of PhysMember.discretize method
• Use a csr_matrix when partitioning matrices in the Analysis._partition method
• Add some unit tests around merge_duplicate_nodes to prevent regression from new approach
• Add some unit tests around discretize method to prevent regression
• Add internal caching of expensive computed fields in Quad3D and Member3D to avoid recomputing the same value multiple times

My current plan with the KD tree is to build it when you call FEModel3D.analyze and keep using it until you add a new node. For most models with only one call to analyze, this should keep the time to build it to a minimum. I would use the scipy.spatial.KDTree since scipy is already a project dependency. The KD Tree would only be used for near node queries (at least for now) and leave the other operations on the nodes using the internal nodes dictionary.

I would love some feedback though from other pynite users, if there are other things that are relatively simple that the KD tree would help out with. Or please speak up if you think the KD approach is not a good idea.

And for those not familiar with the KD tree, this Wikipedia link to k-d tree might be helpful to understand how they can help us improve the finding of near nodes.

Current work is being done here: https://github.com/Apex-Engineers-Inc/Pynite/tree/issue-269-general-performance-improvements

---

2025.06.26 - Update: Currently on my machine the full test suite started off taking 166s, but after making these changes I have checked off so far, the test suite now takes 93s (~1.78x speed up so far). But testing my own test project with only framing members, it went from 15.8s to 4.5s (~3.5x speed up).
Upwards of 90% of the test suite time is the test_tank.py which contains numerous quad elements. I am currently looking into getting this down further as I can see a small handful of methods are taking the bulk of time.

[connorferster]

@JBloss1517 I think I get the idea of using the KD tree but it would take me some real sitting-and-thinking to implement it myself so I am glad you are eager-and-able to do it! I have found that there are some problems that become much easier to solve when you have a graph-based structure (e.g. chains of connected geometries in sectionproperties) and this sounds like exactly one of those problems.

I am excited to see your progress!

[JWock82]

I've implemented a bounding box approach to PhysMember.descritize in the latest development version of Pynite. @JBloss1517 I'm curious how it improves your large model solve times. If there's a big difference I'll continue to add it to merge_duplicate_nodes. Another option I'd consider is a uniform grid. From what I've learned, a k-d tree is a good option for large models, but it brings with it a reliance on SciPy, which is currently an optional dependency. It would become a required dependency.

[JBloss1517]

I really like the simplicity of your approach. I'll test it out on some larger models and see if it makes a dent in the performance (at the very least it's an easy start).

Regarding the KD tree/scipy becoming a required dependency, I completely understand the hesitation, its not a small dependency to add if you don't want/need it. I made some good progress on my branch, but it has since stalled due to the changes becoming too big for me to feel comfortable creating a PR. I would rather incorporate several little PRs so as to not introduce breaking changes and adding a bunch of unnecessary complexity.

I'll say, having a few experimental branches on my fork centered around performance (mainly to see how far I could push the library and learn some things in the process), I was seeing some of the best and easiest wins were had by simply caching things so they don't have to be recomputed multiple times. I'm happy to create a small PR with these changes so you can see them and consider if we want to add them in as well.

[JBloss1517]

I profiled my particular models I was running (which are 2x framed walls with every top and bottom plate, stud, header, jack, and king modeled) and was seeing about 1.5x speed improvement with the changes you made 🎉.

Doing a grid approach might save more time by not needing to iterate over all nodes in your filter, but a bounding box filter of all nodes down to only those that are inside a bounding box before processing them is probably sufficiently fast enough for now. But, if you have the time for something more complex, faster is always welcomed 😀.

[JBloss1517]

One more thing, I know the readme says scipy isn't a requirement, but it looks like it's being included anyways since it's in the dependencies section in setup.py. We should probably move that into one of the optional dependency sections.

https://github.com/JWock82/Pynite/blob/main/setup.py#L22-L27

[JWock82]

That’s right. You’re jogging my memory. On a recent update I switched scipy to be an included package. The solvers use it by default to use sparse matrices, so it made sense to do so. A K-D tree is probably the best long-term strategy, but until then I’m glad we’ve got at least a little bit of a boost.

[JWock82]

I just implemented a keyed-grid approach to merge_duplicate_nodes in the development version. This should greatly improve solve time on large models. Let me know what you think.