building messages front-to-back (into shared mem)

[Gregory Allen]

was "high-throughput data", https://groups.google.com/forum/#!topic/flatbuffers/wQFC11Y202Q

We are still looking at the possibility of using FlatBuffers to build a message *into* a shared memory region, aligned to the start of the buffer, and without a copy.

I think we would need to build the messages from front-to-back instead of back-to-front. The hurdle to this is that the offsets are unsigned, so they can't point backward.

Messages are limited to 2GB (via assert), so all these offsets could probably be treated as signed and nobody would ever notice.

Only the C++ and Go versions would change.
The Java and C# versions already treat these offsets as signed.

We did a preliminary test in C++ where we changed the offsets to signed, and all tests still pass.

A reader that treats the offsets as signed would be backward compatible: it would work with all data that has been saved up to this point. Such a reader would also be able to read message that were built front-to-back.

We could then make a ForwardFlatBufferBuilder that builds messages front-to-back, and the same reader could read a FlatBuffer regardless of which direction it was built.

I think we could do this without any public API change, and with a backward compatible format reader.

Thoughts?

[Wouter van Oortmerssen]

I have definitely considered making this change, as the backwards order is not as essential as it was in a previous iteration of the system.

That said, reasons why it is not an easy choice are:

- A lot of code to rewrite, since the order or writing permeates everything.

- Worse for streaming, as having the parents always before the children was a nice constraint, and on some devices seeking forward may be faster than seeking backwards. Though streaming would need generated code support which at the time of writing we don't even have yet.

- The verifier code currently makes use of the unsigned nature of offsets to guarantee there are no cycles. We'd have to modify it to instead guarantee that all offsets in a single buffer all point in the same direction, which is doable.

That, combined with the fact that the current system doesn't really have many disadvantages. Can you explain why your system needs forward ordering?

--
You received this message because you are subscribed to the Google Groups "FlatBuffers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to flatbuffers...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Gregory Allen]

I don’t think it’s possible to build a FlatBuffer message into a shared memory region without a copy unless messages can be built front-to-back. I deal with large arrays of sample data, and required extra copy make FlatBuffers a non-starter.

Just by making the offsets be signed (instead of unsigned), I think it’s possible to make:
- the builder build either forward or backward (it could be a parameter)
- the decoder able to hand either without caring

Streaming/partial decoding would still be possible if you build the a message backward (as is done now).

Again, some of the implementations already treat the offsets as signed. This would actually improve uniformity across languages.

I don’t think we can attempt front-to-back messages unless offsets can (optionally) be signed. Currently, they’re just limited to 2**31-1.

Thanks,
-Greg

Gregory E. Allen, PhD, Sr Engineering Scientist
Applied Research Laboratories: The University of Texas at Austin
512-835-3487

[mikkelfj]

On Friday, January 15, 2016 at 6:34:29 PM UTC+1, Gregory Allen wrote:

The change also affects the C language with the FlatCC compiler.

I don’t think it’s possible to build a FlatBuffer message into a shared memory region without a copy unless messages can be built front-to-back. I deal with large arrays of sample data, and required extra copy make FlatBuffers a non-starter.

 

Generally, flatbuffers currently need a copy step to retrieve data such as the API's are currently designed - can't speak of all languages though.

But there is no reason why a buffer cannot be generated directly into huge virtual address range back to front using mmap or the equivalent on windows. However, since the there is a 2GB limitation on the data, it is much simpler to just allocated a 2GB working buffer and start from back to front or front to back. The result is about the same on x64 platforms. The mmap approach has the downside that it page faults every 4KB or so unless memory is committed up front, which is exactly what a large malloc would do.

The above does not work well when dealing with a large amount of concurrent flatbuffer jobs because you need to commit significant memory.

When you are memory constrained due to many jobs (like in a web server), you need to reallocate as you grow the buffer. Here it also doesn't matter much which way you build the buffer, except back to front makes bookkeeping more interesting internally using negative offsets.

Where back-to-front really has a disadvantage is on-the-fly streaming where the full buffer is not constructed before transmission. Here the receiver needs to deal with negative offsets and reconstruct data rather than just using a dynamically growing array. For this reason I'd like to see front-to-back support.

Another issue is that in FlatCC which maintains a stack, there is extra copying in some cases due the back to front ordering, but it is not likely that this will be reimplemented more efficiently with front to back due to the complexity of it all.

Still, signed offsets would add a lot of freedom for optimizations.  If I were to start a new implementation, I really would have appreciated signed offsets.

But mostly it is more a matter of perception than a real problem.

 

As to verification:

FlatCC for C makes the same assumption about the unsigned offsets as FlatC for C++. But it also has a max nesting level setting. The verification is limited because it cannot trivially protect against malicously formed overlapping regions that do not exhibiti detectable buffer overruns but still makes in-place buffer modification unsafe. For this reason, I think the verification might as well just check for:

max nesting level

out of bounds

no 0 offset (self reference)

It might make some range checks a bit more expensive, or the opposite, compared to the current algorithm.

A more advanced check could also protect against cycles and overlapping regions, at a significant cost.

Just by making the offsets be signed (instead of unsigned), I think it’s possible to make:
 - the builder build either forward or backward (it could be a parameter)
 - the decoder able to hand either without caring

Yes, I think it is worth going for because it is such a simple change. The encoded does not have to make the move initially, but it is fair to require that the decoder unstands the signed offset. The sooner this change is made, the better.

The encoders can choose to optimize for different things, wrt. assumptions on forward vs reverse seek performance as Wouter suggests.

I don’t think we can attempt front-to-back messages unless offsets can (optionally) be signed. Currently, they’re just limited to 2**31-1.

In an upcoming version of FlatCC more work has been done to isolate the type system to simplify supporting multiple sizes. I think at some point a large flatbuffers format is required. 

Mikkel

[Wouter van Oortmerssen]

On Fri, Jan 15, 2016 at 9:34 AM, Gregory Allen <gal...@arlut.utexas.edu> wrote:

I don’t think it’s possible to build a FlatBuffer message into a shared memory region without a copy unless messages can be built front-to-back.

Why?

 

I deal with large arrays of sample data, and required extra copy make FlatBuffers a non-starter.

Just by making the offsets be signed (instead of unsigned), I think it’s possible to make:
 - the builder build either forward or backward (it could be a parameter)

That is impractical, as I wouldn't want to maintain 2 versions. It might be possible to allow both directions without duplicating code, but it will be tricky to keep it both readable and efficient.

 

 - the decoder able to hand either without caring

Streaming/partial decoding would still be possible if you build the a message backward (as is done now).

Again, some of the implementations already treat the offsets as signed. This would actually improve uniformity across languages.

Some languages don't have unsigned types. This doesn't mean they actually use the signed-ness.

[Gregory Allen]

On Jan 19, 2016, at 7:51 PM, Wouter van Oortmerssen <w...@google.com> wrote:

> On Fri, Jan 15, 2016 at 9:34 AM, Gregory Allen <gal...@arlut.utexas.edu> wrote:
>> I don’t think it’s possible to build a FlatBuffer message into a shared memory region without a copy unless messages can be built front-to-back.
>
> Why?

Said better: I don’t think it’s possible to build a FlatBuffer message to the *start* of a shared memory region without a copy unless messages can be built front-to-back. Or, if you know exactly how big it is ahead of time.

Think of writing into a memmap’d file. You can’t write into it using the current approach without a copy.

If you build front-to-back, you can build a message directly to the shared memory region, growing it as needed without any copying.

By having the offset be signed, you can build front-to-back.

[Wouter van Oortmerssen]

Ah ok, if the buffer has to start at the start of its parent buffer.

I was assuming that if you work with a shared memory block, since you typically can't predict the size of what you're encoding anyway, and thus you need a buffer with some slack, that a pointer inside the buffer as a starting point wouldn't be a problem.

For a mmap'd file you have a problem regardless: there's slack memory either at the start or at the end. Not sure if there's way to truncate either.