I am all for performance improvements. But I am a bit skeptical if it is worth making the interface more complicated.

Almost all graph algorithms need some kind of of work buffer, so we could have something like in al algorithms but in the end it should be the job for Julia's allocator to verify if there is some suitable piece of memory lying around. We can help it by using sizehint! with a suitable heuristic.

I agree that this will usually not be relevant; in my case it is though, and is the main reason I made the changes. I also agree that there is a trade off between performance improvements and complications of the API. On the other hand, I think passing such work buffers as optional arguments is a good solution to such trade-offs: for most users, the complication can be safely ignored and shouldn't complicate their lives much.

As you say, there are potentially many algorithms in Graphs.jl that could take a work buffer; in light of that, maybe this could be more palatable if we settle on a unified name for these kinds of optional buffers, so that it lowers the complications by standardizing across methods.
Maybe just work_buffer (and, if there are multiple, work_buffer1, work_buffer2, etc?)

If we do this then all functions should take exactly one work_buffer (possibly a tuple) and have an appropriate function to initialize the buffer. I think it is a major change which should be discussed separately.

• Work buffers for algorithms? #410

So I think if this is really important for your use case you can either

• Create a version that uses a buffer in the Experimental submodule. Currently we don't guarantee semantic versioning there - this allows use to remove things in the future without breaking the API.
• Or as this code is very simple you might just copy it to your own repository.

But just to clarify - your problem is not that you are building graphs by adding edges until they are connected? Because if that is the issue, there is a much better algorithm.

Create a version that uses a buffer in the Experimental submodule. Currently we don't guarantee semantic versioning there - this allows use to remove things in the future without breaking the API.

I won't be able to find the time for factoring this out into the Experimental submodule, unfortunately.
I'm happy to e.g., add an admonition to the docstring, indicating that the work buffer arguments are unstable API which are subject to breakage though. Factoring this into a submodule, piecing it back together, and adding multiple doc-strings across modules, and eventually loading this behind a Graphs.Experimental call is more fiddling than I'm up for.

Or as this code is very simple you might just copy it to your own repository.

Indeed, I have and will just continue to do that, yep.

But just to clarify - your problem is not that you are building graphs by adding edges until they are connected? Because if that is the issue, there is a much better algorithm.

No, I'm not doing that; appreciate the check though.

As a general side note - and please know that I appreciate these reviews very much (!) and your efforts on what is no doubt spare time (!!) - but I wonder if the level of scrutiny and optimization that many PRs here go through is optimal: I understand the intent and the aim of making stable API and of getting good, maintainable code. But I think there's a risk of trading off too much towards these goals, at the cost of vibrancy and community engagement. From my experience here, there's room for leaning more towards "is this better than what we previously had" over "could this be even better".

PRs like this usually happen on time "stolen away" from our day-jobs, and the odds of returning to PRs for edits, however small, go down very quickly with time; similarly, the expectation that a PR will be a multi-iteration process reduces the likelihood it will be made.

I appreciate the feedback, and I lean in the same direction. The JuliaGraphs community calls have pretty much dried up recently and we don't have much of a community to start with, so it's in our best interest to make engagement rewarding instead of tiresome.
I'm expecting an answer this month on funding I applied to which could serve to revitalize this ecosystem, hopefully I'll have good news to share soon.

but in the end it should be the job for Julia's allocator to verify if there is some suitable piece of memory lying around.

After hitting similar problems to op I feel the need to point out that this statement is a bit problematic as a design philosophy in Julia.

Julias garbage collector is slow, and in practice it's on us as developers not to overwork it constantly. Base julia lets us reuse workspaces in sort and LinearAlgebra solves, and the many in-place ! methods.

For me the shortest paths algorithms here are barely useable at production scale (milllions of calls) due to the allocation and garbage collector overheads. I can also just write fast custom methods of everything that our project needs, but the end point of us all doing that is useful code duplicated and scattered through field-specific tools, rather than centralized and usable to the ecosystem.

But I think there needs to be a broad policy to keep things coherent, like: mutated workspaces are either the first argument with a ! method if they are also the return value (as I would do with Graphs.enumerate_paths!) or passed in as keywords like in Base.sort.

But given that kind of framework PRs adding workspace keywords and ! mutating versions shouldn't be too controversial.