<div dir="ltr">I forgot to Cc this (and some other unimportant replies) to the list.<div><br></div><div>Jay.<br><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">Jay Foad</b> <span dir="ltr"><<a href="mailto:jay.foad@gmail.com">jay.foad@gmail.com</a>></span><br>
Date: 23 April 2014 09:50<br>Subject: Re: [LLVMdev] [RFC] 3-bit Waymarking<br>To: Gabor Greif <<a href="mailto:ggreif@gmail.com">ggreif@gmail.com</a>><br><br><br><div class="">On 22 April 2014 15:28, Gabor Greif <<a href="mailto:ggreif@gmail.com">ggreif@gmail.com</a>> wrote:<br>

> 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>
<br>
</div>Hi Gabor,<br>
<br>
I've looked at your slides. I have two comments about the new<br>
waymarking scheme, as described in your "Comparison" slide.<br>
<br>
<br>
1. I assert without proof :-) that most Values have two Uses, so by<br>
far the worst thing about the current scheme is that it takes *2*<br>
accesses to get from the penultimate Use to the User. When you upgrade<br>
from 2 to 3 bits you get four more tags to play with, so how about<br>
using one or more of them as additional Full Stop tags, that tell you<br>
exactly how far away the user is? E.g. if you created four more full<br>
stop tags you could go from this access pattern:<br>
<br>
2 bits: ...654654343221<br>
<br>
to this:<br>
<br>
3 bits: ...543432211111<br>
<br>
I realise that this is asymptotically worse than your scheme, but I<br>
reckon it might be better in the very common case where there are few<br>
Uses.<br>
<br>
<br>
2. Your "number of accesses" is a bit misleading. I think all the<br>
numbers should be increased by one, because after following the<br>
waymarks we *always* look at the next word as well, to see whether it<br>
is the start of the User, or a pointer to the User. So another way of<br>
spending the four new tags would be to have different kinds of full<br>
stop:<br>
<br>
S = full Stop, User follows inline<br>
P = full stoP, Pointer to User follows<br>
<br>
This avoids the extra access in the (hopefully common) case where the<br>
User follows inline.<br>
<br>
<br>
I reckon these two ideas can be combined, e.g. you could have five<br>
full stop bits as follows:<br>
<br>
P = full stoP, Pointer to User follows<br>
S0 = full Stop, User follows inline after this Use<br>
S1 = full Stop, User follows inline after 1 more Use<br>
S2 = full Stop, User follows inline after 2 more Uses<br>
S3 = full Stop, User follows inline after 3 more Uses<br>
<br>
This would optimise for the case where the Uses are inline, and there<br>
are <= 4 of them.<br>
<span class="HOEnZb"><font color="#888888"><br>
Jay.<br>
</font></span></div><br></div></div>