search

grantshandy / fdg

A Force Directed Graph Drawing Library
https://grantshandy.github.io/fdg
MIT License
183 stars 16 forks source link

Performance improvements: SIMD, parallelization... #15

Open yberreby opened 1 year ago

yberreby commented 1 year ago

Hi,

First off, thank you for writing this library, it's a really neat project.

However, I couldn't help but notice the lack of parallelization. This is of consequence, as simulations slow down to a crawl given enough nodes. SIMD may also help a lot. Going one step further, one could run the computations on GPU.

@grantshandy, you mentioned plans to rewrite this or change the API. I wonder if this is already in the pipeline in some way? i.e., would there be interest in a PR to add support for parallelization / SIMD / general performance improvements, or would it get broken very soon by the said refactoring?

grantshandy commented 1 year ago

I've thought about SIMD/GPU improvements, but when I started this project a few years ago I didn't understand GPU programming well enough. I've been meaning to refactor this project for a few months, but I haven't gotten around to it. Once I get to v1.0, I'd love a PR for some parallelization / SIMD / general performance improvements. I'll start on it this week, and write you back when it's ready :)

yberreby commented 1 year ago

Great! Do let me know. I'll be happy to have a go at it when I have some time.

micahscopes commented 9 months ago

@yberreby if you'd like to collaborate on this I'm interested in helping out

yberreby commented 9 months ago

@micahscopes Sure! Waiting for the v1.0, though

grantshandy commented 9 months ago

Oh god I said I would start 3 months ago and I never got around to it 😬. I'm planning on using fdg in one of my upcoming projects though so maybe that will motivate me to get working on it. It's finals week currently but I should have some time opening up soon to commit to it. Sorry for keeping everyone hanging, I'd love your help with performance improvements!

grantshandy commented 9 months ago

@micahscopes @yberreby I've started making a new (more idiomatic/generic) API in the dev branch, any suggestions?

I've also implemented a naively parallelized Fruchterman-Reingold with rayon on the iterators. It seems to only be better on much larger graphs (1000+ nodes). You're welcome to start making PRs there if that interests you :)

micahscopes commented 9 months ago

@grantshandy wow, exciting!

At a glance the Force trait looks nice and flexible, I like it. The only thing I could think to add might be "lifecycle" methods e.g. for stuff like setup or teardown? I'm not sure if that's necessary though

grantshandy commented 9 months ago

@micahscopes I don't think setup/teardown methods are too necessary because you should be able to do all that within the RAII style. e.g. setup resources in the constructor/Default::default() and teardown by implementing Drop yourself.