From 653371fa06c7589a1097b05f32d6ff26f2fbb337 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Mon, 13 Feb 2017 10:59:20 +0200 Subject: Use variable_cache for target type/pattern-specific prepend/append --- build2/scope.cxx | 84 ++++++++++++++++++++++------------------- build2/variable | 107 ++++++++++++++++++++++++++++------------------------ build2/variable.txx | 58 ++++++++++++++++------------ 3 files changed, 138 insertions(+), 111 deletions(-) (limited to 'build2') diff --git a/build2/scope.cxx b/build2/scope.cxx index d7e9d8e..4449747 100644 --- a/build2/scope.cxx +++ b/build2/scope.cxx @@ -44,52 +44,58 @@ namespace build2 // lookup stem (s->find_original (var, tt, tn, gt, gn, 2).first); - // Implementing proper caching is tricky so for now we are going to re- - // calculate the value every time. This is the same issue and the same - // planned solution as for the override cache (see below). + // Check the cache. // - // Note: very similar logic as in the override cache population code - // below. - // - // @@ MT - // - variable_map::value_data& cache ( - s->target_vars.cache[make_tuple (&v, tt, *tn)]); + pair entry ( + s->target_vars.cache.insert ( + make_tuple (&v, tt, *tn), + stem, + static_cast (v).version)); - // Un-typify the cache. This can be necessary, for example, if we are - // changing from one value-typed stem to another. + value& cv (entry.first); + + // If cache miss/invalidation, update the value. // - if (!stem.defined () || cache.type != stem->type) + if (entry.second.owns_lock ()) { - cache = nullptr; - cache.type = nullptr; // Un-typify. - } + // Un-typify the cache. This can be necessary, for example, if we are + // changing from one value-typed stem to another. + // + // Note: very similar logic as in the override cache population code + // below. + // + if (!stem.defined () || cv.type != stem->type) + { + cv = nullptr; + cv.type = nullptr; // Un-typify. + } - // Copy the stem. - // - if (stem.defined ()) - cache = *stem; + // Copy the stem. + // + if (stem.defined ()) + cv = *stem; - // Typify the cache value in case there is no stem (we still want to - // prepend/append things in type-aware way). - // - if (cache.type == nullptr && var.type != nullptr) - typify (cache, *var.type, &var); + // Typify the cache value in case there is no stem (we still want to + // prepend/append things in type-aware way). + // + if (cv.type == nullptr && var.type != nullptr) + typify (cv, *var.type, &var); - // Now prepend/append the value, unless it is NULL. - // - if (v) - { - if (v.extra == 1) - cache.prepend (names (cast (v)), &var); - else - cache.append (names (cast (v)), &var); + // Now prepend/append the value, unless it is NULL. + // + if (v) + { + if (v.extra == 1) + cv.prepend (names (cast (v)), &var); + else + cv.append (names (cast (v)), &var); + } } // Return cache as the resulting value but retain l.vars, so it looks as // if the value came from s->target_vars. // - l.value = &cache; + l.value = &cv; }; for (const scope* s (this); s != nullptr; ) @@ -394,12 +400,14 @@ namespace build2 // Check the cache. // - pair cache ( + pair entry ( inner_proj->override_cache.insert ( - make_pair (&var, inner_vars), stem)); + make_pair (&var, inner_vars), + stem, + 0)); // Overrides are immutable. - value& cv (cache.first); - bool cl (cache.second.owns_lock ()); + value& cv (entry.first); + bool cl (entry.second.owns_lock ()); // If cache miss/invalidation, update the value. // diff --git a/build2/variable b/build2/variable index 35530ca..10f4ac9 100644 --- a/build2/variable +++ b/build2/variable @@ -1036,7 +1036,7 @@ namespace build2 using value::value; using value::operator=; - size_t version = 0; // Incremented on each modification (override cache). + size_t version = 0; // Incremented on each modification (variable_cache). size_t generation; // load_generation of this value (global state only). }; @@ -1167,6 +1167,57 @@ namespace build2 map_type m_; }; + // Value caching. Used for overrides as well as target type/pattern-specific + // append/prepend. + // + // In many places we assume that we can store a reference to the returned + // variable value (e.g., install::lookup_install()). As a result, in these + // cases where we calculate the value dynamically, we have to cache it + // (note, however, that if the value becomes stale, there is no guarantee + // the references remain valid). + // + // Note that since the cache can be modified on any lookup (including during + // the execute phase), it is protected by its own mutex shard (allocated in + // main()). + // + extern size_t variable_cache_mutex_shard_size; + extern unique_ptr variable_cache_mutex_shard; + + template + class variable_cache + { + public: + // If the returned unique lock is locked, then the value has been + // invalidated. + // + pair + insert (K, const lookup& stem, size_t version); + + private: + struct entry_type + { + // Note: we use value_data instead of value since the result is often + // returned as lookup. We also maintain the version in case one cached + // value (e.g., override) is based on another (e.g., target + // type/pattern-specific prepend/append). + // + variable_map::value_data value; + + size_t version = 0; // Version on which this value is based. + + // Location of the stem as well as the version on which this cache + // value is based. Used to track the location and value of the stem + // for cache invalidation. NULL/0 means there is no stem. + // + const variable_map* stem_vars = nullptr; + size_t stem_version = 0; + }; + + using map_type = std::map; + + map_type m_; + }; + // Target type/pattern-specific variables. // class variable_pattern_map @@ -1219,65 +1270,23 @@ namespace build2 lookup find (const target_type&, const string& tname, const variable&) const; - + // Prepend/append value cache. // // The key is the combination of the "original value identity" (as a // pointer to the value in one of the variable_pattern_map's) and the // "target identity" (as target type and target name). Note that while at // first it may seem like we don't need the target identity, we actually - // do since the stem may itself be target-type/pattern-specific. - // - // @@ MT + // do since the stem may itself be target-type/pattern-specific. See + // scope::find_original() for details. // - mutable std::map, - variable_map::value_data> cache; + mutable + variable_cache> + cache; private: bool global_; map_type map_; }; - - // Value caching. Used for overrides as well as target type/pattern-specific - // append/prepend. - // - // In many places we assume that we can store a reference to the returned - // variable value (e.g., install::lookup_install()). As a result, in these - // cases where we calculate the value dynamically, we have to cache it - // (note, however, that if the value becomes stale, there is no guarantee - // the references remain valid). - // - template - class variable_cache - { - public: - // If the returned unique lock is locked, then the value has been - // invalidated. - // - pair - insert (K, const lookup& stem); - - private: - struct entry_type - { - build2::value value; - - // Location of the stem as well as the version on which this cache - // value is based. Used to track the location and value of the stem - // for cache invalidation. NULL/0 means there is no stem. - // - const variable_map* stem_vars = nullptr; - size_t stem_version = 0; - }; - - using map_type = std::map; - - map_type m_; - }; - - // Allocated in main(). - // - extern size_t variable_cache_mutex_shard_size; - extern unique_ptr variable_cache_mutex_shard; } #include diff --git a/build2/variable.txx b/build2/variable.txx index 5b212f0..5a1b79c 100644 --- a/build2/variable.txx +++ b/build2/variable.txx @@ -557,13 +557,14 @@ namespace build2 // template pair variable_cache:: - insert (K k, const lookup& stem) + insert (K k, const lookup& stem, size_t ver) { - const variable_map* vars (stem.vars); // NULL if undefined. - size_t ver ( - stem.defined () - ? static_cast (stem.value)->version - : 0); + using value_data = variable_map::value_data; + + const variable_map* svars (stem.vars); // NULL if undefined. + size_t sver (stem.defined () + ? static_cast (stem.value)->version + : 0); shared_mutex& m ( variable_cache_mutex_shard[ @@ -576,9 +577,10 @@ namespace build2 // Cache hit. // - if (i != m_.end () && - i->second.stem_vars == vars && - i->second.stem_version == ver) + if (i != m_.end () && + i->second.version == ver && + i->second.stem_vars == svars && + i->second.stem_version == sver) return pair (i->second.value, move (ul)); // Relock for exclusive access. Note that it is entirely possible @@ -593,30 +595,38 @@ namespace build2 pair p (i, i == m_.end ()); if (p.second) - p = m_.emplace (move (k), entry_type {value (nullptr), vars, ver}); + p = m_.emplace (move (k), + entry_type {value_data (nullptr), ver, svars, sver}); entry_type& e (p.first->second); - // Cache miss. - // if (p.second) - ; - // - // Cache invalidation. - // - else if (e.stem_vars != vars || e.stem_version != ver) { - if (e.stem_vars != vars) - e.stem_vars = vars; + // Cache miss. + // + e.value.version++; // New value. + } + else if (e.version != ver || + e.stem_vars != svars || + e.stem_version != sver) + { + // Cache invalidation. + // + assert (e.version <= ver); + e.version = ver; + + if (e.stem_vars != svars) + e.stem_vars = svars; else - assert (e.stem_version <= ver); + assert (e.stem_version <= sver); + + e.stem_version = sver; - e.stem_version = ver; + e.value.version++; // Value changed. } - // - // Cache hit. - // else + // Cache hit. + // ul.unlock (); return pair (e.value, move (ul)); -- cgit v1.1