[RFC/PATCHv2 0/6] generation numbers for faster traversals

[RFC/PATCHv2 0/6] generation numbers for faster traversals

[Jeff King]

Here's an updated version of the series posted here:

  http://article.gmane.org/gmane.comp.version-control.git/176861

I'll discuss specific changes in each patch, but the summary is:

  1. object-cache is now called metadata-cache.

  2. The interface to "decorate" and "metadata-cache" is a little
     cleaner, and it's harder to break it by changing the "width" field
     at runtime.

  3. Cache files have a header with a version for future-proofing.

  4. Cache files on disk are automatically invalidated if grafts or
     replace refs change.

The patches are:

  [1/6]: decorate: allow storing values instead of pointers
  [2/6]: add metadata-cache infrastructure
  [3/6]: commit: add commit_generation function
  [4/6]: pretty: support %G to show the generation number of a commit
  [5/6]: check commit generation cache validity against grafts
  [6/6]: limit "contains" traversals based on commit generation

-Peff

[RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers

[Jeff King]

The decorate API provides a mapping of objects to arbitrary
values. Until now, it did this by allowing you to store a
void pointer, which could point to other storage. This has
two problems:

  1. It's inefficient. To store even a small value, you have
     to allocate persistent storage. So we end up storing
     both the value and a pointer to it.

  2. It's a pain to use. To avoid heap overhead for small
     values, you have to either use a custom allocater, or
     you have to shoe-horn the value into the void pointer
     (if it's small enough to fit).

This patch lets you store fixed-size values directly in the
hash table without allocating them elsewhere. This is a
definite win for any value smaller than or equal to a
pointer. It's probably a win for slightly larger values, but
may eventually be slower for storing large structs (because
the values are copied when the hash grows).

It also provides a more natural interface for storing small
values; see the changes in fast-export.c, which can now drop
its pointer arithmetic magic.

The original "store and retrieve a void pointer" API is easy
to implement on top of this (the values we store are the
pointers). The add_decoration and lookup_decoration
functions are kept for compatibility.

Signed-off-by: Jeff King <peff@peff.net>
---
The "width" field is now const; you must either use a static
initializer or overwrite a struct decoration via memset. This gives us a
little more language-enforced safety.

The "stride" and "end" fields were removed in favor of run-time
calculation. The calculations are wrapped in inline functions to give
the optimizer a chance to remove them.

Since we're translating sizes to pointers in our loops via these
functions now anyway, I made the iteration interface a bit more sane.
It used to be:

  unsigned char *p;
  for (p = n->hash; p < n->end; p += n->stride) {
    struct object_decoration *e = (struct object_decoration *)p;
    ...
  }

which really leaks ugly implementation details. You can now do:

  int i;
  for (i = 0; i < n->size; i++) {
    struct object_decoration *e = decoration_slot(n, i);
    ...
  }

which is a bit more natural.

I peeked at the output of "gcc -O3"; it doesn't actually hoist much of
the decoration_slot calculation out of the loop. But I measured the code
from the previous series with this one, and wasn't able to detect a
difference. So I think using pointers was just a silly premature
micro-optimization.

 Documentation/technical/api-decorate.txt |  164 +++++++++++++++++++++++++++++-
 builtin/fast-export.c                    |   29 ++----
 decorate.c                               |   70 +++++++++----
 decorate.h                               |   37 ++++++-
 4 files changed, 251 insertions(+), 49 deletions(-)

diff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt
index 1d52a6c..b048b28 100644
--- a/Documentation/technical/api-decorate.txt
+++ b/Documentation/technical/api-decorate.txt
@@ -1,6 +1,166 @@
 decorate API
 ============
 
-Talk about <decorate.h>
+The decorate API is a system for efficiently mapping objects to values
+in memory. It is slightly slower than an actual member of an object
+struct (because it incurs a hash lookup), but it uses less memory when
+the mapping is not in use, or when the number of decorated objects is
+small compared to the total number of objects.
 
-(Linus)
+For efficiency, the mapping is capable of storing actual byte values, as
+long as the byte values for each element are of a fixed size. So one
+could, for example, map objects into 32-bit integers. For ease of use,
+functions are provided for storing the values of arbitrary pointers,
+which can point to strings or structs.
+
+Data Structures
+---------------
+
+`struct decoration`::
+
+	This structure represents a single mapping of objects to
+	values. Its fields are:
+
+	`name`:::
+		This field is not used by the decorate API itself, but
+		may be used by calling code.
+
+	`width`:::
+		This field specifies the width (in units of `char`) of
+		the values to be stored. This field must be set to its
+		final value when the decoration struct is initialized.
+		A width of `0` is equivalent to `sizeof(void *)`.
+
+	`nr`:::
+		The number of objects currently mapped by the
+		decoration.
+
+	`size`:::
+		The number of hash slots allocated; this is kept to at
+		least 3/2 of the number of actual slots used, to keep
+		the hash sparse.
+
+	`hash`:::
+		A pointer to an array of actual `object_decoration`
+		structs. Note that because the width of `struct
+		object_decoration` is not known until runtime, this
+		array is stored with type `unsigned char *`. To access
+		individual items, one must perform pointer arithmetic;
+		see the `decoration_by_offset` function below.
+
+`struct object_decoration`::
+
+	A structure representing the decoration of a single object.
+	Callers will not normally need to use this object unless they
+	are iterating all elements in the decoration hash. The `base`
+	field points to the object being mapped (or `NULL` if it is
+	an empty hash slot). The `decoration` field stores the mapped
+	value as a sequence of bytes; use the `width` field in `struct
+	decoration` to know the exact size.
+
+
+Functions
+---------
+
+`add_decoration_value`::
+
+	Add a mapping from an object to a sequence of bytes. The number
+	of bytes pointed to by `decoration` should be equal to the
+	`width` field of the `struct decoration`. If the `old` parameter
+	is not NULL and a there was already a value for the object, the
+	bytes of the old value are copied into `old`.  The return value
+	is `1` if there was a previous value, or `0` otherwise. Note
+	that if there is no previous value, then `old` is left
+	untouched; it is the responsibility of the caller to either
+	check the return value or to set a sentinel value in `old`.
+
+`lookup_decoration_value`::
+
+	Retrieve a decoration from the mapping. The return value is a
+	pointer to the sequence of bytes representing the value (of
+	length `width`), or `NULL` if no value is found.
+
+`add_decoration`::
+
+	Add a mapping from an object to a void pointer. If a previous
+	pointer exists for the object, it is returned; otherwise, `NULL`
+	is returned.
+
+`lookup_decoration`::
+
+	Retrieve a void pointer from the mapping. The return value is
+	the stored pointer, or `NULL` if there is no stored pointer.
+
+`decoration_slot`::
+
+	Retrieve the decoration stored at slot `i` in the hash table.
+	If the `base` field of the returned `struct object_decoration`
+	is `NULL`, then no value is stored at that slot. This function
+	is useful when iterating over the entire contents of the hash
+	table. See the iteration example below.
+
+
+Examples
+--------
+
+Store and retrieve pointers to structs:
+
+-------------------------------------------------------------------
+/* no need to set width parameter; it defaults to sizeof(void *) */
+static struct decoration commit_foos;
+
+void store_foo(const struct commit *c, const char *name)
+{
+	struct foo *value = alloc_foo(name);
+	struct foo *old;
+
+	old = add_decoration(&commit_foos, c->object, value);
+	free(old);
+}
+
+const struct foo *get_foo(const struct commit *c)
+{
+	return lookup_decoration(&commit_foos, c->object);
+}
+-------------------------------------------------------------------
+
+Store and retrieve `unsigned long` integers:
+
+-------------------------------------------------------------------
+static struct decoration longs = { "my longs", sizeof(unsigned long) };
+
+void store_long(const struct object *obj, unsigned long value)
+{
+	unsigned long old;
+	if (add_decoration_value(&longs, obj, &value, &old)
+		printf("old value was %lu\n", old);
+}
+
+void print_long(const struct object *obj)
+{
+	unsigned long *value = lookup_decoration_value(&longs, obj);
+	if (!value)
+		printf("no value\n");
+	else
+		printf("value is %lu\n", *value);
+}
+-------------------------------------------------------------------
+
+Iterate over all stored decorations:
+
+-------------------------------------------------------------------
+void dump_longs(void)
+{
+	int i;
+	for (i = 0; i < longs.size; i++) {
+		struct object_decoration *e = decoration_slot(&longs, i);
+		unsigned long *value = (unsigned long *)e->decoration;
+
+		/* empty hash slot */
+		if (!e->base)
+			continue;
+
+		printf("%s -> %lu\n", sha1_to_hex(e->base->sha1), *value);
+	}
+}
+-------------------------------------------------------------------
diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index daf1945..82b458d 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -59,7 +59,7 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt,
 	return 0;
 }
 
-static struct decoration idnums;
+static struct decoration idnums = { NULL, sizeof(uint32_t) };
 static uint32_t last_idnum;
 
 static int has_unshown_parent(struct commit *commit)
@@ -73,20 +73,9 @@ static int has_unshown_parent(struct commit *commit)
 	return 0;
 }
 
-/* Since intptr_t is C99, we do not use it here */
-static inline uint32_t *mark_to_ptr(uint32_t mark)
-{
-	return ((uint32_t *)NULL) + mark;
-}
-
-static inline uint32_t ptr_to_mark(void * mark)
-{
-	return (uint32_t *)mark - (uint32_t *)NULL;
-}
-
 static inline void mark_object(struct object *object, uint32_t mark)
 {
-	add_decoration(&idnums, object, mark_to_ptr(mark));
+	add_decoration_value(&idnums, object, &mark, NULL);
 }
 
 static inline void mark_next_object(struct object *object)
@@ -96,10 +85,10 @@ static inline void mark_next_object(struct object *object)
 
 static int get_object_mark(struct object *object)
 {
-	void *decoration = lookup_decoration(&idnums, object);
-	if (!decoration)
+	uint32_t *mark = lookup_decoration_value(&idnums, object);
+	if (!mark)
 		return 0;
-	return ptr_to_mark(decoration);
+	return *mark;
 }
 
 static void show_progress(void)
@@ -537,8 +526,6 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)
 static void export_marks(char *file)
 {
 	unsigned int i;
-	uint32_t mark;
-	struct object_decoration *deco = idnums.hash;
 	FILE *f;
 	int e = 0;
 
@@ -547,15 +534,15 @@ static void export_marks(char *file)
 		die_errno("Unable to open marks file %s for writing.", file);
 
 	for (i = 0; i < idnums.size; i++) {
+		struct object_decoration *deco = decoration_slot(&idnums, i);
 		if (deco->base && deco->base->type == 1) {
-			mark = ptr_to_mark(deco->decoration);
-			if (fprintf(f, ":%"PRIu32" %s\n", mark,
+			uint32_t *mark = (uint32_t *)deco->decoration;
+			if (fprintf(f, ":%"PRIu32" %s\n", *mark,
 				sha1_to_hex(deco->base->sha1)) < 0) {
 			    e = 1;
 			    break;
 			}
 		}
-		deco++;
 	}
 
 	e |= ferror(f);
diff --git a/decorate.c b/decorate.c
index 2f8a63e..5a0747e 100644
--- a/decorate.c
+++ b/decorate.c
@@ -14,44 +14,48 @@ static unsigned int hash_obj(const struct object *obj, unsigned int n)
 	return hash % n;
 }
 
-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)
+static int insert_decoration(struct decoration *n, const struct object *base,
+			     const void *decoration, void *old)
 {
 	int size = n->size;
-	struct object_decoration *hash = n->hash;
+	unsigned long width = decoration_width(n);
 	unsigned int j = hash_obj(base, size);
 
-	while (hash[j].base) {
-		if (hash[j].base == base) {
-			void *old = hash[j].decoration;
-			hash[j].decoration = decoration;
-			return old;
+	while (1) {
+		struct object_decoration *e = decoration_slot(n, j);
+		if (!e->base) {
+			e->base = base;
+			memcpy(e->decoration, decoration, width);
+			n->nr++;
+			return 0;
+		}
+		if (e->base == base) {
+			if (old)
+				memcpy(old, e->decoration, width);
+			memcpy(e->decoration, decoration, width);
+			return 1;
 		}
 		if (++j >= size)
 			j = 0;
 	}
-	hash[j].base = base;
-	hash[j].decoration = decoration;
-	n->nr++;
-	return NULL;
 }
 
 static void grow_decoration(struct decoration *n)
 {
 	int i;
 	int old_size = n->size;
-	struct object_decoration *old_hash = n->hash;
+	unsigned char *old_hash = n->hash;
 
 	n->size = (old_size + 1000) * 3 / 2;
-	n->hash = xcalloc(n->size, sizeof(struct object_decoration));
+	n->hash = xcalloc(n->size, decoration_stride(n));
 	n->nr = 0;
 
 	for (i = 0; i < old_size; i++) {
-		const struct object *base = old_hash[i].base;
-		void *decoration = old_hash[i].decoration;
-
-		if (!base)
-			continue;
-		insert_decoration(n, base, decoration);
+		struct object_decoration *e =
+			(struct object_decoration *)
+			(old_hash + i * decoration_stride(n));
+		if (e->base)
+			insert_decoration(n, e->base, e->decoration, NULL);
 	}
 	free(old_hash);
 }
@@ -60,15 +64,35 @@ static void grow_decoration(struct decoration *n)
 void *add_decoration(struct decoration *n, const struct object *obj,
 		void *decoration)
 {
-	int nr = n->nr + 1;
+	void *old = NULL;
+	add_decoration_value(n, obj, &decoration, &old);
+	return old;
+}
 
+int add_decoration_value(struct decoration *n,
+			 const struct object *obj,
+			 const void *decoration,
+			 void *old)
+{
+	int nr = n->nr + 1;
 	if (nr > n->size * 2 / 3)
 		grow_decoration(n);
-	return insert_decoration(n, obj, decoration);
+	return insert_decoration(n, obj, decoration, old);
 }
 
 /* Lookup a decoration pointer */
-void *lookup_decoration(struct decoration *n, const struct object *obj)
+void *lookup_decoration(const struct decoration *n, const struct object *obj)
+{
+	void **v;
+
+	v = lookup_decoration_value(n, obj);
+	if (!v)
+		return NULL;
+	return *v;
+}
+
+void *lookup_decoration_value(const struct decoration *n,
+			      const struct object *obj)
 {
 	unsigned int j;
 
@@ -77,7 +101,7 @@ void *lookup_decoration(struct decoration *n, const struct object *obj)
 		return NULL;
 	j = hash_obj(obj, n->size);
 	for (;;) {
-		struct object_decoration *ref = n->hash + j;
+		struct object_decoration *ref = decoration_slot(n, j);
 		if (ref->base == obj)
 			return ref->decoration;
 		if (!ref->base)
diff --git a/decorate.h b/decorate.h
index e732804..c0e8e3f 100644
--- a/decorate.h
+++ b/decorate.h
@@ -3,16 +3,47 @@
 
 struct object_decoration {
 	const struct object *base;
-	void *decoration;
+	unsigned char decoration[FLEX_ARRAY];
 };
 
 struct decoration {
 	const char *name;
+	/* width of data we're holding; must be set before adding */
+	const unsigned int width;
 	unsigned int size, nr;
-	struct object_decoration *hash;
+	/*
+	 * The hash contains object_decoration structs, but we don't know their
+	 * size until runtime. So we store is as a pointer to characters to
+	 * make pointer arithmetic easier.
+	 */
+	unsigned char *hash;
 };
 
 extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);
-extern void *lookup_decoration(struct decoration *n, const struct object *obj);
+extern void *lookup_decoration(const struct decoration *n, const struct object *obj);
+
+extern int add_decoration_value(struct decoration *n,
+				const struct object *obj,
+				const void *decoration,
+				void *old);
+extern void *lookup_decoration_value(const struct decoration *n,
+				     const struct object *obj);
+
+static inline unsigned long decoration_width(const struct decoration *n)
+{
+	return n->width ? n->width : sizeof(void *);
+}
+
+static inline unsigned long decoration_stride(const struct decoration *n)
+{
+	return sizeof(struct object_decoration) + decoration_width(n);
+}
+
+static inline struct object_decoration *decoration_slot(const struct decoration *n,
+							unsigned i)
+{
+	return (struct object_decoration *)
+		(n->hash + (i * decoration_stride(n)));
+}
 
 #endif
-- 
1.7.6.37.g989c6

Re: [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers

[Jonathan Nieder]

(+cc: David Barr)
Hi,

Jeff King wrote:

> The decorate API provides a mapping of objects to arbitrary
> values. Until now, it did this by allowing you to store a
> void pointer, which could point to other storage. This has
> two problems:
[...]
> This patch lets you store fixed-size values directly in the
> hash table without allocating them elsewhere.

Nice idea.

> --- a/Documentation/technical/api-decorate.txt
> +++ b/Documentation/technical/api-decorate.txt
> @@ -1,6 +1,166 @@
>  decorate API
>  ============
>  
> -Talk about <decorate.h>
> +The decorate API is a system for efficiently mapping objects to values

Thanks for filling in the API docs!  That's awesome.

> +`struct object_decoration`::
> +
> +	A structure representing the decoration of a single object.
> +	Callers will not normally need to use this object unless they
> +	are iterating all elements in the decoration hash. The `base`
> +	field points to the object being mapped (or `NULL` if it is
> +	an empty hash slot). The `decoration` field stores the mapped
> +	value as a sequence of bytes; use the `width` field in `struct
> +	decoration` to know the exact size.

So the `decoration` field is an array rather than a pointer now,
hence...

[...]
> +void dump_longs(void)
> +{
> +	int i;
> +	for (i = 0; i < longs.size; i++) {
> +		struct object_decoration *e = decoration_slot(&longs, i);
> +		unsigned long *value = (unsigned long *)e->decoration;
> +
> +		/* empty hash slot */
> +		if (!e->base)
> +			continue;
> +
> +		printf("%s -> %lu\n", sha1_to_hex(e->base->sha1), *value);

... a cast is needed to use it.  Makes some sense.

What alignment guarantees are there for the field, if any?  I'm
especially worried about platforms like sparc32 where the pointer
width is 32 bits but some types need to be aligned to 64 bits.

> --- a/builtin/fast-export.c
> +++ b/builtin/fast-export.c
[...]

Nice.

> @@ -547,15 +534,15 @@ static void export_marks(char *file)
>  		die_errno("Unable to open marks file %s for writing.", file);
>  
>  	for (i = 0; i < idnums.size; i++) {
> +		struct object_decoration *deco = decoration_slot(&idnums, i);
>  		if (deco->base && deco->base->type == 1) {
> -			mark = ptr_to_mark(deco->decoration);
> -			if (fprintf(f, ":%"PRIu32" %s\n", mark,
> +			uint32_t *mark = (uint32_t *)deco->decoration;
> +			if (fprintf(f, ":%"PRIu32" %s\n", *mark,
>  				sha1_to_hex(deco->base->sha1)) < 0) {

Is this okay according to strict aliasing rules?  Maybe it would be
safer to write

			uint32_t mark;
			memcpy(&mark, deco->decoration, sizeof(mark));

which generates the same code in current versions of gcc on x86 if I
remember correctly.

> --- a/decorate.c
> +++ b/decorate.c
> @@ -14,44 +14,48 @@ static unsigned int hash_obj(const struct object *obj, unsigned int n)
>  	return hash % n;
>  }
>  
> -static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)
> +static int insert_decoration(struct decoration *n, const struct object *base,
> +			     const void *decoration, void *old)
>  {
>  	int size = n->size;
> -	struct object_decoration *hash = n->hash;
> +	unsigned long width = decoration_width(n);

Micronit: why not size_t?

>  	unsigned int j = hash_obj(base, size);
>  
> -	while (hash[j].base) {
> -		if (hash[j].base == base) {
> -			void *old = hash[j].decoration;
> -			hash[j].decoration = decoration;
> -			return old;
> +	while (1) {

Microoptimization: the modulo operation can avoid the conditional (j >= size):

	for (j = hash_obj(base, size); ; j = (j + 1) % size) {
	}

By the way, how do we know this loop will terminate?  Is it because
the insertion function is careful to make sure the table never gets
filled?

[...]
>  static void grow_decoration(struct decoration *n)
>  {
>  	int i;
>  	int old_size = n->size;
> -	struct object_decoration *old_hash = n->hash;
> +	unsigned char *old_hash = n->hash;
>  
>  	n->size = (old_size + 1000) * 3 / 2;
> -	n->hash = xcalloc(n->size, sizeof(struct object_decoration));
> +	n->hash = xcalloc(n->size, decoration_stride(n));
>  	n->nr = 0;
>  
>  	for (i = 0; i < old_size; i++) {
> -		const struct object *base = old_hash[i].base;
> -		void *decoration = old_hash[i].decoration;
> -
> -		if (!base)
> -			continue;
> -		insert_decoration(n, base, decoration);
> +		struct object_decoration *e =
> +			(struct object_decoration *)
> +			(old_hash + i * decoration_stride(n));
> +		if (e->base)
> +			insert_decoration(n, e->base, e->decoration, NULL);

I'm worried about alignment here, too.

[...]
> @@ -60,15 +64,35 @@ static void grow_decoration(struct decoration *n)
[...]
>  /* Lookup a decoration pointer */
> -void *lookup_decoration(struct decoration *n, const struct object *obj)
> +void *lookup_decoration(const struct decoration *n, const struct object *obj)
> +{
> +	void **v;
> +
> +	v = lookup_decoration_value(n, obj);
> +	if (!v)
> +		return NULL;
> +	return *v;
> +}

Maybe memcpy to avoid alignment problems?

	unsigned char *p;
	void *v;

	p = lookup_decoration_value(n, obj);
	if (!p)
		return NULL;
	memcpy(v, p, sizeof(v));
	return v;

But:

> +
> +void *lookup_decoration_value(const struct decoration *n,
> +			      const struct object *obj)
>  {
>  	unsigned int j;
>  
> @@ -77,7 +101,7 @@ void *lookup_decoration(struct decoration *n, const struct object *obj)
>  		return NULL;
>  	j = hash_obj(obj, n->size);
>  	for (;;) {
> -		struct object_decoration *ref = n->hash + j;
> +		struct object_decoration *ref = decoration_slot(n, j);
>  		if (ref->base == obj)
>  			return ref->decoration;

I worry that this could have alignment trouble anyway.

> --- a/decorate.h
> +++ b/decorate.h
> @@ -3,16 +3,47 @@
>  
>  struct object_decoration {
>  	const struct object *base;
> -	void *decoration;
> +	unsigned char decoration[FLEX_ARRAY];
>  };

On some platforms, this becomes

	struct object_decoration {
		const struct object *base;
		unsigned char decoration[];
	};

which I hope would create a type with the alignment of a pointer
(generally sufficient except in odd cases like sparc32).  But on
old-fashioned platforms, it is

	struct object_decoration {
		const struct object *base;
		unsigned char decoration[1];
	};

Will that be a problem, or is it standard for compilers to be smart
enough to pad to a nice alignment?

>  struct decoration {
>  	const char *name;
> +	/* width of data we're holding; must be set before adding */
> +	const unsigned int width;

Makes sense.

>  	unsigned int size, nr;
> -	struct object_decoration *hash;
> +	/*
> +	 * The hash contains object_decoration structs, but we don't know their
> +	 * size until runtime. So we store is as a pointer to characters to
> +	 * make pointer arithmetic easier.
> +	 */
> +	unsigned char *hash;
>  };
[...]
> +extern int add_decoration_value(struct decoration *n,
> +				const struct object *obj,
> +				const void *decoration,
> +				void *old);
> +extern void *lookup_decoration_value(const struct decoration *n,
> +				     const struct object *obj);

If we're willing to incur the cost of a copy that assumes unaligned
objects, perhaps

	extern int lookup_decoration_value(const struct decoration *n,
				const struct object *obj,
				void *result, size_t width);

would be safer.

Aside from the alignment and strict-aliasing worries, this looks very
nice.  Thanks for writing it.

Regards,
Jonathan

Re: [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers

[Jeff King]

On Wed, Jul 13, 2011 at 12:52:50PM -0500, Jonathan Nieder wrote:

> > +void dump_longs(void)
> > +{
> > +	int i;
> > +	for (i = 0; i < longs.size; i++) {
> > +		struct object_decoration *e = decoration_slot(&longs, i);
> > +		unsigned long *value = (unsigned long *)e->decoration;
> > +
> > +		/* empty hash slot */
> > +		if (!e->base)
> > +			continue;
> > +
> > +		printf("%s -> %lu\n", sha1_to_hex(e->base->sha1), *value);
> 
> ... a cast is needed to use it.  Makes some sense.
> 
> What alignment guarantees are there for the field, if any?  I'm
> especially worried about platforms like sparc32 where the pointer
> width is 32 bits but some types need to be aligned to 64 bits.

We're packing these structs into a heap-allocated byte array. Each
struct takes up the size of the struct as defined by the compiler, plus
$width bytes. So with a 32-bit pointer and 32-bit data, you are probably
looking at data fields offset by 32-bits. Which might be wrong on
sparc32.

The result of malloc is guaranteed to be aligned for any type. But for
arrays, I'm not sure how that is handled. The only thing that makes
sense to me is that a sparc compiler with something like:

  struct foo {
    struct bar *pointer; /* pointers are 32-bits */
    double value; /* assume doubles need to be 64-bit aligned */
  };

would have to actually put in 32-bits of padding to meet the alignment
goals (and possibly some padding at the end so that the followup struct
in an array is aligned properly). But I don't know how this is handled,
so I'm just guessing.

And if that is the case, then yeah, there may well be an alignment issue
here. It gets even worse if you try to store something with an odd
alignment, like a 3-byte sequence.

So perhaps the safest thing would be to always memcpy into a real,
properly aligned destination. I'd have to tweak the get_value interface
a little bit, but it's not a big deal. It's going to be a little bit
slower, of course, but I doubt the extra few instructions will be
measurable.

I have to say, though, between the alignment issues and the strict
aliasing, I am tempted to scrap this whole approach and just use macros
to define the few functions we need. It's not like these containers are
heterogenous, or that we have a ton of types. Right now we want to map
"void *" and "uint32_t". In the future, I'd like to map a 20-byte sha1.

Doing something like:

  #define DECLARE_DECORATION(name, type) \
    void decoration_get_##name(struct decoration_##name *, \
                               struct object *, \
                               type value); \
    int decoration_set_##name(struct decoration_##name *, \
                              struct object *, \
                              type *value);

  DECLARE_DECORATION(void, void *);
  DECLARE_DECORATION(uint32, uint32_t);

  /* and then do an IMPLEMENT_DECORATION macro inside decorate.c */

is tempting. Writing your functions inside macros like this is ugly, but
then we know it's right, because the compiler knows what the sizes are
at compile time. And the optimizer can do its job properly, because
we're not fiddling the types at runtime.

> >  	for (i = 0; i < idnums.size; i++) {
> > +		struct object_decoration *deco = decoration_slot(&idnums, i);
> >  		if (deco->base && deco->base->type == 1) {
> > -			mark = ptr_to_mark(deco->decoration);
> > -			if (fprintf(f, ":%"PRIu32" %s\n", mark,
> > +			uint32_t *mark = (uint32_t *)deco->decoration;
> > +			if (fprintf(f, ":%"PRIu32" %s\n", *mark,
> >  				sha1_to_hex(deco->base->sha1)) < 0) {
> 
> Is this okay according to strict aliasing rules?  Maybe it would be
> safer to write
> 
> 			uint32_t mark;
> 			memcpy(&mark, deco->decoration, sizeof(mark));
> 
> which generates the same code in current versions of gcc on x86 if I
> remember correctly.

I guess you didn't read my comments on v1 of the patch. :)

I'm not sure if it's OK or not. Curiously, doing this:

  uint32_t mark = *(uint32_t *)deco->decoration;

generates a warning under -fstrict-aliasing, but:

  uint32_t *mark = (uint32_t *)deco->decoration;
  /* now use *mark */;

does not. I'm not sure if there's a subtlety in the strict aliasing
rules that makes the latter OK, or if it is simply a bug that it doesn't
trigger the compiler warning.

Using memcpy would be the safest thing, both from an alignment and a
strict-aliasing point of view.

> > --- a/decorate.c
> > +++ b/decorate.c
> > @@ -14,44 +14,48 @@ static unsigned int hash_obj(const struct object *obj, unsigned int n)
> >  	return hash % n;
> >  }
> >  
> > -static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)
> > +static int insert_decoration(struct decoration *n, const struct object *base,
> > +			     const void *decoration, void *old)
> >  {
> >  	int size = n->size;
> > -	struct object_decoration *hash = n->hash;
> > +	unsigned long width = decoration_width(n);
> 
> Micronit: why not size_t?

No reason.

> >  	unsigned int j = hash_obj(base, size);
> >  
> > -	while (hash[j].base) {
> > -		if (hash[j].base == base) {
> > -			void *old = hash[j].decoration;
> > -			hash[j].decoration = decoration;
> > -			return old;
> > +	while (1) {
> 
> Microoptimization: the modulo operation can avoid the conditional (j >= size):
> 
> 	for (j = hash_obj(base, size); ; j = (j + 1) % size) {
> 	}

Yeah, that would work. I doubt the performance is measurable. I couldn't
even get a measurable difference in iterating using pointers versus
using indices and converting them to pointers during each run through
the loop. So I suspect we simply don't actually go through this loop
very many times (i.e., the hash is doing its job and entries are spread
out appropriately). So micro-optimizing is probably not worth it.

> By the way, how do we know this loop will terminate?  Is it because
> the insertion function is careful to make sure the table never gets
> filled?

Exactly. See grow_decoration. I had the same question when I looked at
the loop (the termination condition is part of the original code, which
is Linus's).

> > +void *lookup_decoration(const struct decoration *n, const struct object *obj)
> > +{
> > +	void **v;
> > +
> > +	v = lookup_decoration_value(n, obj);
> > +	if (!v)
> > +		return NULL;
> > +	return *v;
> > +}
> 
> Maybe memcpy to avoid alignment problems?
> 
> 	unsigned char *p;
> 	void *v;
> 
> 	p = lookup_decoration_value(n, obj);
> 	if (!p)
> 		return NULL;
> 	memcpy(v, p, sizeof(v));
> 	return v;

Yeah, that would solve it.

> > +void *lookup_decoration_value(const struct decoration *n,
> > +			      const struct object *obj)
> >  {
> >  	unsigned int j;
> >  
> > @@ -77,7 +101,7 @@ void *lookup_decoration(struct decoration *n, const struct object *obj)
> >  		return NULL;
> >  	j = hash_obj(obj, n->size);
> >  	for (;;) {
> > -		struct object_decoration *ref = n->hash + j;
> > +		struct object_decoration *ref = decoration_slot(n, j);
> >  		if (ref->base == obj)
> >  			return ref->decoration;
> 
> I worry that this could have alignment trouble anyway.

I don't think it has alignment problems with the value inside the
struct, since we are just passing a pointer back to it as a void *; it
is the caller who will dereference it. We could pass it back as an
unsigned char *, to make it clear to the caller that they need to
memcpy.

But if you mean there might be an alignment issue looking at the ->base
field of the "struct object_decoration", then yeah, I am not sure of
that.

> >  struct object_decoration {
> >  	const struct object *base;
> > -	void *decoration;
> > +	unsigned char decoration[FLEX_ARRAY];
> >  };
> 
> On some platforms, this becomes
> 
> 	struct object_decoration {
> 		const struct object *base;
> 		unsigned char decoration[];
> 	};
> 
> which I hope would create a type with the alignment of a pointer
> (generally sufficient except in odd cases like sparc32).  But on
> old-fashioned platforms, it is
> 
> 	struct object_decoration {
> 		const struct object *base;
> 		unsigned char decoration[1];
> 	};
> 
> Will that be a problem, or is it standard for compilers to be smart
> enough to pad to a nice alignment?

I don't know. Thanks for mentioning it; it was another issue I had
noticed while writing, but forgot to bring up when I posted the patches.

> If we're willing to incur the cost of a copy that assumes unaligned
> objects, perhaps
> 
> 	extern int lookup_decoration_value(const struct decoration *n,
> 				const struct object *obj,
> 				void *result, size_t width);
> 
> would be safer.

Agreed.

> Aside from the alignment and strict-aliasing worries, this looks very
> nice.  Thanks for writing it.

Thanks for the review. When I wrote it, and even now, I'm still very
unsure that the alignment and aliasing issues are right. It seems to
work so far for me, but:

  1. I'm on x86_64, which is not one of the more oddball platforms for
     alignment issues.

  2. I'm putting in "void *" and "uint32_t" values. Those are about as
     vanilla as you can get. But I don't want to leave a time bomb for
     somebody who tries to store a 3-byte sequence.

So it makes me a bit nervous, and why I'm very tempted by the ugly macro
solution.

-Peff

Re: [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers

[Jeff King]

On Wed, Jul 13, 2011 at 04:08:14PM -0400, Jeff King wrote:

> I have to say, though, between the alignment issues and the strict
> aliasing, I am tempted to scrap this whole approach and just use macros
> to define the few functions we need. It's not like these containers are
> heterogenous, or that we have a ton of types. Right now we want to map
> "void *" and "uint32_t". In the future, I'd like to map a 20-byte sha1.

So here's what that would look like (at least the decorate part).

Doing macro meta-programming like this makes me feel a little dirty, but
I actually think the result is more readable.

  [1/3]: implement generic key/value map
  [2/3]: fast-export: use object to uint32 map instead of "decorate"
  [3/3]: decorate: use "map" for the underlying implementation

What do you think?

-Peff

[PATCH 1/3] implement generic key/value map

[Jeff King]

It is frequently useful to have a fast, generic data
structure mapping keys to values. We already have something
like this in the "decorate" API, but it has two downsides:

  1. The key type must always be a "struct object *".

  2. The value type is a void pointer, which means it is
     inefficient and cumbersome for storing small values.
     One must either encode their value inside the void
     pointer, or allocate additional storage for the pointer
     to point to.

This patch introduces a generic map data structure, mapping
keys of arbitrary type to values of arbitrary type.

One possible strategy for implementation is to have a struct
that points to a sequence of bytes for each of the key and
the value, and to try to treat them as opaque in the code.
However, this code gets complex, has a lot of casts, and
runs afoul of violating alignment and strict aliasing rules.

This patch takes a different approach. We parameterize the
types in each map by putting the declarations and
implementations inside macros, and expand the macros with
the correct types. This lets the compiler see the actual
code, with its real types, and figure out things like struct
packing and alignment itself.

Signed-off-by: Jeff King <peff@peff.net>
---
In addition to switching from using void pointers to macro expansion,
this has one other difference from my previous patch: it handles
arbitrary types for keys, not just object pointers. This was mentioned
by Jakub, and would allow things like a fast bi-directional map for SVN
revision numbers and commits.

I tried to keep the implementation simple. Two things that could be changed:

  1. We can't assume that the map key is a pointer. So the sentinel
     "NULL" value isn't necessarily available to use, and we have to
     keep a separate bit in each hash entry to say "is this valid".
     This means when we _do_ store a pointer, we end up with an extra
     32 bits or so in each hash entry for the "used" flag.

     We could add a macro parameter for sentinel values, so that types
     which _can_ handle this efficiently don't have to pay the price.
     Or we could decide that mapping arbitrary keys isn't worth the
     hassle. I wrote this way to be flexible for future use; I don't
     personally have plans to add svn revision number mappings.

  2. It assumes values are assignable. That means storing something like
     "unsigned char sha1[20]" doesn't work. You can wrap it in a struct,
     but do we assume that struct assignment works everywhere? I didn't
     check, but I think it is in C89 but some antique compilers didn't
     allow it. Switching it to use memcpy() would be easy enough (or
     again, parameterizing so that assignable things don't have to pay
     the price).

 Makefile |    2 +
 map.c    |   86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 map.h    |   24 +++++++++++++++++
 3 files changed, 112 insertions(+), 0 deletions(-)
 create mode 100644 map.c
 create mode 100644 map.h

diff --git a/Makefile b/Makefile
index 46793d1..6242321 100644
--- a/Makefile
+++ b/Makefile
@@ -530,6 +530,7 @@ LIB_H += list-objects.h
 LIB_H += ll-merge.h
 LIB_H += log-tree.h
 LIB_H += mailmap.h
+LIB_H += map.h
 LIB_H += merge-file.h
 LIB_H += merge-recursive.h
 LIB_H += notes.h
@@ -621,6 +622,7 @@ LIB_OBJS += ll-merge.o
 LIB_OBJS += lockfile.o
 LIB_OBJS += log-tree.o
 LIB_OBJS += mailmap.o
+LIB_OBJS += map.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge-file.o
 LIB_OBJS += merge-recursive.o
diff --git a/map.c b/map.c
new file mode 100644
index 0000000..378cecb
--- /dev/null
+++ b/map.c
@@ -0,0 +1,86 @@
+#include "cache.h"
+#include "map.h"
+#include "object.h"
+
+static unsigned int hash_obj(const struct object *obj, unsigned int n)
+{
+	unsigned int hash;
+
+	memcpy(&hash, obj->sha1, sizeof(unsigned int));
+	return hash % n;
+}
+
+static unsigned int cmp_obj(const struct object *a, const struct object *b)
+{
+	return b == a;
+}
+
+#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \
+static int map_insert_##name(struct map_##name *m, \
+			     const ktype key, \
+			     vtype value, \
+			     vtype *old) \
+{ \
+	unsigned int j; \
+ \
+	for (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \
+		if (cmp_fun(m->hash[j].key, key)) { \
+			if (old) \
+				*old = m->hash[j].value; \
+			m->hash[j].value = value; \
+			return 1; \
+		} \
+	} \
+ \
+	m->hash[j].key = key; \
+	m->hash[j].value = value; \
+	m->hash[j].used = 1; \
+	m->nr++; \
+	return 0; \
+} \
+ \
+static void map_grow_##name(struct map_##name *m) \
+{ \
+	struct map_entry_##name *old_hash = m->hash; \
+	unsigned int old_size = m->size; \
+	unsigned int i; \
+ \
+	m->size = (old_size + 1000) * 3 / 2; \
+	m->hash = xcalloc(m->size, sizeof(*m->hash)); \
+	m->nr = 0; \
+ \
+	for (i = 0; i < old_size; i++) { \
+		if (!old_hash[i].used) \
+			continue; \
+		map_insert_##name(m, old_hash[i].key, old_hash[i].value, NULL); \
+	} \
+	free(old_hash); \
+} \
+ \
+int map_set_##name(struct map_##name *m, \
+		   const ktype key, \
+		   vtype value, \
+		   vtype *old) \
+{ \
+	if (m->nr >= m->size * 2 / 3) \
+		map_grow_##name(m); \
+	return map_insert_##name(m, key, value, old); \
+} \
+ \
+int map_get_##name(struct map_##name *m, \
+		   const ktype key, \
+		   vtype *value) \
+{ \
+	unsigned int j; \
+ \
+	if (!m->size) \
+		return 0; \
+ \
+	for (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \
+		if (cmp_fun(m->hash[j].key, key)) { \
+			*value = m->hash[j].value; \
+			return 1; \
+		} \
+	} \
+	return 0; \
+}
diff --git a/map.h b/map.h
new file mode 100644
index 0000000..496c5d1
--- /dev/null
+++ b/map.h
@@ -0,0 +1,24 @@
+#ifndef MAP_H
+#define MAP_H
+
+#define DECLARE_MAP(name, ktype, vtype) \
+struct map_entry_##name { \
+	const ktype key; \
+	vtype value; \
+	unsigned used:1; \
+}; \
+ \
+struct map_##name { \
+	unsigned int size, nr; \
+	struct map_entry_##name *hash; \
+}; \
+ \
+extern int map_get_##name(struct map_##name *, \
+			  const ktype key, \
+			  vtype *value); \
+extern int map_set_##name(struct map_##name *, \
+			  const ktype key, \
+			  vtype value, \
+			  vtype *old); \
+
+#endif /* MAP_H */
-- 
1.7.6.38.ge5b33

Re: [PATCH 1/3] implement generic key/value map

[Bert Wesarg]

On Thu, Jul 14, 2011 at 19:51, Jeff King <peff@peff.net> wrote:
> It is frequently useful to have a fast, generic data
> structure mapping keys to values. We already have something
> like this in the "decorate" API, but it has two downsides:
>
>  1. The key type must always be a "struct object *".
>
>  2. The value type is a void pointer, which means it is
>     inefficient and cumbersome for storing small values.
>     One must either encode their value inside the void
>     pointer, or allocate additional storage for the pointer
>     to point to.
>
> This patch introduces a generic map data structure, mapping
> keys of arbitrary type to values of arbitrary type.
>
> One possible strategy for implementation is to have a struct
> that points to a sequence of bytes for each of the key and
> the value, and to try to treat them as opaque in the code.
> However, this code gets complex, has a lot of casts, and
> runs afoul of violating alignment and strict aliasing rules.
>
> This patch takes a different approach. We parameterize the
> types in each map by putting the declarations and
> implementations inside macros, and expand the macros with
> the correct types. This lets the compiler see the actual
> code, with its real types, and figure out things like struct
> packing and alignment itself.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> In addition to switching from using void pointers to macro expansion,
> this has one other difference from my previous patch: it handles
> arbitrary types for keys, not just object pointers. This was mentioned
> by Jakub, and would allow things like a fast bi-directional map for SVN
> revision numbers and commits.
>
> I tried to keep the implementation simple. Two things that could be changed:
>
>  1. We can't assume that the map key is a pointer. So the sentinel
>     "NULL" value isn't necessarily available to use, and we have to
>     keep a separate bit in each hash entry to say "is this valid".
>     This means when we _do_ store a pointer, we end up with an extra
>     32 bits or so in each hash entry for the "used" flag.
>
>     We could add a macro parameter for sentinel values, so that types
>     which _can_ handle this efficiently don't have to pay the price.
>     Or we could decide that mapping arbitrary keys isn't worth the
>     hassle. I wrote this way to be flexible for future use; I don't
>     personally have plans to add svn revision number mappings.
>
>  2. It assumes values are assignable. That means storing something like
>     "unsigned char sha1[20]" doesn't work. You can wrap it in a struct,
>     but do we assume that struct assignment works everywhere? I didn't
>     check, but I think it is in C89 but some antique compilers didn't
>     allow it. Switching it to use memcpy() would be easy enough (or
>     again, parameterizing so that assignable things don't have to pay
>     the price).
>
>  Makefile |    2 +
>  map.c    |   86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
>  map.h    |   24 +++++++++++++++++
>  3 files changed, 112 insertions(+), 0 deletions(-)
>  create mode 100644 map.c
>  create mode 100644 map.h
>
> diff --git a/Makefile b/Makefile
> index 46793d1..6242321 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -530,6 +530,7 @@ LIB_H += list-objects.h
>  LIB_H += ll-merge.h
>  LIB_H += log-tree.h
>  LIB_H += mailmap.h
> +LIB_H += map.h
>  LIB_H += merge-file.h
>  LIB_H += merge-recursive.h
>  LIB_H += notes.h
> @@ -621,6 +622,7 @@ LIB_OBJS += ll-merge.o
>  LIB_OBJS += lockfile.o
>  LIB_OBJS += log-tree.o
>  LIB_OBJS += mailmap.o
> +LIB_OBJS += map.o
>  LIB_OBJS += match-trees.o
>  LIB_OBJS += merge-file.o
>  LIB_OBJS += merge-recursive.o
> diff --git a/map.c b/map.c
> new file mode 100644
> index 0000000..378cecb
> --- /dev/null
> +++ b/map.c
> @@ -0,0 +1,86 @@
> +#include "cache.h"
> +#include "map.h"
> +#include "object.h"
> +
> +static unsigned int hash_obj(const struct object *obj, unsigned int n)
> +{
> +       unsigned int hash;
> +
> +       memcpy(&hash, obj->sha1, sizeof(unsigned int));
> +       return hash % n;
> +}
> +
> +static unsigned int cmp_obj(const struct object *a, const struct object *b)
> +{
> +       return b == a;
> +}
> +
> +#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \

This define should probably in the header too. Else this is completely useless.

Bert

Re: [PATCH 1/3] implement generic key/value map

[Bert Wesarg]

On Thu, Jul 14, 2011 at 20:52, Bert Wesarg <bert.wesarg@googlemail.com> wrote:
> On Thu, Jul 14, 2011 at 19:51, Jeff King <peff@peff.net> wrote:
>> +#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \
>
> This define should probably in the header too. Else this is completely useless.

Ahh. One have to read patch 2/3, to see how to use this. Please feel
free to ignore this than.

>
> Bert
>

Re: [PATCH 1/3] implement generic key/value map

[Jeff King]

On Thu, Jul 14, 2011 at 08:54:07PM +0200, Bert Wesarg wrote:

> On Thu, Jul 14, 2011 at 20:52, Bert Wesarg <bert.wesarg@googlemail.com> wrote:
> > On Thu, Jul 14, 2011 at 19:51, Jeff King <peff@peff.net> wrote:
> >> +#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \
> >
> > This define should probably in the header too. Else this is completely useless.
> 
> Ahh. One have to read patch 2/3, to see how to use this. Please feel
> free to ignore this than.

Yeah, you could treat this like a C++ template and assume random bits of
code will instantiate a map of whatever types they need. But this is C,
and we only want to instantiate once. So I just figured to keep the
static list of whatever maps git needs in the map.[ch] files.

-Peff

Re: [PATCH 1/3] implement generic key/value map

[Bert Wesarg]

On Thu, Jul 14, 2011 at 20:55, Jeff King <peff@peff.net> wrote:
> On Thu, Jul 14, 2011 at 08:54:07PM +0200, Bert Wesarg wrote:
>
>> On Thu, Jul 14, 2011 at 20:52, Bert Wesarg <bert.wesarg@googlemail.com> wrote:
>> > On Thu, Jul 14, 2011 at 19:51, Jeff King <peff@peff.net> wrote:
>> >> +#define MAP_IMPLEMENT(name, ktype, vtype, cmp_fun, hash_fun) \
>> >
>> > This define should probably in the header too. Else this is completely useless.
>>
>> Ahh. One have to read patch 2/3, to see how to use this. Please feel
>> free to ignore this than.
>
> Yeah, you could treat this like a C++ template and assume random bits of
> code will instantiate a map of whatever types they need. But this is C,
> and we only want to instantiate once. So I just figured to keep the
> static list of whatever maps git needs in the map.[ch] files.

When I wrote such macros in the past, the 'generated' functions where
all static. So one could instantiate a map multiple times in different
compilation units where one need to access this type of map.

But I'm perfectly fine with your way, which is new to me.

Bert

>
> -Peff
>

Re: [PATCH 1/3] implement generic key/value map

[Jeff King]

On Thu, Jul 14, 2011 at 09:07:54PM +0200, Bert Wesarg wrote:

> > Yeah, you could treat this like a C++ template and assume random bits of
> > code will instantiate a map of whatever types they need. But this is C,
> > and we only want to instantiate once. So I just figured to keep the
> > static list of whatever maps git needs in the map.[ch] files.
> 
> When I wrote such macros in the past, the 'generated' functions where
> all static. So one could instantiate a map multiple times in different
> compilation units where one need to access this type of map.

Yeah, that would work. It can bloat the code more, but in practice, not
much. It would also work better if we were providing the map API as a
library to arbitrary code. But we have the luxury of knowing all of the
types that will be used with it at compile time. :)

-Peff

Re: [PATCH 1/3] implement generic key/value map

[Bert Wesarg]

On Thu, Jul 14, 2011 at 21:14, Jeff King <peff@peff.net> wrote:
> Yeah, that would work. It can bloat the code more, but in practice, not
> much. It would also work better if we were providing the map API as a
> library to arbitrary code. But we have the luxury of knowing all of the
> types that will be used with it at compile time. :)

Right, my thinking was more in the library world back than.

Bert

>
> -Peff
>

[PATCH 2/3] fast-export: use object to uint32 map instead of "decorate"

[Jeff King]

Previously we encoded the "mark" mapping inside the "void *"
field of a "struct decorate". It's a little more natural for
us to do so using a data structure made for holding actual
values.

Signed-off-by: Jeff King <peff@peff.net>
---
And this is an example of use. It doesn't save all that much code, but I
think it's a little more natural. It can also save some bytes of the hash
value in each entry if your pointers are larger than 32-bit.

 builtin/fast-export.c |   36 +++++++++++-------------------------
 map.c                 |    2 ++
 map.h                 |    2 ++
 3 files changed, 15 insertions(+), 25 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index daf1945..fd50503 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -12,7 +12,7 @@
 #include "diffcore.h"
 #include "log-tree.h"
 #include "revision.h"
-#include "decorate.h"
+#include "map.h"
 #include "string-list.h"
 #include "utf8.h"
 #include "parse-options.h"
@@ -59,7 +59,7 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt,
 	return 0;
 }
 
-static struct decoration idnums;
+static struct map_object_uint32 idnums;
 static uint32_t last_idnum;
 
 static int has_unshown_parent(struct commit *commit)
@@ -73,20 +73,9 @@ static int has_unshown_parent(struct commit *commit)
 	return 0;
 }
 
-/* Since intptr_t is C99, we do not use it here */
-static inline uint32_t *mark_to_ptr(uint32_t mark)
-{
-	return ((uint32_t *)NULL) + mark;
-}
-
-static inline uint32_t ptr_to_mark(void * mark)
-{
-	return (uint32_t *)mark - (uint32_t *)NULL;
-}
-
 static inline void mark_object(struct object *object, uint32_t mark)
 {
-	add_decoration(&idnums, object, mark_to_ptr(mark));
+	map_set_object_uint32(&idnums, object, mark, NULL);
 }
 
 static inline void mark_next_object(struct object *object)
@@ -96,10 +85,9 @@ static inline void mark_next_object(struct object *object)
 
 static int get_object_mark(struct object *object)
 {
-	void *decoration = lookup_decoration(&idnums, object);
-	if (!decoration)
-		return 0;
-	return ptr_to_mark(decoration);
+	uint32_t ret = 0;
+	map_get_object_uint32(&idnums, object, &ret);
+	return ret;
 }
 
 static void show_progress(void)
@@ -537,8 +525,7 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)
 static void export_marks(char *file)
 {
 	unsigned int i;
-	uint32_t mark;
-	struct object_decoration *deco = idnums.hash;
+	struct map_entry_object_uint32 *map = idnums.hash;
 	FILE *f;
 	int e = 0;
 
@@ -547,15 +534,14 @@ static void export_marks(char *file)
 		die_errno("Unable to open marks file %s for writing.", file);
 
 	for (i = 0; i < idnums.size; i++) {
-		if (deco->base && deco->base->type == 1) {
-			mark = ptr_to_mark(deco->decoration);
-			if (fprintf(f, ":%"PRIu32" %s\n", mark,
-				sha1_to_hex(deco->base->sha1)) < 0) {
+		if (map->used && map->key->type == 1) {
+			if (fprintf(f, ":%"PRIu32" %s\n", map->value,
+				sha1_to_hex(map->key->sha1)) < 0) {
 			    e = 1;
 			    break;
 			}
 		}
-		deco++;
+		map++;
 	}
 
 	e |= ferror(f);
diff --git a/map.c b/map.c
index 378cecb..28f885e 100644
--- a/map.c
+++ b/map.c
@@ -84,3 +84,5 @@ int map_get_##name(struct map_##name *m, \
 	} \
 	return 0; \
 }
+
+MAP_IMPLEMENT(object_uint32, struct object *, uint32_t, cmp_obj, hash_obj)
diff --git a/map.h b/map.h
index 496c5d1..e80d85d 100644
--- a/map.h
+++ b/map.h
@@ -21,4 +21,6 @@ extern int map_set_##name(struct map_##name *, \
 			  vtype value, \
 			  vtype *old); \
 
+DECLARE_MAP(object_uint32, struct object *, uint32_t)
+
 #endif /* MAP_H */
-- 
1.7.6.38.ge5b33

Re: [PATCH 2/3] fast-export: use object to uint32 map instead of "decorate"

[Sverre Rabbelier]

Heya,

On Thu, Jul 14, 2011 at 19:52, Jeff King <peff@peff.net> wrote:
> Previously we encoded the "mark" mapping inside the "void *"
> field of a "struct decorate". It's a little more natural for
> us to do so using a data structure made for holding actual
> values.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> And this is an example of use. It doesn't save all that much code, but I
> think it's a little more natural. It can also save some bytes of the hash
> value in each entry if your pointers are larger than 32-bit.

Did you run any benchmarks on this?

-- 
Cheers,

Sverre Rabbelier

Re: [PATCH 2/3] fast-export: use object to uint32 map instead of "decorate"

[Jeff King]

On Fri, Jul 15, 2011 at 11:40:02AM +0200, Sverre Rabbelier wrote:

> On Thu, Jul 14, 2011 at 19:52, Jeff King <peff@peff.net> wrote:
> > Previously we encoded the "mark" mapping inside the "void *"
> > field of a "struct decorate". It's a little more natural for
> > us to do so using a data structure made for holding actual
> > values.
> >
> > Signed-off-by: Jeff King <peff@peff.net>
> > ---
> > And this is an example of use. It doesn't save all that much code, but I
> > think it's a little more natural. It can also save some bytes of the hash
> > value in each entry if your pointers are larger than 32-bit.
> 
> Did you run any benchmarks on this?

No, I didn't. I expect it to be exactly the same on x86_64. We save
32-bits of pointer space, but the generality I mentioned in patch 1
wastes 32-bits of space for the "used" flag. So it evens out,
space-wise.

The time complexity should be exactly the same (the macro definitions
are more or less the exact decorate code, but with the types
parameterized, so the generated code should be the same).

But I'm not sure this code is going to end up used, anyway. It looks
like we might add a generation header after all.

-Peff

[PATCH 3/3] decorate: use "map" for the underlying implementation

[Jeff King]

The decoration API maps objects to void pointers. This is a
subset of what the map API is capable of, so let's get rid
of the duplicate implementation.

We could just fix all callers of decorate to call the map
API directly. However, the map API is very generic since it
is meant to handle any type. In particular, it can't use
sentinel values like "NULL" to indicate "entry not found"
(since it doesn't know whether the type can represent such a
sentinel value).

Instead, the decorate API just becomes a set of wrappers,
and no callers need to be updated at all.

Signed-off-by: Jeff King <peff@peff.net>
---
The result should perform identically to the existing decorate code with
the exception of the extra "used" field, which makes each hash entry
bigger (see the comments in patch 1/3).

 decorate.c |  105 ++++++++++--------------------------------------------------
 decorate.h |   10 ++----
 map.c      |    1 +
 map.h      |    1 +
 4 files changed, 22 insertions(+), 95 deletions(-)
 rewrite decorate.c (89%)

diff --git a/decorate.c b/decorate.c
dissimilarity index 89%
index 2f8a63e..31e9656 100644
--- a/decorate.c
+++ b/decorate.c
@@ -1,88 +1,17 @@
-/*
- * decorate.c - decorate a git object with some arbitrary
- * data.
- */
-#include "cache.h"
-#include "object.h"
-#include "decorate.h"
-
-static unsigned int hash_obj(const struct object *obj, unsigned int n)
-{
-	unsigned int hash;
-
-	memcpy(&hash, obj->sha1, sizeof(unsigned int));
-	return hash % n;
-}
-
-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)
-{
-	int size = n->size;
-	struct object_decoration *hash = n->hash;
-	unsigned int j = hash_obj(base, size);
-
-	while (hash[j].base) {
-		if (hash[j].base == base) {
-			void *old = hash[j].decoration;
-			hash[j].decoration = decoration;
-			return old;
-		}
-		if (++j >= size)
-			j = 0;
-	}
-	hash[j].base = base;
-	hash[j].decoration = decoration;
-	n->nr++;
-	return NULL;
-}
-
-static void grow_decoration(struct decoration *n)
-{
-	int i;
-	int old_size = n->size;
-	struct object_decoration *old_hash = n->hash;
-
-	n->size = (old_size + 1000) * 3 / 2;
-	n->hash = xcalloc(n->size, sizeof(struct object_decoration));
-	n->nr = 0;
-
-	for (i = 0; i < old_size; i++) {
-		const struct object *base = old_hash[i].base;
-		void *decoration = old_hash[i].decoration;
-
-		if (!base)
-			continue;
-		insert_decoration(n, base, decoration);
-	}
-	free(old_hash);
-}
-
-/* Add a decoration pointer, return any old one */
-void *add_decoration(struct decoration *n, const struct object *obj,
-		void *decoration)
-{
-	int nr = n->nr + 1;
-
-	if (nr > n->size * 2 / 3)
-		grow_decoration(n);
-	return insert_decoration(n, obj, decoration);
-}
-
-/* Lookup a decoration pointer */
-void *lookup_decoration(struct decoration *n, const struct object *obj)
-{
-	unsigned int j;
-
-	/* nothing to lookup */
-	if (!n->size)
-		return NULL;
-	j = hash_obj(obj, n->size);
-	for (;;) {
-		struct object_decoration *ref = n->hash + j;
-		if (ref->base == obj)
-			return ref->decoration;
-		if (!ref->base)
-			return NULL;
-		if (++j == n->size)
-			j = 0;
-	}
-}
+#include "cache.h"
+#include "decorate.h"
+
+void *add_decoration(struct decoration *n, const struct object *obj,
+		     void *decoration)
+{
+	void *ret = NULL;
+	map_set_object_void(&n->map, obj, decoration, &ret);
+	return ret;
+}
+
+void *lookup_decoration(struct decoration *n, const struct object *obj)
+{
+	void *ret = NULL;
+	map_get_object_void(&n->map, obj, &ret);
+	return ret;
+}
diff --git a/decorate.h b/decorate.h
index e732804..6a3adcd 100644
--- a/decorate.h
+++ b/decorate.h
@@ -1,15 +1,11 @@
 #ifndef DECORATE_H
 #define DECORATE_H
 
-struct object_decoration {
-	const struct object *base;
-	void *decoration;
-};
+#include "map.h"
 
 struct decoration {
-	const char *name;
-	unsigned int size, nr;
-	struct object_decoration *hash;
+	char *name;
+	struct map_object_void map;
 };
 
 extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);
diff --git a/map.c b/map.c
index 28f885e..93e0364 100644
--- a/map.c
+++ b/map.c
@@ -86,3 +86,4 @@ int map_get_##name(struct map_##name *m, \
 }
 
 MAP_IMPLEMENT(object_uint32, struct object *, uint32_t, cmp_obj, hash_obj)
+MAP_IMPLEMENT(object_void, struct object *, void *, cmp_obj, hash_obj)
diff --git a/map.h b/map.h
index e80d85d..737054e 100644
--- a/map.h
+++ b/map.h
@@ -22,5 +22,6 @@ extern int map_set_##name(struct map_##name *, \
 			  vtype *old); \
 
 DECLARE_MAP(object_uint32, struct object *, uint32_t)
+DECLARE_MAP(object_void, struct object *, void *)
 
 #endif /* MAP_H */
-- 
1.7.6.38.ge5b33

Re: [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Doing macro meta-programming like this makes me feel a little dirty, but
> I actually think the result is more readable.
>
>   [1/3]: implement generic key/value map
>   [2/3]: fast-export: use object to uint32 map instead of "decorate"
>   [3/3]: decorate: use "map" for the underlying implementation
>
> What do you think?

Yeah, dirty but nice ;-)

[RFC/PATCH 0/5] macro-based key/value maps

[Jeff King]

On Thu, Jul 14, 2011 at 02:06:28PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > Doing macro meta-programming like this makes me feel a little dirty, but
> > I actually think the result is more readable.
> >
> >   [1/3]: implement generic key/value map
> >   [2/3]: fast-export: use object to uint32 map instead of "decorate"
> >   [3/3]: decorate: use "map" for the underlying implementation
> >
> > What do you think?
> 
> Yeah, dirty but nice ;-)

Well, if you like that, then here is the end-result of what the
persistent version would look like. It's quite convenient to use, but an
awful pain to debug.  It's done entirely in the preprocessor; I suspect
if I wrote the code generation externally, that would be easier and more
readable (and there are one or two places where we could be slightly
more efficient, that are just difficult to implement via the
preprocessor).

  [1/5]: implement generic key/value map
  [2/5]: fast-export: use object to uint32 map instead of "decorate"
  [3/5]: decorate: use "map" for the underlying implementation
  [4/5]: map: implement persistent maps
  [5/5]: implement metadata cache subsystem

-Peff

[PATCH 1/5] implement generic key/value map

[Jeff King]

It is frequently useful to have a fast, generic data
structure mapping keys to values. We already have something
like this in the "decorate" API, but it has two downsides:

  1. The key type must always be a "struct object *".

  2. The value type is a void pointer, which means it is
     inefficient and cumbersome for storing small values.
     One must either encode their value inside the void
     pointer, or allocate additional storage for the pointer
     to point to.

This patch introduces a generic map data structure, mapping
keys of arbitrary type to values of arbitrary type.

One possible strategy for implementation is to have a struct
that points to a sequence of bytes for each of the key and
the value, and to try to treat them as opaque in the code.
However, this code gets complex, has a lot of casts, and
runs afoul of violating alignment and strict aliasing rules.

This patch takes a different approach. We parameterize the
types in each map by putting the declarations and
implementations inside macros, and expand the macros with
the correct types. This lets the compiler see the actual
code, with its real types, and figure out things like struct
packing and alignment itself.

Signed-off-by: Jeff King <peff@peff.net>
---
 Documentation/technical/api-map.txt |  160 +++++++++++++++++++++++++++++++++++
 Makefile                            |    2 +
 map.c                               |   86 +++++++++++++++++++
 map.h                               |   26 ++++++
 4 files changed, 274 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/technical/api-map.txt
 create mode 100644 map.c
 create mode 100644 map.h

diff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt
new file mode 100644
index 0000000..4153ef1
--- /dev/null
+++ b/Documentation/technical/api-map.txt
@@ -0,0 +1,160 @@
+map API
+=======
+
+The map API is a system for efficiently mapping keys to values in memory. Items
+are stored in a hash table for fast lookup; storage efficiency is achieved
+through macro-based code generation, which lets the compiler store values
+compactly in memory.
+
+Due to the code generation, there are two different facets of this API: macros
+to build new types of mappings (i.e., generate new function and struct
+definitions), and generated functions to store and retrieve values from a
+particular mapping.
+
+
+Related APIs
+------------
+
+The hash API provides a similar key/value store. However, it does not deal with
+hash collisions itself, leaving the caller to handle bucket management (but
+this is a feature if you are interested in using the collisions as part of an
+algorithm).  Furthermore, it can store only void pointers, making storage of
+small values inefficient and cumbersome.
+
+The decorate API provides a similar interface to map, but is restricted to
+using "struct object" as the key, and a void pointer as the value.
+
+
+Defining New Map Types
+----------------------
+
+A map type is uniquely defined by the pair of its key and value types. To
+define a new type, you must use the `DECLARE_MAP` macro in `map.h`, and the
+`IMPLEMENT_MAP` macro in `map.c`. Their usage is described below:
+
+`DECLARE_MAP`::
+
+	Declare a new type of map, including the struct definition and
+	declarations of access functions. The `name` parameter should describe
+	the types (e.g., `object_uint32` to map objects to 32-bit integers).
+	The `ktype` parameter specifies the C type of the key (e.g.,
+	`struct object *`) and the `vtype` parameter specifies the C type of
+	the value (e.g., `uint32_t`).
+
+`IMPLEMENT_MAP`::
+
+	Create function definitions for a map type. The `name` parameter should
+	match one given to `DECLARE_MAP`. The `equal_fun` parameter should
+	specify a function that, when given two items of type `ktype`, will
+	return a non-zero value if they are equal.  The `hash_fun` parameter
+	should specify a function that will convert an object of type `ktype`
+	into an integer hash value.
+
+Several convenience functions are provided to fill in macro parameters:
+
+`hash_obj`::
+
+	Suitable for `hash_fun` when the key type is `struct object *`.
+
+`obj_equal`::
+
+	Suitable for `equal_fun` when the key type is `struct object *`.
+
+
+Data Structures
+---------------
+
+Each defined map type will have its own structure (e.g., `map_object_uint32`).
+
+`struct map_NAME`::
+
+	A single map object. This struct should be initialized to all-zeroes.
+	The `nr` field specifies the number of items stored in the map. The
+	`size` field specifies the number of hash buckets allocated. The `hash`
+	field stores the actual data. Callers should never need to look at
+	these fields unless they are enumerating all elements of the map (see
+	the example below).
+
+`struct map_entry_NAME`::
+
+	A single entry in the hash, which may or may not contain a value. If
+	the `used` field is false, the `key` and `value` fields should not be
+	examined at all. Otherwise, the `key` and `value` fields represent a
+	single mapped pair.  You should never need to use this type directly,
+	unless you are enumerating all elements of a map.
+
+
+Functions
+---------
+
+Each defined map type will have its own set of access function (e.g.,
+`map_get_object_uint32`).
+
+`map_get_NAME(struct map_NAME *, const ktype key, vtype *value)`::
+
+	Retrieve the value corresponding to `key`, returning it via the pointer
+	`value`. Returns 1 if an item was found, zero otherwise (in which case
+	`value` is unchanged).
+
+`map_set_NAME(struct map_NAME *, const ktype key, vtype value, vtype *old)`::
+
+	Insert a mapping from `key` to `value`. If a mapping for `key` already
+	existed, the previous value is copied into `old` (if it is non-NULL)
+	and the function returns 1. Otherwise, the function returns 0.
+
+
+Examples
+--------
+
+Create a new mapping type of objects to integers:
+
+-------------------------------------------------------------------
+/* in map.h */
+DECLARE_MAP(object_int, struct object *, int)
+
+/* in map.c */
+IMPLEMENT_MAP(object_int, struct object *, int, obj_equal, hash_obj)
+-------------------------------------------------------------------
+
+Store and retrieve integers by object key:
+
+-------------------------------------------------------------------
+static struct map_object_int foos;
+
+void store_foo(const struct commit *c, int foo)
+{
+	int old;
+	if (map_set_object_uint32(&foos, &c->object, foo, &old))
+		printf("old value was %d\n", old);
+}
+
+void print_foo(const struct commit *c)
+{
+	int v;
+
+	if (map_get_object_int(&foos, &c->object, &v))
+		printf("foo: %d\n", v);
+	else
+		printf("no such foo\n");
+}
+-------------------------------------------------------------------
+
+Iterate over all map entries:
+
+-------------------------------------------------------------------
+void dump_foos(void)
+{
+	int i;
+
+	printf("there are %u foos:\n", foos.nr);
+
+	for (i = 0; i < foos.size; i++) {
+		struct map_entry_object_int *e = foos.hash[i];
+
+		if (!e->used)
+			continue;
+
+		printf("%s -> %d\n", sha1_to_hex(e->key->sha1), e->value);
+	}
+}
+-------------------------------------------------------------------
diff --git a/Makefile b/Makefile
index 4ed7996..acda5b8 100644
--- a/Makefile
+++ b/Makefile
@@ -533,6 +533,7 @@ LIB_H += list-objects.h
 LIB_H += ll-merge.h
 LIB_H += log-tree.h
 LIB_H += mailmap.h
+LIB_H += map.h
 LIB_H += merge-file.h
 LIB_H += merge-recursive.h
 LIB_H += notes.h
@@ -624,6 +625,7 @@ LIB_OBJS += ll-merge.o
 LIB_OBJS += lockfile.o
 LIB_OBJS += log-tree.o
 LIB_OBJS += mailmap.o
+LIB_OBJS += map.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge-file.o
 LIB_OBJS += merge-recursive.o
diff --git a/map.c b/map.c
new file mode 100644
index 0000000..35f300e
--- /dev/null
+++ b/map.c
@@ -0,0 +1,86 @@
+#include "cache.h"
+#include "map.h"
+#include "object.h"
+
+static unsigned int hash_obj(const struct object *obj, unsigned int n)
+{
+	unsigned int hash;
+
+	memcpy(&hash, obj->sha1, sizeof(unsigned int));
+	return hash % n;
+}
+
+static int obj_equal(const struct object *a, const struct object *b)
+{
+	return a == b;
+}
+
+#define IMPLEMENT_MAP(name, equal_fun, hash_fun) \
+static int map_insert_##name(struct map_##name *m, \
+			     const map_ktype_##name key, \
+			     map_vtype_##name value, \
+			     map_vtype_##name *old) \
+{ \
+	unsigned int j; \
+\
+	for (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \
+		if (equal_fun(m->hash[j].key, key)) { \
+			if (old) \
+				*old = m->hash[j].value; \
+			m->hash[j].value = value; \
+			return 1; \
+		} \
+	} \
+\
+	m->hash[j].key = key; \
+	m->hash[j].value = value; \
+	m->hash[j].used = 1; \
+	m->nr++; \
+	return 0; \
+} \
+\
+static void map_grow_##name(struct map_##name *m) \
+{ \
+	struct map_entry_##name *old_hash = m->hash; \
+	unsigned int old_size = m->size; \
+	unsigned int i; \
+\
+	m->size = (old_size + 1000) * 3 / 2; \
+	m->hash = xcalloc(m->size, sizeof(*m->hash)); \
+	m->nr = 0; \
+\
+	for (i = 0; i < old_size; i++) { \
+		if (!old_hash[i].used) \
+			continue; \
+		map_insert_##name(m, old_hash[i].key, old_hash[i].value, NULL); \
+	} \
+	free(old_hash); \
+} \
+\
+int map_set_##name(struct map_##name *m, \
+		   const map_ktype_##name key, \
+		   map_vtype_##name value, \
+		   map_vtype_##name *old) \
+{ \
+	if (m->nr >= m->size * 2 / 3) \
+		map_grow_##name(m); \
+	return map_insert_##name(m, key, value, old); \
+} \
+\
+int map_get_##name(struct map_##name *m, \
+		   const map_ktype_##name key, \
+		   map_vtype_##name *value) \
+{ \
+	unsigned int j; \
+\
+	if (!m->size) \
+		return 0; \
+\
+	for (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \
+		if (equal_fun(m->hash[j].key, key)) { \
+			*value = m->hash[j].value; \
+			return 1; \
+		} \
+	} \
+	return 0; \
+}
diff --git a/map.h b/map.h
new file mode 100644
index 0000000..cb2d4e2
--- /dev/null
+++ b/map.h
@@ -0,0 +1,26 @@
+#ifndef MAP_H
+#define MAP_H
+
+#define DECLARE_MAP(name, key_type, value_type) \
+typedef key_type map_ktype_##name; \
+typedef value_type map_vtype_##name; \
+struct map_entry_##name { \
+	map_ktype_##name key; \
+	map_vtype_##name value; \
+	unsigned used:1; \
+}; \
+\
+struct map_##name { \
+	unsigned int size, nr; \
+	struct map_entry_##name *hash; \
+}; \
+\
+extern int map_get_##name(struct map_##name *, \
+			  const map_ktype_##name key, \
+			  map_vtype_##name *value); \
+extern int map_set_##name(struct map_##name *, \
+			  const map_ktype_##name key, \
+			  map_vtype_##name value, \
+			  map_vtype_##name *old);
+
+#endif /* MAP_H */
-- 
1.7.6.34.g86521e

[PATCH 2/5] fast-export: use object to uint32 map instead of "decorate"

[Jeff King]

Previously we encoded the "mark" mapping inside the "void *"
field of a "struct decorate". It's a little more natural for
us to do so using a data structure made for holding actual
values.

Signed-off-by: Jeff King <peff@peff.net>
---
 Documentation/technical/api-map.txt |    2 +-
 builtin/fast-export.c               |   36 ++++++++++------------------------
 map.c                               |    2 +
 map.h                               |    2 +
 4 files changed, 16 insertions(+), 26 deletions(-)

diff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt
index 4153ef1..97e5a32 100644
--- a/Documentation/technical/api-map.txt
+++ b/Documentation/technical/api-map.txt
@@ -149,7 +149,7 @@ void dump_foos(void)
 	printf("there are %u foos:\n", foos.nr);
 
 	for (i = 0; i < foos.size; i++) {
-		struct map_entry_object_int *e = foos.hash[i];
+		struct map_entry_object_int *e = foos.hash + i;
 
 		if (!e->used)
 			continue;
diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index becef85..9247871 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -12,7 +12,7 @@
 #include "diffcore.h"
 #include "log-tree.h"
 #include "revision.h"
-#include "decorate.h"
+#include "map.h"
 #include "string-list.h"
 #include "utf8.h"
 #include "parse-options.h"
@@ -60,7 +60,7 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt,
 	return 0;
 }
 
-static struct decoration idnums;
+static struct map_object_uint32 idnums;
 static uint32_t last_idnum;
 
 static int has_unshown_parent(struct commit *commit)
@@ -74,20 +74,9 @@ static int has_unshown_parent(struct commit *commit)
 	return 0;
 }
 
-/* Since intptr_t is C99, we do not use it here */
-static inline uint32_t *mark_to_ptr(uint32_t mark)
-{
-	return ((uint32_t *)NULL) + mark;
-}
-
-static inline uint32_t ptr_to_mark(void * mark)
-{
-	return (uint32_t *)mark - (uint32_t *)NULL;
-}
-
 static inline void mark_object(struct object *object, uint32_t mark)
 {
-	add_decoration(&idnums, object, mark_to_ptr(mark));
+	map_set_object_uint32(&idnums, object, mark, NULL);
 }
 
 static inline void mark_next_object(struct object *object)
@@ -97,10 +86,9 @@ static inline void mark_next_object(struct object *object)
 
 static int get_object_mark(struct object *object)
 {
-	void *decoration = lookup_decoration(&idnums, object);
-	if (!decoration)
-		return 0;
-	return ptr_to_mark(decoration);
+	uint32_t ret = 0;
+	map_get_object_uint32(&idnums, object, &ret);
+	return ret;
 }
 
 static void show_progress(void)
@@ -538,8 +526,6 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)
 static void export_marks(char *file)
 {
 	unsigned int i;
-	uint32_t mark;
-	struct object_decoration *deco = idnums.hash;
 	FILE *f;
 	int e = 0;
 
@@ -548,15 +534,15 @@ static void export_marks(char *file)
 		die_errno("Unable to open marks file %s for writing.", file);
 
 	for (i = 0; i < idnums.size; i++) {
-		if (deco->base && deco->base->type == 1) {
-			mark = ptr_to_mark(deco->decoration);
-			if (fprintf(f, ":%"PRIu32" %s\n", mark,
-				sha1_to_hex(deco->base->sha1)) < 0) {
+		const struct map_entry_object_uint32 *m = idnums.hash + i;
+
+		if (m->used && m->key->type == 1) {
+			if (fprintf(f, ":%"PRIu32" %s\n", m->value,
+				sha1_to_hex(m->key->sha1)) < 0) {
 			    e = 1;
 			    break;
 			}
 		}
-		deco++;
 	}
 
 	e |= ferror(f);
diff --git a/map.c b/map.c
index 35f300e..1fdd1aa 100644
--- a/map.c
+++ b/map.c
@@ -84,3 +84,5 @@ int map_get_##name(struct map_##name *m, \
 	} \
 	return 0; \
 }
+
+IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
diff --git a/map.h b/map.h
index cb2d4e2..7449593 100644
--- a/map.h
+++ b/map.h
@@ -23,4 +23,6 @@ extern int map_set_##name(struct map_##name *, \
 			  map_vtype_##name value, \
 			  map_vtype_##name *old);
 
+DECLARE_MAP(object_uint32, const struct object *, uint32_t)
+
 #endif /* MAP_H */
-- 
1.7.6.34.g86521e

[PATCH 3/5] decorate: use "map" for the underlying implementation

[Jeff King]

The decoration API maps objects to void pointers. This is a
subset of what the map API is capable of, so let's get rid
of the duplicate implementation.

We could just fix all callers of decorate to call the map
API directly. However, the map API is very generic since it
is meant to handle any type. In particular, it can't use
sentinel values like "NULL" to indicate "entry not found"
(since it doesn't know whether the type can represent such a
sentinel value), which makes the interface slightly more
complicated.

Instead, let's keep the existing decorate API as a wrapper
on top of map. No callers need to be updated at all.

Signed-off-by: Jeff King <peff@peff.net>
---
 Documentation/technical/api-decorate.txt |   38 +++++++++++++-
 decorate.c                               |   85 +++---------------------------
 decorate.h                               |   10 +---
 map.c                                    |    1 +
 map.h                                    |    1 +
 5 files changed, 48 insertions(+), 87 deletions(-)

diff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt
index 1d52a6c..3c1197a 100644
--- a/Documentation/technical/api-decorate.txt
+++ b/Documentation/technical/api-decorate.txt
@@ -1,6 +1,40 @@
 decorate API
 ============
 
-Talk about <decorate.h>
+The decorate API is a system for efficiently mapping objects to values
+in memory. It is slightly slower than an actual member of an object
+struct (because it incurs a hash lookup), but it uses less memory when
+the mapping is not in use, or when the number of decorated objects is
+small compared to the total number of objects.
 
-(Linus)
+The decorate API is a special form of the `map` link:api-map.html[map
+API]. It has slightly simpler calling conventions, but only use objects
+as keys, and can only store void pointers as values.
+
+
+Data Structures
+---------------
+
+`struct decoration`::
+
+	This structure represents a single mapping of objects to values.
+	The `name` field is not used by the decorate API itself, but may
+	be used by calling code. The `map` field represents the actual
+	mapping of objects to void pointers (see the
+	link:api-map.html[map API] for details).
+
+
+Functions
+---------
+
+`add_decoration`::
+
+	Add a mapping from an object to a void pointer. If there was a
+	previous value for this object, the function returns this value;
+	otherwise, the function returns NULL.
+
+`lookup_decoration`::
+
+	Retrieve the stored value pointer for an object from the
+	mapping. The return value is the value pointer, or `NULL` if
+	there is no value for this object.
diff --git a/decorate.c b/decorate.c
index 2f8a63e..31e9656 100644
--- a/decorate.c
+++ b/decorate.c
@@ -1,88 +1,17 @@
-/*
- * decorate.c - decorate a git object with some arbitrary
- * data.
- */
 #include "cache.h"
-#include "object.h"
 #include "decorate.h"
 
-static unsigned int hash_obj(const struct object *obj, unsigned int n)
-{
-	unsigned int hash;
-
-	memcpy(&hash, obj->sha1, sizeof(unsigned int));
-	return hash % n;
-}
-
-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)
-{
-	int size = n->size;
-	struct object_decoration *hash = n->hash;
-	unsigned int j = hash_obj(base, size);
-
-	while (hash[j].base) {
-		if (hash[j].base == base) {
-			void *old = hash[j].decoration;
-			hash[j].decoration = decoration;
-			return old;
-		}
-		if (++j >= size)
-			j = 0;
-	}
-	hash[j].base = base;
-	hash[j].decoration = decoration;
-	n->nr++;
-	return NULL;
-}
-
-static void grow_decoration(struct decoration *n)
-{
-	int i;
-	int old_size = n->size;
-	struct object_decoration *old_hash = n->hash;
-
-	n->size = (old_size + 1000) * 3 / 2;
-	n->hash = xcalloc(n->size, sizeof(struct object_decoration));
-	n->nr = 0;
-
-	for (i = 0; i < old_size; i++) {
-		const struct object *base = old_hash[i].base;
-		void *decoration = old_hash[i].decoration;
-
-		if (!base)
-			continue;
-		insert_decoration(n, base, decoration);
-	}
-	free(old_hash);
-}
-
-/* Add a decoration pointer, return any old one */
 void *add_decoration(struct decoration *n, const struct object *obj,
-		void *decoration)
+		     void *decoration)
 {
-	int nr = n->nr + 1;
-
-	if (nr > n->size * 2 / 3)
-		grow_decoration(n);
-	return insert_decoration(n, obj, decoration);
+	void *ret = NULL;
+	map_set_object_void(&n->map, obj, decoration, &ret);
+	return ret;
 }
 
-/* Lookup a decoration pointer */
 void *lookup_decoration(struct decoration *n, const struct object *obj)
 {
-	unsigned int j;
-
-	/* nothing to lookup */
-	if (!n->size)
-		return NULL;
-	j = hash_obj(obj, n->size);
-	for (;;) {
-		struct object_decoration *ref = n->hash + j;
-		if (ref->base == obj)
-			return ref->decoration;
-		if (!ref->base)
-			return NULL;
-		if (++j == n->size)
-			j = 0;
-	}
+	void *ret = NULL;
+	map_get_object_void(&n->map, obj, &ret);
+	return ret;
 }
diff --git a/decorate.h b/decorate.h
index e732804..6a3adcd 100644
--- a/decorate.h
+++ b/decorate.h
@@ -1,15 +1,11 @@
 #ifndef DECORATE_H
 #define DECORATE_H
 
-struct object_decoration {
-	const struct object *base;
-	void *decoration;
-};
+#include "map.h"
 
 struct decoration {
-	const char *name;
-	unsigned int size, nr;
-	struct object_decoration *hash;
+	char *name;
+	struct map_object_void map;
 };
 
 extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);
diff --git a/map.c b/map.c
index 1fdd1aa..73f45e0 100644
--- a/map.c
+++ b/map.c
@@ -86,3 +86,4 @@ int map_get_##name(struct map_##name *m, \
 }
 
 IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
+IMPLEMENT_MAP(object_void, obj_equal, hash_obj)
diff --git a/map.h b/map.h
index 7449593..cb9aea6 100644
--- a/map.h
+++ b/map.h
@@ -24,5 +24,6 @@ extern int map_set_##name(struct map_##name *, \
 			  map_vtype_##name *old);
 
 DECLARE_MAP(object_uint32, const struct object *, uint32_t)
+DECLARE_MAP(object_void, const struct object *, void *)
 
 #endif /* MAP_H */
-- 
1.7.6.34.g86521e

[PATCH 4/5] map: implement persistent maps

[Jeff King]

It's sometimes useful to keep a mapping across program
invocations (e.g., because a space/time tradeoff makes it
worth keeping a cache of calculated metadata for some
objects).

This adds a persistent version of the map API which can be
backed by a flat memory store (like an mmap'd file). By
itself, it's not very pleasant to use, as the caller is
responsible for actually opening and mapping files. But it
provides the building blocks for disk caches, which will
come in the next patch.

Signed-off-by: Jeff King <peff@peff.net>
---
 Documentation/technical/api-map.txt |  132 +++++++++++++++++++++++++++++
 map.c                               |  157 +++++++++++++++++++++++++++++++++++
 map.h                               |   17 ++++
 3 files changed, 306 insertions(+), 0 deletions(-)

diff --git a/Documentation/technical/api-map.txt b/Documentation/technical/api-map.txt
index 97e5a32..8ac0cc0 100644
--- a/Documentation/technical/api-map.txt
+++ b/Documentation/technical/api-map.txt
@@ -25,6 +25,21 @@ The decorate API provides a similar interface to map, but is restricted to
 using "struct object" as the key, and a void pointer as the value.
 
 
+Persistent Maps
+---------------
+
+Maps come in two flavors: persistent and in-core. In-core maps are
+represented by a hash table, and can contain any C type. Persistent maps
+are backed by flat storage, such as an mmap'd file, and store values
+between program runs. Key and value types must be serializable to
+fixed-width byte values.
+
+The flat storage is a sorted array of key/value pairs, with no
+delimiters between pairs or between elements of a pair.  Persistent maps
+uses an in-core map for newly-added values, and then merge the new
+values into the flat storage on request.
+
+
 Defining New Map Types
 ----------------------
 
@@ -50,6 +65,32 @@ define a new type, you must use the `DECLARE_MAP` macro in `map.h`, and the
 	should specify a function that will convert an object of type `ktype`
 	into an integer hash value.
 
+To define a persistent map, use these macros instead:
+
+`DECLARE_MAP_PERSIST`::
+
+	Declare a new persistent map. The `name` parameter must match a
+	map declared already with `DECLARE_MAP`.
+
+`IMPLEMENT_MAP_PERSIST`::
+
+	Create function definitions for a persistent map. The `name`
+	parameter must match one given to `DECLARE_MAP_PERSIST`.  The
+	`ksize` and `vsize` parameters indicate the size, in bytes, of
+	serialized keys and values.
++
+	The `k_to_disk` and `v_to_disk` parameters specify functions to
+	convert keys and values to their serialized formats; they take a
+	key (or value), and a pointer to memory of at least `ksize` (or
+	`vsize`) bytes to write into. The `disk_to_v` parameter
+	specifies a function to convert a pointer to `vsize` bytes of
+	serialized value into a `vtype`.
++
+	The `disk_lookup_fun` parameter should specify a function for
+	performing a search of the sorted flat disk array (it is given
+	the array, the number of elements, the size of the key and
+	value, and the key to lookup).
+
 Several convenience functions are provided to fill in macro parameters:
 
 `hash_obj`::
@@ -60,6 +101,26 @@ Several convenience functions are provided to fill in macro parameters:
 
 	Suitable for `equal_fun` when the key type is `struct object *`.
 
+`obj_to_disk`::
+
+	Suitable for `k_to_disk` when the key type is `struct object *`.
+
+`uint32_to_disk`::
+
+	Suitable for `k_to_disk` or `v_to_disk` when the type is
+	`uint32_t`. Integers are serialized in network byte order for
+	portability.
+
+`disk_to_uint32`::
+
+	Suitable for `disk_to_v` when the value type is `uint32_t`.
+	Integers are converted back to host byte order.
+
+`disk_lookup_sha1`::
+
+	Suitable for disk_lookup_fun when the serialized keys are sha1
+	hashes.
+
 
 Data Structures
 ---------------
@@ -83,6 +144,14 @@ Each defined map type will have its own structure (e.g., `map_object_uint32`).
 	single mapped pair.  You should never need to use this type directly,
 	unless you are enumerating all elements of a map.
 
+`struct map_persist_NAME`::
+
+	A persistent map. This struct should be initialized to
+	all-zeroes. The `map` field contains a complete in-core map. The
+	`disk_entries` and `disk_nr` fields specify the flat storage.
+	These should not be set directly, but rather through the
+	`attach` function.
+
 
 Functions
 ---------
@@ -102,6 +171,27 @@ Each defined map type will have its own set of access function (e.g.,
 	existed, the previous value is copied into `old` (if it is non-NULL)
 	and the function returns 1. Otherwise, the function returns 0.
 
+`map_persist_get_NAME(struct map_persist_NAME *, const ktype key, vtype *value)`::
+
+	Same as `map_get_NAME`, but for a persistent map.
+
+`map_persist_set_NAME(struct map_persist_NAME *, const ktype key, vtype value)`::
+
+	Same as `map_set_name`, but for a persistent map. It also does
+	not provide the "old" value for the key.
+
+`map_persist_attach_NAME`::
+
+	Attach storage from `buf` of size `len` bytes as the flat
+	backing store for the map. The map does not copy the storage;
+	the caller is responsible for making sure it stays around as
+	long as the map does.
+
+`map_persist_flush_NAME`::
+
+	Merge in-core entries with those found in the backing store, and
+	write the result to `fd`. Returns 0 for success, -1 for failure.
+
 
 Examples
 --------
@@ -158,3 +248,45 @@ void dump_foos(void)
 	}
 }
 -------------------------------------------------------------------
+
+Open and close a disk-backed persistent map of objects to 32-bit
+integers:
+
+-------------------------------------------------------------------
+static int fd;
+static const unsigned char *buf;
+static unsigned len;
+static struct map_persist_object_uint32 map;
+
+void open_map(const char *path)
+{
+	struct stat sb;
+	const unsigned char *p;
+
+	fd = open(path, O_RDONLY);
+	/* it's ok not to attach any backing store at all */
+	if (fd < 0)
+		return;
+
+	fstat(fd, &sb);
+	len = sb.st_size;
+	buf = xmmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);
+
+	map_persist_attach_object_uint32(&map, buf, len);
+}
+
+/* other functions call "get" and "set" */
+
+void close_map(const char *path, const char *tmp)
+{
+	int tmpfd;
+
+	tmpfd = open(tmp, O_RDONLY);
+	if (map_persist_flush_object_uint32(&map, tmpfd) < 0)
+		die_errno("unable to write new map");
+	close(tmpfd);
+	rename(tmp, path);
+
+	munmap(buf, len);
+	close(fd);
+}
diff --git a/map.c b/map.c
index 73f45e0..bb0d60a 100644
--- a/map.c
+++ b/map.c
@@ -1,6 +1,7 @@
 #include "cache.h"
 #include "map.h"
 #include "object.h"
+#include "sha1-lookup.h"
 
 static unsigned int hash_obj(const struct object *obj, unsigned int n)
 {
@@ -15,6 +16,74 @@ static int obj_equal(const struct object *a, const struct object *b)
 	return a == b;
 }
 
+static void obj_to_disk(const struct object *obj, unsigned char *out)
+{
+	hashcpy(out, obj->sha1);
+}
+
+static void uint32_to_disk(uint32_t v, unsigned char *out)
+{
+	v = htonl(v);
+	memcpy(out, &v, 4);
+}
+
+static void disk_to_uint32(const unsigned char *disk, uint32_t *out)
+{
+	memcpy(out, disk, 4);
+	*out = ntohl(*out);
+}
+
+static const unsigned char *disk_lookup_sha1(const unsigned char *buf,
+					     unsigned nr,
+					     unsigned ksize, unsigned vsize,
+					     const unsigned char *key)
+{
+	int pos;
+
+	pos = sha1_entry_pos(buf, ksize + vsize, 0, 0, nr, nr, key);
+	if (pos < 0)
+		return NULL;
+	return buf + (pos * (ksize + vsize)) + ksize;
+}
+
+static int merge_entries(int fd, int ksize, int vsize,
+			 const unsigned char *left, unsigned nr_left,
+			 const unsigned char *right, unsigned nr_right)
+{
+#define ADVANCE(name) \
+	do { \
+		name += ksize + vsize; \
+		nr_##name--; \
+	} while (0)
+#define WRITE_ENTRY(name) \
+	do { \
+		if (write_in_full(fd, name, ksize + vsize) < 0) \
+			return -1; \
+		ADVANCE(name); \
+	} while (0)
+
+	while (nr_left && nr_right) {
+		int cmp = memcmp(left, right, ksize);
+
+		/* skip duplicates, preferring left to right */
+		if (cmp == 0)
+			ADVANCE(right);
+		else if (cmp < 0)
+			WRITE_ENTRY(left);
+		else
+			WRITE_ENTRY(right);
+	}
+	while (nr_left)
+		WRITE_ENTRY(left);
+	while (nr_right)
+		WRITE_ENTRY(right);
+
+#undef WRITE_ENTRY
+#undef ADVANCE
+
+	return 0;
+}
+
 #define IMPLEMENT_MAP(name, equal_fun, hash_fun) \
 static int map_insert_##name(struct map_##name *m, \
 			     const map_ktype_##name key, \
@@ -85,5 +154,93 @@ int map_get_##name(struct map_##name *m, \
 	return 0; \
 }
 
+#define IMPLEMENT_MAP_PERSIST(name, \
+			      ksize, k_to_disk, \
+			      vsize, v_to_disk, disk_to_v, \
+			      disk_lookup_fun) \
+int map_persist_get_##name(struct map_persist_##name *m, \
+			   const map_ktype_##name key, \
+			   map_vtype_##name *value) \
+{ \
+	unsigned char disk_key[ksize]; \
+	const unsigned char *disk_value; \
+\
+	if (map_get_##name(&m->mem, key, value)) \
+		return 1; \
+\
+	if (!m->disk_entries) \
+		return 0; \
+\
+	k_to_disk(key, disk_key); \
+	disk_value = disk_lookup_fun(m->disk_entries, m->disk_nr, \
+				     ksize, vsize, disk_key); \
+	if (disk_value) { \
+		disk_to_v(disk_value, value); \
+		return 1; \
+	} \
+\
+	return 0; \
+} \
+\
+int map_persist_set_##name(struct map_persist_##name *m, \
+			   const map_ktype_##name key, \
+			   map_vtype_##name value) \
+{ \
+	return map_set_##name(&m->mem, key, value, NULL); \
+} \
+\
+static unsigned char *flatten_mem_entries_##name(struct map_persist_##name *m) \
+{ \
+	unsigned char *ret, *out; \
+	int i, nr; \
+\
+	out = ret = xmalloc(m->mem.nr * (ksize + vsize)); \
+	nr = 0; \
+	for (i = 0; i < m->mem.size; i++) { \
+		struct map_entry_##name *e = m->mem.hash + i; \
+\
+		if (!e->used) \
+			continue; \
+\
+		if (nr == m->mem.nr) \
+			die("BUG: map hash contained extra values"); \
+\
+		k_to_disk(e->key, out); \
+		out += ksize; \
+		v_to_disk(e->value, out); \
+		out += vsize; \
+	} \
+\
+	return ret; \
+} \
+\
+void map_persist_attach_##name(struct map_persist_##name *m, \
+			       const unsigned char *buf, \
+			       unsigned int len) \
+{ \
+	m->disk_entries = buf; \
+	m->disk_nr = len / (ksize + vsize); \
+} \
+\
+static int keycmp_##name(const void *a, const void *b) \
+{ \
+	return memcmp(a, b, ksize); \
+} \
+\
+int map_persist_flush_##name(struct map_persist_##name *m, int fd) \
+{ \
+	unsigned char *mem_entries; \
+	int r; \
+\
+	mem_entries = flatten_mem_entries_##name(m); \
+	qsort(mem_entries, m->mem.nr, ksize + vsize, keycmp_##name); \
+\
+	r = merge_entries(fd, ksize, vsize, \
+			  mem_entries, m->mem.nr, \
+			  m->disk_entries, m->disk_nr); \
+	free(mem_entries); \
+	return r; \
+}
+
 IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
 IMPLEMENT_MAP(object_void, obj_equal, hash_obj)
diff --git a/map.h b/map.h
index cb9aea6..ceddc14 100644
--- a/map.h
+++ b/map.h
@@ -23,6 +23,23 @@ extern int map_set_##name(struct map_##name *, \
 			  map_vtype_##name value, \
 			  map_vtype_##name *old);
 
+#define DECLARE_MAP_PERSIST(name) \
+struct map_persist_##name { \
+	struct map_##name mem; \
+	const unsigned char *disk_entries; \
+	unsigned int disk_nr; \
+}; \
+extern int map_persist_get_##name(struct map_persist_##name *, \
+			  const map_ktype_##name key, \
+			  map_vtype_##name *value); \
+extern int map_persist_set_##name(struct map_persist_##name *, \
+			  const map_ktype_##name key, \
+			  map_vtype_##name value); \
+extern void map_persist_attach_##name(struct map_persist_##name *, \
+				      const unsigned char *buf, \
+				      unsigned int len); \
+extern int map_persist_flush_##name(struct map_persist_##name *, int fd);
+
 DECLARE_MAP(object_uint32, const struct object *, uint32_t)
 DECLARE_MAP(object_void, const struct object *, void *)
 
-- 
1.7.6.34.g86521e

[PATCH 5/5] implement metadata cache subsystem

[Jeff King]

There are some calculations that git makes repeatedly, even
though the results are invariant for a certain input (e.g.,
the patch-id of a certain commit). We can make a space/time
tradeoff by caching these on disk between runs.

Even though these may be immutable for a certain commit, we
don't want to directly store the results in the commit
objects themselves, for a few reasons:

  1. They are not necessarily used by all algorithms, so
     bloating the commit object might slow down other
     algorithms.

  2. Because they can be calculated from the existing
     commits, they are redundant with the existing
     information. Thus they are an implementation detail of
     our current algorithms, and should not be cast in stone
     by including them in the commit sha1.

  3. They may only be immutable under a certain set of
     conditions (e.g., which grafts or replace refs we are
     using). Keeping the storage external means we can
     invalidate and regenerate the cache whenever those
     conditions change.

The persistent map API already provides the storage we need.
This new API takes care of the details of opening and
closing the cache files automatically. Callers need only get
and set values as they see fit.

Signed-off-by: Jeff King <peff@peff.net>
---
 Documentation/technical/api-metadata-cache.txt |   67 +++++++++++++
 Makefile                                       |    2 +
 metadata-cache.c                               |  126 ++++++++++++++++++++++++
 metadata-cache.h                               |   10 ++
 4 files changed, 205 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/technical/api-metadata-cache.txt
 create mode 100644 metadata-cache.c
 create mode 100644 metadata-cache.h

diff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt
new file mode 100644
index 0000000..5f4422d
--- /dev/null
+++ b/Documentation/technical/api-metadata-cache.txt
@@ -0,0 +1,67 @@
+metadata cache API
+==================
+
+The metadata cache API provides simple-to-use, persistent key/value
+storage. It is built on the link:api-map.html[map API], so keys and
+values can have any serializable type.
+
+Caches are statically allocated, and no explicit initialization is
+required.  Callers can simply call the "get" and "set" functions for a
+given cache.  At program exit, any new entries in the cache are flushed
+to disk.
+
+
+Defining a New Cache
+--------------------
+
+You need to provide three pieces of information to define a new cache:
+
+name::
+	This name will be used both as part of the C identifier and as
+	part of the filename under which the cache is stored. Restrict
+	the characters used to alphanumerics and underscore.
+
+map::
+	The type of map (declared by `DECLARE_MAP`) that this cache will
+	store.
+
+validity::
+	A function that will generate a 20-byte "validity token"
+	representing the conditions under which the cache is valid.
+	For example, a cache that depended on the structure of the
+	history graph would be valid only under a given set of grafts
+	and replace refs. That set could be stirred into a sha1 and used
+	as a validity token.
+
+You must declare the cache in metadata-cache.h using
+`DECLARE_METADATA_CACHE`, and then implement it in metadata-cache.c
+using `IMPLEMENT_METADATA_CACHE`.
+
+
+Using a Cache
+-------------
+
+Interaction with a cache consists entirely of getting and setting
+values. No initialization or cleanup is required. The get and set
+functions mirror their "map" counterparts; see the
+link:api-map.html[map API] for details.
+
+
+File Format
+-----------
+
+Cache files are stored in the $GIT_DIR/cache directory. Each cache gets
+its own directory, named after the `name` parameter in the cache
+definition. Within each directory is a set of files, one cache per file,
+named after their validity tokens. Caches for multiple sets of
+conditions can simultaneously exist, and git will use whichever is
+appropriate.
+
+The files themselves consist of an 8-byte header. The first four bytes
+are the magic sequence "MTAC" (for "MeTA Cache"), followed by a 4-byte
+version number, in network byte order. This document describes version
+1.
+
+The rest of the file consists of the persistent map data. This is a
+compact, sorted list of keys and values; see the link:api-map.html[map
+API] for details.
diff --git a/Makefile b/Makefile
index acda5b8..3b39538 100644
--- a/Makefile
+++ b/Makefile
@@ -536,6 +536,7 @@ LIB_H += mailmap.h
 LIB_H += map.h
 LIB_H += merge-file.h
 LIB_H += merge-recursive.h
+LIB_H += metadata-cache.h
 LIB_H += notes.h
 LIB_H += notes-cache.h
 LIB_H += notes-merge.h
@@ -629,6 +630,7 @@ LIB_OBJS += map.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge-file.o
 LIB_OBJS += merge-recursive.o
+LIB_OBJS += metadata-cache.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
diff --git a/metadata-cache.c b/metadata-cache.c
new file mode 100644
index 0000000..e217db1
--- /dev/null
+++ b/metadata-cache.c
@@ -0,0 +1,126 @@
+#include "cache.h"
+#include "metadata-cache.h"
+#include "map.h"
+
+static const char *metadata_cache_path(const char *name,
+				       void (*validity)(unsigned char [20]))
+{
+	unsigned char token[20];
+
+	if (validity)
+		validity(token);
+	else
+		hashcpy(token, null_sha1);
+	return git_path("cache/%s/%s", name, sha1_to_hex(token));
+}
+
+#define IMPLEMENT_METADATA_CACHE(name, map, validity) \
+static struct map_persist_##map name##_map; \
+static int name##_fd; \
+static unsigned char *name##_buf; \
+static unsigned long name##_len; \
+\
+static void write_##name##_cache(void) \
+{ \
+	const char *path; \
+	struct strbuf tempfile = STRBUF_INIT; \
+	int fd = -1; \
+\
+	if (!name##_map.mem.nr) \
+		return; \
+\
+	path = metadata_cache_path(#name, validity); \
+	strbuf_addf(&tempfile, "%s.XXXXXX", path); \
+\
+	if (safe_create_leading_directories(tempfile.buf) < 0) \
+		goto fail; \
+	fd = git_mkstemp_mode(tempfile.buf, 0444); \
+	if (fd < 0) \
+		goto fail; \
+\
+	if (write_in_full(fd, "MTAC\x00\x00\x00\x01", 8) < 0) \
+		goto fail; \
+	if (map_persist_flush_##map(&name##_map, fd) < 0) \
+		goto fail; \
+	if (close(fd) < 0) \
+		goto fail; \
+	if (rename(tempfile.buf, path) < 0) \
+		goto fail; \
+\
+	strbuf_release(&tempfile); \
+	return; \
+\
+fail: \
+	close(fd); \
+	unlink(tempfile.buf); \
+	strbuf_release(&tempfile); \
+} \
+\
+static void init_##name##_cache(void) \
+{ \
+	static int initialized; \
+	const char *path; \
+	struct stat sb; \
+	const unsigned char *p; \
+	uint32_t version; \
+\
+	if (initialized) \
+		return; \
+\
+	atexit(write_##name##_cache); \
+	initialized = 1; \
+\
+	path = metadata_cache_path(#name, validity); \
+	name##_fd = open(path, O_RDONLY); \
+	if (name##_fd < 0) \
+		return; \
+\
+	if (fstat(name##_fd, &sb) < 0) \
+		goto fail; \
+	name##_len = sb.st_size; \
+	name##_buf = xmmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, \
+				 name##_fd, 0); \
+\
+	if (name##_len < 8) { \
+		warning("cache '%s' is missing header", path); \
+		goto fail; \
+	} \
+	p = name##_buf; \
+	if (memcmp(p, "MTAC", 4)) { \
+		warning("cache '%s' has invalid magic: %c%c%c%c", \
+			path, p[0], p[1], p[2], p[3]); \
+		goto fail; \
+	} \
+	p += 4; \
+	memcpy(&version, p, 4); \
+	version = ntohl(version); \
+	if (version != 1) { \
+		warning("cache '%s' has unknown version: %"PRIu32, \
+			path, version); \
+		goto fail; \
+	} \
+\
+	map_persist_attach_##map(&name##_map, \
+				     name##_buf + 8, \
+				     name##_len - 8); \
+	return; \
+\
+fail: \
+	close(name##_fd); \
+	name##_fd = -1; \
+	if (name##_buf) \
+		munmap(name##_buf, name##_len); \
+	name##_buf = NULL; \
+	name##_len = 0; \
+} \
+\
+int name##_cache_get(map_ktype_##map key, map_vtype_##map *value) \
+{ \
+	init_##name##_cache(); \
+	return map_persist_get_##map(&name##_map, key, value); \
+} \
+int name##_cache_set(map_ktype_##map key, map_vtype_##map value) \
+{ \
+	init_##name##_cache(); \
+	return map_persist_set_##map(&name##_map, key, value); \
+}
diff --git a/metadata-cache.h b/metadata-cache.h
new file mode 100644
index 0000000..851a4eb
--- /dev/null
+++ b/metadata-cache.h
@@ -0,0 +1,10 @@
+#ifndef METADATA_CACHE_H
+#define METADATA_CACHE_H
+
+#include "map.h"
+
+#define DECLARE_METADATA_CACHE(name, map) \
+extern int name##_cache_get(map_ktype_##map key, map_vtype_##map *value); \
+extern int name##_cache_set(map_ktype_##map key, map_vtype_##map value);
+
+#endif /* METADATA_CACHE_H */
-- 
1.7.6.34.g86521e

[RFC/PATCH 0/2] patch-id caching

[Jeff King]

On Thu, Aug 04, 2011 at 04:43:54PM -0600, Jeff King wrote:

>   [1/5]: implement generic key/value map
>   [2/5]: fast-export: use object to uint32 map instead of "decorate"
>   [3/5]: decorate: use "map" for the underlying implementation
>   [4/5]: map: implement persistent maps
>   [5/5]: implement metadata cache subsystem

And here's a potential user of the new code:

  [1/2]: cherry: read default config
  [2/2]: cache patch ids on disk

-Peff

[PATCH 1/2] cherry: read default config

[Jeff King]

We don't currently read the config at all for git-cherry.
This doesn't seem to cause any issues so far, because what
it does is so simple that none of the configuration matters.

However, the next patch will add a relevant config option.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/log.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index 5c2af59..f385fb8 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -1438,6 +1438,8 @@ int cmd_cherry(int argc, const char **argv, const char *prefix)
 		OPT_END()
 	};
 
+	git_config(git_default_config, NULL);
+
 	argc = parse_options(argc, argv, prefix, options, cherry_usage, 0);
 
 	switch (argc) {
-- 
1.7.6.34.g86521e

[PATCH 2/2] cache patch ids on disk

[Jeff King]

Some workflows may involve running "git cherry" a lot to
look for identical patches. Git ends up calculating the
patch-id of some commits many times, which can be slow.

This patch provides an option to cache the calculated patch
ids persistently on disk. This trades more disk space (and
more RAM used for disk cache) for less CPU time. Whether
this is a good idea depends on your workflow and how much
disk and RAM you have (the cache uses 40 bytes per stored
commit).

Here's one cherry-heavy workflow (checking which topic
branches have been accepted upstream), and some timings:

  have_commits() {
	  test -z "`git cherry "$@" | grep -v ^-`"
  }
  for i in $topic_branches; do
    if have_commits origin/master $i $i@{u}; then
      echo $i: merged to origin/master
    elif have_commits origin/next $i $i@{u}; then
      echo $i: merged to origin/next
    else
      echo $i: not merged
  done

  # without patch
  real    0m9.709s
  user    0m8.693s
  sys     0m0.676s

  # with patch, first run
  real    0m1.946s
  user    0m1.244s
  sys     0m0.428s

  # with patch, subsequent run
  real    0m1.379s
  user    0m0.844s
  sys     0m0.268s

and the disk used:

  $ du -h .git/cache/patch_id/*
  8.0K .git/cache/patch_id/0000000000000000000000000000000000000000

Signed-off-by: Jeff King <peff@peff.net>
---
 cache.h          |    1 +
 config.c         |    5 +++++
 map.c            |   16 ++++++++++++++++
 map.h            |    6 ++++++
 metadata-cache.c |    2 ++
 metadata-cache.h |    2 ++
 patch-ids.c      |   22 +++++++++++++++++++++-
 7 files changed, 53 insertions(+), 1 deletions(-)

diff --git a/cache.h b/cache.h
index 9e12d55..060f0f9 100644
--- a/cache.h
+++ b/cache.h
@@ -596,6 +596,7 @@ extern int read_replace_refs;
 extern int fsync_object_files;
 extern int core_preload_index;
 extern int core_apply_sparse_checkout;
+extern int core_cache_patch_id;
 
 enum branch_track {
 	BRANCH_TRACK_UNSPECIFIED = -1,
diff --git a/config.c b/config.c
index e42c59b..09e84c3 100644
--- a/config.c
+++ b/config.c
@@ -659,6 +659,11 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.cachepatchid")) {
+		core_cache_patch_id = git_config_bool(var, value);
+		return 0;
+	}
+
 	/* Add other config variables here and to Documentation/config.txt. */
 	return 0;
 }
diff --git a/map.c b/map.c
index bb0d60a..9d8d5ab 100644
--- a/map.c
+++ b/map.c
@@ -33,6 +33,16 @@ static void disk_to_uint32(const unsigned char *disk, uint32_t *out)
 	*out = ntohl(*out);
 }
 
+static void sha1_to_disk(struct sha1 v, unsigned char *out)
+{
+	hashcpy(out, v.v);
+}
+
+static void disk_to_sha1(const unsigned char *disk, struct sha1 *out)
+{
+	hashcpy(out->v, disk);
+}
+
 static const unsigned char *disk_lookup_sha1(const unsigned char *buf,
 					     unsigned nr,
 					     unsigned ksize, unsigned vsize,
@@ -244,3 +254,9 @@ int map_persist_flush_##name(struct map_persist_##name *m, int fd) \
 
 IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
 IMPLEMENT_MAP(object_void, obj_equal, hash_obj)
+
+IMPLEMENT_MAP(object_sha1, obj_equal, hash_obj)
+IMPLEMENT_MAP_PERSIST(object_sha1,
+		      20, obj_to_disk,
+		      20, sha1_to_disk, disk_to_sha1,
+		      disk_lookup_sha1)
diff --git a/map.h b/map.h
index ceddc14..18eb939 100644
--- a/map.h
+++ b/map.h
@@ -40,7 +40,13 @@ extern void map_persist_attach_##name(struct map_persist_##name *, \
 				      unsigned int len); \
 extern int map_persist_flush_##name(struct map_persist_##name *, int fd);
 
+struct sha1 {
+	unsigned char v[20];
+};
+
 DECLARE_MAP(object_uint32, const struct object *, uint32_t)
 DECLARE_MAP(object_void, const struct object *, void *)
+DECLARE_MAP(object_sha1, const struct object *, struct sha1)
+DECLARE_MAP_PERSIST(object_sha1)
 
 #endif /* MAP_H */
diff --git a/metadata-cache.c b/metadata-cache.c
index e217db1..0ce0e90 100644
--- a/metadata-cache.c
+++ b/metadata-cache.c
@@ -124,3 +124,5 @@ int name##_cache_set(map_ktype_##map key, map_vtype_##map value) \
 	init_##name##_cache(); \
 	return map_persist_set_##map(&name##_map, key, value); \
 }
+
+IMPLEMENT_METADATA_CACHE(patch_id, object_sha1, NULL)
diff --git a/metadata-cache.h b/metadata-cache.h
index 851a4eb..ff2f6d3 100644
--- a/metadata-cache.h
+++ b/metadata-cache.h
@@ -7,4 +7,6 @@
 extern int name##_cache_get(map_ktype_##map key, map_vtype_##map *value); \
 extern int name##_cache_set(map_ktype_##map key, map_vtype_##map value);
 
+DECLARE_METADATA_CACHE(patch_id, object_sha1)
+
 #endif /* METADATA_CACHE_H */
diff --git a/patch-ids.c b/patch-ids.c
index 5717257..d1818eb 100644
--- a/patch-ids.c
+++ b/patch-ids.c
@@ -3,17 +3,37 @@
 #include "commit.h"
 #include "sha1-lookup.h"
 #include "patch-ids.h"
+#include "metadata-cache.h"
+
+int core_cache_patch_id;
 
 static int commit_patch_id(struct commit *commit, struct diff_options *options,
 		    unsigned char *sha1)
 {
+	if (core_cache_patch_id) {
+		struct sha1 v;
+		if (patch_id_cache_get(&commit->object, &v)) {
+			hashcpy(sha1, v.v);
+			return 0;
+		}
+	}
+
 	if (commit->parents)
 		diff_tree_sha1(commit->parents->item->object.sha1,
 		               commit->object.sha1, "", options);
 	else
 		diff_root_tree_sha1(commit->object.sha1, "", options);
 	diffcore_std(options);
-	return diff_flush_patch_id(options, sha1);
+	if (diff_flush_patch_id(options, sha1) < 0)
+		return -1;
+
+	if (core_cache_patch_id) {
+		struct sha1 v;
+		hashcpy(v.v, sha1);
+		patch_id_cache_set(&commit->object, v);
+	}
+
+	return 0;
 }
 
 static const unsigned char *patch_id_access(size_t index, void *table)
-- 
1.7.6.34.g86521e

Re: [PATCH 2/2] cache patch ids on disk

[Jeff King]

On Thu, Aug 04, 2011 at 04:49:47PM -0600, Jeff King wrote:

> +struct sha1 {
> +	unsigned char v[20];
> +};
> +
> [...]
> +DECLARE_MAP(object_sha1, const struct object *, struct sha1)

I'm not altogether happy with this. But the generated code wants to
treat the value type as something that can be instantiated as "vtype
foo", so we need to wrap a struct around an array to make the compiler
happy.

We could do something a little fancier to avoid this, like separating
"this is what it looks like to declare a value" from "this is what a
passed value looks like". And then use "unsigned char v[20]" for the
former and "unsigned char *" for the latter.

-Peff

Re: [RFC/PATCH 0/5] macro-based key/value maps

[Jeff King]

On Thu, Aug 04, 2011 at 04:43:54PM -0600, Jeff King wrote:

> Well, if you like that, then here is the end-result of what the
> persistent version would look like. It's quite convenient to use, but an
> awful pain to debug.  It's done entirely in the preprocessor; I suspect
> if I wrote the code generation externally, that would be easier and more
> readable (and there are one or two places where we could be slightly
> more efficient, that are just difficult to implement via the
> preprocessor).
> 
>   [1/5]: implement generic key/value map
>   [2/5]: fast-export: use object to uint32 map instead of "decorate"
>   [3/5]: decorate: use "map" for the underlying implementation
>   [4/5]: map: implement persistent maps
>   [5/5]: implement metadata cache subsystem

Side note:

  Commits 1, 4, and 5 introduce infrastructure in the form of static
  functions and macros that contain functions that call the statics. But
  they don't actually instantiate the macro functions themselves, so
  they won't compile with -Werror (due to the "unused static" warning)
  until there is some calling code.

  That hurts bisectability a little if you compile with -Werror (you
  need to add -Wno-error=unused-function). I don't know how much we
  care.

-Peff

Re: [RFC/PATCH 0/5] macro-based key/value maps

[René Scharfe]

Am 05.08.2011 13:03, schrieb Jeff King:
>   Commits 1, 4, and 5 introduce infrastructure in the form of static
>   functions and macros that contain functions that call the statics. But
>   they don't actually instantiate the macro functions themselves, so
>   they won't compile with -Werror (due to the "unused static" warning)
>   until there is some calling code.
> 
>   That hurts bisectability a little if you compile with -Werror (you
>   need to add -Wno-error=unused-function). I don't know how much we
>   care.

I don't know either, but you could avoid the issue by adding a test-maps
command in the first patch and exercising the new functionality a bit.

René

Re: [RFC/PATCH 0/5] macro-based key/value maps

[Jeff King]

On Fri, Aug 05, 2011 at 05:31:37PM +0200, René Scharfe wrote:

> Am 05.08.2011 13:03, schrieb Jeff King:
> >   Commits 1, 4, and 5 introduce infrastructure in the form of static
> >   functions and macros that contain functions that call the statics. But
> >   they don't actually instantiate the macro functions themselves, so
> >   they won't compile with -Werror (due to the "unused static" warning)
> >   until there is some calling code.
> > 
> >   That hurts bisectability a little if you compile with -Werror (you
> >   need to add -Wno-error=unused-function). I don't know how much we
> >   care.
> 
> I don't know either, but you could avoid the issue by adding a test-maps
> command in the first patch and exercising the new functionality a bit.

Yes, but then the final git executable carries around dead code for the
test map and cache types. There are ways to split the macros versus
their instantiation so that the test instantiations only live in the
test-map program, but then that would bring back the "static is not
used" error.

Maybe carrying the dead code isn't that big a deal. It's not that much
extra code.

-Peff

[RFC/PATCHv2 2/6] add metadata-cache infrastructure

[Jeff King]

There is sometimes a need to cache some information about an
object or set of objects persistently across git
invocations. The notes-cache interface can be used for this,
but it is very heavyweight and slow for storing small
values.

This patch introduces a new API, metadata-cache, which
stores a mapping of objects to values in a concise and
efficient form. See the added API documentation for details.

Signed-off-by: Jeff King <peff@peff.net>
---
Many changes here:

  - name changed to metadata-cache

  - cache files have an actual header; I doubt they'll need to change
    much, but it's a lot nicer to have an actual version number to make
    sure it's valid

  - cache files have a 20-byte slot for a validity hash. See patch 5/6
    for an example of use.

  - the data width is stored in only one place, and is const; this gives
    us language support for code accidentally tweaking the width at
    run-time

  - initialization is now done by static initializer, and we lazily open
    the disk cache when requested. This is necessary because of the
    previous point, but it also makes client code simpler.

  - cached entries are automatically written out on program exit.
    Together with the above point, this makes client code very simple
    and natural. You just declare a static cache object, and then lookup
    and add to it as appropriate.

 Documentation/technical/api-decorate.txt       |    3 +
 Documentation/technical/api-metadata-cache.txt |  130 +++++++++
 Makefile                                       |    2 +
 metadata-cache.c                               |  337 ++++++++++++++++++++++++
 metadata-cache.h                               |   40 +++
 5 files changed, 512 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/technical/api-metadata-cache.txt
 create mode 100644 metadata-cache.c
 create mode 100644 metadata-cache.h

diff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt
index b048b28..c761b45 100644
--- a/Documentation/technical/api-decorate.txt
+++ b/Documentation/technical/api-decorate.txt
@@ -13,6 +13,9 @@ could, for example, map objects into 32-bit integers. For ease of use,
 functions are provided for storing the values of arbitrary pointers,
 which can point to strings or structs.
 
+Note that the decorate API only stores the mapping in memory. See the
+metadata-cache API for persistent storage.
+
 Data Structures
 ---------------
 
diff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt
new file mode 100644
index 0000000..192a868
--- /dev/null
+++ b/Documentation/technical/api-metadata-cache.txt
@@ -0,0 +1,130 @@
+Metadata Cache API
+================
+
+The metadata cache API is meant to store a cache of per-object values.
+The aim is for robustness, speed, and simplicity. The stored data must
+be of a fixed size, and the only operations allowed are insertion and
+retrieval with a struct object as the key.
+
+This API is similar to the decorate API, but provides persistence of
+values across multiple invocations. It is also similar to the
+notes-cache API, but is much lighter weight and suitable for storing
+small values. If you are storing large, arbitrary data, consider using
+notes-cache.
+
+
+Storage
+-------
+
+Values are stored both on-disk and in-memory. Newly added values are
+initially stored in a hash table in memory, and written to disk
+automatically on program exit.
+
+The disk storage consists of a single file per cache, located in the
+`$GIT_DIR/cache` directory. See "File Format" below.
+
+When the cache is written to disk, the contents of the in-memory data
+and the disk data are merged, with in-memory values taking precedence
+over disk values. The data is written to a temporary file and atomically
+renamed into the new cache file. Thus there is no lock contention
+between competing processes on either reading or writing (though one
+process's updates may be lost).
+
+
+File Format
+-----------
+
+Cache files begin with a 32-byte header, consisting of:
+
+  - a 4-byte magic token, {'M', 'T', 'A', 'C' }.
+
+  - a 32-bit unsigned integer in network byte-order, indicating the
+    file format version; this document describes version 1.
+
+  - a 32-bit unsigned integer in network byte-order, indicating the
+    width in bytes of single stored data value.
+
+  - a 20-byte sequence indicating the "validity" of the cache; the
+    exact meaning of this value is specific to the type of cache. See
+    the section on "Validity" below.
+
+After the header, the file contains a sequence of key-value pairs, with
+no delimiters. The "key" of each pair is a 20-byte binary sha1. The
+value is a sequence of bytes of length `W`, where `W` is the width
+specified in the header.
+
+
+Cache Validity
+--------------
+
+The contents of a cache file may be valid only under a specific set of
+circumstances. The file header contains a 20-byte validity token which
+can be checked to ensure that the cache data is still valid. The data
+that goes into each token is specific to the type of cache. For example,
+a cache that summarizes information on the history graph would be valid
+only under a specific set of grafts and replace refs.
+
+
+Speed
+-----
+
+Lookup in the cache requires `O(lg(n))` hash comparisons (via binary
+search of the disk contents, or the in-memory hash table).
+
+Insertion into the cache is amortized `O(1)` via the hash table. Writing
+the cache to disk entails `O(n*lg(n) + m)` hash comparisons, where `m`
+is the number of existing disk entries and `n` is the number of newly
+added entries.
+
+
+Data Structures
+---------------
+
+`struct metadata_cache`::
+
+	This structure represents a single metadata cache (i.e., mapping
+	each object to a single fixed-size value). The cache should be
+	allocated in static storage and initialized using the
+	`METADATA_CACHE_INIT` macro. The lookup code will lazily open the
+	on-disk cache as necessary, and any values written by
+	`metadata_cache_add` will be automatically written to disk at
+	program exit.
++
+	The structure should be considered opaque by calling code.
+
+
+Functions
+---------
+
+`METADATA_CACHE_INIT`::
+
+	Static initializer for a metadata cache. The `name` parameter
+	specifies a human-readable name which will be used for storage
+	in `$GIT_DIR/cache/$name`. The `width` parameter specifies the
+	size, in units of `char`, of the data to be stored (e.g., use
+	`sizeof(uint32_t)` to store 32-bit integers). The `validity`
+	parameter is either NULL or a pointer to a function providing a
+	20-byte validity sha1.
+
+`metadata_cache_lookup`::
+
+	Retrieve a value from the object cache. A void pointer to the
+	stored value will be returned, or `NULL` if there is no value.
+
+`metadata_cache_add`::
+
+	Store a value in the object cache. The value pointer should
+	point to exactly `width` bytes of data.
+
+`metadata_cache_lookup_uint32`::
+
+	Convenience wrapper for retrieving unsigned 32-bit integers. The
+	value will be returned via the `value` pointer. The return value
+	is `0` if a value was found, or negative otherwise (in which
+	case the contents of `value` will be unchanged).
+
+`metadata_cache_add_uint32`::
+
+	Convenience wrapper for storing unsigned 32-bit integers. Note
+	that integers are stored on disk in network-byte order, so it is
+	safe to access caches from any architecture.
diff --git a/Makefile b/Makefile
index f8c72e1..d0b1376 100644
--- a/Makefile
+++ b/Makefile
@@ -532,6 +532,7 @@ LIB_H += log-tree.h
 LIB_H += mailmap.h
 LIB_H += merge-file.h
 LIB_H += merge-recursive.h
+LIB_H += metadata-cache.h
 LIB_H += notes.h
 LIB_H += notes-cache.h
 LIB_H += notes-merge.h
@@ -624,6 +625,7 @@ LIB_OBJS += mailmap.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge-file.o
 LIB_OBJS += merge-recursive.o
+LIB_OBJS += metadata-cache.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
diff --git a/metadata-cache.c b/metadata-cache.c
new file mode 100644
index 0000000..e2e5ff8
--- /dev/null
+++ b/metadata-cache.c
@@ -0,0 +1,337 @@
+#include "cache.h"
+#include "metadata-cache.h"
+#include "sha1-lookup.h"
+#include "object.h"
+
+static struct metadata_cache **autowrite;
+static int autowrite_nr;
+static int autowrite_alloc;
+
+static int installed_atexit_autowriter;
+
+static int record_size(const struct metadata_cache *c)
+{
+	/* a record is a 20-byte sha1 plus the width of the value */
+	return c->mem.width + 20;
+}
+
+static const char *metadata_cache_path(const char *name)
+{
+	return git_path("cache/%s", name);
+}
+
+static void close_disk_cache(struct metadata_cache *c)
+{
+	if (c->map) {
+		munmap(c->map, c->maplen);
+		c->map = NULL;
+		c->maplen = 0;
+		c->disk_entries = 0;
+		c->disk_nr = 0;
+	}
+
+	if (c->fd >= 0) {
+		close(c->fd);
+		c->fd = -1;
+	}
+}
+
+static unsigned char *check_cache_header(struct metadata_cache *c,
+					 const char *path)
+{
+	unsigned char *p = c->map;
+	unsigned char validity[20];
+	uint32_t version;
+	uint32_t width;
+
+	if (c->maplen < 32) {
+		warning("cache file '%s' is short (%lu bytes)",
+			path, c->maplen);
+		return NULL;
+	}
+
+	if (memcmp(p, "MTAC", 4)) {
+		warning("cache file '%s' has invalid magic: %c%c%c%c",
+			path, p[0], p[1], p[2], p[3]);
+		return NULL;
+	}
+	p += 4;
+
+	version = ntohl(*(uint32_t *)p);
+	if (version != 1) {
+		warning("cache file '%s' has unknown version: %"PRIu32,
+			path, version);
+		return NULL;
+	}
+	p += 4;
+
+	width = ntohl(*(uint32_t *)p);
+	if (width != c->mem.width) {
+		warning("cache file '%s' does not have desired width: "
+			"(%"PRIu32" != %u", path, width, c->mem.width);
+		return NULL;
+	}
+	p += 4;
+
+	if (c->validity_fun) {
+		c->validity_fun(validity);
+		if (hashcmp(validity, p))
+			return NULL;
+	}
+	else {
+		if (!is_null_sha1(p))
+			return NULL;
+	}
+	p += 20;
+
+	return p;
+}
+
+static void open_disk_cache(struct metadata_cache *c, const char *path)
+{
+	struct stat sb;
+
+	c->fd = open(path, O_RDONLY);
+	if (c->fd < 0)
+		return;
+
+	if (fstat(c->fd, &sb) < 0) {
+		close_disk_cache(c);
+		return;
+	}
+
+	c->maplen = sb.st_size;
+	c->map = xmmap(NULL, c->maplen, PROT_READ, MAP_PRIVATE, c->fd, 0);
+
+	c->disk_entries = check_cache_header(c, path);
+	if (!c->disk_entries) {
+		close_disk_cache(c);
+		return;
+	}
+	c->disk_nr = (sb.st_size - (c->disk_entries - c->map)) / record_size(c);
+}
+
+static unsigned char *flatten_mem_entries(struct metadata_cache *c)
+{
+	int i;
+	unsigned char *ret;
+	int nr;
+
+	ret = xmalloc(c->mem.nr * record_size(c));
+	nr = 0;
+	for (i = 0; i < c->mem.size; i++) {
+		struct object_decoration *e = decoration_slot(&c->mem, i);
+		unsigned char *out;
+
+		if (!e->base)
+			continue;
+
+		if (nr == c->mem.nr)
+			die("BUG: decorate hash contained extra values");
+
+		out = ret + (nr * record_size(c));
+		hashcpy(out, e->base->sha1);
+		out += 20;
+		memcpy(out, e->decoration, c->mem.width);
+		nr++;
+	}
+
+	return ret;
+}
+
+static int void_hashcmp(const void *a, const void *b)
+{
+	return hashcmp(a, b);
+}
+
+static int write_header(int fd, struct metadata_cache *c)
+{
+	uint32_t width;
+	unsigned char validity[20];
+
+	if (write_in_full(fd, "MTAC\x00\x00\x00\x01", 8) < 0)
+		return -1;
+
+	width = htonl(c->mem.width);
+	if (write_in_full(fd, &width, 4) < 0)
+		return -1;
+
+	if (c->validity_fun)
+		c->validity_fun(validity);
+	else
+		hashcpy(validity, null_sha1);
+	if (write_in_full(fd, validity, 20) < 0)
+		return -1;
+
+	return 0;
+}
+
+static int merge_entries(int fd, int size,
+			 const unsigned char *left, unsigned nr_left,
+			 const unsigned char *right, unsigned nr_right)
+{
+#define ADVANCE(name) \
+	do { \
+		name += size; \
+		nr_##name--; \
+	} while(0)
+#define WRITE_ENTRY(name) \
+	do { \
+		if (write_in_full(fd, name, size) < 0) \
+			return -1; \
+		ADVANCE(name); \
+	} while(0)
+
+	while (nr_left && nr_right) {
+		int cmp = hashcmp(left, right);
+
+		/* skip duplicates, preferring left to right */
+		if (cmp == 0)
+			ADVANCE(right);
+		else if (cmp < 0)
+			WRITE_ENTRY(left);
+		else
+			WRITE_ENTRY(right);
+	}
+	while (nr_left)
+		WRITE_ENTRY(left);
+	while (nr_right)
+		WRITE_ENTRY(right);
+
+#undef WRITE_ENTRY
+#undef ADVANCE
+
+	return 0;
+}
+
+static int metadata_cache_write(struct metadata_cache *c, const char *name)
+{
+	const char *path = metadata_cache_path(name);
+	struct strbuf tempfile = STRBUF_INIT;
+	int fd;
+	unsigned char *mem_entries;
+
+	if (!c->mem.nr)
+		return 0;
+
+	strbuf_addf(&tempfile, "%s.XXXXXX", path);
+	if (safe_create_leading_directories(tempfile.buf) < 0 ||
+	    (fd = git_mkstemp_mode(tempfile.buf, 0755)) < 0) {
+		strbuf_release(&tempfile);
+		return -1;
+	}
+
+	if (write_header(fd, c) < 0)
+		goto fail;
+
+	mem_entries = flatten_mem_entries(c);
+	qsort(mem_entries, c->mem.nr, record_size(c), void_hashcmp);
+
+	if (merge_entries(fd, record_size(c),
+			  mem_entries, c->mem.nr,
+			  c->disk_entries, c->disk_nr) < 0) {
+		free(mem_entries);
+		goto fail;
+	}
+	free(mem_entries);
+
+	if (close(fd) < 0)
+		goto fail;
+	if (rename(tempfile.buf, path) < 0)
+		goto fail;
+
+	strbuf_release(&tempfile);
+	return 0;
+
+fail:
+	close(fd);
+	unlink(tempfile.buf);
+	strbuf_release(&tempfile);
+	return -1;
+}
+static void autowrite_metadata_caches(void)
+{
+	int i;
+	for (i = 0; i < autowrite_nr; i++)
+		metadata_cache_write(autowrite[i], autowrite[i]->mem.name);
+}
+
+static void metadata_cache_init(struct metadata_cache *c)
+{
+	if (c->initialized)
+		return;
+
+	open_disk_cache(c, metadata_cache_path(c->mem.name));
+
+	ALLOC_GROW(autowrite, autowrite_nr+1, autowrite_alloc);
+	autowrite[autowrite_nr++] = c;
+	if (!installed_atexit_autowriter) {
+		atexit(autowrite_metadata_caches);
+		installed_atexit_autowriter = 1;
+	}
+
+	c->initialized = 1;
+}
+
+static void *lookup_disk(struct metadata_cache *c,
+			 const struct object *obj)
+{
+	int pos;
+
+	pos = sha1_entry_pos(c->disk_entries, record_size(c), 0,
+			     0, c->disk_nr, c->disk_nr, obj->sha1);
+	if (pos < 0)
+		return NULL;
+
+	return c->disk_entries + (pos * record_size(c)) + 20;
+}
+
+const void *metadata_cache_lookup(struct metadata_cache *c,
+				  const struct object *obj)
+{
+	void *r;
+
+	metadata_cache_init(c);
+
+	r = lookup_decoration_value(&c->mem, obj);
+	if (!r)
+		r = lookup_disk(c, obj);
+	return r;
+}
+
+void metadata_cache_add(struct metadata_cache *c, const struct object *obj,
+			const void *value)
+{
+	metadata_cache_init(c);
+	add_decoration_value(&c->mem, obj, value, NULL);
+}
+
+int metadata_cache_lookup_uint32(struct metadata_cache *c,
+				 const struct object *obj,
+				 uint32_t *value)
+{
+	const uint32_t *out;
+
+	if (record_size(c) != 24)
+		die("BUG: size mismatch in object cache lookup (%d != 24)",
+		    record_size(c));
+
+	out = metadata_cache_lookup(c, obj);
+	if (!out)
+		return -1;
+
+	*value = ntohl(*out);
+	return 0;
+}
+
+void metadata_cache_add_uint32(struct metadata_cache *c,
+			       const struct object *obj,
+			       uint32_t value)
+{
+	if (record_size(c) != 24)
+		die("BUG: size mismatch in object cache add (%d != 24)",
+		    record_size(c));
+
+	value = htonl(value);
+	metadata_cache_add(c, obj, &value);
+}
diff --git a/metadata-cache.h b/metadata-cache.h
new file mode 100644
index 0000000..5b761e1
--- /dev/null
+++ b/metadata-cache.h
@@ -0,0 +1,40 @@
+#ifndef METADATA_CACHE_H
+#define METADATA_CACHE_H
+
+#include "decorate.h"
+
+typedef void (*metadata_cache_validity_fun)(unsigned char out[20]);
+
+struct metadata_cache {
+	metadata_cache_validity_fun validity_fun;
+
+	/* in memory entries */
+	struct decoration mem;
+
+	/* mmap'd disk entries */
+	int fd;
+	unsigned char *map;
+	unsigned long maplen;
+	unsigned char *disk_entries;
+	int disk_nr;
+
+	int initialized;
+};
+
+#define METADATA_CACHE_INIT(name, width, validity) \
+	{ validity, { (name), (width) } }
+
+const void *metadata_cache_lookup(struct metadata_cache *,
+				  const struct object *);
+void metadata_cache_add(struct metadata_cache *, const struct object *,
+			const void *value);
+
+/* Convenience wrappers around metadata_cache_{lookup,add} */
+int metadata_cache_lookup_uint32(struct metadata_cache *,
+				 const struct object *,
+				 uint32_t *value);
+void metadata_cache_add_uint32(struct metadata_cache *,
+			       const struct object *,
+			       uint32_t value);
+
+#endif /* METADATA_CACHE_H */
-- 
1.7.6.37.g989c6

Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure

[Bert Wesarg]

On Wed, Jul 13, 2011 at 09:04, Jeff King <peff@peff.net> wrote:
> diff --git a/metadata-cache.c b/metadata-cache.c
> new file mode 100644
> index 0000000..e2e5ff8
> --- /dev/null
> +++ b/metadata-cache.c
> @@ -0,0 +1,337 @@
> +#include "cache.h"
> +#include "metadata-cache.h"
> +#include "sha1-lookup.h"
> +#include "object.h"
> +
> +static struct metadata_cache **autowrite;
> +static int autowrite_nr;
> +static int autowrite_alloc;
> +
> +static int installed_atexit_autowriter;
> +
> +static int record_size(const struct metadata_cache *c)
> +{
> +       /* a record is a 20-byte sha1 plus the width of the value */
> +       return c->mem.width + 20;

You are circumventing your own API. Why do you don't use the
decoration_width() accessor here? I don't see any check that
METADATA_CACHE_INIT("frotz", 0, NULL) is invalid neither in the
documentation nor in the code.

> +}
> +

Bert

Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure

[Jeff King]

On Wed, Jul 13, 2011 at 10:18:28AM +0200, Bert Wesarg wrote:

> > +static int record_size(const struct metadata_cache *c)
> > +{
> > +       /* a record is a 20-byte sha1 plus the width of the value */
> > +       return c->mem.width + 20;
> 
> You are circumventing your own API. Why do you don't use the
> decoration_width() accessor here? I don't see any check that
> METADATA_CACHE_INIT("frotz", 0, NULL) is invalid neither in the
> documentation nor in the code.

"struct decoration" has the "0 width means store a void pointer" rule
for compatibility with existing callers. But I never intended for
metadata-cache to have such an exception. Nor would it make sense to
store a void pointer. The pointer would be written to disk, and would
then be meaningless during the next run of the program.

I didn't figure anyone would assume the same special rule held for
metadata-cache; the fact that it is implemented using "struct
decoration" is not part of its public API. But I guess I was wrong.

It might make sense to put:

  if (!c->mem.width)
          die("BUG: zero-width metadata-cache");

into the initialization function to make it more clear, and make a note
in the API documentation.

I considered briefly that a zero-width cache might actually be useful
for storing a membership list (i.e., "is this sha1 in the list or not").
But then you have no way of distinguishing "not in the list" from "have
no checked whether it should be in the list". You are probably better
off storing a single byte flag in such cases.

-Peff

Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure

[Bert Wesarg]

On Wed, Jul 13, 2011 at 10:31, Jeff King <peff@peff.net> wrote:
> On Wed, Jul 13, 2011 at 10:18:28AM +0200, Bert Wesarg wrote:
>
>> > +static int record_size(const struct metadata_cache *c)
>> > +{
>> > +       /* a record is a 20-byte sha1 plus the width of the value */
>> > +       return c->mem.width + 20;
>>
>> You are circumventing your own API. Why do you don't use the
>> decoration_width() accessor here? I don't see any check that
>> METADATA_CACHE_INIT("frotz", 0, NULL) is invalid neither in the
>> documentation nor in the code.
>
> "struct decoration" has the "0 width means store a void pointer" rule
> for compatibility with existing callers. But I never intended for
> metadata-cache to have such an exception. Nor would it make sense to
> store a void pointer. The pointer would be written to disk, and would
> then be meaningless during the next run of the program.
>
> I didn't figure anyone would assume the same special rule held for
> metadata-cache; the fact that it is implemented using "struct
> decoration" is not part of its public API. But I guess I was wrong.

You're right here, that it is not part of the public API, but you're
not wrong about your guess. But when reading this patch series, the
reader obviously knows that the metadata-cache uses a struct
decoration for the in-memory values. Thus the reader knows that 0 is
special for struct decoration, and that there is an API to get the
width from the struct decoration.

>
> It might make sense to put:
>
>  if (!c->mem.width)
>          die("BUG: zero-width metadata-cache");
>
> into the initialization function to make it more clear, and make a note
> in the API documentation.

That should be good. Thanks.

Bert

> -Peff
>

Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure

[Jeff King]

On Wed, Jul 13, 2011 at 10:45:52AM +0200, Bert Wesarg wrote:

> > It might make sense to put:
> >
> >  if (!c->mem.width)
> >          die("BUG: zero-width metadata-cache");
> >
> > into the initialization function to make it more clear, and make a note
> > in the API documentation.
> 
> That should be good. Thanks.

I've squashed in the patch below for my next re-roll.

diff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt
index 192a868..e335b96 100644
--- a/Documentation/technical/api-metadata-cache.txt
+++ b/Documentation/technical/api-metadata-cache.txt
@@ -102,9 +102,10 @@ Functions
 	specifies a human-readable name which will be used for storage
 	in `$GIT_DIR/cache/$name`. The `width` parameter specifies the
 	size, in units of `char`, of the data to be stored (e.g., use
-	`sizeof(uint32_t)` to store 32-bit integers). The `validity`
-	parameter is either NULL or a pointer to a function providing a
-	20-byte validity sha1.
+	`sizeof(uint32_t)` to store 32-bit integers). The `width`
+	parameter must be greater than 0. The `validity` parameter is
+	either NULL or a pointer to a function providing a 20-byte
+	validity sha1.
 
 `metadata_cache_lookup`::
 
diff --git a/metadata-cache.c b/metadata-cache.c
index e2e5ff8..025d3a5 100644
--- a/metadata-cache.c
+++ b/metadata-cache.c
@@ -261,6 +261,9 @@ static void metadata_cache_init(struct metadata_cache *c)
 	if (c->initialized)
 		return;
 
+	if (!c->mem.width)
+		die("BUG: tried to initialize zero-width metadata cache");
+
 	open_disk_cache(c, metadata_cache_path(c->mem.name));
 
 	ALLOC_GROW(autowrite, autowrite_nr+1, autowrite_alloc);

-Peff

Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> I considered briefly that a zero-width cache might actually be useful
> for storing a membership list (i.e., "is this sha1 in the list or not").
> But then you have no way of distinguishing "not in the list" from "have
> no checked whether it should be in the list". You are probably better
> off storing a single byte flag in such cases.

Good reasoning; if you are going to add "BUG:zero width", the above is a
good comment to have nearby.

Thanks.

Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> +`metadata_cache_lookup_uint32`::
> +`metadata_cache_add_uint32`::

I think these are "uint31" functions, as you cannot signal missing entry
by returning a value with the MSB set if higher-end of uint32 range can be
a valid value.

> +	if (c->validity_fun) {
> +		c->validity_fun(validity);
> +		if (hashcmp(validity, p))
> +			return NULL;
> +	}

Two comments.

 - I would have expected that c->validity_check() would be a way for a
   caller to implement a boolean function to check the validity of the
   cache, with another hook c->validity_token() to generate/update the
   token. I could then use the 20-byte space to store a timestamp and
   check can say "It was still 3-days ago? fresh enough", or something
   like that. But this is not a complaint--such a scheme I wrote in the
   above four lines may be _too_ flexible to be useful.

 - I wonder if validity_fn() callback wants a callback parameter (the
   pointer "c" itself, after adding an extra field to metadata_cache that
   stores the callback parameter pointer of type "void *" and adding a
   parameter to METADATA_CACHE_INIT() macro to initialize it).

Other than that, this is looking fun ;-)

Re: [RFC/PATCHv2 2/6] add metadata-cache infrastructure

[Jeff King]

On Wed, Jul 13, 2011 at 12:33:24PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > +`metadata_cache_lookup_uint32`::
> > +`metadata_cache_add_uint32`::
> 
> I think these are "uint31" functions, as you cannot signal missing entry
> by returning a value with the MSB set if higher-end of uint32 range can be
> a valid value.

No, look at their definitions. I am careful not to assume we have a
sentinel value for "not found", and you must use them like:

  uint32_t value;
  if (metadata_cache_lookup_uint32(c, obj, &value))
          printf("value is %"PRIu32", value);
  else
          printf("value is not there");

> > +	if (c->validity_fun) {
> > +		c->validity_fun(validity);
> > +		if (hashcmp(validity, p))
> > +			return NULL;
> > +	}
> 
> Two comments.
> 
>  - I would have expected that c->validity_check() would be a way for a
>    caller to implement a boolean function to check the validity of the
>    cache, with another hook c->validity_token() to generate/update the
>    token. I could then use the 20-byte space to store a timestamp and
>    check can say "It was still 3-days ago? fresh enough", or something
>    like that. But this is not a complaint--such a scheme I wrote in the
>    above four lines may be _too_ flexible to be useful.

I started with exactly that interface, and came to the conclusion that
it was unneeded flexibility. I can switch it back, but there's really
not a need to at this point. The fact that there are 20 opaque bytes in
the file is what will live with us from version to version. But if new
code wants to be more flexible about how it checks the bytes, that is
something that can be changed easily when the new code is added.

>  - I wonder if validity_fn() callback wants a callback parameter (the
>    pointer "c" itself, after adding an extra field to metadata_cache that
>    stores the callback parameter pointer of type "void *" and adding a
>    parameter to METADATA_CACHE_INIT() macro to initialize it).

Neither this use nor my proposed patch-id cache would have a need for
it, so I didn't bother. And like above, it can be easily changed later.

> Other than that, this is looking fun ;-)

Thanks. I'm pleased with the performance numbers I'm getting. I'm still
a bit iffy on the alignment and aliasing issues in the first two
patches.

-Peff

[RFC/PATCHv2 3/6] commit: add commit_generation function

[Jeff King]

A commit's generation is its height in the history graph, as
measured from the farthest root. It is defined as:

  - If the commit has no parents, then its generation is 0.

  - Otherwise, its generation is 1 more than the maximum of
    its parents generations.

The following diagram shows a sample history with
generations:

  A(0)--B(1)--C(2)------G(5)--H(6)
         \             /
          D(2)--E(3)--F(4)

Note that C and D have the same generation, as they are both
children of B. Note also that the merge commit G's
generation is 5, not 3, as we take the maximum of its
parents' generations.

Generation numbers can be useful for bounding traversals.
For example, if we have two commits with generations 500 and
600, we know that the second cannot be an ancestor of the
first. The first could be an ancestor of the second, but we
can't know unless we traverse the history graph. However,
when walking backwards from the "600" commit, once we reach
generation "499", we know that the "500" commit cannot be an
ancestor of the "499" commit, and we can stop the traversal
without even looking at the earlier parts of the history.

We already do something similar with commit timestamps in
many traversals. However, timestamps are somewhat
untrustworthy, as we have to deal with clock skew and with
imports from buggy systems.

Generation numbers are easy to calculate recursively, though
you have to go to the roots to do so. This patch calculates
and stores them in a persistent cache.  It uses a simple
recursive algorithm; you could probably drop the recursion
by topologically sorting a list of all commits and filling
in generation numbers left to right. But the recursive
definition coupled with the cache make it very cheap to
calculate generation numbers for new commits at the tip of
history (you only have to traverse back to the last cached
parents).

We could also store generation numbers in the commit header
directly. These would be faster to look at than an external
cache (they would be on par speed-wise with commit
timestamps). But there are a few reasons not to:

  1. The reason to avoid commit timestamps is that they are
     unreliable. Generation numbers would probably be more
     reliable, but they are still redundant with the actual
     graph structure represented by the parent pointers, and
     can therefore be out of sync with the parent
     information. By calculating them ourselves, we know
     they are correct.

  2. With grafts and replacement objects, the graph
     structure (and thus the generation numbers) can be
     changed. So the generation number, while immutable for
     a given commit object, can be changed when we "lie"
     about the graph structure via these mechanisms. Being
     able to simply clear the cache when these things are
     changed is helpful.

  3. There's a lot of existing git history without
     generation headers. So we'd still need to have the same
     cache to handle those cases.

  4. It generally pollutes the header with redundant
     information, which we try to avoid. Putting it in the
     commit header is purely a speedup, and it seems we can
     get similar performance with a generation cache.

Signed-off-by: Jeff King <peff@peff.net>
---
Same as before, but rebased onto the new metadata-cache interface.

 commit.c |   36 ++++++++++++++++++++++++++++++++++++
 commit.h |    2 ++
 2 files changed, 38 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index ac337c7..fb37aa0 100644
--- a/commit.c
+++ b/commit.c
@@ -6,6 +6,7 @@
 #include "diff.h"
 #include "revision.h"
 #include "notes.h"
+#include "metadata-cache.h"
 
 int save_commit_buffer = 1;
 
@@ -878,3 +879,38 @@ int commit_tree(const char *msg, unsigned char *tree,
 	strbuf_release(&buffer);
 	return result;
 }
+
+static struct metadata_cache generations =
+	METADATA_CACHE_INIT("generations", sizeof(uint32_t), NULL);
+
+static unsigned long commit_generation_recurse(struct commit *c)
+{
+	struct commit_list *p;
+	uint32_t r;
+
+	if (!metadata_cache_lookup_uint32(&generations, &c->object, &r))
+		return r;
+
+	if (parse_commit(c) < 0)
+		die("unable to parse commit: %s", sha1_to_hex(c->object.sha1));
+
+	if (!c->parents)
+		return 0;
+
+	r = 0;
+	for (p = c->parents; p; p = p->next) {
+		unsigned long pgen = commit_generation_recurse(p->item);
+		if (pgen > r)
+			r = pgen;
+	}
+	r++;
+
+	metadata_cache_add_uint32(&generations, &c->object, r);
+	return r;
+}
+
+unsigned long commit_generation(const struct commit *commit)
+{
+	/* drop const because we may call parse_commit */
+	return commit_generation_recurse((struct commit *)commit);
+}
diff --git a/commit.h b/commit.h
index a2d571b..bff6b36 100644
--- a/commit.h
+++ b/commit.h
@@ -176,4 +176,6 @@ extern int commit_tree(const char *msg, unsigned char *tree,
 		struct commit_list *parents, unsigned char *ret,
 		const char *author);
 
+unsigned long commit_generation(const struct commit *commit);
+
 #endif /* COMMIT_H */
-- 
1.7.6.37.g989c6

Re: [RFC/PATCHv2 3/6] commit: add commit_generation function

[Eric Sunshine]

On 7/13/2011 3:05 AM, Jeff King wrote:
> A commit's generation is its height in the history graph, as
> measured from the farthest root. It is defined as:
>
>    - Otherwise, its generation is 1 more than the maximum of
>      its parents generations.

Possessive: s/parents/parents'/

> We could also store generation numbers in the commit header
> directly. These would be faster to look at than an external
> cache (they would be on par speed-wise with commit
> timestamps). But there are a few reasons not to:
>
>    2. With grafts and replacement objects, the graph
>       structure (and thus the generation numbers) can be
>       changed. So the generation number, while immutable for
>       a given commit object, can be changed when we "lie"
>       about the graph structure via these mechanisms. Being
>       able to simply clear the cache when these things are
>       changed is helpful.

Would this be clearer? "Being able to rebuild the cache when..."

-- ES

[RFC/PATCHv2 4/6] pretty: support %G to show the generation number of a commit

[Jeff King]

This might be useful for external programs doing topological
sorting or other graph analysis. It's also handy for testing
the generation calculation code.

Signed-off-by: Jeff King <peff@peff.net>
---
This now includes some basic tests.

 Documentation/pretty-formats.txt |    1 +
 pretty.c                         |    3 ++
 t/t6070-commit-generations.sh    |   41 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 45 insertions(+), 0 deletions(-)
 create mode 100755 t/t6070-commit-generations.sh

diff --git a/Documentation/pretty-formats.txt b/Documentation/pretty-formats.txt
index 561cc9f..c58ab52 100644
--- a/Documentation/pretty-formats.txt
+++ b/Documentation/pretty-formats.txt
@@ -133,6 +133,7 @@ The placeholders are:
 - '%gD': reflog selector, e.g., `refs/stash@\{1\}`
 - '%gd': shortened reflog selector, e.g., `stash@\{1\}`
 - '%gs': reflog subject
+- '%G': generation number (i.e., distance of path to farthest root ancestor)
 - '%Cred': switch color to red
 - '%Cgreen': switch color to green
 - '%Cblue': switch color to blue
diff --git a/pretty.c b/pretty.c
index f45eb54..8f1b321 100644
--- a/pretty.c
+++ b/pretty.c
@@ -965,6 +965,9 @@ static size_t format_commit_one(struct strbuf *sb, const char *placeholder,
 			return 2;
 		}
 		return 0;	/* unknown %g placeholder */
+	case 'G':
+		strbuf_addf(sb, "%lu", commit_generation(commit));
+		return 1;
 	case 'N':
 		if (c->pretty_ctx->show_notes) {
 			format_display_notes(commit->object.sha1, sb,
diff --git a/t/t6070-commit-generations.sh b/t/t6070-commit-generations.sh
new file mode 100755
index 0000000..3e0f2ad
--- /dev/null
+++ b/t/t6070-commit-generations.sh
@@ -0,0 +1,41 @@
+#!/bin/sh
+
+test_description='calculate and cache commit generations'
+. ./test-lib.sh
+
+test_expect_success 'setup history' '
+	test_commit one &&
+	test_commit two &&
+	test_commit three &&
+	test_commit four &&
+	git checkout -b other two &&
+	test_commit five &&
+	git checkout master &&
+	git merge other &&
+	test_commit six
+'
+
+cat >expect <<'EOF'
+5 six
+4 Merge branch 'other'
+2 five
+3 four
+2 three
+1 two
+0 one
+EOF
+test_expect_success 'check commit generations' '
+	git log --format="%G %s" >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'cache file was created' '
+	test_path_is_file .git/cache/generations
+'
+
+test_expect_success 'cached values are the same' '
+	git log --format="%G %s" >actual &&
+	test_cmp expect actual
+'
+
+test_done
-- 
1.7.6.37.g989c6

[RFC/PATCHv2 5/6] check commit generation cache validity against grafts

[Jeff King]

Some caches, like the commit generation cache, rely on the
shape of the history graph to be accurate. Because commits
are immutable, that shape should never change. However, our
view onto the graph is modified by grafts and replace refs;
if these change, the values in our cache are invalid and
should be regenerated.

We take a pretty heavy-handed approach, and simply throw out
and regenerate the whole cache when either grafts or replace
refs change. In theory we could be slightly more efficient
by comparing the view under which our cache was generated to
the current one. But doing that is complex, and requires
storing the old state.

Instead, we summarize all of the grafts and replace objects
with a single 20-byte sha1. Because the grafts and replace
refs don't tend to change very often, this is simple and
efficient enough.

The actual contents of what we stir into the sha1 are not
important, as long as:

  1. A given state is consistently represented across runs.

  2. Distinct states generate distinct input to the sha1
     function.

Signed-off-by: Jeff King <peff@peff.net>
---
New in this version of the series.

 Documentation/technical/api-metadata-cache.txt |    7 ++++
 cache.h                                        |    1 +
 commit.c                                       |   24 +++++++++++++++-
 commit.h                                       |    2 +
 metadata-cache.c                               |   16 ++++++++++
 metadata-cache.h                               |    3 ++
 replace_object.c                               |   15 ++++++++++
 t/t6070-commit-generations.sh                  |   36 ++++++++++++++++++++++++
 8 files changed, 103 insertions(+), 1 deletions(-)

diff --git a/Documentation/technical/api-metadata-cache.txt b/Documentation/technical/api-metadata-cache.txt
index 192a868..f43b1ba 100644
--- a/Documentation/technical/api-metadata-cache.txt
+++ b/Documentation/technical/api-metadata-cache.txt
@@ -128,3 +128,10 @@ Functions
 	Convenience wrapper for storing unsigned 32-bit integers. Note
 	that integers are stored on disk in network-byte order, so it is
 	safe to access caches from any architecture.
+
+`metadata_graph_validity`::
+
+	This function is intended to be used with `METADATA_CACHE_INIT`
+	as a validity function. It returns a SHA1 summarizing the
+	current state of any commit grafts and replace objects that
+	would affect the shape of the history graph.
diff --git a/cache.h b/cache.h
index bc9e5eb..50e8a1c 100644
--- a/cache.h
+++ b/cache.h
@@ -745,6 +745,7 @@ static inline const unsigned char *lookup_replace_object(const unsigned char *sh
 		return sha1;
 	return do_lookup_replace_object(sha1);
 }
+extern void replace_object_validity(git_SHA_CTX *ctx);
 
 /* Read and unpack a sha1 file into memory, write memory to a sha1 file */
 extern int sha1_object_info(const unsigned char *, unsigned long *);
diff --git a/commit.c b/commit.c
index fb37aa0..e72bb3e 100644
--- a/commit.c
+++ b/commit.c
@@ -246,6 +246,27 @@ int unregister_shallow(const unsigned char *sha1)
 	return 0;
 }
 
+void commit_graft_validity(git_SHA_CTX *ctx)
+{
+	int i;
+
+	prepare_commit_graft();
+
+	for (i = 0; i < commit_graft_nr; i++) {
+		const struct commit_graft *c = commit_graft[i];
+		git_SHA1_Update(ctx, c->sha1, 20);
+		if (c->nr_parent < 0)
+			git_SHA1_Update(ctx, "shallow", 7);
+		else {
+			uint32_t v = htonl(c->nr_parent);
+			int j;
+			git_SHA1_Update(ctx, &v, sizeof(v));
+			for (j = 0; j < c->nr_parent; j++)
+				git_SHA1_Update(ctx, c->parent[j], 20);
+		}
+	}
+}
+
 int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size)
 {
 	const char *tail = buffer;
@@ -881,7 +902,8 @@ int commit_tree(const char *msg, unsigned char *tree,
 }
 
 static struct metadata_cache generations =
-	METADATA_CACHE_INIT("generations", sizeof(uint32_t), NULL);
+	METADATA_CACHE_INIT("generations", sizeof(uint32_t),
+			    metadata_graph_validity);
 
 static unsigned long commit_generation_recurse(struct commit *c)
 {
diff --git a/commit.h b/commit.h
index bff6b36..e6d144d 100644
--- a/commit.h
+++ b/commit.h
@@ -178,4 +178,6 @@ extern int commit_tree(const char *msg, unsigned char *tree,
 
 unsigned long commit_generation(const struct commit *commit);
 
+void commit_graft_validity(git_SHA_CTX *ctx);
+
 #endif /* COMMIT_H */
diff --git a/metadata-cache.c b/metadata-cache.c
index e2e5ff8..32d3c21 100644
--- a/metadata-cache.c
+++ b/metadata-cache.c
@@ -2,6 +2,7 @@
 #include "metadata-cache.h"
 #include "sha1-lookup.h"
 #include "object.h"
+#include "commit.h"
 
 static struct metadata_cache **autowrite;
 static int autowrite_nr;
@@ -335,3 +336,18 @@ void metadata_cache_add_uint32(struct metadata_cache *c,
 	value = htonl(value);
 	metadata_cache_add(c, obj, &value);
 }
+
+void metadata_graph_validity(unsigned char out[20])
+{
+	git_SHA_CTX ctx;
+
+	git_SHA1_Init(&ctx);
+
+	git_SHA1_Update(&ctx, "grafts", 6);
+	commit_graft_validity(&ctx);
+
+	git_SHA1_Update(&ctx, "replace", 7);
+	replace_object_validity(&ctx);
+
+	git_SHA1_Final(out, &ctx);
+}
diff --git a/metadata-cache.h b/metadata-cache.h
index 5b761e1..15484b5 100644
--- a/metadata-cache.h
+++ b/metadata-cache.h
@@ -37,4 +37,7 @@ void metadata_cache_add_uint32(struct metadata_cache *,
 			       const struct object *,
 			       uint32_t value);
 
+/* Common validity token functions */
+void metadata_graph_validity(unsigned char out[20]);
+
 #endif /* METADATA_CACHE_H */
diff --git a/replace_object.c b/replace_object.c
index d0b1548..9ec462b 100644
--- a/replace_object.c
+++ b/replace_object.c
@@ -115,3 +115,18 @@ const unsigned char *do_lookup_replace_object(const unsigned char *sha1)
 
 	return cur;
 }
+
+void replace_object_validity(git_SHA_CTX *ctx)
+{
+	int i;
+
+	if (!read_replace_refs)
+		return;
+
+	prepare_replace_object();
+
+	for (i = 0; i < replace_object_nr; i++) {
+		git_SHA1_Update(ctx, replace_object[i]->sha1[0], 20);
+		git_SHA1_Update(ctx, replace_object[i]->sha1[1], 20);
+	}
+}
diff --git a/t/t6070-commit-generations.sh b/t/t6070-commit-generations.sh
index 3e0f2ad..0aefd01 100755
--- a/t/t6070-commit-generations.sh
+++ b/t/t6070-commit-generations.sh
@@ -38,4 +38,40 @@ test_expect_success 'cached values are the same' '
 	test_cmp expect actual
 '
 
+cat >expect-grafted <<'EOF'
+1 six
+0 Merge branch 'other'
+EOF
+test_expect_success 'adding grafts invalidates generation cache' '
+	git rev-parse six^ >.git/info/grafts &&
+	git log --format="%G %s" >actual &&
+	test_cmp expect-grafted actual
+'
+
+test_expect_success 'removing graft invalidates cache' '
+	rm .git/info/grafts &&
+	git log --format="%G %s" >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'setup replace ref' '
+	H=$(git rev-parse six^) &&
+	R=$(git cat-file commit $H |
+	    sed /^parent/d |
+	    git hash-object -t commit --stdin -w) &&
+	git update-ref refs/replace/$H $R
+'
+
+test_expect_success 'adding replace refs invalidates generation cache' '
+	git log --format="%G %s" >actual &&
+	test_cmp expect-grafted actual
+'
+
+test_expect_success 'cache respects replace-object settings' '
+	git --no-replace-objects log --format="%G %s" >actual &&
+	test_cmp expect actual &&
+	git log --format="%G %s" >actual &&
+	test_cmp expect-grafted actual
+'
+
 test_done
-- 
1.7.6.37.g989c6

Re: [RFC/PATCHv2 5/6] check commit generation cache validity against grafts

[Eric Sunshine]

On 7/13/2011 3:06 AM, Jeff King wrote:
> +void metadata_graph_validity(unsigned char out[20])
> +{
> +	git_SHA_CTX ctx;
> +
> +	git_SHA1_Init(&ctx);
> +
> +	git_SHA1_Update(&ctx, "grafts", 6);
> +	commit_graft_validity(&ctx);
> +
> +	git_SHA1_Update(&ctx, "replace", 7);
> +	replace_object_validity(&ctx);

The implementation of metadata_graph_validity() makes it clear that 
commit_graft_validity() and replace_object_validity() are computing 
checksums in aid of validity-checking of the generations cache. However, 
the naive reader seeing the names commit_graft_validity() and 
replace_object_validity() in the API is likely to assume that these 
functions are somehow checking validity of the grafts and replace-refs 
themselves, which is not the case. Perhaps better names would be 
commit_graft_checksum() and replace_object_checksum()?

The name metadata_graph_validity() also suffers from this shortcoming. 
The actual validity check is performed by check_cache_header(), whereas 
metadata_graph_validity() is merely computing a checksum.

-- ES

Re: [RFC/PATCHv2 5/6] check commit generation cache validity against grafts

[Jeff King]

On Wed, Jul 13, 2011 at 10:26:28AM -0400, Eric Sunshine wrote:

> On 7/13/2011 3:06 AM, Jeff King wrote:
> >+void metadata_graph_validity(unsigned char out[20])
> >+{
> >+	git_SHA_CTX ctx;
> >+
> >+	git_SHA1_Init(&ctx);
> >+
> >+	git_SHA1_Update(&ctx, "grafts", 6);
> >+	commit_graft_validity(&ctx);
> >+
> >+	git_SHA1_Update(&ctx, "replace", 7);
> >+	replace_object_validity(&ctx);
> 
> The implementation of metadata_graph_validity() makes it clear that
> commit_graft_validity() and replace_object_validity() are computing
> checksums in aid of validity-checking of the generations cache.
> However, the naive reader seeing the names commit_graft_validity()
> and replace_object_validity() in the API is likely to assume that
> these functions are somehow checking validity of the grafts and
> replace-refs themselves, which is not the case. Perhaps better names
> would be commit_graft_checksum() and replace_object_checksum()?

Agreed. The term "validity" is a bit funny, and I think checksum is
better.

> The name metadata_graph_validity() also suffers from this
> shortcoming. The actual validity check is performed by
> check_cache_header(), whereas metadata_graph_validity() is merely
> computing a checksum.

Yeah. I had originally called it metadata_validity_graph() with the
assumption that the metadata-cache would provide a collection of
commonly-used validity functions. That didn't seem quite right, so I
switched the two words around to emphasize that it was about the graph.
But this function really has nothing to do with the metadata-cache at
all (except that validity tokens are a good place to use the result). It
really belongs to the commit subsystem, because it is about the shape of
the history graph.

So here's what I've done for the next iteration:

  1. metadata_graph_validity is now:

      void commit_graph_checksum(unsigned char out[20]);

     and lives in commit.[ch].

  2. commit_graft_validity is now commit_graft_checksum, and is static
     inside commit.c.

  3. replace_object_validity is now replace_objects_checksum. It must
     remain non-static because it lives in replace-object.c. I
     pluralized the "objects" to make it more clear it was not about
     checksumming a single replace_object, but rather all of them.

So now the only two warts I see are:

  1. Some of the *_checksum functions return a 20-byte sha1, and some
     are just meant to stir their contents into a SHA_CTX. I can live
     with that. You can tell which is which by looking at their
     signatures.

  2. The name "replace_object_checksum" can be read as "checksum the
     replace-objects" or as "replace this object's checksum". But the
     ambiguous verb in the name of the subsystem is not a problem I am
     introducing. The "replace-object" subsystem should perhaps have
     been called "replacement-object" from the beginning to make this
     more clear.

Thanks for the suggestions (I also took the suggestions from your other
email for improving the commit message).

-Peff

[RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Jeff King]

When looking for commits that contain other commits (e.g.,
via "git tag --contains"), we can end up traversing useless
portions of the graph. For example, if I am looking for a
tag that contains a commit made last week, there is not much
point in traversing portions of the history graph made five
years ago.

This optimization can provide massive speedups. For example,
doing "git tag --contains HEAD~1000" in the linux-2.6
repository goes from:

  real    0m3.139s
  user    0m3.044s
  sys     0m0.092s

to:

  real    0m0.035s
  user    0m0.028s
  sys     0m0.004s

We could use commit timestamps to know when we are going too
far back in history, but they are sometimes not trustworthy.
Extreme clock skew on committers' machines (or bugs in
commit-generating software) mean that we may stop the
traversal too early when seeing commits skewed into the
past.

Instead, we use the calculated commit generation, which is a
propery of the graph itself (but since we cache it, it's
still cheap to consult).

Signed-off-by: Jeff King <peff@peff.net>
---
Same as previous version.

 builtin/tag.c |   20 +++++++++++++++++---
 1 files changed, 17 insertions(+), 3 deletions(-)

diff --git a/builtin/tag.c b/builtin/tag.c
index 63bce6e..df6de47 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -40,7 +40,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
 }
 
 static int contains_recurse(struct commit *candidate,
-			    const struct commit_list *want)
+			    const struct commit_list *want,
+			    unsigned long cutoff)
 {
 	struct commit_list *p;
 
@@ -57,9 +58,13 @@ static int contains_recurse(struct commit *candidate,
 	if (parse_commit(candidate) < 0)
 		return 0;
 
+	/* stop searching if we go too far back in time */
+	if (commit_generation(candidate) < cutoff)
+		return 0;
+
 	/* Otherwise recurse and mark ourselves for future traversals. */
 	for (p = candidate->parents; p; p = p->next) {
-		if (contains_recurse(p->item, want)) {
+		if (contains_recurse(p->item, want, cutoff)) {
 			candidate->object.flags |= TMP_MARK;
 			return 1;
 		}
@@ -70,7 +75,16 @@ static int contains_recurse(struct commit *candidate,
 
 static int contains(struct commit *candidate, const struct commit_list *want)
 {
-	return contains_recurse(candidate, want);
+	unsigned long cutoff = ULONG_MAX;
+	const struct commit_list *c;
+
+	for (c = want; c; c = c->next) {
+		unsigned long g = commit_generation(c->item);
+		if (g < cutoff)
+			cutoff = g;
+	}
+
+	return contains_recurse(candidate, want, cutoff);
 }
 
 static int show_reference(const char *refname, const unsigned char *sha1,
-- 
1.7.6.37.g989c6

Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Jeff King]

On Wed, Jul 13, 2011 at 03:06:44AM -0400, Jeff King wrote:

> This optimization can provide massive speedups. For example,
> doing "git tag --contains HEAD~1000" in the linux-2.6
> repository goes from:
> 
>   real    0m3.139s
>   user    0m3.044s
>   sys     0m0.092s
> 
> to:
> 
>   real    0m0.035s
>   user    0m0.028s
>   sys     0m0.004s

I pulled this commit message from the original "cutoff at timestamp"
patch, though I did update the timings for the new code. What it doesn't
mention is that the first run will take something like 3.7 seconds, and
then subsequent ones will be way faster. I had mentioned that number
elsewhere in the thread, but it should probably go here. I'll put it in
the next version.

One number I haven't mentioned elsewhere, though, is how expensive it is
to add new commits to the cache. So here's an interesting timing:

  $ cd linux-2.6

  : slow, cache-generating time
  $ rm .git/cache/generations
  $ time git tag --contains HEAD
  real    0m3.795s
  user    0m3.420s
  sys     0m0.372s

  : fast, cached time
  $ time git tag --contains HEAD
  real    0m0.022s
  user    0m0.008s
  sys     0m0.012s

  : now what if we add one more commit?
  $ echo foo >>Makefile && git commit -a -m foo
  $ time git tag --contains HEAD
  real    0m0.271s
  user    0m0.020s
  sys     0m0.252s

It takes barely any time to get the generation of the new commit, but we
spend .25 seconds writing the whole new cache file out. This could be
improved with a more clever disk format that contained a journal of
unsorted newly written entries. You'd still write the full cache out
once in a while, but the cost would be amortized.

I'm not sure the complexity is worth it, though. Yes, the write-out time
is way slower than the super-fast everything-is-cached case. But it
doesn't happen that often (only when you have new commits, _and_ your
traversal actually looks at them). And it's still an order of magnitude
faster than it is without the cache at all. I doubt I would even notice
a quarter-second delay, or would just chalk it up to a few objects
needing to be pulled from disk.

So I'm inclined to leave it as-is, at least for now. If somebody wants
to revisit the topic later and speed up cache writing, they can. But I
don't want a complex solution to hold up this series, which is already a
big improvement.

-Peff

Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> It takes barely any time to get the generation of the new commit, but we
> spend .25 seconds writing the whole new cache file out. This could be
> improved with a more clever disk format that contained a journal of
> unsorted newly written entries. You'd still write the full cache out
> once in a while, but the cost would be amortized.

This series consists of three somewhat related ideas:

 - A generic API to persistently annotate 20-byte keys (typically object
   names);

 - Using that API to implement commit generation numbers;

 - Using commit generation numbers in "tag --contains" traversal.

I think the first one is independently a good change, but I have been
wondering if the entire history needs to be annotated with the generation
number for the goal of the third item. There may be stretches of history
where timestamps are screwed up, but if the commits we should dig through
while traversing (because they, their parents or their children record
skewed timestamps) are minority in the history, the same generic API could
be used to mark only these commits as such, by using far smaller number of
disk I/Os, no?

Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Jeff King]

On Wed, Jul 13, 2011 at 01:33:22PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > It takes barely any time to get the generation of the new commit, but we
> > spend .25 seconds writing the whole new cache file out. This could be
> > improved with a more clever disk format that contained a journal of
> > unsorted newly written entries. You'd still write the full cache out
> > once in a while, but the cost would be amortized.
> 
> This series consists of three somewhat related ideas:
> 
>  - A generic API to persistently annotate 20-byte keys (typically object
>    names);
> 
>  - Using that API to implement commit generation numbers;
> 
>  - Using commit generation numbers in "tag --contains" traversal.

Yup, I think that is accurate.

> I think the first one is independently a good change, but I have been
> wondering if the entire history needs to be annotated with the generation
> number for the goal of the third item. There may be stretches of history
> where timestamps are screwed up, but if the commits we should dig through
> while traversing (because they, their parents or their children record
> skewed timestamps) are minority in the history, the same generic API could
> be used to mark only these commits as such, by using far smaller number of
> disk I/Os, no?

I'm not sure it's workable. To use generations as a cutoff, even
for a subset the subset of commits with broken timestamps, you have to
know the generations of other commits, so you know where the cutoff is.
E.g., in "git tag --contains HEAD~1000", I want to search no farther
back than the generation of HEAD~1000. Which means I need to know what
its generation is, which involves going to the roots at least once. We
don't want to go to the roots on-demand and cache only that one value,
since doing so is expensive. So we may as well cache all generations
as we figure them out, not knowing which ones will be needed for future
traversals.

Or are you suggesting dropping generations entirely, and just using
marked-up commit timestamps (or even a flag saying "this timestamp is
bogus, don't use it for cutoffs")?  I sent such a patch with timings
earlier in this discussion (I can dig it up if you want). Even based on
a notes-cache[1], it's fast (because there aren't very many entries).

But there's a big question of deciding which timestamps are bogus. You
can only compare commits against their ancestors.  A commit skewed to
the past is easy to find; its timestamp is less than one of its
ancestors. But for a commit skewed to the future, its descendants will
all look skewed into the past.

I think we can write our algorithms such that future-skewed timestamps
don't give _wrong_ answers, but are just suboptimal (i.e., they may mark
many legitimate commits as "don't trust this timestamp for cutoff", even
though it is their future-skewed ancestor that is actually the problem).
But I think I still like generation numbers because:

  1. They're simple, complete, and unambiguous. It makes them easy to
     understand and use. And I suspect they can be applied in more
     places than just cutoff. For example, I seem to recall somebody
     mentioning that we could do topo-sorting much more efficiently with
     generation numbers. I'm not sure the same "future-skewed commits
     are correct but slow" property would hold there.

  2. The cache can be generated and maintained on the fly. A cache that
     is simply "if you are in this list, your timestamp is bogus"
     suffers from the problem I mentioned elsewhere. If a commit is not
     in the list, is the timestamp good, or has it simply not been
     checked yet?

If the performance numbers were way worse, I would be more inclined to
stay with a timestamp solution. But they're not really worse. The
performance for initial cache build is about the same (you have to go to
the roots in both cases), and the performance for using the cache is
about the same. The only slowness for the generation slowness is the
extra I/O on writing out the cache. But it's not very much, and it's
actually not that hard a problem to solve; I'm mainly leaving it because
I'm lazy. But it's not as if file system implementors and key/value
database designers haven't been solving the problem for the past 30
years.

-Peff

[1] If we did want to go the route of "is this commit in the set of
commits with bogus timestamps", you could probably make things even
simpler by using a fixed-size bloom filter. Sized appropriately, it will
occasionally give a false positive "this commit has a bogus timestamp".
But as discussed above, that is not going to cause a traversal cutoff to
do the wrong thing, but rather only to consider one extra commit it
might not have otherwise.

Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Or are you suggesting dropping generations entirely, and just using
> marked-up commit timestamps (or even a flag saying "this timestamp is
> bogus, don't use it for cutoffs")?

Not suggesting, but that was exactly what I was wondering.  For example,
still_interesting() in revision.c says "compare timestamp and return SLOP,
not 'we are done'", and presumably that code could notice that "ah, this
commit is marked as being on a stretch that timestamp based cut-off is
unusable--keep digging". The "tag --contains" and "name-rev" would also
have similar logic (I haven't looked at them for a while though).

> But there's a big question of deciding which timestamps are bogus.

I agree that the ones that you need to dig through may not be the ones
with bogus timestamps, but either an ancestor or a descendant (I haven't
thought it through) of a commit with bogus timestamp. That is why I said
"a commit on a stretch that timestamp based cut-off is unusable".

> But I think I still like generation numbers because:
>
>   1. They're simple, complete, and unambiguous.

No question nor dispute about it.

> The only slowness for the generation slowness is the
> extra I/O on writing out the cache. But it's not very much,...

Ok.

Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Jeff King]

On Wed, Jul 13, 2011 at 02:12:55PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > Or are you suggesting dropping generations entirely, and just using
> > marked-up commit timestamps (or even a flag saying "this timestamp is
> > bogus, don't use it for cutoffs")?
> 
> Not suggesting, but that was exactly what I was wondering.  For example,
> still_interesting() in revision.c says "compare timestamp and return SLOP,
> not 'we are done'", and presumably that code could notice that "ah, this
> commit is marked as being on a stretch that timestamp based cut-off is
> unusable--keep digging". The "tag --contains" and "name-rev" would also
> have similar logic (I haven't looked at them for a while though).

Yes, the slop code in still_interesting could use a
"timestamp_is_bogus(commit)" check. It could also use generation
numbers. :)

I actually wonder if we could make merge-base computation more efficient
using generation numbers, and if it would be worth switching more
algorithms over to it. I haven't thought too hard about it, though.

-Peff

Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> diff --git a/builtin/tag.c b/builtin/tag.c
> index 63bce6e..df6de47 100644
> --- a/builtin/tag.c
> +++ b/builtin/tag.c
> @@ -40,7 +40,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
>  }
>  
>  static int contains_recurse(struct commit *candidate,
> -			    const struct commit_list *want)
> +			    const struct commit_list *want,
> +			    unsigned long cutoff)
>  {
>  	struct commit_list *p;
>  
> @@ -57,9 +58,13 @@ static int contains_recurse(struct commit *candidate,
>  	if (parse_commit(candidate) < 0)
>  		return 0;
>  
> +	/* stop searching if we go too far back in time */
> +	if (commit_generation(candidate) < cutoff)
> +		return 0;
> +

Here, the "generation number" was the commit timestamp of the commit in
your earlier round, but now it is not.

I agree with Linus that for the purpose of "rev-list A ^B ^C" computation,
"generation number" is a much better thing to use than the commit
timestamp, and I also think if we want to revamp the codepath around
still_interesting() in revision.c, Linus's "let's add generation header in
new commits" is a good first step. I haven't stared at that codepath long
enough lately to say for sure, but I suspect that in that codepath we
could use generation number in commits when available and fall back to
timestamp with slop without recomputing the generation number and caching
for older commits.

But that is _not_ the codepath your series is about.

What you are trying to say in this series is that "If a tag points at a
commit X (i.e. candidate), another commit Y (i.e. "want") that is much
younger than cannot possibly be included by it, because a tag was made on
commit X way before Y was created". You cut off by "age".

The heuristics would work efficiently to check what tags point at a
relatively recent commit (e.g. when trying to see which releases are
affected and needing a fix by a recently discovered bug introduced by
commit Y) by discarding tags for ancient releases. In such a scenario, the
timestamp of a tagged and ancient commit X on a side branch that was never
merged in the mainline that leads to commit Y (i.e. "want"), in an ideal
world without clock skews, will be way older than the timestamp of commit
Y. In other words, if you use timestamp as "age", even though X and Y do
not relate to each other directly, except that they may share an ancient
common ancestor, their "age"s can be compared and you could apply your
heuristics to optimize.

But if you use the generation number as "age", even in an ideal world
without clock skew nor miscomputed generation number, you no longer can
compare "age" of X and Y.  The ancient side branch that led to X may have
tons more commits than the history leading to Y.

So I have two tangents here.

 * As to revision traversal, the reason we do the SLOP in
   still_interesting() is to avoid the issue arising from the following
   topology:

              5
             /
     ---2---4---...---1
         \
          3---6

   where numbers denote the timestamp of the commit (1 incorrectly records
   ancient timestamp, while everybody else has newer timestamp than its
   parents). When we try to "rev-list 5 --not 1 6", we start from having
   ~1, ~6 and 5 to "currently active" list, and iteratively pick more
   recent commits from the active list to dig deeper while newly found
   ancestors back to the active list. ~6 leads to 3 marked as
   uninteresting and active list gets ~3 while ~6 is removed. 5 leads to 4
   marked as interesting and 4 gets inserted in the list while 5 is
   removed. 4 finds 2 to also be interesting. Then ~3 finds 2 to be
   uninteresting. At that point, we have ~1 (still not processed) and ~2
   in the active list, while we have 5 and 4 in the result list. We need
   to dig through ~1 to realize that 4 is reachable from it to mark it
   uninteresting.

   So how about marking commits (using the metainfo-cache facility) that
   has an ancestor (not necessarily its direct parent) that records a
   younger timestamp (e.g. 1 is such a commit, as its ancestors include
   things like 2 and 4)? There should be relatively small number of them,
   and still_interesting() logic can be told to dig through such commits
   even if everybody is uninteresting in the active list.

 * As to "tag --contains", when timestamp based heuristics breaks down is
   when a tagged commit incorrectly records way young timestamp or the
   "want" commit records way old timetsamp. I haven't thought things
   through, but the same metainfo-cache may be useful to detect which
   commit to dig through ignoring the cutoff heuristics.

Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Jeff King]

On Fri, Jul 15, 2011 at 11:22:03AM -0700, Junio C Hamano wrote:

> > +	/* stop searching if we go too far back in time */
> > +	if (commit_generation(candidate) < cutoff)
> > +		return 0;
> > +
> 
> Here, the "generation number" was the commit timestamp of the commit in
> your earlier round, but now it is not.

Yes.

> [...]
> What you are trying to say in this series is that "If a tag points at a
> commit X (i.e. candidate), another commit Y (i.e. "want") that is much
> younger than cannot possibly be included by it, because a tag was made on
> commit X way before Y was created". You cut off by "age".

More or less. Given two ages, X and Y, you cannot know right off the bat
whether one is an ancestor of the other. You can only know that the
higher generation cannot possibly be an ancestor of the lower
generation.

So yes, in some cases we will see that the tag has generation 5, and the
"want" commit has generation 10, and we will know there is no point in
traversing backwards from 5.

But we may also see a tag with generation 10, and a want commit with
generation 5. In that case, we have to explore backwards, looking to
either find the commit, or to pass a point where we hit a commit with
generation less than 5, at which point we know the want commit cannot be
an ancestor.

So if you have a history like:

    B
   /
  A--C--D--...--Z

and you want to know if "B" is in "Z", you will have to traverse all the
way from Z to A before realizing that B cannot be in it. That will have
the same complexity as finding a merge base (because the merge-base
would breadth-first traverse, looking at the highest age first, and
would therefore touch the same sequence of commits).

> The heuristics would work efficiently to check what tags point at a
> relatively recent commit (e.g. when trying to see which releases are
> affected and needing a fix by a recently discovered bug introduced by
> commit Y) by discarding tags for ancient releases. In such a scenario, the
> timestamp of a tagged and ancient commit X on a side branch that was never
> merged in the mainline that leads to commit Y (i.e. "want"), in an ideal
> world without clock skews, will be way older than the timestamp of commit
> Y. In other words, if you use timestamp as "age", even though X and Y do
> not relate to each other directly, except that they may share an ancient
> common ancestor, their "age"s can be compared and you could apply your
> heuristics to optimize.
> 
> But if you use the generation number as "age", even in an ideal world
> without clock skew nor miscomputed generation number, you no longer can
> compare "age" of X and Y.  The ancient side branch that led to X may have
> tons more commits than the history leading to Y.

Yes, there are cases where commit timestamps can save us some traversal
work over generation numbers. But I think there are also cases where the
reverse is true.

Your example is of a long side branch with very old commits. But you
could also have a short side branch with a very recent commit (think
recent bugfix forked from an old version). Then with commit timestamps
we need to go to the merge base to realize we are talking about
something very old. With a generation number, you can easily see that
the short branch's generation is very low.

Using both as a cutoff (if we assumed we had both, and that they were
both implicitly accurate) would let you optimize for either situation.
In practice, timestamps are either good enough that we don't need
generation numbers, or are considered to be strictly less accurate than
generation numbers.

So I think we will end up with one or the other. Of all of the
complaints I have seen over the use of timestamps for cutoffs, I don't
think performance of these corner cases has been an issue.

>    So how about marking commits (using the metainfo-cache facility) that
>    has an ancestor (not necessarily its direct parent) that records a
>    younger timestamp (e.g. 1 is such a commit, as its ancestors include
>    things like 2 and 4)? There should be relatively small number of them,
>    and still_interesting() logic can be told to dig through such commits
>    even if everybody is uninteresting in the active list.

You don't even need metainfo-cache for this. The number of commits is
very small, so the existing "notes-cache" is plenty fast. I even posted
a patch for this already:

  http://article.gmane.org/gmane.comp.version-control.git/176642

>  * As to "tag --contains", when timestamp based heuristics breaks down is
>    when a tagged commit incorrectly records way young timestamp or the
>    "want" commit records way old timetsamp. I haven't thought things
>    through, but the same metainfo-cache may be useful to detect which
>    commit to dig through ignoring the cutoff heuristics.

It can also break down if intermediate commits are wrong, because we
have to traverse backwards, and we may erroneously cutoff early.

For example:

   A--B--C

   timestamp(A) = 2
   timestamp(B) = 1 # skewed!
   timestamp(C) = 3

If tag=C and want=A, then we traverse backwards from C. We can't stop
immediately because we know that 2 < 3. But we go back to B, and see
that 2 > 1, and assume that A cannot possibly be an ancestor of B.

You can push through another N commits of slop (where N=1 would be fine
in this case). But you can always have a run of N+1 skewed commits (and
the higher N, the more time you are wasting). From earlier measurements
posted to the list, most repos have runs less than a dozen commits.
Linux-2.6 is actually the second highest of those measured, with a run
of 80. The mesa repo apparently has a run of 1520. See:

  http://article.gmane.org/gmane.comp.version-control.git/160163

and the surrounding thread (Jonathan did some measurements, too; he
didn't include a "longest run", but he does include "total number of
skewed commits", which obviously provides an upper bound on a run).

-Peff

Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

>>    So how about marking commits (using the metainfo-cache facility) that
>>    has an ancestor (not necessarily its direct parent) that records a
>>    younger timestamp (e.g. 1 is such a commit, as its ancestors include
>>    things like 2 and 4)? There should be relatively small number of them,
>>    and still_interesting() logic can be told to dig through such commits
>>    even if everybody is uninteresting in the active list.
> ...
>>  * As to "tag --contains", when timestamp based heuristics breaks down is
>>    when a tagged commit incorrectly records way young timestamp or the
>>    "want" commit records way old timetsamp. I haven't thought things
>>    through, but the same metainfo-cache may be useful to detect which
>>    commit to dig through ignoring the cutoff heuristics.
>
> It can also break down if intermediate commits are wrong, because we
> have to traverse backwards, and we may erroneously cutoff early.
>
> For example:
>
>    A--B--C
>
>    timestamp(A) = 2
>    timestamp(B) = 1 # skewed!
>    timestamp(C) = 3
>
> If tag=C and want=A, then we traverse backwards from C. We can't stop
> immediately because we know that 2 < 3. But we go back to B, and see
> that 2 > 1, and assume that A cannot possibly be an ancestor of B.

I envisioned that the metainfo-cache to help rev-list I mentioned earlier
would mark B having an ancestor A that has a timestamp younger than it, so
I think we can certainly notice that we have to "dig through" B.

Re: [RFC/PATCHv2 6/6] limit "contains" traversals based on commit generation

[Jeff King]

On Fri, Jul 15, 2011 at 02:04:06PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> >>    So how about marking commits (using the metainfo-cache facility) that
> >>    has an ancestor (not necessarily its direct parent) that records a
> >>    younger timestamp (e.g. 1 is such a commit, as its ancestors include
> >>    things like 2 and 4)? There should be relatively small number of them,
> >>    and still_interesting() logic can be told to dig through such commits
> >>    even if everybody is uninteresting in the active list.
> > ...
> >>  * As to "tag --contains", when timestamp based heuristics breaks down is
> >>    when a tagged commit incorrectly records way young timestamp or the
> >>    "want" commit records way old timetsamp. I haven't thought things
> >>    through, but the same metainfo-cache may be useful to detect which
> >>    commit to dig through ignoring the cutoff heuristics.
> >
> > It can also break down if intermediate commits are wrong, because we
> > have to traverse backwards, and we may erroneously cutoff early.
> >
> > For example:
> >
> >    A--B--C
> >
> >    timestamp(A) = 2
> >    timestamp(B) = 1 # skewed!
> >    timestamp(C) = 3
> >
> > If tag=C and want=A, then we traverse backwards from C. We can't stop
> > immediately because we know that 2 < 3. But we go back to B, and see
> > that 2 > 1, and assume that A cannot possibly be an ancestor of B.
> 
> I envisioned that the metainfo-cache to help rev-list I mentioned earlier
> would mark B having an ancestor A that has a timestamp younger than it, so
> I think we can certainly notice that we have to "dig through" B.

Right. I thought you were talking about the case where we did not have
such a cache. But given your response, did you mean:

  If we have such a cache, then the only thing left to worry about is
  when we specifically ask about a commit (either a tag or a "want"
  commit) that is skewed.

That I agree with.

-Peff

Generation numbers and replacement objects

[Jakub Narebski]

[Sorry for sending this email like this, but I forgot where
 I wanted to attach it to threads]

Peff, as Junio said somewhere else either in this thread, or the one
started by Linus, we would want generation numbers both without taking
into account replacement objects (e.g. for object traversal during
push / fetch), and with taking it into account (e.g. when showing log
or blame for end user).

So we would need two generation number caches: one with and one
without replaces.  Nb. generation header stored in commit object can
give only the one without replaces, i.e. speed up object enumeration
(what happened to caching GSoC project code?) but not git-log.

Also if replacement object has the same generation as the commit it
replaces, and I think also if it has lower generation number, current
generation numbers would still work (ne need to invalidate cache).

-- 
Jakub Narebski

Re: Generation numbers and replacement objects

[Jeff King]

On Fri, Jul 15, 2011 at 02:01:36PM -0700, Jakub Narebski wrote:

> Peff, as Junio said somewhere else either in this thread, or the one
> started by Linus, we would want generation numbers both without taking
> into account replacement objects (e.g. for object traversal during
> push / fetch), and with taking it into account (e.g. when showing log
> or blame for end user).
> 
> So we would need two generation number caches: one with and one
> without replaces.

Right. And I already outlined a solution for that by indexing the caches
by the validity token (I haven't written the patches yet, but it's a
pretty trivial change).

> Nb. generation header stored in commit object can give only the one
> without replaces, i.e. speed up object enumeration (what happened to
> caching GSoC project code?) but not git-log.

Yes. It is a weakness of putting the generation number in the header. I
think Linus has already said he doesn't care about grafting. You are
welcome to argue with him about that.

> Also if replacement object has the same generation as the commit it
> replaces, and I think also if it has lower generation number, current
> generation numbers would still work (ne need to invalidate cache).

Yes, that is why I said elsewhere "you could be more clever about seeing
how the cache's validity constraints changed". But ultimately, it is not
that expensive to regenerate the cache under the new conditions, grafts
don't change very often, and the code to figure out exactly which parts
of the cache could be saved would be complex.

-Peff

Re: Generation numbers and replacement objects

[Jakub Narebski]

On Fri, Jul 15, 2011, Jeff King wrote:
> On Fri, Jul 15, 2011 at 02:01:36PM -0700, Jakub Narebski wrote:
> 
> > Peff, as Junio said somewhere else either in this thread, or the one
> > started by Linus, we would want generation numbers both without taking
> > into account replacement objects (e.g. for object traversal during
> > push / fetch), and with taking it into account (e.g. when showing log
> > or blame for end user).
> > 
> > So we would need two generation number caches: one with and one
> > without replaces.
> 
> Right. And I already outlined a solution for that by indexing the caches
> by the validity token (I haven't written the patches yet, but it's a
> pretty trivial change).

Actually we wouldn't probably want a separate cache for each validity
token, but two caches: one with and one without... well, perhaps one per
namespace.  But certainly not one per replacement.
 
> > Nb. generation header stored in commit object can give only the one
> > without replaces, i.e. speed up object enumeration (what happened to
> > caching GSoC project code?) but not git-log.
> 
> Yes. It is a weakness of putting the generation number in the header. I
> think Linus has already said he doesn't care about grafting. You are
> welcome to argue with him about that.

I tried, but he isn't responding to questions about replacement objects.

I can agree that grafts are terrible hack, and for me turning off using
generation numbers if there are grafts is reasonable solution.  Not so
with replace objects.

> > Also if replacement object has the same generation as the commit it
> > replaces, and I think also if it has lower generation number, current
> > generation numbers would still work (ne need to invalidate cache).
> 
> Yes, that is why I said elsewhere "you could be more clever about seeing
> how the cache's validity constraints changed". But ultimately, it is not
> that expensive to regenerate the cache under the new conditions, grafts
> don't change very often, and the code to figure out exactly which parts
> of the cache could be saved would be complex.

True.  Well, at least taking hash of only replacements of commit objects
that change generation number could be a reasonable thing... but probably
too complicated anyway.

-- 
Jakub Narebski
Poland