Automatic branch deduplication

[paulovap]

This is an open question for now as I haven't done much research.

Flex/Flat protocol has the concept of reference, which create interesting properties to the payload, such as enabling random access without parsing and deduplicating data by just keeping one instance of the data and insert the reference to it for every other entry.

By exposing an API to add those "references", users can manually perform the deduplication. This is a straightforward approach and already can save a lot of data. But at cost of hand-coding those checks.

My question now is: Is it possible to automatically add branch deduplication, automatically, and efficient enough to be used in real scenarios?

An initial naive solution that come to mind is: Before writing maps and arrays into the buffer, we calculate it's hash we compare against previously stored hashes of the same type. If we have a match we deeply compare both branches and adds a reference if they are deeply equal.

Other things it comes to mind:

• Do we think this is worthy?
• Does it make sense to have a general solution to apply on fbs as well?
• Given we have lot of meta information about the elements, can we figure out a way to do a "perfect hash" and avoid deeply comparisons
• Any other alternative ideas?

[aardappel]

We have this for strings of course in some languages.

Doing it for tables sounds pretty "heavy" to me in cost, and it seems that use cases of sharing tables are fairly niche, i.e. the user will be very aware if they want it, or not.

That said, nothing against providing it as an option if its useful.

I guess the first step would an optional hash function for all tables/structs, maybe? One based on combining sub-hashes with XOR so it can be hierarchically be combined. Having such a function could be useful by itself, and would make it easier to track your own duplicates.

Of course, none of this should ever be automatically on, not just in terms of cost, but also because it would interfere with --gen-mutable etc.