Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve parallel pipe scheduler/pipes are slow when there are a lot of them #34

Open
fechan opened this issue Oct 23, 2024 · 0 comments
Labels
ComputerCraft enhancement New feature or request

Comments

@fechan
Copy link
Owner

fechan commented Oct 23, 2024

Several months ago I implemented a greedy edge-coloring algorithm to identify batches of pipes that can run in parallel. Basically, all the pipes are edges between slot group nodes, and each color represents pipes that will be run in parallel. Then each color gets run sequentially.

It's very fast in runtime, but since the coloring can be far from optimal, and each color takes at least 20ms to run because of how Minecraft works, it's probably worth it to use a slower runtime but more optimal coloring algorithm.

DSatur looks like a good bet; the runtime doesn't take a super massive hit O((n+m)logn) if you use a binary heap versus the existing O(n+m), or better with a fibonacci heap. I have a lua binary heap implementation left over from when I made JackJack, so we can use that.

RLF is even slower runtime but better coloring, but maybe if we cache the graph coloring between runs it won't be so bad. We need a way to store a "factory version" every time the factory gets edited, which might be a little involved.

I stopped playing my modded Minecraft playthrough a while ago, so I haven't been motivated to implement this stuff. But if I play more modded again, I might try implementing this.

@fechan fechan added enhancement New feature or request ComputerCraft labels Oct 23, 2024
@fechan fechan changed the title Improve parallel pipe scheduler Improve parallel pipe scheduler/pipes are slow when there are a lot of them Oct 23, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
ComputerCraft enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant