Unix "find" Expressions Compiled to Bytecode

Posted7 days agoActive2d ago

rcarmo

123 points

17 comments

nullprogram.comTech Discussionstory

informativepositive

Debate

20/100

Command Line ToolConversion_rate_optimizationAI Performance Analysis

Key topics

Command Line Tool

Conversion_rate_optimization

AI Performance Analysis

The Unix "find" command's performance is being reevaluated after a blog post revealed that compiling its expressions to bytecode could be a potential optimization. Commenters chimed in, pointing out that the real bottleneck lies in file system calls, with tasty_freeze estimating that evaluating conditional expressions takes up only a tiny fraction of the overall time, while CerryuDu highlighted the impact of loading directory entries and inodes on a cold cache. Interestingly, nasretdinov and loeg discussed how certain file systems and system calls, like readdirplus and d_type, can mitigate the need for additional stat() calls, with nasretdinov noting that NFS seems to handle subsequent stat() calls efficiently. The discussion also touched on why most "find" implementations use tree-walk interpreters, with drob518 arguing that it's simply because it's easier to implement, not due to performance reasons.

Snapshot generated from the HN discussion

Discussion Activity

Active discussion

First comment

Peak period

0-12h

Avg / period

Comment distribution18 data points

Loading chart...

Based on 18 loaded comments

Key moments

01Story posted
Dec 26, 2025 at 7:35 AM EST
7 days ago
Step 01
02First comment
Dec 26, 2025 at 10:39 AM EST
3h after posting
Step 02
03Peak activity
13 comments in 0-12h
Hottest window of the conversation
Step 03
04Latest activity
Dec 30, 2025 at 11:53 PM EST
2d ago
Step 04

Generating AI Summary...

Analyzing up to 500 comments to identify key contributors and discussion patterns

Discussion (17 comments)

Showing 18 comments

tasty_freeze

7 days ago

2 replies

That is a fun exercise, but I imagine the time to evaluate the conditional expression is a tiny fraction, just a percent or less, than the time it takes to make the file system calls.

nasretdinov

7 days ago

1 reply

For many cases you don't even need to make stat() call to determine whether or not the file is a directory (d_type specifically can tell it: https://man7.org/linux/man-pages/man3/readdir.3.html). That's what allows find(1) to be so quick

loeg

6d ago

1 reply

You could imagine determining from the parsed expression whether or not stat'ing was required.

NFS has readdirplus, but I don't think it ever made its way into Linux/POSIX. (Some filesystems could efficiently return dirents + stat information.)

nasretdinov

6d ago

1 reply

> readdirplus

Well, it definitely does _something_, because on NFS the subsequent stat() calls after reading the directory names do indeed complete instantly :), at least in my testing.

loeg

6d ago

I mean, readdirplus as a local filesystem API. Ultimately unix programs are just invoking getdents() (or equivalent) + stat() (or statx, whatever). Linux nfsclient probably caches the result of readdirplus for subsequent stat.

CerryuDu

7 days ago

... not to mention the time it takes to load directory entries and inodes when the cache is cold.

drob518

7 days ago

3 replies

From the article:

> I was later surprised all the real world find implementations I examined use tree-walk interpreters instead.

I’m not sure why this would be surprising. The find utility is totally dominated by disk IOPS. The interpretation performance of find conditions is totally swamped by reading stuff from disk. So, keep it simple and just use a tree-walk interpreter.

chubot

7 days ago

1 reply

Yeah that's basically what was discussed here: https://lobste.rs/s/xz6fwz/unix_find_expressions_compiled_by...

And then I pointed to this article on databases: https://notes.eatonphil.com/2023-09-21-how-do-databases-exec...

Even MySQL, Duck DB, and Cockroach DB apparently use tree-walking to evaluate expressions, not bytecode!

Probably for the same reason - many parts are dominated by I/O, so the work on optimization goes elsewhere

And MySQL is a super-mature codebase

drob518

6d ago

1 reply

I was just reading a paper about compiling SQL queries (actually about a fast compilation technique that allows for full compilation to machine code that is suitable for SQL and WASM): https://dl.acm.org/doi/pdf/10.1145/3485513

Sounds like many DBs do some level of compilation for complex queries. I suspect this is because SQL has primitives that actually compute things (e.g. aggregations, sorts, etc.). But find does basically none of that. Find is completely IO-bound.

hxtk

6d ago

1 reply

Virtually all databases compile queries in one way or another, but they vary in the nature of their approaches. SQLite for example uses bytecode, while Postgres and MySQL both compile it to a computation tree which basically takes the query AST and then substitutes in different table/index operations according to the query planner.

SQLite talks about the reasons for each variation here: https://sqlite.org/whybytecode.html

drob518

6d ago

Thanks for the reference.

Someone

6d ago

2 replies

[delayed]

drob518

6d ago

1 reply

If it was easier to interpret byte codes, nobody would use a tree-walk interpreter. There’s no performance reason to use a tree-walk interpreter. They all do it because it’s easy. You basically already have the expression in tree form, regardless of where you end up. So, stop processing the tree and just interpret it.

Someone

6d ago

[delayed]

maxbond

6d ago

File operations are a good candidate for testing with side effects since they ship with every OS and are not very expensive in a tmpfs, but you don't have to let it perform side effects. You could pass the eval function a delegate which it calls methods on to perform side effects and pass in a mocked delegate during testing.

adrian_b

6d ago

The assumption that "find" performance is dominated by disk IOPS is not generally valid.

For instance, I normally compile big software projects in RAM disks (Linux tmpfs).

Such big software projects may have very great numbers of files and subdirectories and their building scripts may use "find".

In such a case there are no SSD or HDD I/O operations, everything is done in the main memory, so the intrinsic performance of "find" may matter.

burnt-resistor

6d ago

1 reply

I recently wrote a "du" summarizer of additional stats in C because it's faster than du, find, or any sort of scripting language tree walker.

For archiving, I also wrote a parallel walker and file hasher that only does one pass of data and stores results to a sqlite database. It's basically poor-man's IDS and bitrot detection.

hxtk

2d ago

The latter sounds like a reimplementation of AIDE, which exists in major Linux distributions’ default package managers.

Did you ever compare what you wrote to that?

View full discussion on Hacker News

ID: 46391448Type: storyLast synced: 12/29/2025, 12:25:25 PM

Want the full context?

Jump to the original sources

Read the primary article or dive into the live Hacker News thread when you're ready.

Open link View on HN