Steven Schveighoffer wrote:
On Mon, 19 Oct 2009 14:51:32 -0400, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> wrote:
I just wrote this to Sean and Walter and subsequently discussed it
with Walter. Walter thinks this should work. Does anyone have the time
and inclination to test this out? It would involve hacking into
druntime's implementation of ~= (I'm not sure what the function name
is). I'd really appreciate this; I'm overloaded as it is.
==================
In wake of the recent demise of T[new], I was thinking of finding ways
of making ~= efficient for T[].
Currently ~= is slow because accessing GC.sizeOf(void*) acquires a
global lock and generally must figure out a lot of things about the
pointer to make a decision.
Also, ~= is dangerous because it allows slices to stomp over other
slices.
I was thinking of solving these issues by keeping an LRU (Least
Recently Used) cache inside the implementation of ~=. The LRU would
only have a few entries (4-8) and would store the parameters of the
last ~= calls, and their cached capacities.
So whenever code calls arr ~= b, the LRU is searched first. If the
system finds "arr" (both bounds) in the LRU, that means the cached
capacity is correct and can solve the matter without an actual trip to
the GC at all! Otherwise, do the deed and cache the new slice and the
new capacity.
This also solves the lack of safety: if you request a growth on an
array you just grew, it's impossible to have a valid slice beyond
that array.
This LRU would allow us to keep the slice API as it currently is, and
also at excellent efficiency.
What do you think?
This is a very good idea. Incidentally, you only need the upper bound
location, the beginning location is irrelevant, since you don't grow
down.
Awesome, didn't think of that. So now more cases are caught:
auto a = new int[100];
a ~= 42;
a = a[50 .. $];
a ~= 52;
That wouldn't have worked with my original suggestion, but it does work
safely with yours.
What do you do in the case where the memory was recycled? Does a
GC collection cycle clean out the cache as well?
As you saw, there was some discussion about that as well.
This is better than my two previous ideas. The only drawback I see is
if you have many threads doing appending, or you are appending more than
8 arrays at once in a round-robin fashion, you would lose all the
benefit (although it shouldn't affect correctness). At that point
however, you'd have to ask yourself why you aren't using a specialized
appender type or function.
Yah. As I suspect a lot of code is actually doing round-robin naturally,
I'm considering using a random eviction strategy. That way performance
will degrade smoother. A more advanced algorithm would use introspection
to choose dynamically between LRU and random.
Andrei
