From 8543327654443db1981142bbe18f3878e464e981 Mon Sep 17 00:00:00 2001 From: Dan Willemsen Date: Tue, 18 Oct 2016 17:38:28 -0700 Subject: Remove "out" special case handling from FindEmulator We removed the special casing of $OUT_DIR from our findleaves commands to fix problems where $OUT_DIR was named the same as a real directory. But now TEST_FIND_EMULATOR (and regen) is broken, since the real command finds out/Android.mk, but the emulated version does not. Since we're already traversing output directories that aren't called "out", just remove the "out" special casing from the find emulator. This raises the time to init the find emulator from 0.85s to 1.12s on my machine with one product built. But this only happens when you're about to read all of the makefiles anyways, not during regen. The node count goes from 683196 to 894396. --- find.cc | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) diff --git a/find.cc b/find.cc index 2539212..1d9252f 100644 --- a/find.cc +++ b/find.cc @@ -726,8 +726,7 @@ class FindEmulatorImpl : public FindEmulator { return (!HasPrefix(s, "../") && !HasPrefix(s, "/") && !HasPrefix(s, ".repo") && - !HasPrefix(s, ".git") && - !HasPrefix(s, "out")); + !HasPrefix(s, ".git")); } const DirentNode* FindDir(StringPiece d, bool* should_fallback) { @@ -874,8 +873,7 @@ class FindEmulatorImpl : public FindEmulator { if (!strcmp(ent->d_name, ".") || !strcmp(ent->d_name, "..") || !strcmp(ent->d_name, ".repo") || - !strcmp(ent->d_name, ".git") || - !strcmp(ent->d_name, "out")) + !strcmp(ent->d_name, ".git")) continue; string npath = path; -- cgit v1.2.3 From 439f6f1553ad197b7c6921b28f848456cfb50ea9 Mon Sep 17 00:00:00 2001 From: Dan Willemsen Date: Wed, 19 Oct 2016 01:13:54 -0700 Subject: Optimize findleaves regen check If we've found all possible files in a leaf directory, we don't need to re-run findleaves every time the leaf directory's timestamp changes, we just need to make sure the file(s) that we found still exist. This saves a few seconds every time an atomic write is done in a source directory next to an Android.mk file. (Atomic writes use renames, so they always change the directory's timestamp) With the last commit that finds out/Android.mk and out/CleanSpec.mk, it turns out that the output directory's timestamp was changing every build, causing the global Android.mk & CleanSpec.mk findleaves.py command to be executed every regen check. TEST_FIND_EMULATOR still passes after this change. --- find.cc | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++-------------- find.h | 1 + ninja.cc | 5 ++++ regen.cc | 10 +++++++ 4 files changed, 90 insertions(+), 20 deletions(-) diff --git a/find.cc b/find.cc index 1d9252f..5d9cab6 100644 --- a/find.cc +++ b/find.cc @@ -23,6 +23,7 @@ #include #include +#include #include #include @@ -38,6 +39,8 @@ class FindCond { public: virtual ~FindCond() = default; virtual bool IsTrue(const string& path, unsigned char type) const = 0; + virtual bool Countable() const = 0; + virtual unsigned Count() const = 0; protected: FindCond() = default; }; @@ -48,12 +51,20 @@ class NameCond : public FindCond { public: explicit NameCond(const string& n) : name_(n) { + has_wildcard_ = (n.find_first_of("?*[") != string::npos); } virtual bool IsTrue(const string& path, unsigned char) const override { return fnmatch(name_.c_str(), Basename(path).data(), 0) == 0; } + virtual bool Countable() const override { + return !has_wildcard_; + } + virtual unsigned Count() const override { + return 1; + } private: string name_; + bool has_wildcard_; }; class TypeCond : public FindCond { @@ -64,6 +75,12 @@ class TypeCond : public FindCond { virtual bool IsTrue(const string&, unsigned char type) const override { return type == type_; } + virtual bool Countable() const override { + return false; + } + virtual unsigned Count() const override { + return 0; + } private: unsigned char type_; }; @@ -76,6 +93,12 @@ class NotCond : public FindCond { virtual bool IsTrue(const string& path, unsigned char type) const override { return !c_->IsTrue(path, type); } + virtual bool Countable() const override { + return false; + } + virtual unsigned Count() const override { + return 0; + } private: unique_ptr c_; }; @@ -90,6 +113,12 @@ class AndCond : public FindCond { return c2_->IsTrue(path, type); return false; } + virtual bool Countable() const override { + return false; + } + virtual unsigned Count() const override { + return 0; + } private: unique_ptr c1_, c2_; }; @@ -104,6 +133,12 @@ class OrCond : public FindCond { return c2_->IsTrue(path, type); return true; } + virtual bool Countable() const override { + return c1_->Countable() && c2_->Countable();; + } + virtual unsigned Count() const override { + return c1_->Count() + c2_->Count(); + } private: unique_ptr c1_, c2_; }; @@ -118,7 +153,7 @@ class DirentNode { virtual bool RunFind(const FindCommand& fc, int d, string* path, unordered_map* cur_read_dirs, - string* out) const = 0; + vector& out) const = 0; virtual bool IsDirectory() const = 0; @@ -133,13 +168,12 @@ class DirentNode { const string& path, unsigned char type, int d, - string* out) const { + vector& out) const { if (fc.print_cond && !fc.print_cond->IsTrue(path, type)) return; if (d < fc.mindepth) return; - *out += path; - *out += ' '; + out.push_back(path); } string base_; @@ -154,7 +188,7 @@ class DirentFileNode : public DirentNode { virtual bool RunFind(const FindCommand& fc, int d, string* path, unordered_map*, - string* out) const override { + vector& out) const override { PrintIfNecessary(fc, *path, type_, d, out); return true; } @@ -224,7 +258,7 @@ class DirentDirNode : public DirentNode { virtual bool RunFind(const FindCommand& fc, int d, string* path, unordered_map* cur_read_dirs, - string* out) const override { + vector& out) const override { ScopedReadDirTracker srdt(this, *path, cur_read_dirs); if (!srdt.ok()) { fprintf(stderr, "FindEmulator: find: File system loop detected; `%s' is " @@ -237,8 +271,7 @@ class DirentDirNode : public DirentNode { if (fc.prune_cond && fc.prune_cond->IsTrue(*path, DT_DIR)) { if (fc.type != FindCommandType::FINDLEAVES) { - *out += *path; - *out += ' '; + out.push_back(*path); } return true; } @@ -250,7 +283,7 @@ class DirentDirNode : public DirentNode { size_t orig_path_size = path->size(); if (fc.type == FindCommandType::FINDLEAVES) { - size_t orig_out_size = out->size(); + size_t orig_out_size = out.size(); for (const auto& p : children_) { DirentNode* c = p.second; // We will handle directories later. @@ -265,8 +298,20 @@ class DirentDirNode : public DirentNode { } // Found a leaf, stop the search. - if (orig_out_size != out->size()) + if (orig_out_size != out.size()) { + // If we've found all possible files in this directory, we don't need + // to add a regen dependency on the directory, we just need to ensure + // that the files are not removed. + if (fc.print_cond->Countable() && + fc.print_cond->Count() == out.size() - orig_out_size) { + fc.read_dirs->erase(*path); + for (unsigned i = orig_out_size; i < out.size(); i++) { + fc.found_files->push_back(out[i]); + } + } + return true; + } for (const auto& p : children_) { DirentNode* c = p.second; @@ -318,7 +363,7 @@ class DirentSymlinkNode : public DirentNode { virtual bool RunFind(const FindCommand& fc, int d, string* path, unordered_map* cur_read_dirs, - string* out) const override { + vector& out) const override { unsigned char type = DT_LNK; if (fc.follows_symlinks && errno_ != ENOENT) { if (errno_) { @@ -786,14 +831,13 @@ class FindEmulatorImpl : public FindEmulator { } } - const size_t orig_out_size = out->size(); + vector results; for (const string& finddir : fc.finddirs) { const string dir = ConcatDir(fc.chdir, finddir); if (!CanHandle(dir)) { LOG("FindEmulator: Cannot handle find dir (%s): %s", dir.c_str(), cmd.c_str()); - out->resize(orig_out_size); return false; } @@ -801,7 +845,6 @@ class FindEmulatorImpl : public FindEmulator { const DirentNode* base = FindDir(dir, &should_fallback); if (!base) { if (should_fallback) { - out->resize(orig_out_size); return false; } if (!fc.redirect_to_devnull) { @@ -814,18 +857,28 @@ class FindEmulatorImpl : public FindEmulator { string path = finddir; unordered_map cur_read_dirs; - if (!base->RunFind(fc, 0, &path, &cur_read_dirs, out)) { + if (!base->RunFind(fc, 0, &path, &cur_read_dirs, results)) { LOG("FindEmulator: RunFind failed: %s", cmd.c_str()); - out->resize(orig_out_size); return false; } } - if (!out->empty() && (*out)[out->size()-1] == ' ') - out->resize(out->size()-1); + if (results.size() > 0) { + // Calculate and reserve necessary space in out + size_t new_length = 0; + for (const string& result : results) { + new_length += result.size() + 1; + } + out->reserve(out->size() + new_length - 1); - if (fc.type == FindCommandType::FINDLEAVES) { - *out = SortWordsInString(*out); + if (fc.type == FindCommandType::FINDLEAVES) { + sort(results.begin(), results.end()); + } + + WordWriter writer(out); + for (const string& result : results) { + writer.Write(result); + } } LOG("FindEmulator: OK"); @@ -963,6 +1016,7 @@ class FindEmulatorImpl : public FindEmulator { FindCommand::FindCommand() : follows_symlinks(false), depth(INT_MAX), mindepth(INT_MIN), redirect_to_devnull(false), + found_files(new vector()), read_dirs(new unordered_set()) { } diff --git a/find.h b/find.h index ab92e67..1eee1e6 100644 --- a/find.h +++ b/find.h @@ -49,6 +49,7 @@ struct FindCommand { int mindepth; bool redirect_to_devnull; + unique_ptr> found_files; unique_ptr> read_dirs; private: diff --git a/ninja.cc b/ninja.cc index 05d0ad1..579cea3 100644 --- a/ninja.cc +++ b/ninja.cc @@ -754,6 +754,11 @@ class NinjaGenerator { DumpString(fp, d); } + DumpInt(fp, cr->find->found_files->size()); + for (StringPiece s : *cr->find->found_files) { + DumpString(fp, ConcatDir(cr->find->chdir, s)); + } + DumpInt(fp, cr->find->read_dirs->size()); for (StringPiece s : *cr->find->read_dirs) { DumpString(fp, ConcatDir(cr->find->chdir, s)); diff --git a/regen.cc b/regen.cc index 01bacb7..137d205 100644 --- a/regen.cc +++ b/regen.cc @@ -59,6 +59,7 @@ class StampChecker { string cmd; string result; vector missing_dirs; + vector files; vector read_dirs; }; @@ -245,6 +246,11 @@ class StampChecker { LOAD_STRING(fp, &s); sr->missing_dirs.push_back(s); } + int num_files = LOAD_INT(fp); + for (int j = 0; j < num_files; j++) { + LOAD_STRING(fp, &s); + sr->files.push_back(s); + } int num_read_dirs = LOAD_INT(fp); for (int j = 0; j < num_read_dirs; j++) { LOAD_STRING(fp, &s); @@ -303,6 +309,10 @@ class StampChecker { if (Exists(dir)) return true; } + for (const string& file : sr->files) { + if (!Exists(file)) + return true; + } for (const string& dir : sr->read_dirs) { // We assume we rarely do a significant change for the top // directory which affects the results of find command. -- cgit v1.2.3