<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On 22 April 2014 15:28, Gabor Greif <span dir="ltr"><<a href="mailto:ggreif@gmail.com" target="_blank">ggreif@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Hi devs,<br>
<br>
after my intentionally "playful" EuroLLVM presentation (*) I think it<br>
would be time to get serious about merging to ToT. But we should<br>
probably find out whether an optimized algorithm is desired at all.<br>
<br>
So I'd solicit comments from the code owners (Use.{h,cpp}) and anybody<br>
who is interested. For closer scrutiny, the code is here:<br>
<<a href="http://llvm.org/viewvc/llvm-project/llvm/branches/ggreif/waymark-64-new/" target="_blank">http://llvm.org/viewvc/llvm-project/llvm/branches/ggreif/waymark-64-new/</a>><br></blockquote><div><br></div><div>
Just to stimulate discussion, here's another playful/bizarre idea for improving the current 2-bit waymarking scheme.</div><div><br></div><div>Use this encoding:</div><div><br></div><div>00 = s (stop)</div><div>01 = 1</div>
<div>10 = 2</div><div>11 = 3</div><div><br></div><div>Change the order of fields in a Use to be prev, next, value. I think we can guarantee that the first word of a User has 00 in its low order bits, so if you try to read just beyond the end of the Use array, it'll look like a stop tag.</div>
<div><br></div><div>Then the sequence goes like this, where I've used a colon to separate the real tags (in Uses) from the fake tag (in the first word of the User):</div><div><br></div><div>encoding: ...s121s112s32s22s12s3s1s:s</div>
<div>accesses: ...5876576546546545434332:</div><div><br></div><div>To decode this, skip digits until you reach a stop tag, and then read all the digits up to the next stop tag. The digits tell you how far to skip from the terminating stop tag to the start of the User, using a "3-adic numeration system" (<a href="http://en.wikipedia.org/wiki/Bijective_numeration">http://en.wikipedia.org/wiki/Bijective_numeration</a>):</div>
<div><br></div><div>0 = (empty string)</div><div>1 = 1</div><div>2 = 2</div><div>3 = 3</div><div>4 = 11</div><div>5 = 12</div><div>6 = 13</div><div>7 = 21</div><div>...</div><div>13 = 111</div><div>14 = 112</div><div>15 = 113</div>
<div>16 = 121</div><div>...</div><div><br></div><div>This is asymptotically better than the current system because it's (more or less) using base 3 instead of base 2 to encode the skip distances. However, it's probably not very good in practice, because it needs more accesses when there are only one or two Uses, which is probably the common case. Oh well.</div>
<div><br></div><div>Jay.</div></div></div></div>