3 ms·

Unix "find" expressions compiled to bytecode

125 points by rcarmo 10mo ago

tasty_freeze 10mo 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.
- CerryuDu 10mo ago
  ... not to mention the time it takes to load directory entries and inodes when the cache is cold.
- nasretdinov 10mo 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: https://man7.org/linux/man-pages/man3/readdir.3.html https://man7.org/linux/man-pages/man3/readdir.3.html). That's what allows find(1) to be so quick
  - loeg 10mo 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.)
    - nasretdinov 10mo ago
      > 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 10mo 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.
drob518 10mo 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.
- chubot 10mo ago
  Yeah that's basically what was discussed here: https://lobste.rs/s/xz6fwz/unix_find_expressions_compiled_bytecode 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-execute-expressions.html 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 10mo 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): https://dl.acm.org/doi/pdf/10.1145/3485513 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 10mo ago
      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 https://sqlite.org/whybytecode.html
burnt-resistor 10mo ago
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. The latter is orders of magnitude slower, but ultimately it's bounded by iteration of kernel vfs structures and any hard IOPS that are spent to fetch metadata from slower media. 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 10mo 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?

125 points by rcarmo 10mo 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.

CerryuDu 10mo ago
... not to mention the time it takes to load directory entries and inodes when the cache is cold.
nasretdinov 10mo 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: https://man7.org/linux/man-pages/man3/readdir.3.html https://man7.org/linux/man-pages/man3/readdir.3.html). That's what allows find(1) to be so quick
- loeg 10mo 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.)
  - nasretdinov 10mo ago
    > 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 10mo 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.

drob518 10mo 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.

chubot 10mo ago
Yeah that's basically what was discussed here: https://lobste.rs/s/xz6fwz/unix_find_expressions_compiled_bytecode 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-execute-expressions.html 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 10mo 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): https://dl.acm.org/doi/pdf/10.1145/3485513 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 10mo ago
    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 https://sqlite.org/whybytecode.html

burnt-resistor 10mo ago

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. The latter is orders of magnitude slower, but ultimately it's bounded by iteration of kernel vfs structures and any hard IOPS that are spent to fetch metadata from slower media. 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 10mo 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?