Capnp serialization

[codepilot]

Specifically:

https://capnproto.org/encoding.html#canonicalization

RapidWright encodes as a message, with a segment list header, inside of gzip.

I purpose making the files for the contest, or even in general for RapidWright use the canonical encoding. It allows for streaming reading and writing of files with tiny memory usage. Also, it allows for a unique bit representation for the messages, for taking a hash for instance.

The change would be invisible to anyone who doesn't care about the specific encoding as it is a subset of valid encodings.

If consensus forms around this, I volunteer to get it done quickly in Java for RapidWright. I already made the needed encoder/decoder in typescript and c++ for use in browser as JavaScript and Wasm. I will post the repository in a reply to this shortly, probably early next week.

Thanks,

Daniel

[eddieh-xlnx]

Hi @codepilot. Great observations. It sounds like you want streaming read/write capabilities so that when reading you can stream through the file just once to pluck out the important subset of data (which you would need to copy out of the stream, rather than use zero-copy) without holding the entire message in memory -- is that right?

Currently, I think I can see a number of issues:

• Firstly, capnproto-java does not seem to support canonical output. Granted, that is a ticket from 2015, but I haven't found any mention to the contrary. This would mean the only option here would be some external post-processing to transform the capnproto-java's non canonical message to a canonical one.
• Writing such messages would likely impose additional constraints on the writer, due to the need for preorder.
• Likewise, it would also mean that incremental updates to an existing message (overwriting existing preorder object pointers with postorder pointers) like I do in nxroute would not be possible.
• Canonical ordering limits the message to a single segment, which would further limit our ability to handle large messages.

In our profiles, we've seen Interchange I/O only be a small amount of runtime compared to solving the routing problem, and the Physical Netlist should not consume all that much memory. One thing I have been considering is providing the benchmarks in non-gzipped form so that the entire file can be mmap-ed too.

I'm open to be convinced otherwise though.

[codepilot]

Stream to create JSON for example, preorder is perfect for that. I have that working. Canonical embedded in gzip, can stream from the gzip to json to gzip to return in a streaming way from a server for instance.

I can try to add to capnproto-java or just make a small standalone java class for the conversion. IDK how quick they accept pull requests.

I commented on that issue capnproto/capnproto-java#14 (comment)

I am leaning towards a post-processing step in the benchmark-producing code.

Also, canonicalization does not need or use the schema, so the code to do it is very short.

Only 2 passes are needed, first pass to calculate the sizes of children, second pass streams out to file, no whole-allocation needed.

Shouldn't effect nxroute or anything as long as canonical order isn't required from participants.

Canonical ordering could remove the use of segments entirely. Relative pointers are limited to 4GB, which would mean consecutive child pointers of a struct would limited to 4GB.

It may not be good to adopt this everywhere, but only for interchange output when specially desired.

Canonical files that can be mmap-ed would be my ideal, and I would use a stand alone thing in my own code to make such if not provided.

Daniel

[codepilot]

Already got a reply capnproto/capnproto-java#14 (comment)
I will try to put it there.

Daniel

[eddieh-xlnx]

I'm all for allowing more efficiency of the FPGA Interchange Format, so if you see this as a bottleneck (it's not intended to be!) then I'm open to optionally providing the benchmarks in this canonical yet still standard-compliant form.

It's worth emphasizing (at the risk of being long-winded!) that the contest's scoring criteria does not directly reward memory efficiency (as long as it does not exceed a hard limit, which is 64GB RAM currently). The most significant reward is wall clock runtime, and in our profiles this runtime is dominated by solving the routing problem, with Interchange I/O only contributing a small portion to this. However, I can't discount that memory efficiency has an indirect effect on runtime, nor can I discount (nay, I can instead hope for!) that the routing portion becomes the minority component of runtime and I/O the majority in which case looking at this optimization makes sense!

[codepilot]

I am starting to do some routing successfully in my implementation. Serialization/deser is a significant portion of time lol. I suppose that is a good thing? But, if we could have an option for non-gzipped, canonical form input/outputs that would be noticeably quicker for me.

[eddieh-xlnx]

Really happy to hear that! Let's say I provide all benchmarks in an uncompressed form. Under this regime, my understanding is that due to capnp's zero-copy approach, deserialization is a case of loading (or mmap-ing) this binary file into memory.

I'm less clear about what the most efficient method for serialization is. Currently, RWRoute transforms the FPGAIF message into its own (RapidWright's own) data model, and then on completion it reconstructs a new FPGAIF message. NXRoute currently copies the original message so that it can modify it, and then writes that new copy to disk. What's interesting with NXRoute is that it only needs to make incremental modifications (after all, it only needs to add PIPs and in fact is not allowed to touch anything else), however, it appears that official capnp advice is that it does not support mutating existing messages since it can be (a) unsafe with untrusted input (not applicable here) and (b) can introduce leaks/holes in the message since any overwritten values become disowned orphans occupying space. I'd be fine with such leaks/holes if it can save me doing a big memory copy.... I think it might be possible to do this in the original C++ library, but I haven't figured out a way to do this in pycapnp yet.

In any case, I continue to be open to using the canonical format if you can show me some data of its benefits. You can contact me privately with this if you don't want to post it.