Rethinking intern() for python

[Stephen J. Turnbull]

John Arbash Meinel writes:

 > The current string definition is:
 > typedef struct {
 >     Py_ssize_t ob_refcnt;	32/64bit counter
 >     PyTypeObject *ob_type;	32/64bit pointer
 >     Py_ssize_t ob_size;		32/64bit counter
 >     long ob_shash;		32/64bit hash
 >     int ob_sstate;		32bit state
 >     char ob_sval[1];		8bit space for NULL
 > } PyStringObject;
 > 
 > ob_sstate is taking up 4-bytes just to store one of the values 0, 1, 2,
 > to indicate the INTERN state of the string. Which is 3-bytes of direct
 > waste.
 >
 > Also, at least with my compiler, the 1 byte for ob_sval[] actually
 > causes the sizeof(PyStringObject) to get 4 more bytes. Which means that
 > every malloc() is over-allocating *another* 3 bytes.

I don't think so.  This looks like the usual C idiom for a variable-
sized data area, which works because C doesn't use the "1" for
anything except determining the size of a statically-allocated
PyStringObject.  So with the exception of the null string (of which
there will be exactly one in your table), you're going to need to
allocate that space anyway, and you can't move it, it has to be the
last member of the struct.  If the compiler wastes space by allocating
to alignment boundaries, it wastes it, but in general you can't do
anything about it.  Or am I missing something?

This may make my previous comment irrelevant, because XEmacs uses a
pointer to a separately malloc'd pool instead of immediate storage for
strings.

 > be valid, and have that value indicate there is a different structure to
 > check.
 > 
 > If you went approximately minimal, you would end up with:
 > typedef struct {
 >     Py_ssize_t ob_refcnt;	32/64bit counter
 >     PyTypeObject *ob_type;	32/64bit pointer
 >     long ob_shash;		32/64bit hash
 >     short ob_size;		32/64bit counter

This can be done with alignment attributes in GCC, but in many
compilers (and GCC by default IIRC) members are typically allocated on
int alignment boundaries.

I bet you can't move or resize ob_size and still pretend this is a
PyObject.  In particular, isn't the Boolean test on an object
implemented as self.ob_size != 0?  Anyway, you need to watch out for
that kind of thing.  The ob_shash, ob_sstate, and ob_sval members are
probably string-specific, so you can play with them.

 >     unsigned char ob_sstate;	32bit state
 >     char ob_sval[];		8bit space for NULL
 > } PyStringObject;

 > Which is right at 16 bytes of overhead, down from 24. I don't really
 > like that ob_sval is no longer aligned on a 4-byte boundary, so we could
 > probably do something about that. As I understand it, malloc would align
 > an actual allocation to 4-byte boundary anyway...

malloc typically aligns allocations according to internal
requirements, including the need to store malloc accounting data.  I
wouldn't worry about it.  It's the C compiler that determines the
internal alignment of structs, and that's hairy.