Delta generation

When storing or sending rather large serialized objects it might be unnecessary to send the whole object if the receiving part has knowledge about the object.

In this case, it might be tempting to produce a delta of the serialized object in order to minimize data sent, or data written to disk. For my case, it was mostly about data written to disk.

I decided to pretty quickly test if it was worth to produce a delta (diff) of the byte arrays in order to decrease the amount of bytes written to disk.

Approach

First I did the quickest possible implementation, diffing byte by byte in order to achieve to generate the delta. The procedure basically went:

for (i = 0; i < left.Length; i++)
{
if (left[i] != right[i])
{
//Diff in byte, do something
}
...
}

Running a benchmark on that approach immediately showed that it was as bad as it looks. It will give the smallest amount of bytes to write to disk but it's incredibly slow.

The benchmark consisted of writing 100 files, each being 10 Mb in size (10 * 1024 * 1024 bytes). Each file had 1% of its data modified in total, in 3 different places. I used random data to modify, so the output in reality in this particular benchmark was in average slightly below that as expected.

As seen above, the implementation did save fewer bytes to disk (around 1%) yet the total time was way above the full save, saving 1gb to disk compared to around 10mb for the trivial delta implementation.

As the delta handling took a whopping 90% of the total time, I decided to make a quick attempt at speeding it up with pointer arithmetic instead.

Unsafe pointer arithmetics in .NET

.NET allows unsafe pointer arithmetics using the unsafe keyword. In order to make it compile in the released version of dotnet core, you'll have to add

"buildOptions": {
"allowUnsafe": true
}

To the project.json file.

This was also a pretty trivial implementation, basically only changing to:

fixed (byte* bptrRight = right)
fixed (byte* bptrLeft = left)
{
long* ptrLeft = (long*)bptrLeft;
long* ptrRight = (long*)bptrRight;
for (i = 0; i < left.Length; i += sizeof(long))
{
var ptrIndex = i / sizeof(long);
if (ptrLeft[ptrIndex] != ptrRight[ptrIndex])
{
//Diff in long, do something
}
...
}

The above implementation is severely lacking in support for inputs, as it requires arrays in sizes divisable by sizeof(long). None of the implementations support shrinking the output array albeit they do support enlargening it.

It did however procude some interesting results:

As seen above, the time spent on delta handling decreased to about 15-20%. The bytes written on the other hand increased as expected, since it's now only a diff by 8 bytes at a time instead of 1.

It might be tempting to go further with it to make it fully working with different byte arrays but as the size of the array decreases, it only adds time rather than saves time. When IO bound it might be an option, but unless that it doesn't seem worth it with this trivial implementation at least.

The code can be found on github but I'd advise you to not use it for other thing than exploring.