From 5f0958fa57770e13b8696b8ee6fc87890333d90b Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 5 Feb 2024 15:13:38 -0500
Subject: opt: Enable BFTW_STAT when profitable

---
 src/expr.h |  2 ++
 src/opt.c  | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 93 insertions(+)

(limited to 'src')

diff --git a/src/expr.h b/src/expr.h
index 4d607a4..349e052 100644
--- a/src/expr.h
+++ b/src/expr.h
@@ -110,6 +110,8 @@ struct bfs_expr {
 	bool always_true;
 	/** Whether this expression always evaluates to false. */
 	bool always_false;
+	/** Whether this expression uses stat(). */
+	bool calls_stat;
 
 	/** Estimated cost. */
 	float cost;
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;
-- 
cgit v1.2.3