Inline structs and lists

[Kenton Varda]

While working on the meta-schema I found myself wanting inline structs and lists.  I just pushed some code implementing this.  Use like so:

struct Foo fixed(2 words, 3 pointers) {

  # ... some fields that come to less than 2 words, 3 pointers ...

}

struct Bar {

  foo @0 :Inline(Foo);

  fourMoreFoos @1 : InlineList(Foo, 4);

}

The effect is what you'd expect:  A Bar object contains 5 Foo objects directly within it, without having to follow a pointer.

I haven't updated the docs yet nor implemented inline blobs (InlineData would make sense, InlineText I'm not so sure).  Will get to that soon.

There are some weird quirks:  You can't set a default value for an inline field.  Supporting this would require doing non-zero initialization on the outer object, because the inner object's accessors otherwise have no way of knowing what default they are supposed to use.  But non-zero initialization will break a bunch of other things.  Instead I'm just thinking about it as:  "When you inline a field, you're inlining its default values.  You don't get to override them."  (I doubt anyone cares about setting defaults for struct fields anyway.)

In a somewhat related development, it occurred to me that when you are encoding a list of structs where the struct type is less than one word in size, you might as well just encode it like a primitive-value list.  E.g. if you have a pair of Int16s in a struct, why not encode it like a list of 32-bit data values?  The remote end already has to handle this correctly in order to satisfy the rule that a primitive list can be upgraded to a struct list.  There's really no reason to pad these structs out to word length, or waste a word on the list tag.  I went ahead and implemented this.

[James McKaskill]

> struct Foo fixed(2 words, 3 pointers) {
# ... some fields that come to less than 2 words, 3 pointers ...
}

How about using a different term then struct? Though I presume it
doesn't always need to be used Inline and normal usage is still
supported, in which case keeping struct might be wise.

> InlineData would make sense

Is InlineList(UInt8) sufficient or would you still want the typedef?

> In a somewhat related development, it occurred to me that when you are encoding a list of structs where the struct type is less than one word in size, you might as well just encode it like a primitive-value list. E.g. if you have a pair of Int16s in a struct, why not encode it like a list of 32-bit data values?

This has an interesting side effect. It means a List(UInt8) can be
upgraded to a List(UInt16) where the first byte is taken. In my
current implementation I explicitly broke out the composite and
pointer lists when reading from a list. However this actually results
in a much simpler approach. I now only treat pointer lists as a
special case, all the others simply look to see if there is enough
data.

For example before I had something like this:

func (p Pointer) readList(i int) uint64 {
switch p.typ {
case Composite:
if i < int(p.size) && p.dataBits > 0 {
return little64(p.seg.Data[p.off+int32(i)*(p.dataBits/8+int32(p.ptrs)*8):])
}
case PointerList:
p = p.ReadPtr(i)
if p.typ == Struct && p.dataBits > 0 {
return little64(p.seg.Data[p.off:])
}
}
return 0
}

func (p Pointer) ReadList8(i int) uint8 {
if p.typ != Byte1List {
return uint8(p.readList(i))
} else if i < int(p.size) {
return p.seg.Data[p.off+int32(i)]
} else {
return 0
}
}

Now I have the following:

func (p Pointer) listOffset(i, sz int) int {
if i >= p.size {
return -1
} else if sz <= p.dataBits {
return p.off*8 + i*(p.dataBits + p.ptrs*64)
} else if p.dataBits > 0 { // detecting if we have a pointer list
return -1
} else if m := p.ReadPtr(i); sz <= m.dataBits {
return m.off*8
} else {
return -1
}
}

func (p Pointer) ReadList8(i int) (ret uint8) {
if off := p.listOffset(i, 8); off >= 0 {
ret = p.seg.Data[off/8]
}
return
}


Another interesting twist. In my API I return an inner pointer to the
struct data for a composite list. This way composite lists and pointer
lists look the same for readers that don't care. Now I would return an
inner pointer to the list data for any non-pointer list. Supporting
List(Bool) for this is kind of annoying. My pointers at the moment are
byte offset based.

-- James

-- James

> --
> You received this message because you are subscribed to the Google Groups
> "Cap'n Proto" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to capnproto+...@googlegroups.com.
> Visit this group at http://groups.google.com/group/capnproto?hl=en-US.
>
>

[James McKaskill]

> Supporting List(Bool) for this is kind of annoying. My pointers at the moment are
byte offset based.

Never mind, I was being dense. I changed the offset to be in bits and
it simplifies a number of things.

-- James

-- James

[Kenton Varda]

On Fri, Apr 26, 2013 at 9:47 AM, James McKaskill <ja...@foobar.co.nz> wrote:

> struct Foo fixed(2 words, 3 pointers) {
  # ... some fields that come to less than 2 words, 3 pointers ...
}

How about using a different term then struct? Though I presume it
doesn't always need to be used Inline and normal usage is still
supported, in which case keeping struct might be wise.

Yeah, it only gets inlined when you use Inline() at the usage site; otherwise it is a regular struct.  In fact, it's perfectly fine to take an existing struct and add the fixed() notation later on, then start inlining it (in new usages; existing uses obviously have to stay out-of-line for compatibility).  Of course, once you've declared it fixed(), you have to leave it that way, and cannot change the fixed size.

I'm not super happy with the syntax of fixed(), but couldn't think of a good alternative.  I think, though, that I'm going to replace "words" with "bytes" since users of Cap'n Proto often won't know what it considers to be a word.  ("bytes" is already supported now for the specific cases of 1, 2, or 4 bytes.)

 

> InlineData would make sense

Is InlineList(UInt8) sufficient or would you still want the typedef?

List(UInt8) and Data are encoded the same but accessed differently in the API.  In particular you often want to get a direct pointer to the underlying bytes for Data, but List cannot support this in general because of the need for endianness translation.

 

> In a somewhat related development, it occurred to me that when you are encoding a list of structs where the struct type is less than one word in size, you might as well just encode it like a primitive-value list.  E.g. if you have a pair of Int16s in a struct, why not encode it like a list of 32-bit data values?

This has an interesting side effect. It means a List(UInt8) can be
upgraded to a List(UInt16) where the first byte is taken.

Actually, I do not allow that at present.  The rule is that a list of primitives can be upgraded to a list of structs, but not vice-versa.  Technically the implementation needs to handle both directions so that old binaries can read new data just as well as new binaries can read old data, but implementations do *not* need to handle the case of upgrading a list to a struct and then downgrading it to a list of a different type.

 

Another interesting twist. In my API I return an inner pointer to the
struct data for a composite list. This way composite lists and pointer
lists look the same for readers that don't care. Now I would return an
inner pointer to the list data for any non-pointer list. Supporting
List(Bool) for this is kind of annoying. My pointers at the moment are
byte offset based.

I forgot to mention, I decided that upgrading List(Bool) to a list of structs should not be supported after all.  There was some non-zero overhead to allow this in C++ (mainly because pointers can only address bytes, not bits), and I realized that in many languages the overhead would be considerably greater.

[Alek Storm]

I'm not sure the complexity/benefit ratio is favorable here. Yes, there are space savings in eliminating pointers, but I believe this is negligible: when applied to the motivating use case (a list of structs, each containing a pointer to a struct), this new format will only reduce the final size by four bytes after packing (one each for the tag, offset, and data and pointer sizes, respectively - nearly all inlined structs should be small), and since each nested pointer in the list will be identical (unless the encoder is very strange), any entropy-encoding compressor (e.g. gzip or snappy) will further reduce each occurrence to only a few bits. Reducing in-memory size (which obviously can't be packed/compressed during construction without getting quite clever) strikes me as much less of a concern.

The case for eliminating indirection (and thereby improving CPU cache performance by decreasing the number of entries that must be stored per struct) doesn't seem applicable often either, since most long lists are built/read by accessing each element one at a time, in a single pass - this keeps the required cache space constant. For each element, the cache miss on its pointer will happen only once, and further accesses to its fields will have essentially the same latency as if it were inlined. The only pathological case would be multiple passes over the same list, which is already widely known to be slow in many other collections libraries.

All this being said, I am quite willing to be convinced that the optimization is worthwhile by benchmarks :)

And the savings, if any, would come at a heavy syntactic cost: a new construct introducing three new keywords ("fixed", "bytes", and "pointers"), and two new types (:Inline and :InlineList), as well as encouragement for users to violate the core promise of Cap'n Proto: forwards-compatibility. Since inlined structs should be small (the more fields a struct has, the more likely it is to need to grow in the future, and the smaller the ratio of inlined-to-non-inlined size anyway), I submit that if users *really* need the benefits outlined above, they can simply manually inline the fields themselves. This is ugly, but will discourage users from shooting themselves in the foot by inlining a struct that isn't really fixed-size for an optimization they don't really need - and annotations that simulate inlined structs in generated code will make this nearly painless (so the HAS_A relationship is maintained), while only burdening the language implementors that want to support it.

Alek

--

[Kenton Varda]

I am sympathetic to this argument, particularly after implementing inlines and finding them more complicated and quirky than I expected.  E.g. the fact that inline fields cannot have default values is weird, but implementing default values would have excessive overhead.  And the fact that fixed-width structs explicitly abandon the extensibility principles that are considered a key feature of the whole protocol is...  worrying.

I think that measuring the absolute number of bytes saved by an inline field doesn't tell us much.  What we really want to know is, are there legitimate use cases where the savings of inline fields would be a large percentage of the overall message size?

Note that manual inlining is not always feasible.  Consider the case of a union which you really want to be reusable.  You really can't just copy the whole union around, but most unions are 1 or 2 words so embedding it by pointer means 50%-100% overhead.  On the other hand, my argument against making unions reusable in the first place was explicitly because you might later decide you want to attach some extra information to them, which you can't do with a fixed-width struct.

Anyone else have an opinion on this?  Did I just waste the last week working on a misfeature?  (Well, I did fix a bunch of small things at the same time, so not a complete waste, but...)

-Kenton

[James McKaskill]

> What we really want to know is, are there legitimate use cases where the savings of inline fields would be a large percentage of the overall message size?

Do you care about heavily optimizing the in memory size or is the
compressed format more important?

> Note that manual inlining is not always feasible. Consider the case of a union which you really want to be reusable. You really can't just copy the whole union around, but most unions are 1 or 2 words so embedding it by pointer means 50%-100% overhead.

I was wondering about this. If the struct is less than 7 bytes, could
we embed it in the pointer value itself. IE use a pointer tag of 2 +
something in first byte, and then the next 7 bytes are the actual
struct value. Would save you a word, but seems a bit hackish ... But
it allows an implementation to use it and still have the ability to
switch to a normal pointer when the struct becomes larger.

The whole inline data thing feels like you're requiring the user to
know and guess the max size of the struct in the future, which would
necessitate that they know the packing format, alignment, etc and can
manually figure out how much space might be needed.

I haven't actually done any work yet to support it, so I'm personally
not too fussed either way.

-- James

-- James

[James McKaskill]

> > > In a somewhat related development, it occurred to me that when you are encoding a list of structs where the struct type is less than one word in size, you might as well just encode it like a primitive-value list. E.g. if you have a pair of Int16s in a struct, why not encode it like a list of 32-bit data values?

> > This has an interesting side effect. It means a List(UInt8) can be
> > upgraded to a List(UInt16) where the first byte is taken.

> Actually, I do not allow that at present. The rule is that a list of primitives can be upgraded to a list of structs, but not vice-versa. Technically the implementation needs to handle both directions so that old binaries can read new data just as well as new binaries can read old data, but implementations do *not* need to handle the case of upgrading a list to a struct and then downgrading it to a list of a different type.

I'm not sure if thats the case. If we start out with
List(UInt8)

Sometime down the road this gets updated to
struct Foo {
a @0 :UInt8;
}
List(Foo)
New users of List(Foo) will still serialize it as a List(U8).

Further down the line this gets updated to
struct Foo {
a @0 :UInt8;
b @1 :UInt8;
}

Newer users will create it as a List(U16) via the same rule.
All three users should be able to read data from the new users.

I've handled this quite cleanly by divorcing the API data size from
the serialized data size, even if the data is serialized as a
composite type. As long as the API size <= serialized size, I just
return the first x bytes.

For my C code atm I don't allow the upgrade, so to read a List(Bool)
it must also be serialized as a List(Bool). This vastly simplifies all
the other cases and means I can use pointers rather than bit offsets.
The go code uses bit offsets.

-- James

-- James

[Kenton Varda]

On Mon, Apr 29, 2013 at 6:55 PM, James McKaskill <ja...@foobar.co.nz> wrote:

> What we really want to know is, are there legitimate use cases where the savings of inline fields would be a large percentage of the overall message size?

Do you care about heavily optimizing the in memory size or is the
compressed format more important?

Both are important.  Reducing cache pressure has a surprisingly large effect on performance.  Also, for intra-datacenter traffic, bandwidth is generally not a concern so people may not want to pack.

That said, Cap'n Proto is already far ahead of everything else on in-memory size so maybe squeezing it further is not hugely beneficial.

 

> Note that manual inlining is not always feasible.  Consider the case of a union which you really want to be reusable.  You really can't just copy the whole union around, but most unions are 1 or 2 words so embedding it by pointer means 50%-100% overhead.

I was wondering about this. If the struct is less than 7 bytes, could
we embed it in the pointer value itself. IE use a pointer tag of 2 +
something in first byte, and then the next 7 bytes are the actual
struct value. Would save you a word, but seems a bit hackish ... But
it allows an implementation to use it and still have the ability to
switch to a normal pointer when the struct becomes larger.

Ehh...  first impression is that this sounds too hacky for not enough benefit.  But I'll think about it.

 

The whole inline data thing feels like you're requiring the user to
know and guess the max size of the struct in the future, which would
necessitate that they know the packing format, alignment, etc and can
manually figure out how much space might be needed.

Yeah.  Certainly if we provide this feature it would only be for advanced users who are OK working that stuff out.  But providing the option might lure people into shooting themselves in the foot...

On Mon, Apr 29, 2013 at 8:04 PM, James McKaskill <ja...@foobar.co.nz> wrote:

I'm not sure if thats the case. If we start out with

List(UInt8)

Sometime down the road this gets updated to
struct Foo {
a @0 :UInt8;
}
List(Foo)
New users of List(Foo) will still serialize it as a List(U8).

Further down the line this gets updated to
struct Foo {
a @0 :UInt8;
b @1 :UInt8;
}

Newer users will create it as a List(U16) via the same rule.
All three users should be able to read data from the new users.

Yikes, nice catch.  Yes, my current implementation is broken in this case.

Of course, a receiver that is expecting List(UInt16) (not a 16-bit strurct, but a list of primitive UInt8's) should still reject List(UInt8).  Not only is there no legal way for that transition to happen, but allowing it would lead to unaligned reads and even a potential 1-byte buffer overrun on the last element.

 

I've handled this quite cleanly by divorcing the API data size from
the serialized data size, even if the data is serialized as a
composite type. As long as the API size <= serialized size, I just
return the first x bytes.

For my C code atm I don't allow the upgrade, so to read a List(Bool)
it must also be serialized as a List(Bool). This vastly simplifies all
the other cases and means I can use pointers rather than bit offsets.
The go code uses bit offsets.

Yeah, I decided that List(Bool) <-> List(struct) isn't allowed because of this exact difficulty.  So you can go back to byte offsets in Go.

[Keir Mierle]

What about making List(Bool) a separate toplevel type? BoolVector? BoolList? Or even consider omitting specialized list of bools entirely from the first version or two of capnproto until a clear need is demonstrated. What are the expected use cases for lists of bools? Expanding bitfields? Wouldn't those be better served by regressing them to boolean types?

In my experience violating the liskov substitution principle is bad, and List(Bool) feels like it's doing exactly that. 

I expect most on the list are familiar with C++'s vector<bool> debacle, but I link to it for posterity:

http://www.gotw.ca/publications/N1211.pdf

[Kenton Varda]

Wouldn't disallowing List(Bool) in itself be a violation of the Liskov substitution principle?  :)  Unless we entirely eliminate Bool as a type, which I don't think we want to do...

[Keir Mierle]

I agree it's murky since this isn't classes exactly. Here's one possibility:

- List(Bool) is mapped to List(byte). This way you can upgrade everything fine, and compression will get back most (but not all) of the excess zero bits.

- Offer a BoolList specialization that does not pretend to be a normal list, but is instead a different type of object for the case that you truly need packed bits.

Another possibility (totally nuts, unacceptable performance issues):

- Switch pointers from bytes to bits.

[Keir Mierle]

Further thinking: the Bool type itself is violating the Liskov substitution principle. If you have a List(T), where T can be "any type", and "bool is a type", then List(Bool) should be valid, and should behave exactly as all other List(T). Instead there are special restrictions on List(Bool).

Here's a third idea: Eliminate Booleans as a base type. It sounds crazy, but I don't think it's totally crazy.

- As suggested earlier, offer a BoolList or VectorBool type for variable-length bool lists.

- Offer a "Bitset" type with symbolic names for the bits. Without thinking too deeply, I think it may be possible to offer an upgrade path from bitset to struct { bitset@0, <other fields>}

I admit I haven't carefully thought though the bitset idea and wire format implications yet.

Keir

[Andrew Lutomirski]

On Tue, Apr 30, 2013 at 2:14 PM, Keir Mierle <mie...@gmail.com> wrote:
> Further thinking: the Bool type itself is violating the Liskov substitution
> principle. If you have a List(T), where T can be "any type", and "bool is a
> type", then List(Bool) should be valid, and should behave exactly as all
> other List(T). Instead there are special restrictions on List(Bool).
>
> Here's a third idea: Eliminate Booleans as a base type. It sounds crazy, but
> I don't think it's totally crazy.
> - As suggested earlier, offer a BoolList or VectorBool type for
> variable-length bool lists.
> - Offer a "Bitset" type with symbolic names for the bits. Without thinking
> too deeply, I think it may be possible to offer an upgrade path from bitset
> to struct { bitset@0, <other fields>}
>
> I admit I haven't carefully thought though the bitset idea and wire format
> implications yet.

This is, I think, just complicated enough to inspire a feature
request: can we have something like capnpc
--are-definitions-compatible?

--Andy

[Kenton Varda]

On Tue, Apr 30, 2013 at 2:14 PM, Keir Mierle <mie...@gmail.com> wrote:

Further thinking: the Bool type itself is violating the Liskov substitution principle. If you have a List(T), where T can be "any type", and "bool is a type", then List(Bool) should be valid, and should behave exactly as all other List(T). Instead there are special restrictions on List(Bool). 

Here's a third idea: Eliminate Booleans as a base type. It sounds crazy, but I don't think it's totally crazy.

- As suggested earlier, offer a BoolList or VectorBool type for variable-length bool lists.

- Offer a "Bitset" type with symbolic names for the bits. Without thinking too deeply, I think it may be possible to offer an upgrade path from bitset to struct { bitset@0, <other fields>}

This is adding practical complexity to achieve theoretical purity.  I don't think that's a good trade-off.  Theoretical purity is good when it means there are fewer things the user needs to know, but what you're suggesting seems like the opposite.

If the inability to replace List(Bool) with List(struct) is a real problem, I'd rather solve it by re-introducing the implementation overhead needed to support it correctly.  But I'm not convinced that it is a real problem.

[Kenton Varda]

On Tue, Apr 30, 2013 at 2:15 PM, Andrew Lutomirski <an...@luto.us> wrote:

This is, I think, just complicated enough to inspire a feature

request: can we have something like capnpc
--are-definitions-compatible?

Yes!  This is on my list, although it's relatively low priority compared to actually implementing the system.  :)  (Maybe someone would like to contribute?)

Ideally you'd be able to set things up so that git (or whatever you use) will automatically check for compatibility whenever you commit changes to a .capnp file.

[Mark Miller]

Is compatibility commutative? Assuming not, is it a partial order? A lattice? Assuming yes, now that you also have interfaces, new services can invoke old services and vice versa. So interface compatibility may need to account for co-variance and contra-variance of argument and return compatibility. 

(There was an old Sun Labs tech report from the Spring project that tried to map compatibility relationships onto subtyping. It was unsound but it may be relevant. Unfortunately, I don't know what to search for to find it. A bit of searching just now was fruitless.)

--

You received this message because you are subscribed to the Google Groups "Cap'n Proto" group.
To unsubscribe from this group and stop receiving emails from it, send an email to capnproto+...@googlegroups.com.
Visit this group at http://groups.google.com/group/capnproto?hl=en-US.
 
 

--
Text by me above is hereby placed in the public domain

  Cheers,
  --MarkM

[Kenton Varda]

Compatibility is commutative, but is only transitive if all changes are in the same "direction" -- upgrade or downgrade.  If you perform a series of upgrades to a type, the result is compatible with the original type.  If you apply a series of downgrades, they are also compatible.  But if you apply a mixture of upgrades and downgrades, the result is not compatible.

For example, if you start with struct A, remove its last field (a downgrade) to produce B, and then add a different field (an upgrade) to produce C, A is compatible with B and B is compatible with C but A is not compatible with C.

Our tool would want to enforce that any changes are strictly in the upgrade direction.

[Mark S. Miller]

The "same direction" constraint is surprising. Is this because you don't allow holes in the numbering? If you did, and you never reused an old number for something else, would the "same direction" constraint go away? Are you disallowing this only to avoid a minor representation cost?

    Cheers,
    --MarkM

[Kenton Varda]

On Tue, Apr 30, 2013 at 8:51 PM, Mark S. Miller <eri...@google.com> wrote:

The "same direction" constraint is surprising. Is this because you don't allow holes in the numbering? If you did, and you never reused an old number for something else, would the "same direction" constraint go away? Are you disallowing this only to avoid a minor representation cost?

So, JSON, Protobufs, and everything else all have the same directionality constraint, but only in that you can't reuse the same field identifier (name in JSON, number in protobufs) for a differently-typed field.  I assume you only find the constraint surprising in the case where reuse isn't happening, right?  Otherwise, if compatibility were fully transitive and commutative, then every struct would be compatible with every other struct, since every struct is clearly compatible with the empty struct.

I think what you're missing about Cap'n Proto is that the field numbers do not directly translate to positions.  Different fields have different widths, and pointers are actually segregated from flat data.  Therefore, the position of any particular field necessarily depends on what fields were declared "before" it.  The purpose of the field numbers in Cap'n Proto is only to provide a stable ordering -- one which developers are unlikely to "mess up" by adding new fields somewhere other than at the end of the struct.

The restriction that field numbers cannot have "holes" follows from this.  Removing an earlier field would cause all later fields to shift forward, so this cannot be allowed.

In practice, no one ever removes fields from protobufs, because doing so leads to the risk that the field number will be accidentally reused.  Instead, they rename the field to something like "OBSOLETE".  So, Cap'n Proto is merely enforcing what was already best practice.

[Keir Mierle]

On Tue, Apr 30, 2013 at 9:19 PM, Kenton Varda <temp...@gmail.com> wrote:

On Tue, Apr 30, 2013 at 8:51 PM, Mark S. Miller <eri...@google.com> wrote:

The "same direction" constraint is surprising. Is this because you don't allow holes in the numbering? If you did, and you never reused an old number for something else, would the "same direction" constraint go away? Are you disallowing this only to avoid a minor representation cost?

So, JSON, Protobufs, and everything else all have the same directionality constraint, but only in that you can't reuse the same field identifier (name in JSON, number in protobufs) for a differently-typed field.  I assume you only find the constraint surprising in the case where reuse isn't happening, right?  Otherwise, if compatibility were fully transitive and commutative, then every struct would be compatible with every other struct, since every struct is clearly compatible with the empty struct.

I think what you're missing about Cap'n Proto is that the field numbers do not directly translate to positions.  Different fields have different widths, and pointers are actually segregated from flat data.  Therefore, the position of any particular field necessarily depends on what fields were declared "before" it.  The purpose of the field numbers in Cap'n Proto is only to provide a stable ordering -- one which developers are unlikely to "mess up" by adding new fields somewhere other than at the end of the struct.

The restriction that field numbers cannot have "holes" follows from this.  Removing an earlier field would cause all later fields to shift forward, so this cannot be allowed.

In practice, no one ever removes fields from protobufs, because doing so leads to the risk that the field number will be accidentally reused.  Instead, they rename the field to something like "OBSOLETE".  So, Cap'n Proto is merely enforcing what was already best practice.

While I did see the "OBSOLETE_foo" technique at Google, this was not the only way. Both my group and the protos from other groups I used often followed a pattern like this:

message AnOldAndCruftyMessage {

  optional int32 a_field = 3; 

  // ...many more fields

  // Deleted fields: 10, 17, 22, 3.

}

The advantage is that the deleted fields don't clutter the file. The disadvantage is that it is possible to accidentally reuse a field. This approach won't work for capnproto because without the sizing information, the compiler can't generate backwards compatible code. But perhaps we could have a more compact "remove" annotation instead of keeping the entire field around. Currently, to delete a field you need to do something like:

struct Person {

  name @0 :Text;

  birthdate @3 :Date;

  email @1 :Text;

  phones @2 :List(PhoneNumber);

  DELETED_crufty_extras_here @10 :DELETED_CruftyStruct;

}

struct DELETED_CruftyStruct {

  // This used to have lots of crufty fields, but is deleted.

}

What about instead something like:

struct Person {

  name @0 :Text;

  birthdate @3 :Date;

  email @1 :Text;

  phones @2 :List(PhoneNumber);

  Deleted(10 :Struct, 5 :Int32);

}

which makes it possible to remove the dependent struct definitions as well. Furthermore, if we assume that deleted fields are always 8-sized (so structs) then potentially even the type of the deleted field could be omitted unless it is a different size (e.g. bool). I don't care especially about the particular syntax for indicating deletes, but I do want a clean way of removing old fields.

[Kenton Varda]

Yeah, I'd be happy to entertain a way to mark deleted fields...  eventually.  But this is obviously pretty low priority.  :)

BTW, you can use "Object" as the type for deleted pointer-typed fields (structs, lists, probably interfaces).  "Object" is the new dynamic field type, which I implemented yesterday.

[Alek Storm]

On Mon, Apr 29, 2013 at 6:09 PM, Kenton Varda <temp...@gmail.com> wrote:

I am sympathetic to this argument, particularly after implementing inlines and finding them more complicated and quirky than I expected.  E.g. the fact that inline fields cannot have default values is weird, but implementing default values would have excessive overhead.  And the fact that fixed-width structs explicitly abandon the extensibility principles that are considered a key feature of the whole protocol is...  worrying.

I think that measuring the absolute number of bytes saved by an inline field doesn't tell us much.  What we really want to know is, are there legitimate use cases where the savings of inline fields would be a large percentage of the overall message size?

Agreed.

Note that manual inlining is not always feasible.  Consider the case of a union which you really want to be reusable.  You really can't just copy the whole union around, but most unions are 1 or 2 words so embedding it by pointer means 50%-100% overhead.  On the other hand, my argument against making unions reusable in the first place was explicitly because you might later decide you want to attach some extra information to them, which you can't do with a fixed-width struct.

Good point. How about allowing users to trade processing time for memory efficiency, and get reusable unions to boot? Encode the maximum size of the union in the first three bits of the discriminant* (I'm sure users will be fine with only 8192 possible union fields), but rather than having the value immediately follow, place it at the end of the data section, and place the values of unions with higher ordinals in reverse order from there. For example:

union A {
  one @0 :Boolean;
  two @1 :UInt8;
}

union B {
  one @0 :Int16;
  two @1 :Object;
}

struct Foo {
  x @0 :A;
  bar @1 :UInt8;
  y @2 :B;
  baz @3 :Int16;
  qux @4 :Text;
}

+--------+---------------+-----------+------------+
| x_s(3) | x_disc(13)    | bar(8)    | pad(8)     | // normal, absolutely-positioned fields
+--------+---------------+-----------+------------+
| y_s(3) | y_disc(13)    | baz(16)                |
+--------+---------------+------------------------+
| pad(32)                                         | // pad to word boundary
+------------------------+-----------+------------+
| y_data(16)             | pad(8)    | x_data(8)  | // union data fields in reverse order
+------------------------+-----------+------------+
| qux(64)                                         | // here be the pointer section
|                                                 |
+-------------------------------------------------+
| y_pointer(64)                                   | // union pointer fields in reverse order
|                                                 |
+-------------------------------------------------+

This allows unions to evolve independently of one another, making them reusable (i.e. typed), while consuming no extra space. The downside, however, is that since the size of a typed union is no longer known beforehand, its position must be calculated relative to all typed unions before it - in other words, worst-case access time is linear in the number of typed unions in the struct (although presumably the information will be cached on successive lookups). Since I expect the number of unions (especially typed unions) per struct to be quite small, I doubt this will be an issue in practice.

Since typed unions may grow freely, extra information can be attached by adding a new union field pointing to a struct with the data, although the other union fields might have to be duplicated in the referenced struct, and the client API would be clumsy. Instead, by stealing another bit from the discriminant, we can indicate whether there is an "extra information" struct pointer following the normal pointer section entry for the union (if present). This makes handling default values for versions missing the extra information a snap, and takes up the exact same amount of space as it would if the user had had the foresight to wrap the union in a struct beforehand. First-class support in the schema language could look like one of the following, and would also be applicable to enums:

union Foo {
  one @0 :Boolean;
  two @1 :UInt8;
  data {
    bar @0 :Float32;
    qux @1 :Text;
  }
}

# or

struct Extra {
  bar @0 :Float32;
  qux @1 :Text;
}

union Foo data(Extra) {
  one @0 :Boolean;
  two @1 :UInt8;
}

Thoughts?

* Similar in spirit to the C section of list pointers, but instead divided into two bits for the size in bytes (1, 2, 4, or 8; 0 is already covered by enums), and one for whether a pointer value is possible.

Anyone else have an opinion on this?  Did I just waste the last week working on a misfeature?  (Well, I did fix a bunch of small things at the same time, so not a complete waste, but...)

I wouldn't say that; now we know how complex they are to implement :). And I've certainly wasted more than a week on my own share of misfeatures in the past.

Alek

[Alek Storm]

On Tue, Apr 30, 2013 at 1:20 PM, Keir Mierle <mie...@gmail.com> wrote:

<snip>

What about making List(Bool) a separate toplevel type? BoolVector? BoolList? Or even consider omitting specialized list of bools entirely from the first version or two of capnproto until a clear need is demonstrated.

Please don't do that; `List(Bool)` works perfectly fine in Java/Scala :).

What are the expected use cases for lists of bools? Expanding bitfields? Wouldn't those be better served by regressing them to boolean types?

In my experience violating the liskov substitution principle is bad, and List(Bool) feels like it's doing exactly that. 

I think that's technically true only if `List` is covariant, which would imply immutability, but I get your meaning. However, there's nothing that says "For all T, `List(T)` must map to a generic type `Foo<T>` in the target language". If bits not being addressable in C causes problems, you can always make it a separate (non-reference-extracting?) monomorphic type, perhaps overridable via an annotation.

Alek

[Kenton Varda]

Under this scheme, calculating the offset of a union value would be complicated.  Consider the case where a 1-byte union is followed by a 2-byte union.  The 2-byte union has to be properly-aligned, so simple addition is not good enough.  Also, these unions cannot be located in space otherwise wasted to padding.  A 1-byte union followed by a 4-byte union followed by another 1-byte union would end up taking 16 bytes.  Seems too complicated.

I'm also not confident at all in your expectation that few structs would include more than one union.  For example, just in schema.capnp I have Type and Value unions which usually come in pairs.  I could easily see someone used to algebraic typing writing lots of union type and using them extensively.

[Alek Storm]

On Fri, May 3, 2013 at 11:59 AM, Kenton Varda <temp...@gmail.com> wrote:

Under this scheme, calculating the offset of a union value would be complicated.  Consider the case where a 1-byte union is followed by a 2-byte union.  The 2-byte union has to be properly-aligned, so simple addition is not good enough.  Also, these unions cannot be located in space otherwise wasted to padding.  A 1-byte union followed by a 4-byte union followed by another 1-byte union would end up taking 16 bytes.  Seems too complicated.

Clarified this via IM; you meant that although (paraphrasing) locating typed unions in padding space wouldn't be impossible, it would be too slow to be practical. And yes, it would be in many cases, but I believe there are others where memory usage is more of a bottleneck than CPU time (and when copying around large data structures, memory usage costs CPU time anyway). And I'd argue that it's still less complex overall than inline structs :)

I'm also not confident at all in your expectation that few structs would include more than one union.  For example, just in schema.capnp I have Type and Value unions which usually come in pairs.  I could easily see someone used to algebraic typing writing lots of union type and using them extensively.

Yeah, the best countermeasure would be documentation here (although in the example you mention, I doubt performance is much of a concern). Users can choose either inline or typed unions, so it's only the ones who don't read the docs that would see a performance difference - although I'm certainly guilty of not reading docs very carefully before.

In any case, the above proposal was just an attempt to provide an alternative to inline structs for one of their (rare) use cases that can't be replicated some other way: efficient reusable unions. But since I still don't believe the complexity/efficiency tradeoff is worth it, I propose putting inline structs on hold for now, at least until we can gather more data about their possible uses.

Alek

[Kenton Varda]

I've decided to scrap inlines for now.  I'm leaving the code in the compiler, but commenting out the places where the relevant keywords and type names (fixed, Inline, InlineList, InlineData) are made visible -- so the whole implementation is still there but there's no way to use it.  I think we can just leave unions as they are.

[Kenton Varda]

So yeah, that ended up being about 10% of Cap'n Proto's total codebase that I just deleted -- and I didn't even delete the compiler-side parts.  Sigh.