Dynamic size lists and Orphans

[ma...@voltanet.io]

Hello guys,

I have to build a dynamic size list of elements T (capnp struct), in which its size I cannot deduce it before traversing the data structure (and traversing it twice does not work either).

I was trying to use a vector of Orphans (allocated by the Orphanate of the builder) as some of the threads were suggesting, but apparently they get 0ed once the auto references go out from scope(stack).

I had a std::vector<Orphan<T>>, and I was push_back() with std::move/kj::mv.  

Any idea on how to solve this issue? 

Thanks and regards

Marc

[Kenton Varda]

Hi Marc,

The orphans only get zeroed if they go out of scope without being adopted, but in sounds like you should be adopting them into your list in the end, right? It might help if you showed us your code.

Note that there is an awkward thing about doing this with a struct list, which is that a struct list is normally encoded "flat", with the structs appearing one after the other, not as a list of pointers. Therefore you can't directly adopt an Orphan<T> into a List<T>. You have a few options:

- list.adoptWithCaveats(i, kj::mv(vec[i])) will make a shallow copy of the struct in order to move it into the list. Any pointers within are moved over without a recursive copy. The original copy of the struct gets zero'd leaving a hole in your message, wasting space, which you may or may not care about.

- Instead of vector<Orphan<T>>, use vector<Orphan<SomeType>> where SomeType is a plain-old-C-struct containing members mirroring the fields of T. Sub-objects can be represented as orphans. Then when you actually create the List<T> later, you do a shallow copy by hand. This avoids leaving a zero'd hole.

- Instead of List<T>, use List<TBox>, where TBox is a struct which contains only one field of type T. This essentially turns your list into a list of pointers which allows you to adopt T's into it without caveats, but it makes your protocol uglier.

-Kenton

--
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.

[Marc Sune]

Hi Kenton,

Thanks for the answers. 

Inline:

On Sat, Oct 17, 2015 at 12:35 AM, Kenton Varda <ken...@sandstorm.io> wrote:

Hi Marc,

The orphans only get zeroed if they go out of scope without being adopted, but in sounds like you should be adopting them into your list in the end, right? It might help if you showed us your code.

Right. Basically;

x.capnp:

struct R{}

struct S{}

struct T {

     //Fixed fields

     data union {

         elem0 @9 : Void; 

         elem1 @10: R;

         elem2 @11: S;

         //...

     }

}

struct Operations{

   //Fixed fields

   listOps : List(T);

}

The code basically walks through a tree of data, where the elements can be modified while I am traversing. That's why I cannot pre-calculate the size of the List.

What I was doing (pseudo code):

scan_branch(..., capnp::Orphanage orphanage, std::vector<capnp::Orphan<T>> ops, ...){

    auto o = orphanage.newOrphan<T>();

    //Set fields of o, including union data with the appropriate init()

    ops.push_back(kj::mv(o));

}

And then after scanning all branches they are 0ed. What I just realised now is that I was doing a kj::mv(o) of the T reference got via get() method to the final List in Operations, instead of calling the adoption method; can this be the problem? Or there is something more wrong in there.

 

Note that there is an awkward thing about doing this with a struct list, which is that a struct list is normally encoded "flat", with the structs appearing one after the other, not as a list of pointers. Therefore you can't directly adopt an Orphan<T> into a List<T>. You have a few options:

- list.adoptWithCaveats(i, kj::mv(vec[i])) will make a shallow copy of the struct in order to move it into the list. Any pointers within are moved over without a recursive copy. The original copy of the struct gets zero'd leaving a hole in your message, wasting space, which you may or may not care about.

Ok. I would prefer to avoid these extra holes. The dataset (the list) can be big, and this wasting in the wire can become a problem later.

 

- Instead of vector<Orphan<T>>, use vector<Orphan<SomeType>> where SomeType is a plain-old-C-struct containing members mirroring the fields of T. Sub-objects can be represented as orphans. Then when you actually create the List<T> later, you do a shallow copy by hand. This avoids leaving a zero'd hole.

That's an option I already though about, but it seems to me a bit unnecessary (I have to define new types that are repeated, like T)

 

- Instead of List<T>, use List<TBox>, where TBox is a struct which contains only one field of type T. This essentially turns your list into a list of pointers which allows you to adopt T's into it without caveats, but it makes your protocol uglier.

Did not get this one. I will inspect the code. But I don't know if it would work with the struct having the data union.

Thanks and regards

marc

[Marc Sune]

Kenton,

Solved. I substituted:

        sr.initOp(ops.size());

        int i=0;

-       for(auto it = ops.begin(); it != ops.end(); ++it, ++i){

-               auto itt = (*it).get();

-               sr.getOp()[i] = kj::mv(itt);

-       }

+       for(auto it = ops.begin(); it != ops.end(); ++it, ++i)

+               sr.getOp().adoptWithCaveats(i, std::move(*it));

And all worked...

Funny enough, I had read it once already:

https://groups.google.com/forum/#!topic/capnproto/ONvRxloWZlw

But I could not find it when I really needed (why are google groups so badly indexed in Google?)

Trying to add some value here beyond repeating a question (sigh...); it might be useful for other developers to add an some code with dynamic size lists in the example set.

Cheers

Marc

[Kenton Varda]

Hi Marc,

Keep in mind that adoptWithCaveats() leaves holes in your message, which you said you'd prefer to avoid. It's definitely the easiest approach, though.

One of these days I plan to make the code generator also generate "POCO" equivalents of each type which would more readily support mutation at the expense of requiring a copy at serialization time...

-Kenton