Unix "find" expressions compiled to bytecode

(nullprogram.com)

93 points by rcarmo9 hours ago

2 comments

drob5183 hours ago
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.
- Someone1 hour ago
 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.
 - drob5181 hour ago
 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.
 - maxbond1 hour 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.
- chubot2 hours ago
 Yeah that's basically what was discussed here: <a href="https://lobste.rs/s/xz6fwz/unix_find_expressions_compiled_bytecode" rel="nofollow">https://lobste.rs/s/xz6fwz/unix_find_expressions_compiled_by...</a>And then I pointed to this article on databases: <a href="https://notes.eatonphil.com/2023-09-21-how-do-databases-execute-expressions.html" rel="nofollow">https://notes.eatonphil.com/2023-09-21-how-do-databases-exec...</a>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 elsewhereAnd MySQL is a super-mature codebase
 - drob51856 minutes ago
 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): <a href="https://dl.acm.org/doi/pdf/10.1145/3485513" rel="nofollow">https://dl.acm.org/doi/pdf/10.1145/3485513</a>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.
tasty_freeze6 hours ago
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.
- nasretdinov5 hours ago
 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: <a href="https://man7.org/linux/man-pages/man3/readdir.3.html" rel="nofollow">https://man7.org/linux/man-pages/man3/readdir.3.html</a>). That's what allows find(1) to be so quick
 - loeg2 hours ago
 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.)
 - nasretdinov1 hour ago
 > readdirplusWell, 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.
 - loeg1 hour 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.
- CerryuDu5 hours ago
 ... not to mention the time it takes to load directory entries and inodes when the cache is cold.