From cb3805257092cea2fa6d1fce8d2f99f6b01f44ed Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Tue, 24 Jan 2023 17:17:06 -0500 Subject: opt: Move costs out of the parser --- src/opt.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+) (limited to 'src/opt.c') diff --git a/src/opt.c b/src/opt.c index c80d584..1daf390 100644 --- a/src/opt.c +++ b/src/opt.c @@ -804,6 +804,8 @@ static struct bfs_expr *optimize_empty(struct opt_state *state, struct bfs_expr static struct bfs_expr *optimize_exec(struct opt_state *state, struct bfs_expr *expr) { if (expr->exec->flags & BFS_EXEC_MULTI) { expr->always_true = true; + } else { + expr->cost = 1000000.0; } return expr; @@ -929,6 +931,50 @@ static bfs_eval_fn *const opt_always_false[] = { eval_quit, }; +#define FAST_COST 40.0 +#define FNMATCH_COST 400.0 +#define STAT_COST 1000.0 +#define PRINT_COST 20000.0 + +/** + * Table of expression costs. + */ +static const struct { + /** The evaluation function with this cost. */ + bfs_eval_fn *eval_fn; + /** The matching cost. */ + float cost; +} opt_costs[] = { + {eval_access, STAT_COST}, + {eval_acl, STAT_COST}, + {eval_capable, STAT_COST}, + {eval_empty, 2 * STAT_COST}, // readdir() is worse than stat() + {eval_fls, PRINT_COST}, + {eval_fprint, PRINT_COST}, + {eval_fprint0, PRINT_COST}, + {eval_fprintf, PRINT_COST}, + {eval_fprintx, PRINT_COST}, + {eval_fstype, STAT_COST}, + {eval_gid, STAT_COST}, + {eval_inum, STAT_COST}, + {eval_links, STAT_COST}, + {eval_lname, FNMATCH_COST}, + {eval_name, FNMATCH_COST}, + {eval_newer, STAT_COST}, + {eval_nogroup, STAT_COST}, + {eval_nouser, STAT_COST}, + {eval_path, FNMATCH_COST}, + {eval_perm, STAT_COST}, + {eval_samefile, STAT_COST}, + {eval_size, STAT_COST}, + {eval_sparse, STAT_COST}, + {eval_time, STAT_COST}, + {eval_uid, STAT_COST}, + {eval_used, STAT_COST}, + {eval_xattr, STAT_COST}, + {eval_xattrname, STAT_COST}, +}; + /** * Table of simple predicates. */ @@ -1017,6 +1063,14 @@ static struct bfs_expr *optimize_expr_lookup(struct opt_state *state, struct bfs } } + expr->cost = FAST_COST; + for (size_t i = 0; i < BFS_COUNTOF(opt_costs); ++i) { + if (opt_costs[i].eval_fn == expr->eval_fn) { + expr->cost = opt_costs[i].cost; + break; + } + } + for (size_t i = 0; i < BFS_COUNTOF(opt_preds); ++i) { if (opt_preds[i].eval_fn == expr->eval_fn) { infer_pred_facts(state, opt_preds[i].pred); -- cgit v1.2.3