git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Jonathan Nieder <jrnieder@gmail.com>
Date
Jul 13, 2011, 17:52 UTC
Message-ID
<20110713175250.GA1448@elie>
In-Reply-To
<20110713065700.GA18566@sigill.intra.peff.net>

(+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.
Show 8 quoted lines
> --- 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.
Show 9 quoted lines
> +`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...

[...]
Show 12 quoted lines
> +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.
Show 11 quoted lines
> @@ -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.

Show 13 quoted lines
> --- 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?
Show 8 quoted lines
>  	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?

[...]
Show 24 quoted lines
>  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)
[...]
Show 11 quoted lines
>  /* 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:
Show 14 quoted lines
> +
> +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.
Show 9 quoted lines
> --- 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.
Show 9 quoted lines
>  	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;
>  };
[...]
Show 6 quoted lines
> +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

Previous: Jeff KingNext: Jeff King
Message 3 of 57 in “[RFC/PATCHv2 0/6] generation numbers for faster traversals”
  1. Jeff KingJul 13, 2011
  2. 1/6 decorate: allow storing values instead of pointersJeff King, Jul 13, 2011
  3. Jonathan NiederJul 13, 2011
  4. Jeff KingJul 13, 2011
  5. Jeff KingJul 14, 2011
  6. 1/3 implement generic key/value mapJeff King, Jul 14, 2011
  7. Bert WesargJul 14, 2011
  8. Bert WesargJul 14, 2011
  9. Jeff KingJul 14, 2011
  10. Bert WesargJul 14, 2011
  11. Jeff KingJul 14, 2011
  12. Bert WesargJul 14, 2011
  13. 2/3 fast-export: use object to uint32 map instead of "decorate"Jeff King, Jul 14, 2011
  14. Sverre RabbelierJul 15, 2011
  15. Jeff KingJul 15, 2011
  16. 3/3 decorate: use "map" for the underlying implementationJeff King, Jul 14, 2011
  17. Junio C HamanoJul 14, 2011
  18. 0/5 macro-based key/value mapsJeff King, Aug 4, 2011
  19. 1/5 implement generic key/value mapJeff King, Aug 4, 2011
  20. 2/5 fast-export: use object to uint32 map instead of "decorate"Jeff King, Aug 4, 2011
  21. 3/5 decorate: use "map" for the underlying implementationJeff King, Aug 4, 2011
  22. 4/5 map: implement persistent mapsJeff King, Aug 4, 2011
  23. 5/5 implement metadata cache subsystemJeff King, Aug 4, 2011
  24. 0/2 patch-id cachingJeff King, Aug 4, 2011
  25. 1/2 cherry: read default configJeff King, Aug 4, 2011
  26. 2/2 cache patch ids on diskJeff King, Aug 4, 2011
  27. Jeff KingAug 4, 2011
  28. Jeff KingAug 5, 2011
  29. René ScharfeAug 5, 2011
  30. Jeff KingAug 6, 2011
  31. 2/6 add metadata-cache infrastructureJeff King, Jul 13, 2011
  32. Bert WesargJul 13, 2011
  33. Jeff KingJul 13, 2011
  34. Bert WesargJul 13, 2011
  35. Jeff KingJul 13, 2011
  36. Junio C HamanoJul 13, 2011
  37. Junio C HamanoJul 13, 2011
  38. Jeff KingJul 13, 2011
  39. 3/6 commit: add commit_generation functionJeff King, Jul 13, 2011
  40. Eric SunshineJul 13, 2011
  41. 4/6 pretty: support %G to show the generation number of a commitJeff King, Jul 13, 2011
  42. 5/6 check commit generation cache validity against graftsJeff King, Jul 13, 2011
  43. Eric SunshineJul 13, 2011
  44. Jeff KingJul 13, 2011
  45. 6/6 limit "contains" traversals based on commit generationJeff King, Jul 13, 2011
  46. Jeff KingJul 13, 2011
  47. Junio C HamanoJul 13, 2011
  48. Jeff KingJul 13, 2011
  49. Junio C HamanoJul 13, 2011
  50. Jeff KingJul 13, 2011
  51. Junio C HamanoJul 15, 2011
  52. Jeff KingJul 15, 2011
  53. Junio C HamanoJul 15, 2011
  54. Jeff KingJul 15, 2011
  55. Generation numbers and replacement objectsJakub Narebski, Jul 15, 2011
  56. Jeff KingJul 15, 2011
  57. Jakub NarebskiJul 16, 2011

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.