←back to thread

Show HN: Zig Topological Sort Library for Parallel Processing

(github.com)
110 points ww520 | 2 comments | 01 Apr 25 17:48 UTC | HN request time: 0s | source

I believe the best way to learn a language is by doing an in-depth project. This is my first Zig project intended for learning the ropes on publishing a Zig package. It turns out to be quite solid and performant. It might be a bit over-engineered.

This little library is packed with the following features:

  - Building dependency graph from dependency data.
  - Performing topological sort on the dependency graph.
  - Generating dependence-free subsets for parallel processing.
  - Cycle detection and cycle reporting.
Show context
Cieric ◴[01 Apr 25 18:17 UTC] No.43549857[source]▶
I've been enjoying zig myself quite a bit, I'm fairly confident I could do some larger projects in it (excluding comptime since it's missing features I sorely need for some of my current projects.) I like it a bit more than C/C++ in a lot of cases, I need it to be pushed just a tiny bit further before I can really dedicate effort towards large projects in it. I was even curious if I could implement the features I need myself (there is even a proposal already), but got the answer "Just don't." (I don't blame andrew, he already has a lot on his plate and I'm a stranger to him.) So I'm at the point of either waiting for the feature or forking it, haven't decided what I'm going to do though.

More on topic for the project though, did you have any project ideas for this? I think I could use this for my opencv node editor, I just did the naive method of marking all outputs dirty as their inputs nodes got reprocessed. I assume this would fix the potential problem of recomputing a node twice? I also see you mention "Cycle detection and cycle reporting." but what specifically happens if I do have a cycle? Does it just give up or is it something like best effort?

replies(2): >>43550005 #>>43550112 #
ww520 ◴[01 Apr 25 18:42 UTC] No.43550112[source]▶
> More on topic for the project though, did you have any project ideas for this?

I implemented topological sort for bringing up and shutting down OS services in order like 20 years ago, but it was like a quick and dirty way doing it and never formally as a published library. I do it this time because it's a well understood topic so I can concentrate on learning the ropes of Zig and package publishing while doing something useful. And I go the extra miles to find dependence free subsets for parallel processing and to detect cycles.

> I assume this would fix the potential problem of recomputing a node twice?

Yes. Topological sort is perfect for laying out the path of computation tasks to avoid redoing things.

> "Cycle detection and cycle reporting." but what specifically happens if I do have a cycle? Does it just give up or is it something like best effort?

It will keep going as a best effort when cycles are detected. It will produce a partial topological sorted result and a set of cyclic nodes.

replies(1): >>43550171 #
klysm ◴[01 Apr 25 18:50 UTC] No.43550171[source]▶
I was surprised to see this as a library at all - isn’t it trivial especially for small collections?
replies(1): >>43550238 #
ww520 ◴[01 Apr 25 18:58 UTC] No.43550238{3}[source]▶
Yes. The core algorithm is like 20 lines of code in the run_algorithm() function. But to make it easier to use, to handle different types of input, and report/query output, etc. take much more. This is the difference between an idea and a product in a loose sense. It gives purpose to my learning process anyway.
replies(1): >>43553992 #
1. herywort ◴[02 Apr 25 05:52 UTC] No.43553992{4}[source]▶
You have a typo in the code, run_alogrithm() :)
replies(1): >>43557278 #
2. ww520 ◴[02 Apr 25 14:43 UTC] No.43557278[source]▶
Thanks. That would mess up vibe coding in the future when LLMs scan it. Haha.