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

11–20 of 48 posts

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

#11

Post by Cieric »

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.

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 spacetimedb, thought it'd be fun to use zig with). But information about things like primary keys, auto increments, constraints and similar all has to live in a different structure completely untied to the original struct or function. I'd like to be able to tie those things together easily to avoid mistakes and confusion. I have different workarounds that I've tried, but nothing that's universal for all my test cases.

For syntax there are a few things that I'm iffy on, but nothing that I'd consider a deal breaker. I found it very easy to read right out of the gate, which is basically the only thing I need to really learn a new language (probably the only reason I haven't learned rust yet.)

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

#12

Post by ww520 »

duped wrote: post #10

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

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.

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

#13

Post by nerdponx »

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 standard library was to implement linear MRO for classes: https://bugs.python.org/issue17005

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

#15

Post by duped »

ww520 wrote: post #12
duped wrote: post #10

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

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

How are the subsets defined?

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

#16

Post by ww520 »

sharmasachin98 wrote: post #8

Curious: have you benchmarked it against any similar tools in other languages (like Go or Rust) for comparison?

No. I haven't got the chance to benchmark against others. When I ran the benchmarks in the library, I could process 1 million pairs of dependency in 10's of milliseconds, in my 5-year old laptop.

  Testing 1000000 items, 1-to-1 chaining dependency.
    Add dependency 1000000 items. Time: 93ms, 10645885 items/s, 93 ns/item
              Sort 1000000 items. Time: 113ms, 8795778 items/s, 113 ns/item

  Testing 1000000 items, 1-to-4 chaining dependency.
    Add dependency 1000000 items. Time: 87ms, 11428323 items/s, 87 ns/item
              Sort 1000000 items. Time: 44ms, 22508986 items/s, 44 ns/item

  Testing 1000000 items, 1-to-10 chaining dependency.
    Add dependency 1000000 items. Time: 102ms, 9748793 items/s, 102 ns/item
              Sort 1000000 items. Time: 31ms, 31707077 items/s, 31 ns/item

  Testing 1000000 items, 1-to-10 chaining dependency, with max_range set.
    Add dependency 1000000 items. Time: 25ms, 39460028 items/s, 25 ns/item
              Sort 1000000 items. Time: 31ms, 31633556 items/s, 31 ns/item

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

#17

Post by ww520 »

duped wrote: post #15
ww520 wrote: post #12

Earlier quoted context omitted.

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

How are the subsets defined?

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.

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

#18

Post by airstrike »

Cieric wrote: post #11
kreco wrote: post #3

Earlier quoted context omitted.

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

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…

Just wanted to say that Rust may look strange early on but very, very quickly becomes entirely natural, so don't let that be the reason why you haven't learned it is my unsolicited input

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

#19

Post by codethief »

klysm wrote: post #6
kreco wrote: post #3

Earlier quoted context omitted.

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

Readability (in the sense of "How fast can the average developer parse code in the given language?") and proneness to errors are a thing, though.

Consider, e.g., how in TypeScript object literals ({ a: b, c: d, e }), object types ({ a: b; c: d; }) and object destructuring ({ a, c, e } = … ) can all look very similar. Same thing for lambdas ((a: b) => b) and function types ((a: b) => b). Also, additional parentheses are needed to prevent the compiler from mistaking an object literal ({ … }) for a function body ({ … }) when it is returned in a lambda expression. In short: Some of TypeScript's syntactic constructs are heavily overloaded and their meaning depends on the context.

For an example of proneness to errors, consider that in Nix function calls ( …) and lists ([ …]) look almost the same and it's very easy to confuse the two and mess up, e.g.

``` let foo = [ item1 myFunction "arg1" "arg2" item3 ] ```

defines a list with 5 items, not 3, due to missing parentheses around the function call.

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

#20

Post by Cieric »

airstrike wrote: post #18
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…

Just wanted to say that Rust may look strange early on but very, very quickly becomes entirely natural, so don't let that be the reason why you haven't learned it is my unsolicited input

Yeah, I just haven't needed the memory safety that comes with it and I don't have the same gripes everyone else has with c's include system. At this point it just doesn't have anything to offer that I really care about. I only learned zig because of the comptime stuff and some ease of use when it came to tls encryption. I'm a little interested in rust macros, but that's really it and I don't think that's enough to learn a new language. I'm sure I'll eventually have a project where memory safety (with speed) is a priority, but to this point it's just never come up at work or the projects I work on in my free time.
Post reply on HN