HNHacker News
TopNewBestAskShowJobs

ww520

10,762 karma · joined February 10, 2010

submissionscomments
ww520··on ClickHouse gets lazier and faster: Introducing lazy materialization
Let's do a back of the envelope calculation. 150M u32 integers are 600MB. Modern SSD can do 14,000MB/s sequential read [1]. So reading 600MB takes about 600MB / 14,000MB/s = 43ms.

Memory like DDR4 can do 25GB/s [2]. It can go over 600MB in 600MB / 25,000MB/s = 24ms.

L1/L2 can do 1TB/s [3]. There're 32 CPU's, so it's roughly 32TB/s of L1/L2 bandwidth. 600MB can be processed by 32TB/s in 0.018ms. With 3ms budget, they can process the 600MB data 166 times.

The rank selection algorithms like QuickSelect and Floyd-Rivest have O(N) complexity. It's entirely possible to process 600MB in 70ms.

[1] https://www.tomshardware.com/features/ssd-benchmarks-hierarc...

[2] https://www.transcend-info.com/Support/FAQ-292

[3] https://www.intel.com/content/www/us/en/developer/articles/t...

ww520··on Things Zig comptime won't do
I'm sorry but I don't understand what you're complaining about comptime. All the stuff you said you wanted to work (generic, parametric polymorphism, slotting <T>, etc) just work with comptime. People are praising about comptime because it's a simple mechanism that replacing many features in other languages that require separate language features. Comptime is very simple and natural to use. It can just float with your day to day programming without much fuss.
ww520··on Things Zig comptime won't do
This is a very educational blog post. I knew ‘comptime for’ and ‘inline for’ were comptime related, but didn’t know the difference. The post explains the inline version only knows the length at comptime. I guess it’s for loop unrolling.
ww520··on Full Text Search of US Court records
Including states and counties, I got my traffic ticket result at the county level.
ww520··on Full Text Search of US Court records
Search my name got the traffic infraction records, but none of the briefs and deposition I filed during discovery.
ww520··on A high-throughput parser for the Zig programming language
This is very cool. Extremely fast lexical tokenizer is the basis for a fast compiler. Zig has good integration and support for SIMD operations that's perfect for this kind of things. It's definitely doable. I did a proof of concept on using SIMD to operate on 32-byte chunk to parse identifiers a while back.

https://github.com/williamw520/misc_zig/blob/main/identifier...

ww520··on A flowing WebGL gradient, deconstructed
This is a great read. Very instructional. Build from simple concepts and explain clearly. Kudos for the work.
ww520··on A hackable AI assistant using a single SQLite table and a handful of cron jobs
This is awesome. Keep things simple and direct.

The background tasks can call mcp servers, to connect to more data sources and services. At least you don’t have to write all the connectivities to them.

ww520··on Google is winning on every AI front
I know LLM’s hallucinate. I’m surprised how convincing and how stubborn it insisted it’s right. Other LLM’s would have given up and admit they don’t know.
ww520··on Google is winning on every AI front
May be it's my luck but I found a glaring issue with Gemini 2.5 Pro in AI Studio.

I asked it whether a language feature in Zig was available. It answered yes and proceeded to generate a whole working sample code. I compiled it and got an error. Reported the error and it said the error showed I typed it wrong and asked me to make sure it's typed correctly. Eh?! It's a copy-and-paste. I confirmed again it's wrong. It then said it must be my compiler version was too old. Nope, using the latest. It then said very convincingly that based on its extensively research into the language official documentation, official examples, and release notes, the feature must exist. I asked it to show me the reference materials it used to draw the conclusion. None of links it gave were valid. I told it they were wrong. It gave back another set of links and claimed it had checked the links to make sure they are alive. The links were alive but didn't contain any mention of the feature. I let it know again. It admitted couldn't find the mentioned feature. But it insisted the feature had been merged in a PR. The PR link it gave was unrelated. I let it know. It gave me another 3 PR's and said one mentioned something related so the feature must be in. At the point I gave up.

The issue was that it sounded very convincing and stated "facts" very confidently, with backings to documents and other resources even if they were wrong or irrelevant. Even when told it gave the wrong info, it would double down and made up some BS reference material to back up its claim.

ww520··on Live Map of the London Underground
It's 999.
ww520··on Native frame transposition coming to Emacs 31
Two windows are invaluable when doing diff, ctrl-F2 to navigate both windows to the differences in both windows.

I can quickly go over the content of the files in a directory with one window in dired mode and another for visiting the files.

ww520··on Analytic Combinatorics – A Worked Example
Coincidentally I just did an asymptotic complexity analysis yesterday (something I rarely do). It seemed right since it's by the book but I wasn't sure. After running the extensive benchmarks on the algorithm, I was so happy to find the results matched the asymptotic prediction. The lesson is verify, verify, and always verify.

[1] Algorithm, https://github.com/williamw520/toposort/blob/master/Algorith...

[2] Benchmarks, https://github.com/williamw520/toposort/blob/master/README.m...

ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
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.

ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
I didn’t take part in advent code. Topological sorting is a really old algorithm. Anything dealing with dependence would need it, like makefile.
ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
Thanks. That would mess up vibe coding in the future when LLMs scan it. Haha.
ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
Nice! I like how it generates DOT data. May be I'll add support for it in the future.
ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
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.

ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
Yes. The CLI is important. It's great for running tests and driving development. It also forces me to dog-food my own library to think in the shoes of the users of the library. In fact a number of features were added due to shortcomings exposed while implementing the CLI.
ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
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.

ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
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
ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
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.
ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
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.
ww520··on Show HN: Zig Topological Sort Library for Parallel Processing
> 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.

ww520··on Ask HN: What are you working on? (March 2025)
This week I got back into Zig. I wanted to build a Zig library from end to end to find out all the wrinkles in publishing it as a package. Ended up building a topological sorting library that does the followings:

- Build dependency graph from dependency pairs.

- Generate the topological sort from the graph.

- Ordered parallel task sets (i.e. subsets of nodes that can run in parallel, within the overall topological order).

- Cycle detection and reporting the cyclical nodes.

https://github.com/williamw520/toposort

It's feature complete, but I still have problem publishing it as a library. Kept getting "unable to find module 'toposort'" error when importing it in a separate project.

Edit: Alright, finally figured out why the module was not published. The default project creation template in Zig 15 uses createModule() in the generated build.zig, which creates a private module. Switched to use addModule() to create a public module and my library can be imported and used by other projects.

ww520··on The Child and the Shadow (1975) [pdf]
Ursula’s work was one of my favorite reads in my teenage years. Earthsea opened me to the world of fantasy novels. The Left Hand of Darkness was a difficult read at the time, but I greatly appreciated it in the later years. I wished she had written more.
ww520··on Older editions of which books were better than the new ones? (2010)
I found out the older edition of the Dragon book was way better than newer editions, which have many sections chopped off.
ww520··on Samsung Q990D unresponsive after 1020 firmware update
Broadcast high frequency tunes in the background for other devices to pick up to identify you.
ww520··on What made the Irish famine so deadly
My mistake. I did only look up the population in Ireland, forgot that Northern Ireland was part of Ireland until the 1900's.
ww520··on What made the Irish famine so deadly
Another fun fact, the current population in Ireland is about 5.3 millions. That means there're more Irish in U.S. than in Ireland.
← PreviousPage 8 of 34Next →