Re: struct hashmap_entry packing
On Mon, Aug 04, 2014 at 09:20:02PM +0200, Karsten Blees wrote: I don't see any reason to avoid the packed attribute, if it helps us. As you noted, anything using __attribute__ probably supports it, and if not, we can conditionally #define PACKED_STRUCT or something, like we do for NORETURN. Since it's purely an optimization, if another compiler doesn't use it, no big deal. That being said, I don't know if those padding bytes are actually causing a measurable slowdown. It may not even be worth the trouble. Its not about performance (or correctness, in case of platforms that don't support unaligned read), just about saving memory (e.g. mapping int to int requires 24 bytes per entry, vs. 16 with packed structs). The biggest things we might map are probably one entry per-object. So in a repository like linux.git, we're talking about 32MB in the worst case. That's not nothing, but it's also not the end of the world. I'd be more concerned with how that trashes the cache (and consequently causes slowdown) than somebody running out of memory. So my general opinion is that if it's easy to get the space back, great. But if it creates a maintenance hassle, it's not worth the effort. That said, I really don't think it would be much maintenance hassle to mark the hashmap_entry as packed, and compilers can either handle it or not. -Peff -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: struct hashmap_entry packing
Am 02.08.2014 00:37, schrieb Jeff King:
On Tue, Jul 29, 2014 at 10:40:12PM +0200, Karsten Blees wrote:
The sizeof() has to be the same regardless of whether the hashmap_entry
is standalone or in another struct, and therefore must be padded up to
16 bytes. If we stored x in that padding in the combined struct, it
would be overwritten by our memset.
The struct-packing patch was ultimately dropped because there was no way
to reliably make it work on all platforms. See [1] for discussion, [2] for
the final, 'most compatible' version.
Thanks for the pointers; I should have guessed there was more to it and
searched the archive myself.
Hmmm. Now that we have __attribute__((packed)) in pack-bitmap.h, perhaps
we should do the same for stuct hashmap_entry? (Which was the original
proposal anyway...). Only works for GCC, but that should cover most builds
/ platforms.
I don't see any reason to avoid the packed attribute, if it helps us. As
you noted, anything using __attribute__ probably supports it, and if
not, we can conditionally #define PACKED_STRUCT or something, like we do
for NORETURN. Since it's purely an optimization, if another compiler
doesn't use it, no big deal.
That being said, I don't know if those padding bytes are actually
causing a measurable slowdown. It may not even be worth the trouble.
Its not about performance (or correctness, in case of platforms that don't
support unaligned read), just about saving memory (e.g. mapping int to int
requires 24 bytes per entry, vs. 16 with packed structs).
The padding at the end of a structure is only needed for proper alignment in
arrays. Struct hashmap_entry is always used as prefix of some other structure,
never as an array, so there are no alignment issues here.
Typical memory layouts on 64-bit platforms are as follows (note that even in
the 'followed by int64' case, all members are properly aligned):
Unpacked struct followed by int32 - wastes 1/3 of memory:
struct {
struct hashmap_entry {
00-07 struct hashmap_entry *next;
08-11 int hash;
12-15 // padding
} ent;
16-19 int32_t value;
20-23 // padding
}
Packed struct followed by int32:
struct {
struct hashmap_entry {
00-07 struct hashmap_entry *next;
08-11 int hash;
} ent;
12-15 int32_t value;
}
Packed struct followed by int64:
struct {
struct hashmap_entry {
00-07 struct hashmap_entry *next;
08-11 int hash;
} ent;
12-15 // padding
16-23 int64_t value;
}
Array of packed struct (not used):
struct hashmap_entry {
00-07 struct hashmap_entry *next;
08-11 int hash;
}; // [0]
struct hashmap_entry {
12-19 struct hashmap_entry *next; // !!!unaligned!!!
20-23 int hash;
}; // [1]
--
To unsubscribe from this list: send the line unsubscribe git in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: struct hashmap_entry packing
On Tue, Jul 29, 2014 at 10:40:12PM +0200, Karsten Blees wrote: The sizeof() has to be the same regardless of whether the hashmap_entry is standalone or in another struct, and therefore must be padded up to 16 bytes. If we stored x in that padding in the combined struct, it would be overwritten by our memset. The struct-packing patch was ultimately dropped because there was no way to reliably make it work on all platforms. See [1] for discussion, [2] for the final, 'most compatible' version. Thanks for the pointers; I should have guessed there was more to it and searched the archive myself. Hmmm. Now that we have __attribute__((packed)) in pack-bitmap.h, perhaps we should do the same for stuct hashmap_entry? (Which was the original proposal anyway...). Only works for GCC, but that should cover most builds / platforms. I don't see any reason to avoid the packed attribute, if it helps us. As you noted, anything using __attribute__ probably supports it, and if not, we can conditionally #define PACKED_STRUCT or something, like we do for NORETURN. Since it's purely an optimization, if another compiler doesn't use it, no big deal. That being said, I don't know if those padding bytes are actually causing a measurable slowdown. It may not even be worth the trouble. Btw.: Using struct-packing on 'struct bitmap_disk_entry' means that the binary format of .bitmap files is incompatible between GCC and other builds, correct? The on-disk format is defined by JGit; if there are differences between the builds, that's a bug (and I would not be too surprised if there is one, as bitmaps have gotten very extensive testing on 32- and 64-bit gcc, but probably not much elsewhere). We do use structs to represent disk structures in other bits of the packfile code (e.g., struct pack_idx_header), but the struct is vanilla enough that we assume every compiler gives us two tightly-packed 32-bit integers without having to bother with the packed attribute (and it seems to have worked in practice). We should probably be more careful with that bitmap code. It looks like it wouldn't be too bad to drop it. I'll see if I can come up with a patch. -Peff -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: struct hashmap_entry packing
Am 28.07.2014 19:17, schrieb Jeff King:
Hi Karsten,
The hashmap_entry documentation claims:
`struct hashmap_entry`::
An opaque structure representing an entry in the hash table,
which must be used as first member of user data structures.
Ideally it should be followed by an int-sized member to prevent
unused memory on 64-bit systems due to alignment.
I'm not sure if the statement about alignment is true. If I have a
struct like:
struct magic {
struct hashmap_entry map;
int x;
};
the statement above implies that I should be able to fit this into only
16 bytes on an LP64 system. But I can't convince gcc to do it. And I
think that makes sense, if you consider code like:
memset(magic.map, 0, sizeof(struct hashmap_entry));
The sizeof() has to be the same regardless of whether the hashmap_entry
is standalone or in another struct, and therefore must be padded up to
16 bytes. If we stored x in that padding in the combined struct, it
would be overwritten by our memset.
The struct-packing patch was ultimately dropped because there was no way
to reliably make it work on all platforms. See [1] for discussion, [2] for
the final, 'most compatible' version.
Am I missing anything? If this is the case, we should probably drop that
bit from the documentation.
Hmmm. Now that we have __attribute__((packed)) in pack-bitmap.h, perhaps
we should do the same for stuct hashmap_entry? (Which was the original
proposal anyway...). Only works for GCC, but that should cover most builds
/ platforms.
Btw.: Using struct-packing on 'struct bitmap_disk_entry' means that the
binary format of .bitmap files is incompatible between GCC and other
builds, correct?
It's possible that we could get around it by
embedding the hashmap_entry elements directly into the parent struct,
Already tried that, see [3].
[1] http://article.gmane.org/gmane.comp.version-control.git/239069
[2] http://article.gmane.org/gmane.comp.version-control.git/241865
[3] http://article.gmane.org/gmane.comp.version-control.git/239435
--
To unsubscribe from this list: send the line unsubscribe git in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
struct hashmap_entry packing
Hi Karsten,
The hashmap_entry documentation claims:
`struct hashmap_entry`::
An opaque structure representing an entry in the hash table,
which must be used as first member of user data structures.
Ideally it should be followed by an int-sized member to prevent
unused memory on 64-bit systems due to alignment.
I'm not sure if the statement about alignment is true. If I have a
struct like:
struct magic {
struct hashmap_entry map;
int x;
};
the statement above implies that I should be able to fit this into only
16 bytes on an LP64 system. But I can't convince gcc to do it. And I
think that makes sense, if you consider code like:
memset(magic.map, 0, sizeof(struct hashmap_entry));
The sizeof() has to be the same regardless of whether the hashmap_entry
is standalone or in another struct, and therefore must be padded up to
16 bytes. If we stored x in that padding in the combined struct, it
would be overwritten by our memset.
Am I missing anything? If this is the case, we should probably drop that
bit from the documentation. It's possible that we could get around it by
embedding the hashmap_entry elements directly into the parent struct,
but we would be counting on a reader dereferencing it as a hashmap_entry
seeing the members at the exact same offset. I'd imagine that's one of
those things that holds most of the time, but is violating the standard.
It's probably not worth it to save a few bytes.
-Peff
--
To unsubscribe from this list: send the line unsubscribe git in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
