dsimcha wrote:
== Quote from Andrei Alexandrescu ([email protected])'s article
dsimcha wrote:
== Quote from Andrei Alexandrescu ([email protected])'s article
Steven Schveighoffer wrote:
On Thu, 19 Nov 2009 12:01:25 -0500, dsimcha <[email protected]> wrote:
== Quote from Andrei Alexandrescu ([email protected])'s
article
dsimcha wrote:
== Quote from Andrei Alexandrescu ([email protected])'s
article
Yes, it will be because the book has a few failing unittests. In
fact, I
was hoping I could talk you or David into doing it :o).
Andrei
Unfortunately, I've come to hate the MRU idea because it would fail
miserably for
large arrays. I've explained this before, but not particularly
thoroughly, so
I'll try to explain it more thoroughly here. Let's say you have an
array that
takes up more than half of the total memory you are using. You try
to append to
it and:
1. The GC runs. The MRU cache is therefore cleared.
2. Your append succeeds, but the array is reallocated.
3. You try to append again. Now, because you have a huge piece of
garbage that
you just created by reallocating on the last append, the GC needs
to run again.
The MRU cache is cleared again.
4. Goto 2.
This is not a matter of principles, but one of implementation. When you
GC, you can adjust the cache instead of clearing it.
Technically true, but what is a matter of principles is whether the
implementation
of arrays should be very tightly coupled to the implementation of the
GC. Fixing
this issue would have massive ripple effects throughout the already
spaghetti
code-like GC, and might affect GC performance. For every single
object the GC
freed, it would have to look through the MRU cache and remove it from
there if
present, too.
You perform the lookup via MRU cache (after mark, before sweep). I see
it as a single function call at the right place in the GC.
The point is that this **can** be done, but we probably don't **want** to
introduce this kind of coupling, especially if we want our GC model to
be sane
enough that people might actually come along and write us a better GC
one day.
What about implementing it as a hook "do this between mark and sweep"?
Then it becomes decoupled from the GC.
-Steve
I think these are great ideas, but you'd need to transport certain
information to the cache so it can adjust its pointers. Anyhow, I
believe this is worth exploring because it can help with a great many
other things such as weak pointers and similar checks and adjustments
(there was a paper on GC assertions that I don't have time to dig right
now. Aw what the heck, found it:
http://www.eecs.tufts.edu/~eaftan/gcassertions-mspc-2008.pdf
Andrei
The hook doesn't sound like a bad idea, but it raises a lot of issues with the
implementation details. These are things I could figure out given plenty of
time.
I'd like weak refs, too. However, I don't think this makes the short list for
D2
because:
1. Doing it at all properly requires a lot of thought about what a good design
for such an API should be and how to implement it efficiently.
2. I think we still need an ArrayBuilder or something because, while the MRU
would be reasonably efficient, it still wouldn't be as efficient as an
ArrayBuilder, and would do nothing to solve the uniqueness problem. Therefore,
I
think fleshing out ArrayBuilder is a higher priority. I was thinking of a
design
something like this:
abstract class Array {
// A bunch of final methods for .length, opIndex, etc.
// No .ptr or opSlice.
}
class UniqueArray : Array {
// Still no .ptr or opSlice. Has .toImmutable, which allows
// for conversion to immutability iff the elements are either
// pure value types or themselves immutable.
//
// Also, can deterministically delete old arrays on reallocation,
// since it owns a unique reference, leading to more GC-efficient
// appending.
}
class ArrayBuilder : Array {
// Add opSlice and .ptr. Appending doesn't deterministically
// delete old arrays, even if the GC supports this. No guarantees
// about uniqueness.
}
What does .toImmutable return? As far as I can tell making UniqueArray a
class can't work because by definition you give up controlling how many
references to the array there could be in a program.
Andrei
Sorry, forgot to flesh out a few details.
1. .toImmutable() returns an immutable slice, but also sets UniqueArray's
pointer
member to null, so no instance of UniqueArray has a mutable reference any
longer.
After this is called, the UniqueArray object will be invalid unless
reinitialized.
Ok, so destructive extraction. Perfect.
2. After thinking about this some more, the big issue I see is ref opIndex. We
can either:
a. Disallow it for both UniqueArray and ArrayBuilder.
b. Allow it for both UniqueArray and ArrayBuilder and accept
that a sufficiently dumb programmer can invalidate the
guarantees of UniqueArray by taking the address of one of the
elements and saving it somewhere. Probably a bad idea, since
assumeUnique() already works for the careful programmer, and
UniqueArray is supposed to provide ironclad guarantees.
c. Don't define opIndex in the abstract base class at all, thus
making Array almost useless as an abstract base class.
Welcome to my demons :o).
One possibility that I thought of for a long time would be to disallow
taking the address of a ref. That reduces the scope of the problem but
doesn't eliminate it:
void main() {
auto a = new UniqueArray(10);
fun(a[0], a);
}
void fun(ref int a, UniqueArray b)
{
auto imm = b.toImmutable();
// here a is a mutable alias into an immutable array!!!
}
So that doesn't work, but I thought I'd mention it :o).
Another possibility is to expose opIndex to return by value and also
opIndexAssign that sets the value. That would be a no-no in C++ because
copying is arbitrarily expensive, but I have a feeling that in D it is
sensible to consider and foster that all objects should be defined to be
cheap to copy (e.g. refcounting, COW etc.) If we go by the notion that
in D we can always assume copy costs are reasonable, this last
possibility would work. With the newfangled operators, it would even
work beautifully because you can do all sorts of things like a[1] += 4
without ever exposing a ref to the user.
Andrei
