I do not know when/if the delta compression will be needed at all, but this is a thought that I've stumbled upon and need to write down.
Currently, augs::object_delta specialization for types that are memcpy-safe does a bytewise delta compression that is completely unaware of the underlying structure layout. This is rather inefficient in light of this new strategy:
Let the delta compression routine introspect recursively both the encoded object and the object encoded against: that recursion would stop only with types satisfying std::is_enum or std::is_arithmetic (later maybe also std::bitsets), hereafter named "leaves". Keep an index variable that is incremented for every leaf checked for difference.
If corresponding leaves of the two objects differ, write index into the buffer and write bytewise content of the new leaf.
Pros:
Unlike bytewise compression, and since the compiler knows the sizes of the fields in advance, we completely avoid writing the counts of changed bytes, cutting the amount of collateral data in half (on average).
Unless in extreme cases, our indices can always be unsigned chars, as it will suffice for structures having as many as 255 fields in total. It is however very probable that a structure can exceed 255 bytes for whom the bytewise compression must either use an unsigned short or some tricky bitfields.
Cons:
If the whole object changes, that strategy is inferior to the current one, as it writes all indices instead of a single "changed span" indicator. In case of sparse modifications however, this will be mostly superior.
Our Introspector-generator will need a modification that will make it possible to know the number of fields in compile time, to know if unsigned char will suffice for storage of indices.
The new approach will have worse time performance as a loop with bytewise comparison (current approach) can be expected to fit better in cache than the code generated for introspection.
geneotech
commented
6 years ago
I do not know when/if the delta compression will be needed at all, but this is a thought that I've stumbled upon and need to write down.
Currently,
augs::object_deltaspecialization for types that are memcpy-safe does a bytewise delta compression that is completely unaware of the underlying structure layout. This is rather inefficient in light of this new strategy:std::is_enumorstd::is_arithmetic(later maybe alsostd::bitsets), hereafter named "leaves". Keep anindexvariable that is incremented for every leaf checked for difference.indexinto the buffer and write bytewise content of the new leaf.Pros:
unsigned chars, as it will suffice for structures having as many as 255 fields in total. It is however very probable that a structure can exceed 255 bytes for whom the bytewise compression must either use anunsigned shortor some tricky bitfields.Cons:
Introspector-generatorwill need a modification that will make it possible to know the number of fields in compile time, to know ifunsigned charwill suffice for storage of indices.