Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Zig Topological Sort Library for Parallel Processing

github.com

Post reply on HN
Print view View original

1–10 of 48 posts

Show HN: Zig Topological Sort Library for Parallel Processing

#1

Post by ww520 »

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 HN: Zig Topological Sort Library for Parallel Processing
github.com

Re: Show HN: Zig Topological Sort Library for Parallel Processing

#2

Post by Cieric »

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?

Re: Show HN: Zig Topological Sort Library for Parallel Processing

#3

Post by kreco »

Cieric wrote: post #2

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 nee…

Could you describe briefly what feature you are sorely missing?

I like the language intention but I can't get past the syntax.

Re: Show HN: Zig Topological Sort Library for Parallel Processing

#4

Post by ww520 »

Cieric wrote: post #2

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 nee…

> 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.

Re: Show HN: Zig Topological Sort Library for Parallel Processing

#5

Post by klysm »

ww520 wrote: post #4
Cieric wrote: post #2

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 nee…

> 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 some…

I was surprised to see this as a library at all - isn’t it trivial especially for small collections?

Re: Show HN: Zig Topological Sort Library for Parallel Processing

#6

Post by klysm »

kreco wrote: post #3
Cieric wrote: post #2

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 nee…

Could you describe briefly what feature you are sorely missing? I like the language intention but I can't get past the syntax.

Syntax is so much less important that semantics that it isn’t even really worth talking about in my opinion

Re: Show HN: Zig Topological Sort Library for Parallel Processing

#7

Post by ww520 »

klysm wrote: post #5
ww520 wrote: post #4

Earlier quoted context omitted.

> 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 some…

I was surprised to see this as a library at all - isn’t it trivial especially for small collections?

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.

Re: Show HN: Zig Topological Sort Library for Parallel Processing

#10

Post by duped »

> Generating dependence-free subsets for parallel processing.

Unsure how this is defined (*) but graph cutting approaches to concurrent task scheduling is both pessimistic (poor utilization of available resources) and (iirc) NP-hard, so you pay an big cost upfront.

On the other hand, if you know the indegree/outdegree of each node at the time they are visited (meaning the graph is static) you can run Kahn's algorithm concurrently and put each node into a shared work queue. You can optimize that further by having per-thread work queues and stealing between them. Depending on what the nodes represent there are even more optimizations and heuristics, concurrent task scheduling is a hard problem.

* imagine the graph

(a, b) (a, c) (b, d) (c, d)

Is it possible to get nodes b and c in parallel "subsets" in your library?

Post reply on HN