Am 07.02.2014 21:56, schrieb Junio C Hamano:
> * kb/fast-hashmap (2014-01-03) 19 commits
>  - hashmap.h: make sure map entries are tightly packed
>   (merged to 'next' on 2014-01-03 at dc85001)
>  The tip one does not seem to have reached concensus (yet).

See discussion leading up to $gmane/239433.

I'd like to finish this up, so here are the options regarding the tip commit as 
I see them, ordered least risk to broadest compiler support:

1.) Drop the tip commit

Wastes 4 bytes of memory per entry on 64-bit platforms (still an improvement 
wrt memory, hash.[ch] wastes 4 bytes per bucket).
Works on all platforms.

2.) Keep the tip commit, i.e. "__attribute__(__packed__)"

Currently in pu at 036ad21.
Fixes the problem for 64-bit GCC only.
May fail on HP, all other platforms #define __attribute__ /* empty */

3.) Replace with the patch below, i.e. "#pragma pack"

Same as $gmane/239430 + $gmane/239433.
Should fix the problem for most compilers, with unit-test to make sure.
May fail on IRIX/MIPSPro (supposedly wants "#pragma pack(0)" to reset packing 
to default).

I don't know whether IRIX is still relevant (support ended Dec 2013). But if we 
fix this issue, I'd like to support as many platforms as possible, even though 
I can't test them all. The inline __attribute__ syntax is a dead end in that 
respect, so I'd suggest to go for #pragma pack (3). At the very least we 
shouldn't stall the rest of the patch series on a hunch that the last 
(unfortunately non-standard) patch may break on some legacy system.


Subject: [PATCH] hashmap.h: make sure map entries are tightly packed

Extending 'struct hashmap_entry' with an int-sized member shouldn't waste
memory on 64-bit systems. This is already documented in api-hashmap.txt,
but struct hashmap_entry needs to be packed for this to work. E.g.

 struct name_entry {
   struct hashmap_entry ent; /* consists of pointer + int */
   int namelen;
   char *name;

should be 24 instead of 32 bytes.

Packing structures is compiler-specific, most compilers support [1]:

 #pragma pack(n) - to set structure packing
 #pragma pack()  - to reset structure packing to default

Compilers are supposed to ignore unknown #pragmas, so using this without
further #if <compiler> guards should be safe.

Wasting a few bytes for padding is acceptable, however, compiling the rest
of git with packed structures (and thus mis-aligned arrays of structs) is
not. Add a test to ensure that '#pragma pack()' really resets the packing.

[1] Compiler docs regarding #pragma pack:

Supposedly wants #pragma pack(0) to reset:

Not supported:

Signed-off-by: Karsten Blees <>
 hashmap.h          |  7 +++++++
 t/ |  6 ++++++
 test-hashmap.c     | 17 +++++++++++++++++
 3 files changed, 30 insertions(+)

diff --git a/hashmap.h b/hashmap.h
index a816ad4..93b330b 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -15,10 +15,17 @@ extern unsigned int memihash(const void *buf, size_t len);
 /* data structures */
+ * Set struct packing to 4 so that we don't waste memory on 64-bit systems.
+ * Struct hashmap_entry is used as prefix to other (un-packed) structures,
+ * so this won't cause alignment issues e.g. for odd elements in an array.
+ */
+#pragma pack(4)
 struct hashmap_entry {
        struct hashmap_entry *next;
        unsigned int hash;
+#pragma pack()
 typedef int (*hashmap_cmp_fn)(const void *entry, const void *entry_or_key,
                const void *keydata);
diff --git a/t/ b/t/
index 391e2b6..3f3c90b 100755
--- a/t/
+++ b/t/
@@ -237,4 +237,10 @@ test_expect_success 'grow / shrink' '
+test_expect_success '"#pragma pack()" resets packing to default' '
+       test_hashmap "pragma-pack" "ok"
diff --git a/test-hashmap.c b/test-hashmap.c
index f5183fb..64bd9ec 100644
--- a/test-hashmap.c
+++ b/test-hashmap.c
@@ -36,6 +36,12 @@ static struct test_entry *alloc_test_entry(int hash, char 
*key, int klen,
        return entry;
+struct pointer_int
+       void *ptr;
+       int i;
 #define HASH_METHOD_FNV 0
 #define HASH_METHOD_I 1
 #define HASH_METHOD_IDIV10 2
@@ -136,6 +142,7 @@ static void perf_hashmap(unsigned int method, unsigned int 
  * remove key -> NULL / old value
  * iterate -> key1 value1\nkey2 value2\n...
  * size -> tablesize numentries
+ * pragma-pack -> ok / failure
  * perfhashmap method rounds -> test hashmap.[ch] performance
@@ -239,6 +246,16 @@ int main(int argc, char *argv[])
                        /* print table sizes */
                        printf("%u %u\n", map.tablesize, map.size);
+               } else if (!strcmp("pragma-pack", cmd)) {
+                       if ((sizeof(struct pointer_int) % sizeof(void *)) == 0)
+                               printf("ok\n");
+                       else
+                               printf("sizeof(pointer+int) (%u) is not a "
+                                      "multiple of sizeof(pointer) (%u)!\n",
+                                      (unsigned) sizeof(struct pointer_int),
+                                      (unsigned) sizeof(void *));
                } else if (!strcmp("perfhashmap", cmd) && l1 && l2) {
                        perf_hashmap(atoi(p1), atoi(p2));

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to
More majordomo info at

Reply via email to