Hacker News Reader

SUPERCILEXon Lockless MPSC/SPMC/MPMC queues are not queues

Fair point, though I'm not sure I agree. MPMC channels underpin pretty much every general task scheduler (take a peek inside tokio or rayon for example). And SPSCs are quite useful for designing custom pipelines. Though I agree that MPMC channels are silly.

SUPERCILEXon Lockless MPSC/SPMC/MPMC queues are not queues

As noted by other commenters, the point I was trying to get across is that the way we implement lockless channels is suboptimal and could be made faster from a theoretical standpoint.

In my benchmarks[1], the average processing time for an element is 250ns with 4 producers and 4 consumers contending heavily. That's terrible! Even if your numbers are correct, 100ns is a bit faster than two round trips to RAM while 33ns is about three round trips to L3 and ~100x slower than spamming a core with add operations. That's slow.

[1]: https://github.com/SUPERCILEX/lockness/blob/master/bags/benc... $ cargo bench -- 8_threads/std_mpmc

SUPERCILEXon Lockless MPSC/SPMC/MPMC queues are not queues

Thanks for sharing, I had not! It sounds like "processor sharing" would be the expected mode of operation for lockless queues. But see my comment to the parent, this is not how they work.

SUPERCILEXon Lockless MPSC/SPMC/MPMC queues are not queues

This is actually a great analogy because it exemplifies the misconceptions people have about lockless queues.

In the example with multiple counters, in real life each counter could shout out a number and have people approach their respective counters in parallel. But this is not how lockless queues work. Instead, the person at the head of the queue holds a baton and when multiple numbers are called, everybody waiting in the queue goes up to the counter of the person holding the baton. Once that head-of-the-queue has made it to the counter, they give the baton to the person behind them who then drags everybody along to their counter. And so on.

The article was arguing for a lockless channel implementation akin to your interpretation of a queue with parallel access to the counters.

SUPERCILEXon Ask HN: Is trusted client compute possible?

So you have to use probabilistic methods, makes sense thanks!

SUPERCILEXon Ask HN: Is trusted client compute possible?

Thanks for the links!

SUPERCILEXon Metric Time

I made something similar a while back where you can set your own start and end time for the "day": https://alexsaveau.dev/10hrday

The point was to be able to divide the day into nicely sized bites for getting stuff done. I chose 10 minutes in an hour for that reason: you can get a small task done in one "minute."

SUPERCILEXon Ask HN: Could you share your personal blog here?

https://alexsaveau.dev/blog

Mostly about performance and project internals.

SUPERCILEXon The fastest rm command and one of the fastest cp commands

Except they are and your claims are trivial to disprove: simply run the benchmarks under perf. You'll find that most of the time is spent on the rwsem which is described here onwards: https://www.kernel.org/doc/html/latest/filesystems/path-look...

SUPERCILEXon The fastest rm command and one of the fastest cp commands

No. Run the benchmark on a tmpfs:

$ hyperfine --warmup 3 -N "./test /dev/shm 8 zip" "./test /dev/shm 8 chain" Benchmark 1: ./test /dev/shm 8 zip Time (mean ± σ): 118.5 ms ± 11.6 ms [User: 92.9 ms, System: 726.6 ms] Range (min … max): 103.6 ms … 143.4 ms 23 runs

Benchmark 2: ./test /dev/shm 8 chain Time (mean ± σ): 235.7 ms ± 11.0 ms [User: 116.4 ms, System: 1537.7 ms] Range (min … max): 220.1 ms … 258.3 ms 13 runs

Summary './test /dev/shm 8 zip' ran 1.99 ± 0.22 times faster than './test /dev/shm 8 chain'

SUPERCILEXon The fastest rm command and one of the fastest cp commands

> is disk IO bottlenecked by NVMe/PCIe limits, or by disk iops limits?

Note that I'm out of my depth here, so this is all speculation. Until we hit hardware limitations (which will be PCIe 6 if I had to guess), I'm pretty sure those are the same thing. One read/write iop = 4KiB. If your PCIe bandwidth is limited to N GB/s, then there are only so many iops you can physically send/receive to/from the SSD, regardless of how many iops the SSD could be capable of processing. So currently we're bottlenecked by PCIe, but I doubt that will continue to be the case.

> again, you're handwaving on what "interfere" means

It depends on how the file system is implemented, but my guess would be that a lock on the inode or block cache entry is acquired.

> do "inode mappings" represent resources with no shared resource constraints?

Those are the contents of the directory. The problem is not reading them, but changing them.

SUPERCILEXon The fastest rm command and one of the fastest cp commands

A directory is a file like anything else that contains a map of names to inodes. If you're trying to add or remove mappings (create or delete files), then clearly some synchronization must occur or the contents of the file will contain garbage. In theory you could get away with a very small critical section that says "lock bytes N through M" of the file, but then how do you deal with disk block alignment (i.e. two pairs of n-m bytes are on the same disk block, so they need to take turns anyway) and how do you deal with I/O errors (the first n-m bytes fail, but the second n-m succeed, now you have a hole with garbage).

Also no need to theorize: run the benchmark I linked for yourself. It clearly shows a massive advantage to having each thread work with its own directory.

SUPERCILEXon The fastest rm command and one of the fastest cp commands

Added a small clarification: "The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention. In brief, file creation or deletion cannot occur at the same time within one directory."

Plus accompanying benchmark: https://alexsaveau.dev/blog/projects/performance/files/fuc/f...

---

> file operations are (almost always) io bound

This is a common misconception. It was presumably true a decade ago, but PCIe is getting exponentially faster every 3 years: https://arstechnica.com/gadgets/2022/06/months-after-finaliz...

The NVMe protocol has extremely deep queues [1] and leaving them empty means leaving performance on the table. I think you'll find it surprisingly difficult to saturate the PCIe bus with just one core: PCIe 7 will support 512GB/s. Assuming a single core can produce 64 bytes (an entire cache line!) per cycle running at 5GHz, you're still only at 320/512=62.5% saturation. This napkin math is a little BS, but my point is that individual cores are quickly going to be outpaced by bandwidth availability.

> and totally unclear how directories represent an "interference" boundary

To add a bit more color here, it depends on how your file system is implemented. I belive Windows stores every file's metadata in a global database, so segmenting operations by directory yields no benefits. On the other hand, Unix FSs tend to store file_name to inode mappings per directory, so creating a new mapping in one directory doesn't interfere with another directory.

[1]: https://en.wikipedia.org/wiki/NVM_Express#Comparison_with_AH...

SUPERCILEXon The fastest rm command and one of the fastest cp commands

We're working on this! https://github.com/axboe/liburing/issues/830

SUPERCILEXon The fastest rm command and one of the fastest cp commands

I added a clarification to the benchmarks section:

"The macOS/Windows implementations are currently equivalent to the *_rayon implementations shown in the benchmarks."

Rayon is pretty good, but clearly suboptimal as evidenced by the benchmarks.

SUPERCILEXon Ask HN: Can you share websites that are pushing the utility of browsers forward?

We're building a small game that runs on the web: https://supercilex.github.io/grocery_bagger_9000/

SUPERCILEXon Ask HN: Has YouTube been defaulting every video to 360p for you?

Ok, based on this response and others it seems like this might be something on my end... I'll look into getting a bug report to support.

SUPERCILEXon Ask HN: Has YouTube been defaulting every video to 360p for you?

That looks cool (especially sponsorblock), thanks for the tip!

SUPERCILEXon Show HN: A pseudo-random directory hierarchy generator written in Rust

The story around this project is a bit of a weird tangent. I'm working on another project (not ready to share) that uses tokio and needs to delete a bunch of files. I was surprised to discover that tokio's remove_dir_all implementation forwards to the stdlib, meaning it is completely sequential. To squeeze out every ounce of performance, I decided to write a crate that deletes files in parallel as fast as possible (still WIP), but to do so, it turns out I need a way to reliably and deterministically generate a bunch of files to delete so I can benchmark deletion performance properly. So here I am, finally popping that third plate off the stack. :)

FTZZ is designed (and optimized) primarily for Linux, but also works on macOS and Windows.

FTZZ is insanely fast and will saturate your machine when creating empty files — I can reach 800K files/s on my laptop. I'm considering the project complete, but it still has a few flaws: - Memory usage is not fully bounded, meaning you could theoretically run out if you try to generate a tree billions of directories wide. - The error between the target number of files and the actual number of generated files grows with the maximum depth of the tree. I'm using a LogNormal distribution, but probably incorrectly. - When generating an exact number of files or bytes, their distribution can get messed up because I haven't looked into how to properly distribute the remaining files/bytes.

If you want a more in-depth dive into the technical and performance details, I wrote up a blog post about them: https://alexsaveau.dev/blog/projects/performance/files/ftzz/.... If you think this project is cool, please consider upvoting my Stack Overflow answer: https://stackoverflow.com/a/69714764/4548500.

SUPERCILEXon The fastest way to copy a file?

Whoops, author here. That was a mistake, I meant to say the copy_file_range syscall since that's what Rust uses by default under the hood on Linux (or copyfile on macOS). Updated the article with those corrections.