Cache MatchCache results for all changes
Since walking changes ends up repeating many matches for the same
changes, store the results for all change matches instead of throwing
them away when moving to a new change. Although this change ends up
storing significantly more results, the space needs of this change
should not grow unreasonably. The approximate growth should be by the
size of a HashMap by query Strings populated with an Integer to point to
the results, plus a pointer to two bits sets per query, plus
approximately 2 bits per change (in the worse case) due to the space
efficient BitMap based Table used to store these results.
In a massive real world case where there are likely around 34K changes
and approximately max 6K query results per change (2K tasks * 3
queries). The extra storage for the HashMap likely works out likely
around at least 1.6MB + the size of the query Strings, i.e. likely less
than 34MB. The Pointers to the BitMaps will likely use around 6K queries
* 16B = 96K. And finally, an additional 8K for the result BitMaps. This
likely adds up to around 36MB for a status:open --task--aplicable query.
This should give a good enough picture to show that this should not have
a serious impact on memory, and testing confirms that is the case.
In the sample walking ancestors this caching saves a small but
measurable amount of the total time. In the case of a task.config which
walks all dependencies for a change when run with status:open --no-limit
--task--applicable the gain can be seen below.
Before this change: 4m18s 4m4s 4m37s 3m56s 4m5s
After this change: 3m37s 3m34s 4m6s 6m23s 3m42s
Change-Id: I5b2d2b948e30a2f410be3a400522b9d3db045518
6 files changed
