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

31–40 of 48 posts

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

#31

Post by ww520 »

jitl wrote: post #27

For something like task scheduling in a build system, if you use an up-front partition of the tasks like this, you may have a task that has all its dependencies fulfilled because tasks may have different durations, but still remains unscheduled. For example, with this input: $ cat data.file root: parentA parentB parentA: C D parentB: E F Asking the package tool for the sorted sets gives me: $ ./zig-out/bin/toposort-c…

That's a great point! Unfortunately Topological Sort generates a linear order, forcing nodes to run one after another. This library attempts to bring some parallel processing into the picture by grouping dependence-free nodes together. This produces a linear batches.

  {C D E F}, {parentA parentB}, {root}
Within a batch, nodes can run parallel. Between batches, they still need to run one after another.

What you're asking for is to partition the dependency graph according to node dependency with minimum span.

  { {C D} parentA } \
  { {E F} parentB } - {root}
Or with a shared leader.

  { {C D S} parentA } \
  { {E F S} parentB } - {root}
And on top of that, add node weight into the consideration. That's hard.

For now, you can send notification to a dependent when the leading task finishes. E.g. When C finishes, notifies parentA. When D finishes, notifies parentA. When parentA notices that all its leading tasks have done, it can start.

The library can help in maintaining the dependency relationship and let the task query its leaders and dependents.

For task running, it would be a separate library using the TopoSort library and specifically geared toward scheduling tasks.

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

#32

Post by emmanueloga_ »

For those that have not implemented toposort or don't remember it: 1) only directed graphs without cycles can be topologically sorted (DAGs) 2) there can be more than one topological order and 2) reverse post order of depth first traversal from every unvisited node shields a topological order.

In JavaScript:

    function toposort(graph = { a: ['b', 'c'], b: ['d'] }) {
      const order = [];
      const visited = new Map();
      
      function dfs(node) {
        const status = visited.get(node);

        if (status === 1) throw new Error("Cycle found.");
        if (status === 2) return;

        visited.set(node, 1); // In progress.
        const adjacent = graph[node] ?? [];
        for (const neighbor of adjacent) dfs(neighbor);
        visited.set(node, 2); // Done.

        order.unshift(node); // Reverse post order.
      }

      for (const node in graph) {
        if (!visited.has(node)) dfs(node);
      }

      return order;
    }

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

#34

Post by ww520 »

hbbio wrote: post #33

Congrats! I like Zig a lot even though I never implemented a full project with it. FWIW we had to build a related lib in TypeScript: https://github.com/okcontract/graph as part of the runtime of https://github.com/okcontract/cells

Nice! I like how it generates DOT data. May be I'll add support for it in the future.

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

#35

Post by Cieric »

kreco wrote: post #29
Cieric wrote: post #11

Earlier quoted context omitted.

For me it's all comptime stuff and it's kind of arbitrary things like parsing out the type information of a function doesn't include the name of the function parameters, but basically everything else that has a name has that information present in their info structure. The other thing is tags, being able to tag things that I can parse at compile time. I'm making something close to a database orm, (specifically it's s…

Thanks for the reply. I totally understand how those two features could be useful. For the parameter name feature, I can't imagine a strong reason for not implementing it (I mean, apart of "we have other stuff to prioritize"). For the tag I could see an attribute system like in C++ [0] On a tangential topic, I believe that's exactly the Pandora box of meta-programming. [0] https://en.cppreference.com/w/cpp/language/a…

I think at one point they rejected the idea, but I think it was from 2018 or so. The cpp attributes does seem like what I'd want, but yeah c++ compile time code isn't good enough for what I need.

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

#36

Post by paulddraper »

chubot wrote: post #9

Hm this reminds me that the Python stdlib has grown a module for topological sorting fo a graph: https://docs.python.org/3/library/graphlib.html I haven't used it yet, I'd be curious if anyone has

It’s a common algorithmic need.

Not as common as array sort. But still common.

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

#37

Post by herywort »

ww520 wrote: post #7
klysm wrote: post #5

Earlier quoted context omitted.

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.

You have a typo in the code, run_alogrithm() :)

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

#38

Post by genewitch »

ww520 wrote: post #31
jitl wrote: post #27

For something like task scheduling in a build system, if you use an up-front partition of the tasks like this, you may have a task that has all its dependencies fulfilled because tasks may have different durations, but still remains unscheduled. For example, with this input: $ cat data.file root: parentA parentB parentA: C D parentB: E F Asking the package tool for the sorted sets gives me: $ ./zig-out/bin/toposort-c…

That's a great point! Unfortunately Topological Sort generates a linear order, forcing nodes to run one after another. This library attempts to bring some parallel processing into the picture by grouping dependence-free nodes together. This produces a linear batches. {C D E F}, {parentA parentB}, {root} Within a batch, nodes can run parallel. Between batches, they still need to run one after another. What you're aski…

Did you use this library on the advent of code 2024? I'd never heard of topological sorting prior to that problem - and it was real early in the game.

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

#39

Post by jessekv »

nerdponx wrote: post #13
chubot wrote: post #9

Hm this reminds me that the Python stdlib has grown a module for topological sorting fo a graph: https://docs.python.org/3/library/graphlib.html I haven't used it yet, I'd be curious if anyone has

I used it to build a (now permanently unfinished) lightweight DAG runner that uses only the Python standard library, with the intention that you can just copy the .py file into a project and use it without installing anything other than Python on your system. I think it might be of niche use to some people, but I personally wasn't even dogfooding it, I was just scratching an itch. The purpose of adding it to the stan…

I built one too! I started with networkx but migrated to graphlib with python 3.9.

I run it in production for many customers. It's great to have this in the std lib.

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

#40

Post by throwawaymaths »

FL33TW00D wrote: post #24
klysm wrote: post #21

Earlier quoted context omitted.

Sure but I don’t think those examples really matter once you establish basic familiarity with a language. The semantics and constructs a language provides are much more important and debating syntax is missing the forest for the trees

The array syntax is very offensive: `const a = [3]i32{ 1, 2, 3 };` A set is denoted by braces, not an array.

1. using [] drops context-freeness. what is: foo[1]? is that foo type array with one element? or accessing the foo array at index 1?

2. how do you feel about array initialization in C?

3. you can think of {...} as defining memory regions, curlies around code are defining "a memory block of instructions"

Post reply on HN