> 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
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.
SQLite talks about the reasons for each variation here: https://sqlite.org/whybytecode.html
Also, decreasing CPU usage many not speed up find (much), but it would leave more time for running other processes.
I’m not claiming anything, certainly not that; I’m questioning whether the additional complexity of designing a bytecode VM is worth it because it makes testing easier.
For instance, I normally compile big software projects in RAM disks (Linux tmpfs), because I typically use computers with no less than 64 GB of DRAM.
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.
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.
Did you ever compare what you wrote to that?
tasty_freeze•1mo ago
CerryuDu•1mo ago
nasretdinov•1mo ago
loeg•1mo ago
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•1mo ago
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•1mo ago