Revision b16a8277644e4b1d21c08d97de757105039dc7ae authored by Derrick Stolee on 16 September 2020, 18:07:52 UTC, committed by Junio C Hamano on 17 September 2020, 16:31:25 UTC
Commit e3696980 (diff: halt tree-diff early after max_changes,
2020-03-30) intended to create a mechanism to short-circuit a diff
calculation after a certain number of paths were modified. By
incrementing a "num_changes" counter throughout the recursive
ll_diff_tree_paths(), this was supposed to match the number of changes
that would be written into the changed-path Bloom filters.
Unfortunately, this was not implemented correctly and instead misses
simple cases like file modifications. This then does not stop very
large changed-path filters from being written (unless they add or remove
many files).

To start, change the implementation in ll_diff_tree_paths() to instead
use the global diff_queue_diff struct's 'nr' member as the count. This
is a way to simplify the logic instead of making more mistakes in the
complicated diff code.

This has a drawback: the diff_queue_diff struct only lists the paths
corresponding to blob changes, not their leading directories. Thus,
get_or_compute_bloom_filter() needs an additional check to see if the
hashmap with the leading directories becomes too large.

One reason why this was not caught by test cases was that the test in
t4216-log-bloom.sh that was supposed to check this "too many changes"
condition only checked this on the initial commit of a repository. The
old logic counted these values correctly. Update this test in a few
ways:

1. Use GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS to reduce the limit,
   allowing smaller commits to engage with this logic.

2. Create several interesting cases of edits, adds, removes, and mode
   changes (in the second commit). By testing both sides of the
   inequality with the *_MAX_CHANGED_PATHS variable, we can see that
   the count is exactly correct, so none of these changes are missed
   or over-counted.

3. Use the trace2 data value filter_found_large to verify that these
   commits are on the correct side of the limit.

Another way to verify the behavior is correct is through performance
tests. By testing on my local copies of the Git repository and the Linux
kernel repository, I could measure the effect of these short-circuits
when computing a fresh commit-graph file with changed-path Bloom filters
using the command

  GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS=N time \
    git commit-graph write --reachable --changed-paths

and reporting the wall time and resulting commit-graph size.

For Git, the results are

|        |      N=1       |       N=10     |      N=512     |
|--------|----------------|----------------|----------------|
| HEAD~1 | 10.90s  9.18MB | 11.11s  9.34MB | 11.31s  9.35MB |
| HEAD   |  9.21s  8.62MB | 11.11s  9.29MB | 11.29s  9.34MB |

For Linux, the results are

|        |       N=1      |     N=20      |     N=512     |
|--------|----------------|---------------|---------------|
| HEAD~1 | 61.28s  64.3MB | 76.9s  72.6MB | 77.6s  72.6MB |
| HEAD   | 49.44s  56.3MB | 68.7s  65.9MB | 69.2s  65.9MB |

Naturally, the improvement becomes much less as the limit grows, as
fewer commits satisfy the short-circuit.

Reported-by: SZEDER Gábor <szeder.dev@gmail.com>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
1 parent 9a7a9ed
Raw File
pretty.h
#ifndef PRETTY_H
#define PRETTY_H

#include "cache.h"
#include "string-list.h"

struct commit;
struct strbuf;

/* Commit formats */
enum cmit_fmt {
	CMIT_FMT_RAW,
	CMIT_FMT_MEDIUM,
	CMIT_FMT_DEFAULT = CMIT_FMT_MEDIUM,
	CMIT_FMT_SHORT,
	CMIT_FMT_FULL,
	CMIT_FMT_FULLER,
	CMIT_FMT_ONELINE,
	CMIT_FMT_EMAIL,
	CMIT_FMT_MBOXRD,
	CMIT_FMT_USERFORMAT,

	CMIT_FMT_UNSPECIFIED
};

struct pretty_print_context {
	/*
	 * Callers should tweak these to change the behavior of pp_* functions.
	 */
	enum cmit_fmt fmt;
	int abbrev;
	const char *after_subject;
	int preserve_subject;
	struct date_mode date_mode;
	unsigned date_mode_explicit:1;
	int print_email_subject;
	int expand_tabs_in_log;
	int need_8bit_cte;
	char *notes_message;
	struct reflog_walk_info *reflog_info;
	struct rev_info *rev;
	const char *output_encoding;
	struct string_list *mailmap;
	int color;
	struct ident_split *from_ident;
	unsigned encode_email_headers:1;

	/*
	 * Fields below here are manipulated internally by pp_* functions and
	 * should not be counted on by callers.
	 */
	struct string_list in_body_headers;
	int graph_width;
};

/* Check whether commit format is mail. */
static inline int cmit_fmt_is_mail(enum cmit_fmt fmt)
{
	return (fmt == CMIT_FMT_EMAIL || fmt == CMIT_FMT_MBOXRD);
}

struct userformat_want {
	unsigned notes:1;
	unsigned source:1;
};

/* Set the flag "w->notes" if there is placeholder %N in "fmt". */
void userformat_find_requirements(const char *fmt, struct userformat_want *w);

/*
 * Shortcut for invoking pretty_print_commit if we do not have any context.
 * Context would be set empty except "fmt".
 */
void pp_commit_easy(enum cmit_fmt fmt, const struct commit *commit,
			struct strbuf *sb);

/*
 * Get information about user and date from "line", format it and
 * put it into "sb".
 * Format of "line" must be readable for split_ident_line function.
 * The resulting format is "what: name <email> date".
 */
void pp_user_info(struct pretty_print_context *pp, const char *what,
			struct strbuf *sb, const char *line,
			const char *encoding);

/*
 * Format title line of commit message taken from "msg_p" and
 * put it into "sb".
 * First line of "msg_p" is also affected.
 */
void pp_title_line(struct pretty_print_context *pp, const char **msg_p,
			struct strbuf *sb, const char *encoding,
			int need_8bit_cte);

/*
 * Get current state of commit message from "msg_p" and continue formatting
 * by adding indentation and '>' signs. Put result into "sb".
 */
void pp_remainder(struct pretty_print_context *pp, const char **msg_p,
			struct strbuf *sb, int indent);

/*
 * Create a text message about commit using given "format" and "context".
 * Put the result to "sb".
 * Please use this function for custom formats.
 */
void repo_format_commit_message(struct repository *r,
			const struct commit *commit,
			const char *format, struct strbuf *sb,
			const struct pretty_print_context *context);
#ifndef NO_THE_REPOSITORY_COMPATIBILITY_MACROS
#define format_commit_message(c, f, s, con) \
	repo_format_commit_message(the_repository, c, f, s, con)
#endif

/*
 * Parse given arguments from "arg", check it for correctness and
 * fill struct rev_info.
 */
void get_commit_format(const char *arg, struct rev_info *);

/*
 * Make a commit message with all rules from given "pp"
 * and put it into "sb".
 * Please use this function if you have a context (candidate for "pp").
 */
void pretty_print_commit(struct pretty_print_context *pp,
			const struct commit *commit,
			struct strbuf *sb);

/*
 * Change line breaks in "msg" to "line_separator" and put it into "sb".
 * Return "msg" itself.
 */
const char *format_subject(struct strbuf *sb, const char *msg,
			const char *line_separator);

/* Check if "cmit_fmt" will produce an empty output. */
int commit_format_is_empty(enum cmit_fmt);

#endif /* PRETTY_H */
back to top