<div dir="ltr">Hi Guys,<div><br></div><div class="gmail_extra"><div class="gmail_quote">On Tue, Mar 15, 2016 at 11:46 AM, Levente Uzonyi <span dir="ltr"><<a href="mailto:leves@caesar.elte.hu" target="_blank">leves@caesar.elte.hu</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"> <br>Hi Clément,<br>
<br>
On Tue, 15 Mar 2016, Clément Bera wrote:<br>
<br>
(no quote again, sorry)<br>
<br>
So, the idea is to add a counter to each cache entry, and increase it on each hit. Once a counter reaches a given limit, divide all counters by two[1], and optionally do housekeeping stuff.<br>
By housekeeping I mean removing entries with zero counter value, resorting the entries based on the counter values, and optionally reverting to a single method when there's only one cache entry left.<br>
By optionally I mean that if you don't want to do the housekeeping every time the limit is reached, then another counter can be introduced, so that only every nth time will housekeeping occur.<br>
Since there are at most six cache entries, sorting can be done by Insertion sort or a hardcoded Optimal sorting network. The former would be simple and efficient, the latter could be even more efficient but more complex as well.<br>
<br>
In practice this can be done (at least) two ways:<br>
<br>
1. If there's a free byte at each entry, then the cache entries can store their own counters. If we use single byte counters, then it's practical to use 256 as the limit. That way division happens when the counter overflows. That takes at least 128 cache hits between two divisions, but if we eventually revert to a single method when there's only one entry left in the PIC, then the average number will be slightly higher than 128.<br>
<br>
Pros:<br>
- simple bookkeeping<br>
- sorting can be done in-place<br>
Cons:<br>
- there's probably no free byte<br>
- if we don't want to do the housekeeping too often, then the PIC will need a few more extra bytes to store another counter for that<br>
<br>
2. Add a single 64-bit word to the PIC. The lower 6 bytes can be used for the 6 counters, one per cache entry. The remaining two bytes can hold the housekeeping counter.<br>
<br>
Pros:<br>
- still fairly simple bookkeeping, but overflows will have side-effects on the next byte. This can be worked around by leaving an empty bit<br>
between the counter bytes, at the cost of reducing the size of the housekeeping counter. Another option is to check the counter value before incrementing it to avoid overflows altogether.<br>
- dividing all counters by two can be done in a few machine instructions<br>
- 7-bit or 9-bit counters can be used as well<br>
Cons<br>
- incrementing a counter is a bit more complex<br>
- sorting is trickier because the counter values will have to be swapped as well<br>
<br>
Assuming there's no free byte, I'd start straight with 2., but even adding a 64-bit word to a PIC doesn't seem too easy.<br>
<br>
Levente<br>
<br>
[1] This scheme holds information about not that recent hits as well, but the effect of the past decreases exponentially, so it's a fairly good approximation of the most recent hits without the need to store any additional data. I came up with this method a few years ago, yet I still couldn't find out what it's called.<br></blockquote></div><br><div><div><br class="">Reorganizing 6-element PICs doesn't really make sense. The cost of the counters would likely outweigh the benefits of reordering the PICs. Look at the time taken for a monomorphic send vs the worst case PIC send (6th case), vs a megamorphic send:</div><div><br></div><div><div>| n |</div><div>n := 1000000000.</div><div>{[| v |</div><div> v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>i < 1 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]].</div><div> [| v |</div><div> v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 1 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]].</div><div> [| v |</div><div> v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 6 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]].</div><div> [| v |</div><div> v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 7 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]]} collect: [:ea| ea timeToRun] #(2716 7013 7376 8350)</div></div><div><br></div><div><br></div><div>So on a 2.2GHz MacBook Pro Core i7 the monomorphic send of #species (block 2) takes (7.013 - 2.716) / 1,000,000,000, = 4.3 nanoseconds; the polymorphic send in the 6th case of a PIC (block 3) takes (7.376 - 2.716) / 1,000,000,000, = 4.66 nanoseconds. Only the open PIC send (full hashed lookup) takes significantly longer, (8.35 - 2.716) / 1,000,000,000 = 5.63 nanoseconds.</div><div><br></div><div>Let's add a counter; this is probably a lot more expensive than a VM counter implementation, but it gives us a sense of scale.<br><div><br></div><div>| n |</div><div>n := 1000000000.</div><div>{[| v c |</div><div> c := 0. v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>c := c + 1.</div><div><span class="" style="white-space:pre"> </span>i < 1 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]].</div><div> [| v c |</div><div> c := 0. v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>c := c + 1.</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 1 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]].</div><div> [| v c |</div><div> c := 0. v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>c := c + 1.</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 6 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]].</div><div> [| v c |</div><div> c := 0. v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>c := c + 1.</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 7 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]]} collect: [:ea| ea timeToRun] #(3399 7755 8361 9017)<br><br>So a counter adds approximately #(7755 8361 9017) sum - #(7013 7376 8350) sum / (#(7013 7376 8350) collect: [:eq| ea - 2716]) sum = 16% overhead, whereas the difference between a monomorphic send and the worst case polymorphic send is 7376 - 2716 / (7013 - 2716) asFloat = 8% slower. So the maximum improvement counters could make would be 8%. Even if their cost fell to 1/4 of the cost above they would cost 50% of the maximum return they could deliver. It's not worth the complexity; the gains would be in the noise.</div></div><div><br></div><div><br></div><div><N.B.> The above PIC sends contain an error in my methodology. Tim redesigned PICs late last year so that a two element PIC does a test and then jumps to the 6th case to perform the next test. If the PIC is extended that jump is modified to jump to the 5th case, the next extension changes to the 4th case and so on. So in fact, to measure the cost of a send to the 6th element of the PIC we need to change v back to the have the class of the 2nd case:</div><div><br></div><div><div><span class="" style="white-space:pre"> </span>[| v |</div><div><span class="" style="white-space:pre"> </span> v := 1.</div><div><span class="" style="white-space:pre"> </span> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 7 ifTrue: [v := #(1.0 #one 'one' #[1]. 1.0. $1. #(1)) at: i]]].</div></div><div><br></div><div>If you try this the above numbers don't change significantly, so I've been lazy and haven't redone my analysis, but here's an example run:</div><div><br></div><div><div>| n |</div><div>n := 1000000000.</div><div>{[| v |</div><div> v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>i < 1 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]].</div><div> [| v |</div><div> v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 1 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]].</div><div> [| v |</div><div> v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 7 ifTrue: [v := #(1.0 #one 'one' #[1]. 1.0. $1. #(1)) at: i]]].</div><div> [| v |</div><div> v := 1.</div><div> 1 to: n do:</div><div><span class="" style="white-space:pre"> </span>[:i|</div><div><span class="" style="white-space:pre"> </span>v species.</div><div><span class="" style="white-space:pre"> </span>i < 7 ifTrue: [v := #(1.0 #one 'one' #[1]. $1. #(1)) at: i]]]} collect: [:ea| ea timeToRun] #(2778 7370 7683 8683)</div></div><div></N.B.></div><div><br></div><div><br></div><div>Some remarks.</div><div><br></div><div>Counters are expensive. Sista already goes to some effort to minimise their costs. We count conditional branches instead of full sends. The green book presents measurements on the Smalltalk-80 V2 image of 1983 that says conditional branch bytecodes (as in inlined ifTrue:ifFalse:, and: to:do: et al) are 6 times less frequent than send bytecodes, and in today's code that's likely fallen a little as people write more OO code.</div><div><br></div><div>Architectural solutions such as Spur and Sista offer much mofre substantial gains; Spur shows a -40% speedup across a range of benchmarks. I expect Sista will deliver more when we are more aggressive with register allocation and the range of optmizations we implement although right now we're seeing similar gains to Spur. My expectation is based both on the success of other adaptive optimizers, and my experience in tuning OO systems, where the first impelmentation is almost universally slower than the one it replaes, the full gains only cming after careful performance measurement and tuning; Sista is very young as yet.</div></div><div><br></div><div class="gmail_signature"><div dir="ltr"><div><span style="font-size:small;border-collapse:separate"><div>_,,,^..^,,,_<br></div><div>best, Eliot</div></span></div></div></div>
</div></div>