summaryrefslogtreecommitdiffstats
path: root/src/opt.c
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2024-02-05 15:13:38 -0500
committerTavian Barnes <tavianator@tavianator.com>2024-02-06 15:22:39 -0500
commit5f0958fa57770e13b8696b8ee6fc87890333d90b (patch)
treed365645b2fd7f9625effdff8e656b59ea10763af /src/opt.c
parent6bb323d446e2500c5a20866b56335ac8633e1c23 (diff)
downloadbfs-5f0958fa57770e13b8696b8ee6fc87890333d90b.tar.xz
opt: Enable BFTW_STAT when profitable
Diffstat (limited to 'src/opt.c')
-rw-r--r--src/opt.c91
1 files changed, 91 insertions, 0 deletions
diff --git a/src/opt.c b/src/opt.c
index 28a2255..74145ac 100644
--- a/src/opt.c
+++ b/src/opt.c
@@ -1004,6 +1004,13 @@ static struct bfs_expr *annotate_fnmatch(struct bfs_opt *opt, struct bfs_expr *e
return expr;
}
+/** Annotate -f?print. */
+static struct bfs_expr *annotate_fprint(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) {
+ const struct colors *colors = expr->cfile->colors;
+ expr->calls_stat = colors && colors_need_stat(colors);
+ return expr;
+}
+
/** Estimate probability for -x?type. */
static void estimate_type_probability(struct bfs_expr *expr) {
unsigned int types = expr->num;
@@ -1204,6 +1211,38 @@ static struct bfs_expr *annotate_visit(struct bfs_opt *opt, struct bfs_expr *exp
}
}
+ /** Table of stat-calling primaries. */
+ static bfs_eval_fn *const calls_stat[] = {
+ eval_empty,
+ eval_flags,
+ eval_fls,
+ eval_fprintf,
+ eval_fstype,
+ eval_gid,
+ eval_inum,
+ eval_links,
+ eval_newer,
+ eval_nogroup,
+ eval_nouser,
+ eval_perm,
+ eval_samefile,
+ eval_size,
+ eval_sparse,
+ eval_time,
+ eval_uid,
+ eval_used,
+ eval_xattr,
+ eval_xattrname,
+ };
+
+ expr->calls_stat = false;
+ for (size_t i = 0; i < countof(calls_stat); ++i) {
+ if (expr->eval_fn == calls_stat[i]) {
+ expr->calls_stat = true;
+ break;
+ }
+ }
+
#define FAST_COST 40.0
#define FNMATCH_COST 400.0
#define STAT_COST 1000.0
@@ -1294,6 +1333,7 @@ static const struct visitor annotate = {
{eval_access, annotate_access},
{eval_empty, annotate_empty},
{eval_exec, annotate_exec},
+ {eval_fprint, annotate_fprint},
{eval_lname, annotate_fnmatch},
{eval_name, annotate_fnmatch},
{eval_path, annotate_fnmatch},
@@ -2130,6 +2170,43 @@ static struct bfs_expr *optimize(struct bfs_opt *opt, struct bfs_expr *expr) {
return expr;
}
+/** Estimate the odds of an expression calling stat(). */
+static float expr_stat_odds(struct bfs_expr *expr) {
+ if (expr->calls_stat) {
+ return 1.0;
+ }
+
+ float nostat_odds = 1.0;
+ float reached_odds = 1.0;
+ for (struct bfs_expr *child = bfs_expr_children(expr); child; child = child->next) {
+ float child_odds = expr_stat_odds(child);
+ nostat_odds *= 1.0 - reached_odds * child_odds;
+
+ if (expr->eval_fn == eval_and) {
+ reached_odds *= child->probability;
+ } else if (expr->eval_fn == eval_or) {
+ reached_odds *= 1.0 - child->probability;
+ }
+ }
+
+ return 1.0 - nostat_odds;
+}
+
+/** Estimate the odds of calling stat(). */
+static float estimate_stat_odds(struct bfs_ctx *ctx) {
+ if (ctx->unique) {
+ return 1.0;
+ }
+
+ float nostat_odds = 1.0 - expr_stat_odds(ctx->exclude);
+
+ float reached_odds = 1.0 - ctx->exclude->probability;
+ float expr_odds = expr_stat_odds(ctx->expr);
+ nostat_odds *= 1.0 - reached_odds * expr_odds;
+
+ return 1.0 - nostat_odds;
+}
+
int bfs_optimize(struct bfs_ctx *ctx) {
bfs_ctx_dump(ctx, DEBUG_OPT);
@@ -2196,6 +2273,20 @@ int bfs_optimize(struct bfs_ctx *ctx) {
opt_leave(&opt, "${blu}-maxdepth${rs} ${bld}%d${rs}\n", ctx->maxdepth);
}
+ if (opt.level >= 3) {
+ // bfs_eval() can do lazy stat() calls, but only on one thread.
+ float lazy_cost = estimate_stat_odds(ctx);
+ // bftw() can do eager stat() calls in parallel
+ float eager_cost = 1.0 / ctx->threads;
+
+ if (eager_cost <= lazy_cost) {
+ opt_enter(&opt, "lazy stat cost: ${ylw}%g${rs}\n", lazy_cost);
+ ctx->flags |= BFTW_STAT;
+ opt_leave(&opt, "eager stat cost: ${ylw}%g${rs}\n", eager_cost);
+ }
+
+ }
+
opt_leave(&opt, NULL);
return 0;