<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Mon, Dec 11, 2017 at 3:50 PM Rahul Chaudhry via gnu-gabi <<a href="mailto:gnu-gabi@sourceware.org">gnu-gabi@sourceware.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">A simple combination of delta-encoding and run_length-encoding is one of the<br>
first schemes we experimented with (32-bit entries with 24-bit 'delta' and an<br>
8-bit 'count'). This gave really good results, but as Sri mentions, we observed<br>
several cases where the relative relocations were not on consecutive offsets.<br>
There were common cases where the relocations applied to alternate words, and<br>
that totally wrecked the scheme (a bunch of entries with delta==16 and<br>
count==1).<br></blockquote><div><br></div><div>For the same issue in a different context, I recently implemented a scheme using run-length-encoding but using a variable stride.  So for a run of alternate words, you still get a single entry, but with stride 16 instead of 8.  In my application, most cases of strides > 8 are a run of only 2 or 3 but there are a few cases of dozens or hundreds with a stride of 16.  My case is a solution tailored to exactly one application (a kernel), so there is a closed sample set that's all that matters and the trade-off between simplicity of the analysis and compactness of the results is different than the general case you're addressing (my "analysis" consists of a few lines of AWK).  But I wonder if it might be worthwhile to study the effect a variable-stride RLE scheme or adding the variable-stride ability into your hybrid scheme has on your sample applications.</div><div><br></div><div>Since we're talking about specifying a new ABI that will be serving us for many years to come and will be hard to change once deployed, it seems worth spending quite a bit of effort up front to come to the most compact scheme that's feasible.</div></div></div><div dir="ltr">-- <br></div><div class="gmail_signature" data-smartmail="gmail_signature"><p dir="ltr"><br>
Thanks,<br>
Roland</p>
</div>