Array Slices and Interior Pointers

[Alex Rønne Petersen]

On 11-12-2012 19:11, Robert Jacques wrote:
> On Tue, 11 Dec 2012 11:25:44 -0600, Alex Rønne Petersen <alex at lycus.org>
> wrote:
>> On 11-12-2012 08:29, Rainer Schuetze wrote:
>>> On 11.12.2012 01:04, Alex Rønne Petersen wrote:
>>>> http://xtzgzorex.wordpress.com/2012/12/11/array-slices-and-interior-pointers/
>>>>
>>>>
>>>> Destroy.
>>>>
>
> Done.
>
> [snip]
>
>> From what I could find in e.g. the Boehm GC, there seems to be
>> significant work done to catch interior pointers in addition to base
>> pointers (grep for GC_all_interior_pointers and related symbols).
>
> *Ahem* Arguments regarding performance require A) hard numbers and B)
> are implementation specific.

Yes, but I'm not really here to convince anyone about whether interior 
pointers are needed or not. I was looking for input on the soundness of 
my proposal in order to /avoid/ interior pointers. Just that.

That is to say: I don't care enough about arguing this particular point 
to actually construct a benchmark. If you don't think interior pointers 
are a problem, that is fine, but then your input on the proposal 
probably isn't very useful, because even if I took back my argument 
about performance, interior pointers are still a very real problem for D 
integration into the CLI.

>
> [snip]
>
>> Suppose we have a field int* p;
>
> p _isn't_ a slice, so you're 'fixes' don't apply.

I was replying to Rainer's question about interior pointers and type 
precision in general. You're taking my reply way out of context.

>
> [snip]
>
>> So we have to look at the pointer and first figure out what kind of
>> memory block it is /actually/ pointing to before we have any kind of
>> type info available (just the knowledge that it's of type int* is not
>> particularly useful by itself other than knowing that it could be a
>> pointer at all).
>
> How is p >> 12 slow or difficult? (Assuming log2(PageSize) == 12)

Doesn't look slow and difficult to me. But it depends on the GC 
implementation, as you said. :)

>
>> So the TL;DR is: We avoid extra work to figure out the actual type of
>> the memory something is pointing to by simply making such cases illegal.
>
> At the cost of extra work and more memory everywhere arrays are used.

Yes.

>
>> Whether that is practical, I do not know, and I don't plan to push for
>> it anytime soon at least. But it has to be done for D to ever run on
>> the CLI.
>
> The issue with the CLI has nothing to do with this. The problem is that
> D arrays are D slices (i.e. we don't have T[new]) and D code is written
> to be slice compatible. Whereas the .Net libraries are, for the most
> part, slice incompatible. So slice-based code, in D or .Net, has to
> constantly convert back to arrays, which is a major performance sink.

I'm sorry, but you are wrong.

Interior pointers are /not/ permitted in the CLI. See Ecma 335, I.8.2.1.1.

D as it exists today cannot work in the CLI if it requires interior 
pointers for such a fundamental language feature no matter how you look 
at it.

>
> [snip]
>
>> But if we make this assumption, D can never run on the CLI.
>
> False, see http://dnet.codeplex.com/.

No, not false. This project is stalled because of slices. And 
regardless, the CLI spec clearly does not allow interior pointers.

>
>> Interior pointers are OK in the stack and registers, so taking
>> pointers to fields inside aggregates should be fine so long as they
>> are not stored in the heap.
>
> So what about unions?

Emit a type info bit saying "scan conservatively". Unions are the 
exception rather than the rule. As far as the CLI goes, unions cannot 
work at all, obviously.

-- 
Alex Rønne Petersen
alex at lycus.org
http://lycus.org