[Cython] Another potential optimization possible with transforms

[Martin C. Martin]

Hi,

There's a potential optimization I mentioned on the Lisp inspired 
transforms page, where you could reorder bitfields in order to pack them 
most efficiently.  Eerily, someone at my job just committed something 
that did just that.  We have a custom defstruct, called defstruct-bv, 
which allows you to specify bit fields.  (Lisp doesn't come with 
bitfields.)  Here's the checkin message:

Log:
At compile time, automatically optimize the layout of bits in a
defstruct-bv definition to minimize the number of words used by the
resulting struct.

This is an instance of the bin-packing problem, which is NP-hard.
Fortunately, it has a good heuristic solution, first-fit decreasing,
which gets very close to optimal answers. I just implemented that as
a wrapper around the existing defstruct-bv, which I renamed
defstruct-bv-internal.

There is no longer any reason to worry about the order of bit field
definitions within a lisp struct.

If you have a struct that you don't want this to happen to (perhaps
because you have a performance consideration for the layout), add
(:optimize-p NIL) as an option to defstruct-bv.

I was somewhat disappointed with the results: most of our structs were
already laid out as optimally as this algorithm is able to achieve.
The single exception was the faring-atom struct, which got 16 bytes
smaller.

Best,
Martin