> 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.
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.
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
> 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.
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