Re: [capnproto] [Feature Request] Putting List() object at last and allow reuse of the MallocMessageBuilder
Cross-segment references are in fact expressed as a pair of a segment number and an offset today. So with sufficiently complex allocation logic, you could indeed allocate the side objects in a separate segment from the list itself, and thus allow the list to be resized continuously. But the C++ implementation, at least, was never intended to be used this way. The main purpose of segments in C++ is to allow more space to be allocated without relocating the existing data in memory. Each time an allocation is unable to be satisfied by the existing segments, a new segment is allocated, usually twice the size of the previous one. Perhaps it would not take too much effort to expose some APIs such that you can designate a particular list must live in its own segment, so that it can be grown, and the segment itself can even be re-allocated in a different location to accommodate when the list outgrows the previous allocation. This of course means that all Reader and Builder objects pointing into the list would be invalidated any time it grows. But I suppose a carefully-written application could handle all that. There is another problem with this, though, which is that "far pointers" (that point across segment boundaries) have more overhead than in-segment pointers. An in-segment pointer is always 8 bytes. Far pointers typically require 8 bytes in the source segment *and* 8 bytes in the destination segment, for a total of 16 bytes. (And when the destination segment doesn't have space to allocate this, 16 bytes will be needed in some other segment, for a total of 24 bytes). In a large list of small items this overhead could be substantial. -Kenton On Mon, Jun 5, 2023 at 11:26 AM Jonathan Shapiro wrote: > Chiming in here in relative ignorance… > > Offhand, it seems to me that the advantage to placing strings last is that > you can buffer them in another segment making a single pass over the struct > array and then appending them without a second touch. It plays fairly > nicely with the cache, and writev() becomes your friend when the time comes > to do your I/O. > > Offhand, it seems to me that you could equally well buffer the structs, > but it depends on the on-wire representation for references. > > Logical truncate and physical truncate are two different things. I’d have > to look at the wire representation to be sure, but I suspect it’s okay to > truncate an already buffered array in the sense that the recipient will not > be told about the (now garbage) extra bytes. Not efficient from a > transmission perspective, and I can’t think of a good use case. > > Kevin: I have two ignorant design questions here: > > 1. Given that messages are already divided into segments, did you consider > an on-wire representation for references taking the form segment::offset > coupled with an in-memory segment table somewhere? I expect you did, and > I’m wondering what the issues are/were? Wide adoption of writev() is > relatively recent, which seems relevant here, but using a byte offset on > the wire precludes both out-of-order segment serialization and out-of order > segment writes. > > 2. If there were a reason to, does the current API expose the on-wire > reference representation? Is the current representation effectively part of > the API? > > > Jonathan > > > > On Mon, Jun 5, 2023 at 7:32 AM 'Kenton Varda' via Cap'n Proto < > capnproto@googlegroups.com> wrote: > >> Hi Gokul, >> >> There's currently no way to "inline" one struct into another. >> >> The fundamental problem you have here is this: Say you have a list >> containing pointer values, and the list is actually at the end of the >> message. So, you can resize it without fragmentation. You add one new >> element. Then you populate the element, by allocating the pointer values >> that go into it. These new allocations are added to the end of the message, >> therefore the list is no longer at the end, and so can no longer be resized >> without fragmentation. Yes, in theory, if you could remove all of the >> objects allocated past the end of the list, then you could perhaps resize >> it again. But, then you'd have to bring those object back again, added to >> the end of the list. Each time you added a new element, the number of >> objects that you are rolling back and forward every time increases, so the >> overall time complexity ends up being O(n^2). >> >> You might want to consider an alternative design: Instead of a list, >> maybe you want a stream. In a streaming approach, you would append each >> item to your byte stream as a new encoded message. The down side of this >> approach is that you cannot easily jump to a random location in the list; >> you must parse the items in order. But maybe that's OK for your use case. >> >> A third approach could combine the two: You could create a stream of >> messages, and separately maintain an index into that stream. The index >> would store the starting byte offset of each message in the stream, so you >> can seek to
Re: [capnproto] [Feature Request] Putting List() object at last and allow reuse of the MallocMessageBuilder
Chiming in here in relative ignorance…
Offhand, it seems to me that the advantage to placing strings last is that
you can buffer them in another segment making a single pass over the struct
array and then appending them without a second touch. It plays fairly
nicely with the cache, and writev() becomes your friend when the time comes
to do your I/O.
Offhand, it seems to me that you could equally well buffer the structs, but
it depends on the on-wire representation for references.
Logical truncate and physical truncate are two different things. I’d have
to look at the wire representation to be sure, but I suspect it’s okay to
truncate an already buffered array in the sense that the recipient will not
be told about the (now garbage) extra bytes. Not efficient from a
transmission perspective, and I can’t think of a good use case.
Kevin: I have two ignorant design questions here:
1. Given that messages are already divided into segments, did you consider
an on-wire representation for references taking the form segment::offset
coupled with an in-memory segment table somewhere? I expect you did, and
I’m wondering what the issues are/were? Wide adoption of writev() is
relatively recent, which seems relevant here, but using a byte offset on
the wire precludes both out-of-order segment serialization and out-of order
segment writes.
2. If there were a reason to, does the current API expose the on-wire
reference representation? Is the current representation effectively part of
the API?
Jonathan
On Mon, Jun 5, 2023 at 7:32 AM 'Kenton Varda' via Cap'n Proto <
capnproto@googlegroups.com> wrote:
> Hi Gokul,
>
> There's currently no way to "inline" one struct into another.
>
> The fundamental problem you have here is this: Say you have a list
> containing pointer values, and the list is actually at the end of the
> message. So, you can resize it without fragmentation. You add one new
> element. Then you populate the element, by allocating the pointer values
> that go into it. These new allocations are added to the end of the message,
> therefore the list is no longer at the end, and so can no longer be resized
> without fragmentation. Yes, in theory, if you could remove all of the
> objects allocated past the end of the list, then you could perhaps resize
> it again. But, then you'd have to bring those object back again, added to
> the end of the list. Each time you added a new element, the number of
> objects that you are rolling back and forward every time increases, so the
> overall time complexity ends up being O(n^2).
>
> You might want to consider an alternative design: Instead of a list, maybe
> you want a stream. In a streaming approach, you would append each item to
> your byte stream as a new encoded message. The down side of this approach
> is that you cannot easily jump to a random location in the list; you must
> parse the items in order. But maybe that's OK for your use case.
>
> A third approach could combine the two: You could create a stream of
> messages, and separately maintain an index into that stream. The index
> would store the starting byte offset of each message in the stream, so you
> can seek to it. The elements of the index are fixed-size (just an integer),
> so you could maintain the index as a Cap'n Proto List(UInt64) or the like.
>
> -Kenton
>
> On Wed, May 31, 2023 at 10:14 AM Gokul Rajiv
> wrote:
>
>> Hi Kenton,
>>
>> As a follow up to the case of structs containing pointer/non-primitive
>> types, might there currently exist workarounds to being able to resize
>> lists of these structs (like the one below) at the back of a message:
>> perhaps removing the allocated non-primitive data or embedding them inline
>> in the struct?
>>
>> ```
>> struct FourPoints {
>> pt1 @0 :import "vector2.capnp".Vector2f; # bottom-left
>> pt2 @1 :import "vector2.capnp".Vector2f; # bottom-right
>> pt3 @2 :import "vector2.capnp".Vector2f; # top-right
>> pt4 @3 :import "vector2.capnp".Vector2f; # top-left
>> }
>>
>> # the size of TagDetection is known
>> struct TagDetection {
>> id @0 :UInt32;
>> hammingDistance @1 :UInt8;
>> tagSize @2 :Float32;
>> areaPixel @3 :Float32; # number of pixels the tag occupies in the
>> image
>>
>> tagCenter @4 :import "vector2.capnp".Vector2f;
>>
>> # corners
>> pointsPolygon @5 :FourPoints;
>> pointsUndistortedPolygon @6 :FourPoints;
>>
>> poseInCameraFrame @7 :import "se3.capnp".Se3; # in RDF camera frame
>> }
>> ```
>>
>> Of course, I could manually list the primitive fields of the constituent
>> non-primitive types of the struct, but I'm trying to avoid having to do
>> this.
>>
>> - Gokul
>> On Monday, December 12, 2022 at 9:22:22 PM UTC+8 Hui min wrote:
>>
>>> Hi Kenton,
>>>
>>> Got it, it makes sense. So if I remove `labelString` data from the
>>> definition, I could use truncate function to operate my detections @4
>>> :List(Detection2d); object. Thanks!
>>>
>>> On Tuesday, 6 December 2022 at 10:43:17 pm UTC+8
Re: [capnproto] [Feature Request] Putting List() object at last and allow reuse of the MallocMessageBuilder
Hi Gokul,
There's currently no way to "inline" one struct into another.
The fundamental problem you have here is this: Say you have a list
containing pointer values, and the list is actually at the end of the
message. So, you can resize it without fragmentation. You add one new
element. Then you populate the element, by allocating the pointer values
that go into it. These new allocations are added to the end of the message,
therefore the list is no longer at the end, and so can no longer be resized
without fragmentation. Yes, in theory, if you could remove all of the
objects allocated past the end of the list, then you could perhaps resize
it again. But, then you'd have to bring those object back again, added to
the end of the list. Each time you added a new element, the number of
objects that you are rolling back and forward every time increases, so the
overall time complexity ends up being O(n^2).
You might want to consider an alternative design: Instead of a list, maybe
you want a stream. In a streaming approach, you would append each item to
your byte stream as a new encoded message. The down side of this approach
is that you cannot easily jump to a random location in the list; you must
parse the items in order. But maybe that's OK for your use case.
A third approach could combine the two: You could create a stream of
messages, and separately maintain an index into that stream. The index
would store the starting byte offset of each message in the stream, so you
can seek to it. The elements of the index are fixed-size (just an integer),
so you could maintain the index as a Cap'n Proto List(UInt64) or the like.
-Kenton
On Wed, May 31, 2023 at 10:14 AM Gokul Rajiv
wrote:
> Hi Kenton,
>
> As a follow up to the case of structs containing pointer/non-primitive
> types, might there currently exist workarounds to being able to resize
> lists of these structs (like the one below) at the back of a message:
> perhaps removing the allocated non-primitive data or embedding them inline
> in the struct?
>
> ```
> struct FourPoints {
> pt1 @0 :import "vector2.capnp".Vector2f; # bottom-left
> pt2 @1 :import "vector2.capnp".Vector2f; # bottom-right
> pt3 @2 :import "vector2.capnp".Vector2f; # top-right
> pt4 @3 :import "vector2.capnp".Vector2f; # top-left
> }
>
> # the size of TagDetection is known
> struct TagDetection {
> id @0 :UInt32;
> hammingDistance @1 :UInt8;
> tagSize @2 :Float32;
> areaPixel @3 :Float32; # number of pixels the tag occupies in the image
>
> tagCenter @4 :import "vector2.capnp".Vector2f;
>
> # corners
> pointsPolygon @5 :FourPoints;
> pointsUndistortedPolygon @6 :FourPoints;
>
> poseInCameraFrame @7 :import "se3.capnp".Se3; # in RDF camera frame
> }
> ```
>
> Of course, I could manually list the primitive fields of the constituent
> non-primitive types of the struct, but I'm trying to avoid having to do
> this.
>
> - Gokul
> On Monday, December 12, 2022 at 9:22:22 PM UTC+8 Hui min wrote:
>
>> Hi Kenton,
>>
>> Got it, it makes sense. So if I remove `labelString` data from the
>> definition, I could use truncate function to operate my detections @4
>> :List(Detection2d); object. Thanks!
>>
>> On Tuesday, 6 December 2022 at 10:43:17 pm UTC+8 ken...@cloudflare.com
>> wrote:
>>
>>> Hi Hui,
>>>
>>> Again sorry for the slow reply.
>>>
>>> In fact, the functionality you suggest does exist today, in the form of
>>> `capnp::Orphan::truncate()`, which can be used to resize a list
>>> (truncate *or* extend), doing so in-place if possible. If the list is at
>>> the end of the message, it's possible it can be extended in-place. To use
>>> it, you would do:
>>>
>>> ```
>>> auto orphan = reader.disownDetections();
>>> orphan.truncate(newSize);
>>> reader.adoptDetections(kj::mv(orphan));
>>> ```
>>>
>>> HOWEVER, there is a problem that might apply to your sample use case:
>>> Your `Detection2d` struct contains `labelString @1 :Text`, which is a
>>> pointer type. When you set this field to a string value, the string is
>>> allocated at the end of the message. This means your list is *not* at the
>>> end of the message anymore, so you are no longer able to resize the list to
>>> make it longer. To be able to extend your list, you will need the list to
>>> contain only primitive types, so that it stays at the end of the message.
>>>
>>> -Kenton
>>>
>>> On Sat, Nov 5, 2022 at 9:16 PM Hui min wrote:
>>>
Hi Cap'n Proto Team,
Thanks for the amazing tool you have created so far.
Understand that with the current design of arena style memory
allocation, we cannot simply reuse the message, and re-init List() object
to send it again. This will cause the message to grow every time we send
(memory leak).
However, sending variable length data is still pretty common practice.
If we have to reallocate a brand new heap for new message, it is quite
wasteful. In most cases however, the variable length list is
