From aa29434a2feebc8925307372c27a5f56021620fc Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Thu, 14 Apr 2022 14:43:43 +0200 Subject: Add header cache to cc::compile_rule::enter_header() --- libbuild2/c/init.cxx | 2 +- libbuild2/cc/compile-rule.cxx | 203 ++++++++++++++++++++++++++++++++++++------ libbuild2/cc/compile-rule.hxx | 7 +- libbuild2/cc/module.hxx | 15 +++- libbuild2/cxx/init.cxx | 2 +- libbuild2/dyndep.cxx | 8 +- 6 files changed, 202 insertions(+), 35 deletions(-) (limited to 'libbuild2') diff --git a/libbuild2/c/init.cxx b/libbuild2/c/init.cxx index f39114c..4c051b0 100644 --- a/libbuild2/c/init.cxx +++ b/libbuild2/c/init.cxx @@ -391,7 +391,7 @@ namespace build2 inc }; - auto& m (extra.set_module (new module (move (d)))); + auto& m (extra.set_module (new module (move (d), rs))); m.init (rs, loc, extra.hints, *cm.x_info); return true; diff --git a/libbuild2/cc/compile-rule.cxx b/libbuild2/cc/compile-rule.cxx index a5e5417..002c889 100644 --- a/libbuild2/cc/compile-rule.cxx +++ b/libbuild2/cc/compile-rule.cxx @@ -248,12 +248,34 @@ namespace build2 }; compile_rule:: - compile_rule (data&& d) + compile_rule (data&& d, const scope& rs) : common (move (d)), rule_id (string (x) += ".compile 6") { static_assert (sizeof (match_data) <= target::data_size, "insufficient space"); + + // Locate the header cache (see enter_header() for details). + // + { + string mn (string (x) + ".config"); + + header_cache_ = rs.find_module (mn); // Must be there. + + const scope* ws (rs.weak_scope ()); + if (ws != &rs) + { + const scope* s (&rs); + do + { + s = s->parent_scope ()->root_scope (); + + if (const auto* m = s->find_module (mn)) + header_cache_ = m; + + } while (s != ws); + } + } } template @@ -2044,7 +2066,7 @@ namespace build2 pair er ( enter_header ( a, bs, t, li, - f, false /* cache */, false /* normalized */, + move (f), false /* cache */, false /* normalized */, pfx_map, so_map)); ht = er.first; @@ -2062,7 +2084,7 @@ namespace build2 // diagnostics won't really add anything to the compiler's. So // let's only print it at -V or higher. // - if (ht == nullptr) + if (ht == nullptr) // f is still valid. { assert (!exists); // Sanity check. @@ -2110,6 +2132,8 @@ namespace build2 // messy, let's keep both (it would have been nicer to print // ours after the compiler's but that isn't easy). // + // Note: if ht is NULL, f is still valid. + // r = "ERROR unable to update header '"; r += (ht != nullptr ? ht->path () : f).string (); r += '\''; @@ -2573,7 +2597,7 @@ namespace build2 pair r ( enter_header ( a, bs, t, li, - f, false /* cache */, false /* normalized */, + move (f), false /* cache */, false /* normalized */, pfx_map, so_map)); if (!r.second) // Shouldn't be remapped. @@ -2601,7 +2625,7 @@ namespace build2 pair er ( enter_header ( a, bs, t, li, - f, false /* cache */, false /* normalized */, + move (f), false /* cache */, false /* normalized */, pfx_map, so_map)); ht = er.first; @@ -2620,7 +2644,7 @@ namespace build2 // diagnostics won't really add anything to the compiler's. So // let's only print it at -V or higher. // - if (ht == nullptr) + if (ht == nullptr) // f is still valid. { assert (!exists); // Sanity check. @@ -2667,6 +2691,8 @@ namespace build2 // messy, let's keep both (it would have been nicer to print // ours after the compiler's but that isn't easy). // + // Note: if ht is NULL, f is still valid. + // rs = !exists ? string ("INCLUDE") : ("ERROR unable to update header '" + @@ -2790,17 +2816,115 @@ namespace build2 } #endif + //atomic_count cache_hit {0}; + //atomic_count cache_mis {0}; + //atomic_count cache_cls {0}; + + // The fp path is only moved from on success. + // // Note: this used to be a lambda inside extract_headers() so refer to the // body of that function for the overall picture. // pair compile_rule:: enter_header (action a, const scope& bs, file& t, linfo li, - path& fp, bool cache, bool norm, + path&& fp, bool cache, bool norm, optional& pfx_map, const srcout_map& so_map) const { tracer trace (x, "compile_rule::enter_header"); + // It's reasonable to expect the same header to be included by multiple + // translation units, which means we will be re-doing this work over and + // over again. And it's not exactly cheap, taking up to 50% of an + // up-to-date check time on some projects. So we are going to cache the + // header path to target mapping. + // + // While we pass quite a bit of specific "context" (target, base scope) + // to enter_file(), here is the analysis why the result will not depend + // on this context for the non-absent header (fp is absolute): + // + // 1. Let's start with the base scope (bs). Firstly, the base scope + // passed to map_extension() is the scope of the header (i.e., it is + // the scope of fp.directory()). Other than that, the target base + // scope is only passed to build_prefix_map() which is only called + // for the absent header (linfo is also only used here). + // + // 2. Next is the target (t). It is passed to build_prefix_map() but + // that doesn't matter for the same reason as in (1). Other than + // that, it is only passed to build2::search() which in turn passes + // it to target type-specific prerequisite search callback (see + // target_type::search) if one is not NULL. The target type in + // question here is one of the headers and we know all of them use + // the standard file_search() which ignores the passed target. + // + // 3. Finally, so_map could be used for an absolute fp. While we could + // simply not cache the result if it was used (second half of the + // result pair is true), there doesn't seem to be any harm in caching + // the remapped path->target mapping. In fact, if to think about it, + // there is no harm in caching the generated file mapping since it + // will be immediately generated and any subsequent inclusions we + // will "see" with an absolute path, which we can resolve from the + // cache. + // + // To put it another way, all we need to do is make sure that if we were + // to not return an existing cache entry, the call to enter_file() would + // have returned exactly the same path/target. + // + // @@ Could it be that the header is re-mapped in one config but not the + // other (e.g., when we do both in src and in out builds and we pick + // the generated header in src)? If so, that would lead to a + // divergence. I.e., we would cache the no-remap case first and then + // return it even though the re-map is necessary? Why can't we just + // check for re-mapping ourselves? A: the remapping logic in + // enter_file() is not exactly trivial. + // + // But on the other hand, I think we can assume that different + // configurations will end up with different caches. In other words, + // we can assume that for the same "cc amalgamation" we use only a + // single "version" of a header. Seems reasonable. + // + // Note also that while it would have been nice to have a unified cc + // cache, the map_extension() call is passed x_inc which is module- + // specific. In other words, we may end up mapping the same header to + // two different targets depending on whether it is included from, say, + // C or C++ translation unit. We could have used a unified cache for + // headers that were mapped using the fallback target type, which would + // cover the installed headers. Maybe, one day (it's also possible that + // separate caches reduce contention). + // + // Another related question is where we want to keep the cache: project, + // strong amalgamation, or weak amalgamation (like module sidebuilds). + // Some experimentation showed that weak has the best performance (which + // suggest that a unified cache will probably be a win). + // + // Note also that we don't need to clear this cache since we never clear + // the targets set. In other words, the only time targets are + // invalidated is when we destroy the build context, which also destroys + // the cache. + // + const config_module& hc (*header_cache_); + + // First check the cache. + // + if (fp.absolute ()) + { + if (!norm) + { + normalize_external (fp, "header"); + norm = true; + } + + slock l (hc.header_map_mutex); + auto i (hc.header_map.find (fp)); + if (i != hc.header_map.end ()) + { + //cache_hit.fetch_add (1, memory_order_relaxed); + return make_pair (i->second, false); + } + + //cache_mis.fetch_add (1, memory_order_relaxed); + } + struct data { linfo li; @@ -2810,24 +2934,44 @@ namespace build2 // If it is outside any project, or the project doesn't have such an // extension, assume it is a plain old C header. // - return enter_file ( - trace, "header", - a, bs, t, - fp, cache, norm, - [this] (const scope& bs, const string& n, const string& e) + auto r (enter_file ( + trace, "header", + a, bs, t, + fp, cache, norm, + [this] (const scope& bs, const string& n, const string& e) + { + return map_extension (bs, n, e, x_inc); + }, + h::static_type, + [this, &d] (action a, const scope& bs, const target& t) + -> const prefix_map& + { + if (!d.pfx_map) + d.pfx_map = build_prefix_map (bs, a, t, d.li); + + return *d.pfx_map; + }, + so_map)); + + // Cache. + // + if (r.first != nullptr) + { + const file* f; { - return map_extension (bs, n, e, x_inc); - }, - h::static_type, - [this, &d] (action a, const scope& bs, const target& t) - -> const prefix_map& + ulock l (hc.header_map_mutex); + auto p (hc.header_map.emplace (move (fp), r.first)); + f = p.second ? nullptr : p.first->second; + } + + if (f != nullptr) { - if (!d.pfx_map) - d.pfx_map = build_prefix_map (bs, a, t, d.li); + //cache_cls.fetch_add (1, memory_order_relaxed); + assert (r.first == f); + } + } - return *d.pfx_map; - }, - so_map); + return r; } // Note: this used to be a lambda inside extract_headers() so refer to the @@ -3588,7 +3732,7 @@ namespace build2 if (const file* ht = enter_header ( a, bs, t, li, - hp, cache, cache /* normalized */, + move (hp), cache, cache /* normalized */, pfx_map, so_map).first) { // If we are reading the cache, then it is possible the file has @@ -3603,7 +3747,7 @@ namespace build2 // Verify/add it to the dependency database. // if (!cache) - dd.expect (ht->path ()); // @@ Use hp (or verify match)? + dd.expect (ht->path ()); skip_count++; return *u; @@ -3617,7 +3761,7 @@ namespace build2 return fail (*ht); } else - return fail (hp); + return fail (hp); // hp is still valid. }; // As above but for a header unit. Note that currently it is only used @@ -3634,10 +3778,10 @@ namespace build2 const file* ht ( enter_header (a, bs, t, li, - hp, true /* cache */, false /* normalized */, + move (hp), true /* cache */, false /* normalized */, pfx_map, so_map).first); - if (ht == nullptr) + if (ht == nullptr) // hp is still valid. { diag_record dr; dr << error << "header " << hp << " not found and no rule to " @@ -5738,6 +5882,9 @@ namespace build2 // cc.config module and that is within our amalgmantion seems like a // good place. // + // @@ TODO: maybe we should cache this in compile_rule ctor like we + // do for the header cache? + // const scope* as (&rs); { const scope* ws (as->weak_scope ()); @@ -5753,7 +5900,7 @@ namespace build2 // This is also the module that registers the scope operation // callback that cleans up the subproject. // - if (cast_false ((*s)["cc.core.vars.loaded"])) + if (cast_false (s->vars["cc.core.vars.loaded"])) as = s; } while (s != ws); diff --git a/libbuild2/cc/compile-rule.hxx b/libbuild2/cc/compile-rule.hxx index 00965fc..16b33fa 100644 --- a/libbuild2/cc/compile-rule.hxx +++ b/libbuild2/cc/compile-rule.hxx @@ -22,6 +22,8 @@ namespace build2 namespace cc { + class config_module; + // The order is arranged so that their integral values indicate whether // one is a "stronger" than another. // @@ -42,7 +44,7 @@ namespace build2 dyndep_rule { public: - compile_rule (data&&); + compile_rule (data&&, const scope&); virtual bool match (action, target&) const override; @@ -120,7 +122,7 @@ namespace build2 pair enter_header (action, const scope&, file&, linfo, - path&, bool, bool, + path&&, bool, bool, optional&, const srcout_map&) const; optional @@ -180,6 +182,7 @@ namespace build2 private: const string rule_id; + const config_module* header_cache_; }; } } diff --git a/libbuild2/cc/module.hxx b/libbuild2/cc/module.hxx index a91d723..ee9349a 100644 --- a/libbuild2/cc/module.hxx +++ b/libbuild2/cc/module.hxx @@ -4,6 +4,8 @@ #ifndef LIBBUILD2_CC_MODULE_HXX #define LIBBUILD2_CC_MODULE_HXX +#include + #include #include @@ -78,6 +80,15 @@ namespace build2 bool new_config = false; // See guess() and init() for details. + // Header cache (see compile_rule::enter_header()). + // + // We place it into the config module so that we have an option of + // sharing it for the entire weak amalgamation. + // + public: + mutable shared_mutex header_map_mutex; + mutable std::unordered_map header_map; + private: // Defined in gcc.cxx. // @@ -105,10 +116,10 @@ namespace build2 { public: explicit - module (data&& d) + module (data&& d, const scope& rs) : common (move (d)), link_rule (move (d)), - compile_rule (move (d)), + compile_rule (move (d), rs), install_rule (move (d), *this), libux_install_rule (move (d), *this) {} diff --git a/libbuild2/cxx/init.cxx b/libbuild2/cxx/init.cxx index 0ebb424..3a934db 100644 --- a/libbuild2/cxx/init.cxx +++ b/libbuild2/cxx/init.cxx @@ -868,7 +868,7 @@ namespace build2 inc }; - auto& m (extra.set_module (new module (move (d)))); + auto& m (extra.set_module (new module (move (d), rs))); m.init (rs, loc, extra.hints, *cm.x_info); return true; diff --git a/libbuild2/dyndep.cxx b/libbuild2/dyndep.cxx index 727a28c..55b02ed 100644 --- a/libbuild2/dyndep.cxx +++ b/libbuild2/dyndep.cxx @@ -389,6 +389,9 @@ namespace build2 const function& get_pfx_map, const dyndep_rule::srcout_map& so_map) { + // NOTE: see enter_header() caching logic if changing anyting here with + // regards to the target and base scope usage. + // Find or maybe insert the target. The directory is only moved from if // insert is true. Note that it must be normalized. // @@ -561,6 +564,9 @@ namespace build2 // Note: we now always use absolute path to the translation unit so this // no longer applies. But let's keep it for posterity. // + // Also note that we now assume (see cc::compile_rule::enter_header()) a + // relative path signifies a generated header. + // #if 0 if (f.relative () && rels.relative ()) { @@ -590,7 +596,7 @@ namespace build2 const file* pt (nullptr); bool remapped (false); - // If still relative then it does not exist. + // If relative then it does not exist. // if (fp.relative ()) { -- cgit v1.1