←back to thread

Show HN: Zig Topological Sort Library for Parallel Processing

(github.com)
110 points ww520 | 1 comments | 01 Apr 25 17:48 UTC | HN request time: 0.198s | 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
sharmasachin98 ◴[01 Apr 25 18:58 UTC] No.43550240[source]▶
Curious: have you benchmarked it against any similar tools in other languages (like Go or Rust) for comparison?
replies(1): >>43550674 #
1. ww520 ◴[01 Apr 25 19:47 UTC] No.43550674[source]▶
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