Open doganulus opened 3 years ago
I don't want to discourage people from exploring this, however while I am probably the person that originally brought up delta-encoding as an alternative in the context of OSI, I brought it up more as a last resort alternative, not as something to positively persue:
Any delta-encoding scheme increases complexity in the protocol and the state machines, which is fairly undesirable in the context of OSI due to the validation concerns. When OSI is e.g. used for the validation of safety critical autonomous driving functions, the simulation and its models must also be validated. This is already a fairly tall order, without the added complexity in state maintenance on both sides.
In terms of performance, delta-encoding is also fairly likely to be at least a double-edged sword:
If one wants to achieve maximal performance, models and simulators are best kept in the same process (address space), since that will be the fastest way to transport data and have the minimum amount of context switches per simulation step. In that case it is unclear whether reducing the amount of data transfered (thereby reducing memory pressure) will outweigh the computational complexity due to the encoding/decoding overhead (mispredicted branches, etc.). This is even more true for encoding schemes that more closely resemble in-memory data layouts, like flatbuffers, which often allow usage of data without the decoding step.
If on the other hand one already employs an architecture that distributes models across address spaces (or even worse across the network), then performance is already taking a huge hit due to the latency alone; delta-encoding might help in that case, but it seems like fixing the wrong problem. In any case such use cases could employ their own over-the-wire encoding scheme to aleviate the bandwidth hit.
We have many low-hanging fruit in terms of performance problems, which should be persued first, IMHO:
If those avenues do not provide sufficient performance, then I think more radical proposals are needed, with different delta-encoding schemes (and even compression schemes) being on the table.
@pmai Thank you for your comments. That's great because I think the opposite, this is a conceptual issue (together with other temporal aspects) that should be considered early. Hence I am here to help the standardization efforts to reach a solid foundation to handle/check/generate temporal sequences regardless of the message content.
As you have described, there is a risk for tools, simulators, and other implementations to be hit by performance problems when things were getting more and more complex. Since I don't see any way to contain everything inside monolithic applications, these messages will be transmitted from one place to another. From one tool to another. No matter what. At the core of the simulator, we may not want to delta-encoded messages. That's fine then we don't. But I think OSI, as being an interface to other applications at the periphery, must support it by default.
This is also a great way to represent static information. Indeed a static field is just a regular field, which is never updated during simulation. No need to filter and make a disctinction between static/dynamic. Just set it in the first message and don't update. And who knows maybe I need to update static
info on-the-fly...
Said those, this is not even the first use case. Delta-encoding is widely used to reduce the size of logfiles. See Value Change Dump (.vcd) format for digital circuit simulators for example. And we have the same use case here for driving simulations. Whether you do a post-simulation-analysis or replay over logfiles, we want them compact.
Below is how I would approach to the solution in the context of the OSI.
First of all, the bulk of the task is already done by protocol buffers and flatbuffers. From the OSI perspective (as an interface), the remaining things we should do is:
the same as before
or no change
This (1) was default in proto2
but changed in proto3
and then added later here. It is also added to flatbuffers recently here. And (2) is not the business of the serialization format so they keep it as null
.
The rest is up to tools, simulators, implementations. They do not have to use missing fields but we make the standard ready when they choose to implement.
Describe the feature
This issue discusses the delta encoding feature mentioned here. The idea is to encode just fields which change in an OSI trace file over time. Hence would reduce the file size and better the performance of any simulation tool which uses delta encoding.
This issue illustrates the basic concept and aims to start a discussion/documentation/formalization for this important feature.
Describe the solution you would like
An OSI trace file represents a temporal behavior that maps points in time to fully populated OSI messages. Below I would proceed over examples on how to represent them and I use JSON syntax for simplicity.
Below is a discrete time behavior as time field implicitly increases 1 time unit per message and each message is fully populated. This would be the golden representation for a temporal behavior but also it is super-inefficient when time unit is chosen small (e.g. nanoseconds as currently set).
Often we want to use a small time unit when denoting time as complex systems and their components operates on many different timescales. The choice of small time unit creates a lot of repetitive observations that can be handled by compressing the behavior in time, only recording time points when something changed, as follows:
This is what I would call a dense time behavior and repeating messages are skipped and we add a time field (stamp) not to lose where we are in time. Hence, we can jump an arbitrary amount of time at each new message. In practice, we just start at this level and currently how it is done in OSI and elsewhere.
Up to now, this was just an introduction but I also want to show that this is a half-way practice as we can compress more, using delta-encoding.
Finally I show the desired delta-encoded representation compressed both in time and value.
It is important that the meaning of temporal behavior didn't change from (1) to (3) while the size would be significantly smaller in practice. That's easier to read/write/copy/transmit.
Describe alternatives you have considered
In the example above, we apply the concept of forward persistence, that is, once a field set in time, it is interpreted to hold its value until set again. The backward persistence, that is, we interpret the field value holds since last time point, is also possible but the former is chosen because it is the standard behavior of variable assignment in programming languages.
Describe the backwards compatibility
This feature alters the meaning of missing fields in OSI messages ("missing -> as same as before", previously "missing -> default value or null") for all field types. Please see the topic of Field Presence for
protobuf
s and Nullable Scalar forflatbuf
s. Whileproto2
support explicit field presence for scalar, we need to handle it explicitly forproto3
andflatbuffers
. This may create a backward compatibility issue.Additional context