<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On 14-lug-10, at 15:19, Steve Schveighoffer wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div>----- Original Message ----<br><blockquote type="cite">From: Fawzi Mohamed <<a href="mailto:fawzi@gmx.ch">fawzi@gmx.ch</a>><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><blockquote type="cite">----- Forwarded Message ----<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"><blockquote type="cite">From: Steve Schveighoffer <<a href="mailto:schveiguy@yahoo.com">schveiguy@yahoo.com</a>><br></blockquote></blockquote></blockquote><blockquote type="cite"><font class="Apple-style-span" color="#540000">[...]</font></blockquote><blockquote type="cite">I am not sure I follow, you mean using the new function to determine how many <br></blockquote><blockquote type="cite">pages really commit?<br></blockquote><blockquote type="cite">well indeed you would spare some cycles, but at the cost of using memory, not <br></blockquote><blockquote type="cite">sure it is really a win (the use of pages already<br></blockquote><br>I assume the newCapacity function is used to avoid constantly looking for new <br>memory to allocate. The theory being if you are appending, you don't want to <br>just allocate exactly what you need, you want to preallocate a little more.<br><br>At least when the current pool is exhausted, newCapacity is used to allocate a <br>fresh block, I just don't know why it's not used to extend the current block <br>(which is why I'm trying to add that feature).<br></div></blockquote><div><br></div>ok I understand, it makes sense.</div><div><br><blockquote type="cite"><div>One of the issues with the current GC is that getting a size of a memory block <br>that consists of hundreds or thousands of pages is that it is a linear search <br>for the end of the block. This is mitigated by the LRU cache, but once you <br>exceed the number of cache, performance should probably fall off a cliff <br>(however, it doesn't for reasons I don't understand). But when I extend a <br>block, it must do this same linear search to find the page size before doing an <br>extend. I'm trying to do that linear search as little as possible. All this <br>could probably be mitigated if the allocated length was somehow cached per <br>allocated page.<br></div></blockquote><div><br></div>I discussed about this with winterwar (wm4), I had proposed some enhancements, but it seems that most of these did not really improve things much.</div><div>(I was arguing for a global array with pool sizes, as I thought that it would be better from the caching prespective).</div><div>About the linear search a simple way would be to add some extra flags, like</div><div>PAGE_PLUS_0 PAGE_PLUS_1, PAGE_PLUS_2, PAGE_PLUS_3, PAGE_PLUS_4,...</div><div>and then use that to know that if you are at PAGE_PLUS_x you have to jump back at least 2^x pages.</div><div>with very few bits you can drastically reduce the jumps.</div><div>The idea is *not* o encode the exact jump, but just the position of the highest bit of the jump.</div><div>linear search is fast (and well cached), so you really win only if you encode large jumps, thus the exponential growth.</div><div>The other option is to encode the exact address (wm4 was rooting for that), but I feel that the extra memory used defeats the advantages.</div><div><br></div><div><blockquote type="cite"><div>I didn't write newCapacity, so I'm not sure about the theory behind it, or what <br>desirable properties for appending are. But it does make sense to me that if <br>you are continuously appending, you want to preallocate more than "just enough <br>to append the new data". How much more, I have no clue :) I assumed the <br>formula in newCapacity was written by someone who knows what they are doing. <br>Well, except for using the element size in the percentage formula.<br></div></blockquote><div><br></div>well the initial formula in tango clearly had a flaw (exploding for some arguments), I have reduced it to and interpolation between using </div><div><span class="Apple-tab-span" style="white-space:pre"> </span>a/100 percentage more space (geometric growth)</div><div>and adding something that grows proportionally to </div><div><span class="Apple-tab-span" style="white-space:pre"> </span>x/log2(x)</div><div>which is the average storage used by each bit of x (log2(x) is the number of bits of x).</div><div>x/log2(x) goes to inifinity for x=0, and grows less than just x for large x.</div><div>In the end I choose a functional form with 2 parameters (a,b, well minBits if one really wants, but I think it is not so useful).</div><div><br></div><div><blockquote type="cite"><div>[...]<br>The other factors are seemingly arbitrary, so I'm not sure how to tune those.<br></div></blockquote><br></div><div>Indeed I did not know a meaningful way to tune those parameters, so I just choose values that looked good and reasonable to me, and called it a day :).</div><div><br></div><div>Fawzi</div></body></html>