[HN Gopher] Unix "find" expressions compiled to bytecode
___________________________________________________________________
Unix "find" expressions compiled to bytecode
Author : rcarmo
Score : 94 points
Date : 2025-12-26 12:35 UTC (10 hours ago)
(HTM) web link (nullprogram.com)
(TXT) w3m dump (nullprogram.com)
| tasty_freeze wrote:
| 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.
| CerryuDu wrote:
| ... not to mention the time it takes to load directory entries
| and inodes when the cache is cold.
| nasretdinov wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| 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.
| drob518 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| Someone wrote:
| Is it truly simpler to do that? A separate "command line to
| byte codes" module would be way easier to test than one that
| also does the work, including making any necessary syscalls.
|
| Also, decreasing CPU usage many not speed up _find_ (much), but
| it would leave more time for running other processes.
| drob518 wrote:
| 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.
| maxbond wrote:
| 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.
___________________________________________________________________
(page generated 2025-12-26 23:00 UTC)