{"thread":{"id":"37232","subject":"struct hashmap_entry packing","startedAt":"2014-07-28T17:17:44Z","lastAt":"2014-08-06T19:32:32Z","messageCount":12,"participants":["Jeff King","Karsten Blees","Vicent Martí","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"246806","messageId":"20140728171743.GA1927@peff.net","threadId":"37232","inReplyTo":null,"subject":"struct hashmap_entry packing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-28T17:17:44Z","receivedAt":"2014-07-28T17:17:44Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Hi Karsten,\n\nThe hashmap_entry documentation claims:\n\n  `struct hashmap_entry`::\n\n\tAn opaque structure representing an entry in the hash table,\n\twhich must be used as first member of user data structures.\n\tIdeally it should be followed by an int-sized member to prevent\n\tunused memory on 64-bit systems due to alignment.\n\nI'm not sure if the statement about alignment is true. If I have a\nstruct like:\n\n    struct magic {\n\t    struct hashmap_entry map;\n\t    int x;\n    };\n\nthe statement above implies that I should be able to fit this into only\n16 bytes on an LP64 system. But I can't convince gcc to do it. And I\nthink that makes sense, if you consider code like:\n\n   memset(&magic.map, 0, sizeof(struct hashmap_entry));\n\nThe sizeof() has to be the same regardless of whether the hashmap_entry\nis standalone or in another struct, and therefore must be padded up to\n16 bytes. If we stored \"x\" in that padding in the combined struct, it\nwould be overwritten by our memset.\n\nAm I missing anything? If this is the case, we should probably drop that\nbit from the documentation. It's possible that we could get around it by\nembedding the hashmap_entry elements directly into the parent struct,\nbut we would be counting on a reader dereferencing it as a hashmap_entry\nseeing the members at the exact same offset. I'd imagine that's one of\nthose things that holds most of the time, but is violating the standard.\nIt's probably not worth it to save a few bytes.\n\n-Peff\n"},{"id":"246944","messageId":"53D806AC.3070806@gmail.com","threadId":"37232","inReplyTo":"20140728171743.GA1927@peff.net","subject":"Re: struct hashmap_entry packing","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-07-29T20:40:12Z","receivedAt":"2014-07-29T20:40:12Z","isPatch":false,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 28.07.2014 19:17, schrieb Jeff King:\n> Hi Karsten,\n> \n> The hashmap_entry documentation claims:\n> \n>   `struct hashmap_entry`::\n> \n> \tAn opaque structure representing an entry in the hash table,\n> \twhich must be used as first member of user data structures.\n> \tIdeally it should be followed by an int-sized member to prevent\n> \tunused memory on 64-bit systems due to alignment.\n> \n> I'm not sure if the statement about alignment is true. If I have a\n> struct like:\n> \n>     struct magic {\n> \t    struct hashmap_entry map;\n> \t    int x;\n>     };\n> \n> the statement above implies that I should be able to fit this into only\n> 16 bytes on an LP64 system. But I can't convince gcc to do it. And I\n> think that makes sense, if you consider code like:\n> \n>    memset(&magic.map, 0, sizeof(struct hashmap_entry));\n> \n> The sizeof() has to be the same regardless of whether the hashmap_entry\n> is standalone or in another struct, and therefore must be padded up to\n> 16 bytes. If we stored \"x\" in that padding in the combined struct, it\n> would be overwritten by our memset.\n> \n\nThe struct-packing patch was ultimately dropped because there was no way\nto reliably make it work on all platforms. See [1] for discussion, [2] for\nthe final, 'most compatible' version.\n\n> Am I missing anything? If this is the case, we should probably drop that\n> bit from the documentation.\n\nHmmm. Now that we have \"__attribute__((packed))\" in pack-bitmap.h, perhaps\nwe should do the same for stuct hashmap_entry? (Which was the original\nproposal anyway...). Only works for GCC, but that should cover most builds\n/ platforms.\n\nBtw.: Using struct-packing on 'struct bitmap_disk_entry' means that the\nbinary format of .bitmap files is incompatible between GCC and other\nbuilds, correct?\n\n> It's possible that we could get around it by\n> embedding the hashmap_entry elements directly into the parent struct,\n\nAlready tried that, see [3].\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/239069\n[2] http://article.gmane.org/gmane.comp.version-control.git/241865\n[3] http://article.gmane.org/gmane.comp.version-control.git/239435\n"},{"id":"247152","messageId":"20140801223739.GA15649@peff.net","threadId":"37232","inReplyTo":"53D806AC.3070806@gmail.com","subject":"Re: struct hashmap_entry packing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-01T22:37:39Z","receivedAt":"2014-08-01T22:37:39Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 29, 2014 at 10:40:12PM +0200, Karsten Blees wrote:\n\n> > The sizeof() has to be the same regardless of whether the hashmap_entry\n> > is standalone or in another struct, and therefore must be padded up to\n> > 16 bytes. If we stored \"x\" in that padding in the combined struct, it\n> > would be overwritten by our memset.\n> > \n> \n> The struct-packing patch was ultimately dropped because there was no way\n> to reliably make it work on all platforms. See [1] for discussion, [2] for\n> the final, 'most compatible' version.\n\nThanks for the pointers; I should have guessed there was more to it and\nsearched the archive myself.\n\n> Hmmm. Now that we have \"__attribute__((packed))\" in pack-bitmap.h, perhaps\n> we should do the same for stuct hashmap_entry? (Which was the original\n> proposal anyway...). Only works for GCC, but that should cover most builds\n> / platforms.\n\nI don't see any reason to avoid the packed attribute, if it helps us. As\nyou noted, anything using __attribute__ probably supports it, and if\nnot, we can conditionally #define PACKED_STRUCT or something, like we do\nfor NORETURN. Since it's purely an optimization, if another compiler\ndoesn't use it, no big deal.\n\nThat being said, I don't know if those padding bytes are actually\ncausing a measurable slowdown. It may not even be worth the trouble.\n\n> Btw.: Using struct-packing on 'struct bitmap_disk_entry' means that the\n> binary format of .bitmap files is incompatible between GCC and other\n> builds, correct?\n\nThe on-disk format is defined by JGit; if there are differences between\nthe builds, that's a bug (and I would not be too surprised if there is\none, as bitmaps have gotten very extensive testing on 32- and 64-bit\ngcc, but probably not much elsewhere).\n\nWe do use structs to represent disk structures in other bits of the\npackfile code (e.g., struct pack_idx_header), but the struct is vanilla\nenough that we assume every compiler gives us two tightly-packed 32-bit\nintegers without having to bother with the \"packed\" attribute (and it\nseems to have worked in practice).\n\nWe should probably be more careful with that bitmap code. It looks like\nit wouldn't be too bad to drop it. I'll see if I can come up with a\npatch.\n\n-Peff\n"},{"id":"247155","messageId":"20140801231044.GA17960@peff.net","threadId":"37232","inReplyTo":"20140801223739.GA15649@peff.net","subject":"[PATCH] pack-bitmap: do not use gcc packed attribute","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-01T23:10:44Z","receivedAt":"2014-08-01T23:10:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 01, 2014 at 06:37:39PM -0400, Jeff King wrote:\n\n> > Btw.: Using struct-packing on 'struct bitmap_disk_entry' means that the\n> > binary format of .bitmap files is incompatible between GCC and other\n> > builds, correct?\n> \n> The on-disk format is defined by JGit; if there are differences between\n> the builds, that's a bug (and I would not be too surprised if there is\n> one, as bitmaps have gotten very extensive testing on 32- and 64-bit\n> gcc, but probably not much elsewhere).\n> \n> We do use structs to represent disk structures in other bits of the\n> packfile code (e.g., struct pack_idx_header), but the struct is vanilla\n> enough that we assume every compiler gives us two tightly-packed 32-bit\n> integers without having to bother with the \"packed\" attribute (and it\n> seems to have worked in practice).\n> \n> We should probably be more careful with that bitmap code. It looks like\n> it wouldn't be too bad to drop it. I'll see if I can come up with a\n> patch.\n\nI confirmed that this does break horribly without the packed attribute\n(as you'd expect; it's asking for 48-bit alignment!). p5310 notices it,\n_if_ you have jgit installed to check against.\n\nHere's a fix.\n\n-- >8 --\nSubject: pack-bitmap: do not use gcc packed attribute\n\nThe \"__attribute__\" flag may be a noop on some compilers.\nThat's OK as long as the code is correct without the\nattribute, but in this case it is not. We would typically\nend up with a struct that is 2 bytes too long due to struct\npadding, breaking both reading and writing of bitmaps.\n\nWe can work around this by using an array of unsigned char\nto represent the data, and relying on get/put_be32 to handle\nalignment issues as we interact with the array.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThe accessors may be overkill; each function is called only a single\ntime in the whole codebase. But doing it this way rather than accessing\nentry[4] inline at least puts the magic constants all in one place.\n\n pack-bitmap-write.c | 10 ++++------\n pack-bitmap.c       | 12 ++++++------\n pack-bitmap.h       | 42 +++++++++++++++++++++++++++++++++++++-----\n 3 files changed, 47 insertions(+), 17 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 5f1791a..f885a7a 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -473,7 +473,7 @@ static void write_selected_commits_v1(struct sha1file *f,\n \n \tfor (i = 0; i < writer.selected_nr; ++i) {\n \t\tstruct bitmapped_commit *stored = &writer.selected[i];\n-\t\tstruct bitmap_disk_entry on_disk;\n+\t\tunsigned char on_disk[BITMAP_DISK_ENTRY_LEN];\n \n \t\tint commit_pos =\n \t\t\tsha1_pos(stored->commit->object.sha1, index, index_nr, sha1_access);\n@@ -481,11 +481,9 @@ static void write_selected_commits_v1(struct sha1file *f,\n \t\tif (commit_pos < 0)\n \t\t\tdie(\"BUG: trying to write commit not in index\");\n \n-\t\ton_disk.object_pos = htonl(commit_pos);\n-\t\ton_disk.xor_offset = stored->xor_offset;\n-\t\ton_disk.flags = stored->flags;\n-\n-\t\tsha1write(f, &on_disk, sizeof(on_disk));\n+\t\tbitmap_disk_entry_create(on_disk, commit_pos,\n+\t\t\t\t\t stored->xor_offset, stored->flags);\n+\t\tsha1write(f, on_disk, sizeof(on_disk));\n \t\tdump_bitmap(f, stored->write_as);\n \t}\n }\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 91e4101..1b2a473 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -203,7 +203,7 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)\n \n \tuint32_t i;\n \tstruct stored_bitmap **recent_bitmaps;\n-\tstruct bitmap_disk_entry *entry;\n+\tunsigned char *entry;\n \n \trecent_bitmaps = xcalloc(MAX_XOR_OFFSET, sizeof(struct stored_bitmap));\n \n@@ -214,14 +214,14 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)\n \t\tuint32_t commit_idx_pos;\n \t\tconst unsigned char *sha1;\n \n-\t\tentry = (struct bitmap_disk_entry *)(index->map + index->map_pos);\n-\t\tindex->map_pos += sizeof(struct bitmap_disk_entry);\n+\t\tentry = index->map + index->map_pos;\n+\t\tindex->map_pos += BITMAP_DISK_ENTRY_LEN;\n \n-\t\tcommit_idx_pos = ntohl(entry->object_pos);\n+\t\tcommit_idx_pos = bitmap_disk_entry_object_pos(entry);\n \t\tsha1 = nth_packed_object_sha1(index->pack, commit_idx_pos);\n \n-\t\txor_offset = (int)entry->xor_offset;\n-\t\tflags = (int)entry->flags;\n+\t\txor_offset = (int)bitmap_disk_entry_xor_offset(entry);\n+\t\tflags = (int)bitmap_disk_entry_flags(entry);\n \n \t\tbitmap = read_bitmap_1(index);\n \t\tif (!bitmap)\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 8b7f4e9..0d57706 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -5,11 +5,43 @@\n #include \"khash.h\"\n #include \"pack-objects.h\"\n \n-struct bitmap_disk_entry {\n-\tuint32_t object_pos;\n-\tuint8_t xor_offset;\n-\tuint8_t flags;\n-} __attribute__((packed));\n+/*\n+ * This is the equivalent of:\n+ *\n+ *\tuint32_t object_pos;\n+ *\tuint8_t xor_offset;\n+ *\tuint8_t flags;\n+ *\n+ * but due to the funny sizing, we cannot rely on the compiler to give us the\n+ * exact struct packing we want. So let's treat it as an array and just provide\n+ * a few helpers for accessing the components.\n+ */\n+#define BITMAP_DISK_ENTRY_LEN 6\n+\n+static inline void bitmap_disk_entry_create(unsigned char *on_disk,\n+\t\t\t\t\t    uint32_t object_pos,\n+\t\t\t\t\t    uint8_t xor_offset,\n+\t\t\t\t\t    uint8_t flags)\n+{\n+\tput_be32(on_disk, object_pos);\n+\ton_disk[4] = xor_offset;\n+\ton_disk[5] = flags;\n+}\n+\n+static inline uint32_t bitmap_disk_entry_object_pos(unsigned char *on_disk)\n+{\n+\treturn get_be32(on_disk);\n+}\n+\n+static inline uint8_t bitmap_disk_entry_xor_offset(unsigned char *on_disk)\n+{\n+\treturn on_disk[4];\n+}\n+\n+static inline uint8_t bitmap_disk_entry_flags(unsigned char *on_disk)\n+{\n+\treturn on_disk[5];\n+}\n \n struct bitmap_disk_header {\n \tchar magic[4];\n-- \n2.1.0.rc0.286.g5c67d74\n"},{"id":"247156","messageId":"20140801231217.GB17960@peff.net","threadId":"37232","inReplyTo":"20140801231044.GA17960@peff.net","subject":"Re: [PATCH] pack-bitmap: do not use gcc packed attribute","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-01T23:12:17Z","receivedAt":"2014-08-01T23:12:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 01, 2014 at 07:10:44PM -0400, Jeff King wrote:\n\n> I confirmed that this does break horribly without the packed attribute\n> (as you'd expect; it's asking for 48-bit alignment!). p5310 notices it,\n> _if_ you have jgit installed to check against.\n\nEr, that should be t5310, of course. p5310 is the perf test, which does\nnot notice the problem. :)\n\n-Peff\n"},{"id":"247239","messageId":"53DFDCD2.2090803@gmail.com","threadId":"37232","inReplyTo":"20140801231044.GA17960@peff.net","subject":"Re: [PATCH] pack-bitmap: do not use gcc packed attribute","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-08-04T19:19:46Z","receivedAt":"2014-08-04T19:19:46Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 02.08.2014 01:10, schrieb Jeff King:\n> On Fri, Aug 01, 2014 at 06:37:39PM -0400, Jeff King wrote:\n> \n>>> Btw.: Using struct-packing on 'struct bitmap_disk_entry' means that the\n>>> binary format of .bitmap files is incompatible between GCC and other\n>>> builds, correct?\n>>\n>> The on-disk format is defined by JGit; if there are differences between\n>> the builds, that's a bug (and I would not be too surprised if there is\n>> one, as bitmaps have gotten very extensive testing on 32- and 64-bit\n>> gcc, but probably not much elsewhere).\n>>\n>> We do use structs to represent disk structures in other bits of the\n>> packfile code (e.g., struct pack_idx_header), but the struct is vanilla\n>> enough that we assume every compiler gives us two tightly-packed 32-bit\n>> integers without having to bother with the \"packed\" attribute (and it\n>> seems to have worked in practice).\n>>\n>> We should probably be more careful with that bitmap code. It looks like\n>> it wouldn't be too bad to drop it. I'll see if I can come up with a\n>> patch.\n> \n> I confirmed that this does break horribly without the packed attribute\n> (as you'd expect; it's asking for 48-bit alignment!). p5310 notices it,\n> _if_ you have jgit installed to check against.\n> \n> Here's a fix.\n> \n> Subject: pack-bitmap: do not use gcc packed attribute\n> \n> The \"__attribute__\" flag may be a noop on some compilers.\n> That's OK as long as the code is correct without the\n> attribute, but in this case it is not. We would typically\n> end up with a struct that is 2 bytes too long due to struct\n> padding, breaking both reading and writing of bitmaps.\n> \n> We can work around this by using an array of unsigned char\n> to represent the data, and relying on get/put_be32 to handle\n> alignment issues as we interact with the array.\n> \n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> The accessors may be overkill; each function is called only a single\n> time in the whole codebase. But doing it this way rather than accessing\n> entry[4] inline at least puts the magic constants all in one place.\n> \n[...]\n\nHmm, I wonder if it wouldn't be simpler to read / write the desired on-disk\nstructure directly, without copying to a uchar[6] first.\n\nWhen writing, sha1write already buffers the data, so calling this with 4/1/1\nbytes of payload shouldn't affect performance.\n\nSimilarly for reading - we already have a function to read a bitmap and\nadvance the 'file' position, why not have similar functions to read uint8/32\nin a stream-based fashion?\n\nThis raises the question why we read via mmap at all (without munmap()ing the\nfile when done...). We copy all data into internal data structures anyway. Is\nan fopen/fread-based solution (with fread_u8/_u32 helpers) that much slower?\n\n\nHere's what I came up with (just a sketch, commit message is lacky and the\nhelper functions deserve a better place / name):\n\n----8<-----\nSubject: [PATCH] pack-bitmap: do not use packed structs to read / write bitmap\n files\n\nSigned-off-by: Karsten Blees <blees@dcon.de>\n---\n pack-bitmap-write.c | 18 +++++++++++++-----\n pack-bitmap.c       | 21 ++++++++++++++-------\n pack-bitmap.h       |  6 ------\n 3 files changed, 27 insertions(+), 18 deletions(-)\n\ndiff --git a/pack-bitmap-write.c b/pack-bitmap-write.c\nindex 5f1791a..01995cb 100644\n--- a/pack-bitmap-write.c\n+++ b/pack-bitmap-write.c\n@@ -465,6 +465,16 @@ static const unsigned char *sha1_access(size_t pos, void *table)\n \treturn index[pos]->sha1;\n }\n \n+static inline void sha1write_u8(struct sha1file *f, uint8_t data)\n+{\n+\tsha1write(f, &data, sizeof(data));\n+}\n+static inline void sha1write_u32(struct sha1file *f, uint32_t data)\n+{\n+\tdata = htonl(data);\n+\tsha1write(f, &data, sizeof(data));\n+}\n+\n static void write_selected_commits_v1(struct sha1file *f,\n \t\t\t\t      struct pack_idx_entry **index,\n \t\t\t\t      uint32_t index_nr)\n@@ -473,7 +483,6 @@ static void write_selected_commits_v1(struct sha1file *f,\n \n \tfor (i = 0; i < writer.selected_nr; ++i) {\n \t\tstruct bitmapped_commit *stored = &writer.selected[i];\n-\t\tstruct bitmap_disk_entry on_disk;\n \n \t\tint commit_pos =\n \t\t\tsha1_pos(stored->commit->object.sha1, index, index_nr, sha1_access);\n@@ -481,11 +490,10 @@ static void write_selected_commits_v1(struct sha1file *f,\n \t\tif (commit_pos < 0)\n \t\t\tdie(\"BUG: trying to write commit not in index\");\n \n-\t\ton_disk.object_pos = htonl(commit_pos);\n-\t\ton_disk.xor_offset = stored->xor_offset;\n-\t\ton_disk.flags = stored->flags;\n+\t\tsha1write_u32(f, commit_pos);\n+\t\tsha1write_u8(f, stored->xor_offset);\n+\t\tsha1write_u8(f, stored->flags);\n \n-\t\tsha1write(f, &on_disk, sizeof(on_disk));\n \t\tdump_bitmap(f, stored->write_as);\n \t}\n }\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 91e4101..cb1b2dd 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -197,13 +197,23 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,\n \treturn stored;\n }\n \n+static inline uint32_t read_u32(const unsigned char *buffer, size_t *pos)\n+{\n+\tuint32_t result = get_be32(buffer + *pos);\n+\t(*pos) += sizeof(result);\n+\treturn result;\n+}\n+static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)\n+{\n+\treturn buffer[(*pos)++];\n+}\n+\n static int load_bitmap_entries_v1(struct bitmap_index *index)\n {\n \tstatic const size_t MAX_XOR_OFFSET = 160;\n \n \tuint32_t i;\n \tstruct stored_bitmap **recent_bitmaps;\n-\tstruct bitmap_disk_entry *entry;\n \n \trecent_bitmaps = xcalloc(MAX_XOR_OFFSET, sizeof(struct stored_bitmap));\n \n@@ -214,15 +224,12 @@ static int load_bitmap_entries_v1(struct bitmap_index *index)\n \t\tuint32_t commit_idx_pos;\n \t\tconst unsigned char *sha1;\n \n-\t\tentry = (struct bitmap_disk_entry *)(index->map + index->map_pos);\n-\t\tindex->map_pos += sizeof(struct bitmap_disk_entry);\n+\t\tcommit_idx_pos = read_u32(index->map, &index->map_pos);\n+\t\txor_offset = (int) read_u8(index->map, &index->map_pos);\n+\t\tflags = (int) read_u8(index->map, &index->map_pos);\n \n-\t\tcommit_idx_pos = ntohl(entry->object_pos);\n \t\tsha1 = nth_packed_object_sha1(index->pack, commit_idx_pos);\n \n-\t\txor_offset = (int)entry->xor_offset;\n-\t\tflags = (int)entry->flags;\n-\n \t\tbitmap = read_bitmap_1(index);\n \t\tif (!bitmap)\n \t\t\treturn -1;\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 8b7f4e9..487600b 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -5,12 +5,6 @@\n #include \"khash.h\"\n #include \"pack-objects.h\"\n \n-struct bitmap_disk_entry {\n-\tuint32_t object_pos;\n-\tuint8_t xor_offset;\n-\tuint8_t flags;\n-} __attribute__((packed));\n-\n struct bitmap_disk_header {\n \tchar magic[4];\n \tuint16_t version;\n-- \n2.0.3.920.g16a4828.dirty\n"},{"id":"247240","messageId":"53DFDCE2.9060406@gmail.com","threadId":"37232","inReplyTo":"20140801223739.GA15649@peff.net","subject":"Re: struct hashmap_entry packing","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-08-04T19:20:02Z","receivedAt":"2014-08-04T19:20:02Z","isPatch":false,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 02.08.2014 00:37, schrieb Jeff King:\n> On Tue, Jul 29, 2014 at 10:40:12PM +0200, Karsten Blees wrote:\n> \n>>> The sizeof() has to be the same regardless of whether the hashmap_entry\n>>> is standalone or in another struct, and therefore must be padded up to\n>>> 16 bytes. If we stored \"x\" in that padding in the combined struct, it\n>>> would be overwritten by our memset.\n>>>\n>>\n>> The struct-packing patch was ultimately dropped because there was no way\n>> to reliably make it work on all platforms. See [1] for discussion, [2] for\n>> the final, 'most compatible' version.\n> \n> Thanks for the pointers; I should have guessed there was more to it and\n> searched the archive myself.\n> \n>> Hmmm. Now that we have \"__attribute__((packed))\" in pack-bitmap.h, perhaps\n>> we should do the same for stuct hashmap_entry? (Which was the original\n>> proposal anyway...). Only works for GCC, but that should cover most builds\n>> / platforms.\n> \n> I don't see any reason to avoid the packed attribute, if it helps us. As\n> you noted, anything using __attribute__ probably supports it, and if\n> not, we can conditionally #define PACKED_STRUCT or something, like we do\n> for NORETURN. Since it's purely an optimization, if another compiler\n> doesn't use it, no big deal.\n> \n> That being said, I don't know if those padding bytes are actually\n> causing a measurable slowdown. It may not even be worth the trouble.\n> \n\nIts not about performance (or correctness, in case of platforms that don't\nsupport unaligned read), just about saving memory (e.g. mapping int to int\nrequires 24 bytes per entry, vs. 16 with packed structs).\n\nThe padding at the end of a structure is only needed for proper alignment in\narrays. Struct hashmap_entry is always used as prefix of some other structure,\nnever as an array, so there are no alignment issues here.\n\nTypical memory layouts on 64-bit platforms are as follows (note that even in\nthe 'followed by int64' case, all members are properly aligned):\n\n\nUnpacked struct followed by int32 - wastes 1/3 of memory:\n\n      struct {\n        struct hashmap_entry {\n00-07     struct hashmap_entry *next;\n08-11     int hash;\n12-15     // padding\n        } ent;\n16-19   int32_t value;\n20-23   // padding\n      }\n\n\nPacked struct followed by int32:\n\n      struct {\n        struct hashmap_entry {\n00-07     struct hashmap_entry *next;\n08-11     int hash;\n        } ent;\n12-15   int32_t value;\n      }\n\n\nPacked struct followed by int64:\n\n      struct {\n        struct hashmap_entry {\n00-07     struct hashmap_entry *next;\n08-11     int hash;\n        } ent;\n12-15   // padding\n16-23   int64_t value;\n      }\n\n\nArray of packed struct (not used):\n\n      struct hashmap_entry {\n00-07   struct hashmap_entry *next;\n08-11   int hash;\n      }; // [0]\n      struct hashmap_entry {\n12-19   struct hashmap_entry *next; // !!!unaligned!!!\n20-23   int hash;\n      }; // [1]\n"},{"id":"247285","messageId":"CAFFjANRwnd4u1Axs64xZNvc1kHynjswX_t4pS3EjBsTsZP0Y7w@mail.gmail.com","threadId":"37232","inReplyTo":"53DFDCD2.2090803@gmail.com","subject":"Re: [PATCH] pack-bitmap: do not use gcc packed attribute","fromName":"Vicent Martí","fromEmail":"tanoku@gmail.com","sentAt":"2014-08-05T18:38:21Z","receivedAt":"2014-08-05T18:38:21Z","isPatch":true,"sender":{"key":"tanoku@gmail.com","avatar":"https://gravatar.com/avatar/271386991cb4c2b8f1e1ed1d059f3422cc3485de7a598f65043f70be021d095b?d=mp&s=160"},"body":"On Mon, Aug 4, 2014 at 9:19 PM, Karsten Blees <karsten.blees@gmail.com> wrote:\n> This raises the question why we read via mmap at all\n\nThe first version of the pack bitmap format I wrote for GitHub was 50%\nfaster to load than this one because it was designed to be mmapable.\nEventually we moved to the JGit-compatible bitmap format (because I\nget paid a lot of money to do as I'm told -- not because of some\ninherent benefit of the JGit format), which needs to be read\nsequentially, but I never bothered to change the mmap reading code.\n\nI believe your patch makes a lot of sense -- at this point we could as\nwell remove the mmaping altogether and read the file sequentially.\n\nCheers,\nvmg\n"},{"id":"247287","messageId":"20140805184724.GA10369@peff.net","threadId":"37232","inReplyTo":"53DFDCD2.2090803@gmail.com","subject":"Re: [PATCH] pack-bitmap: do not use gcc packed attribute","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-05T18:47:24Z","receivedAt":"2014-08-05T18:47:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 04, 2014 at 09:19:46PM +0200, Karsten Blees wrote:\n\n> Hmm, I wonder if it wouldn't be simpler to read / write the desired on-disk\n> structure directly, without copying to a uchar[6] first.\n\nProbably. My initial attempt was to keep together the read/write logic\nabout which sizes each item is, but I think the result ended up\nunnecessarily verbose and harder to follow.\n\n> Here's what I came up with (just a sketch, commit message is lacky and the\n> helper functions deserve a better place / name):\n\nI like it. Want to clean it up and submit in place of mine?\n\n-Peff\n"},{"id":"247288","messageId":"20140805185137.GB10369@peff.net","threadId":"37232","inReplyTo":"53DFDCE2.9060406@gmail.com","subject":"Re: struct hashmap_entry packing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-08-05T18:51:37Z","receivedAt":"2014-08-05T18:51:37Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 04, 2014 at 09:20:02PM +0200, Karsten Blees wrote:\n\n> > I don't see any reason to avoid the packed attribute, if it helps us. As\n> > you noted, anything using __attribute__ probably supports it, and if\n> > not, we can conditionally #define PACKED_STRUCT or something, like we do\n> > for NORETURN. Since it's purely an optimization, if another compiler\n> > doesn't use it, no big deal.\n> > \n> > That being said, I don't know if those padding bytes are actually\n> > causing a measurable slowdown. It may not even be worth the trouble.\n> > \n> \n> Its not about performance (or correctness, in case of platforms that don't\n> support unaligned read), just about saving memory (e.g. mapping int to int\n> requires 24 bytes per entry, vs. 16 with packed structs).\n\nThe biggest things we might map are probably one entry per-object. So in\na repository like linux.git, we're talking about 32MB in the worst case.\nThat's not nothing, but it's also not the end of the world. I'd be more\nconcerned with how that trashes the cache (and consequently causes\nslowdown) than somebody running out of memory.\n\nSo my general opinion is that if it's easy to get the space back, great.\nBut if it creates a maintenance hassle, it's not worth the effort.\n\nThat said, I really don't think it would be much maintenance hassle to\nmark the hashmap_entry as packed, and compilers can either handle it or\nnot.\n\n-Peff\n"},{"id":"247355","messageId":"53E27ADC.4070501@gmail.com","threadId":"37232","inReplyTo":"20140805184724.GA10369@peff.net","subject":"Re: [PATCH] pack-bitmap: do not use gcc packed attribute","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2014-08-06T18:58:36Z","receivedAt":"2014-08-06T18:58:36Z","isPatch":true,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 05.08.2014 20:47, schrieb Jeff King:\n> On Mon, Aug 04, 2014 at 09:19:46PM +0200, Karsten Blees wrote:\n> \n>> Hmm, I wonder if it wouldn't be simpler to read / write the desired on-disk\n>> structure directly, without copying to a uchar[6] first.\n> \n> Probably. My initial attempt was to keep together the read/write logic\n> about which sizes each item is, but I think the result ended up\n> unnecessarily verbose and harder to follow.\n> \n\nYeah, having read / write logic in different files is confusing, esp. when\nnot using structs to define the file format.\n\n>> Here's what I came up with (just a sketch, commit message is lacky and the\n>> helper functions deserve a better place / name):\n> \n> I like it. Want to clean it up and submit in place of mine?\n> \n\nWill do, but it will have to wait till next week.\n\n> -Peff\n> \n"},{"id":"247357","messageId":"xmqqd2cdmn1r.fsf@gitster.dls.corp.google.com","threadId":"37232","inReplyTo":"53E27ADC.4070501@gmail.com","subject":"Re: [PATCH] pack-bitmap: do not use gcc packed attribute","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-08-06T19:32:32Z","receivedAt":"2014-08-06T19:32:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Karsten Blees <karsten.blees@gmail.com> writes:\n\n> Am 05.08.2014 20:47, schrieb Jeff King:\n>> On Mon, Aug 04, 2014 at 09:19:46PM +0200, Karsten Blees wrote:\n>> \n>>> Hmm, I wonder if it wouldn't be simpler to read / write the desired on-disk\n>>> structure directly, without copying to a uchar[6] first.\n>> \n>> Probably. My initial attempt was to keep together the read/write logic\n>> about which sizes each item is, but I think the result ended up\n>> unnecessarily verbose and harder to follow.\n>> \n>\n> Yeah, having read / write logic in different files is confusing, esp. when\n> not using structs to define the file format.\n>\n>>> Here's what I came up with (just a sketch, commit message is lacky and the\n>>> helper functions deserve a better place / name):\n>> \n>> I like it. Want to clean it up and submit in place of mine?\n>> \n>\n> Will do, but it will have to wait till next week.\n\nThanks, both.\n"}]}