Find emulator unnecessarily greedy

[kevin-brodsky-arm]

I have been working on Android for a few years now, and I have been facing a rather annoying issue for almost as long: whenever the build system decides that all the Ninja files need to be regenerated and the Makefiles included again, kati gets stuck on including art/Android.mk, sometimes for a very long time (10 min+). Other members of my team have also encountered that issue.

A few weeks ago, I finally realised why this happens. Since Soong passes --use_find_emulator, when kati encounters the first find in the Makefiles (which happens to be in art/Android.mk), it calls ConstructDirectoryTree(""), creating a representation of the whole tree in memory. This is already a very greedy approach when starting from a clean tree, but in my case it gets much worse, as I store multiple output directories in the root of the tree. In fact, since I don't have enough space on my SSD to store all those output directories, I instead store them on HDD and put symlinks at the root. As a result, kati spends a lot of time constructing a tree of irrelevant directories on a slow medium. #86 seems to complain about a similar same issue, but AFAICT the underlying issue didn't actually get resolved.

Unsurprisingly, disabling the find emulator results in a large performance increase in my situation. However, I can see how that approach can be useful; I think it just needs to be made less greedy. I can think of a few ways to achieve that:

1. Construct the directory tree as needed. No find command ever starts from the root of the tree, it always specifies a subdirectory. By indexing only the relevant subdirectories as encountered, unrelated directories would not cause any issue.
2. Pass a list of top-level directories to --use_find_emulator, so that only those are indexed.
3. Ignore top-level symlinks.

Option 1 is probably the best, but requires refactoring the find emulator quite a bit. Option 2 is much easier to implement but requires a corresponding change in Soong. Option 3 is probably too ad-hoc.

Any thoughts?

[danw]

Yeah, we've hit similar problems elsewhere, but I hadn't seen it as much here. Soong also has a similar concept, and flat out ignores directories with certain "marker" files in them, so it never recurses into output directories. But for legacy reasons, I suspect kati's find emulator may still need to know about the current output directory.

At first glance, I kinda like option 1 -- it would also mean that once everything in a certain subdir got converted to Soong, we'd no longer need to walk that directory with Kati (at least with enough cleanup). But as you say, it could be a large project. And would we limit it to each top level directory, or something further down? It's possible that someone is using a directory to store their output directories... (and we'd want further down for some of the soong conversion optimizations)

Option 3 seems to only work if you've got problematic symlinks, but not if there are actually multiple output trees in the source tree.

I guess with option 2 we'd read the full list in soong_ui, filter out the known output dirs, and then add back the current output directory?

I may take a quick look at option 1 and see if a lazy loading approach would work. It may not be too bad.

[kevin-brodsky-arm]

Thanks for you comment Dan. I hadn't realised that some Android.mk's actually use find commands in the output directory! It shouldn't make too much difference for either option 1 or 2 though.

I think with option 1 you don't have to assume anything about top-level directories, instead you just cache the results every time you emulate a find command for a given path (which means that you never traverse more directories than the actual find command would have traversed).

For option 2 I was thinking about having some kind of hardcoded top-level directories list in Soong (+ the current output directory), but this may not be ideal. Soong should know the path of all projects though, so it could in principle figure out what are the top-level directories.

[danw]

Soong doesn't know the paths that are in your source -- it's agnostic to whether you're using git / tarballs / perforce / etc. (We may care about folders that don't contain Android.mk / Android.bp files too)

I'm still planning on looking at the on-demand solution, but another option I just thought about is to use the marker files to prune the list, and use the fallback path if someone does use find / etc into those directories. (If the find emulator doesn't understand the find command, or it's pointing outside the directory the find emulator cached, it falls back to actually calling find).

Separately, I'd love to get rid of that fallback path, since it's an easy way to make your build times much longer than they should be, but that's a separate topic.

[kevin-brodsky-arm]

Using marker files and falling back if needed sounds like a good solution for the time being, it also makes it consistent with Soong's own finder. That shouldn't really increase the use of the fallback path, since these directories are not supposed to be looked into in the first place.