←back to thread

Show HN: Zig Topological Sort Library for Parallel Processing

(github.com)
110 points ww520 | 4 comments | 01 Apr 25 17:48 UTC | HN request time: 0.854s | 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
duped ◴[01 Apr 25 19:01 UTC] No.43550260[source]▶
> 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?

replies(1): >>43550304 #
ww520 ◴[01 Apr 25 19:05 UTC] No.43550304[source]▶
Yes. It would produce dependence-free subsets. I just ran your sample (assuming a,b means a depends on b).

  Topologically sorted sets: [ { d }  { b c }  { a }  ]
  Topologically sorted list: [ d b c a ]
  Nodes: [ a b c d ]
  Dependency tree:
  [ d ]
    d -> [ b c ]
      b -> [ a ]
        a ->
      c -> [ a ]
        a ->
The dependence-free subset finding is probably not exhausting and optimal. I haven't gone through formal proofing. It's opportunistic and best effort at best currently.
replies(1): >>43550520 #
1. duped ◴[01 Apr 25 19:30 UTC] No.43550520[source]▶
How are the subsets defined?
replies(1): >>43550769 #
2. ww520 ◴[01 Apr 25 20:02 UTC] No.43550769[source]▶
At every round of the algorithm, all nodes with 0 in-degree (i.e. they are not depending on anyone) are collected as a dependence-free subset.

They serve as the root set to the rest of the graph for the current round. The depending nodes reached from root set have their in-degree decremented. When their in-degrees reach 0, they are added to the next root set.

I'm using double-buffering to maintain the current root set for processing and to collect the next root set for the next round, instead of using a queue as in Kahn's algorithm. At the end of the round, I simply swap the double-buffers. It's very efficient. When the next root set is empty, all nodes have been processed.

replies(1): >>43557666 #
3. duped ◴[02 Apr 25 15:19 UTC] No.43557666[source]▶
Do you define "in degree" as the number of incoming edges from nodes that have not been visited/sorted yet?

I believe what you've implemented is equivalent to Kahn's algorithm. Your double buffer is the queue.

replies(1): >>43561204 #
4. ww520 ◴[02 Apr 25 20:34 UTC] No.43561204{3}[source]▶
It's a variant to the Kahn's algorithm. Here's the description in the comment on the function.

  // This is a variant to the Kahn's algorithm, with additions on
  // finding dependence-free subsets and finding the cyclic nodes.
  //
  // This algorithm iteratively finds out the root sets of the graph.
  // 1. Find the first root set of the graph.
  // 2. Remove the nodes of the root set from the graph.
  // 3. Find the next root set. Go to 2 until the graph is empty.
  // A root set consists of nodes depending on no other nodes, i.e.
  // nodes whose incoming link count is 0.
The successive root sets form a topological order.

The in-degree of a node is the count of the incoming links of the leading nodes that the node is depending on. The in-degree can change as other nodes are removed from the graph.

Kahn's algorithm uses a queue to hold the pending nodes and works on one node at a time. My insight is that it's simpler to treat the root nodes as sets, and to partition the root nodes into the current root set and the next root set, which work nicely with the double-buffer mechanism. As a benefit, the nodes in a root set are dependence-free with regard to the current round and can be used for parallel processing.