RFC: naming for FrontTransversal and Transversal ranges

[Robert Jacques]

On Thu, 30 Apr 2009 20:52:05 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:
> Robert Jacques wrote:
>> On Thu, 30 Apr 2009 15:57:17 -0400, Andrei Alexandrescu  
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>> People have complained about the incredibly bad, unsafe, and slow  
>>> behavior of appending. Even before the considerable recent slowdown of  
>>> ~=, there were speed concerns. Worse than that, the completely weird  
>>> behavior of slices that grow to stomp on other slices cannot be  
>>> defended.
>>  Actually, this is a problem due to an optimization in the current GC.  
>> Fixing it is rather trivial: simply store the maximum requested array  
>> end at either the beginning or end of the memory block.
>
> How does an arbitrary slice get to the beginning/end of the memory  
> block? I guess that's not a fat pointer anymore, it's an obese pointer.

Okay, so you have:

struct T[]{
     T* ptr;
     size_t length;
     MemInfo* memInfo;
}

struct MemInfo {
     size_t refCount; //not included if not reference counting
     size_t capacity;
}

And MemInfo is located in the first 2 words of the memory block.
Then the start of the memory block == memInfo*.
The end of the memory block to (cast(byte)memInfo* ) + memInfo.capacity;
T* and T*+length both point to locations between between the memory start  
and end (i.e. between memInfo* and memInfo* + capacity/(2*size_t) )

In terms of size, it keeps the pointer down to 3 words, which is only  
slightly chubbier than the current arrays. And given at the minimum you  
have to store a pointer the the ref count, its no larger than it has to  
be. (Exception: Manual memory management could with separate array types,  
could strip off this extra word)

>> But the bigger [ (x ~ y) may or may not create a new array ]
>
> x ~ y always creates a new array.

Opps, sorry. x ~= y.

>> I'm a little sad to hear you say this, as both Daniel Keep and I posted  
>> sample pseudo code on how to do slice types properly in both reference  
>> counted and manual managed memory systems.
>
> No need to be sad. The code is obvious. What I was saying is that people  
> actually need to get their hand on the container so they can control its  
> scope.

Could you clarify something for me. Is this a low-level implementation  
argument or a high-level semantic argument you're making?

>>> A design that has one container type and several slice types that  
>>> crawl it in various ways is very compelling, and I think it will be a  
>>> huge selling point for D. It would be odd, not natural, to have arrays  
>>> as a singularly distinct container that is in fact its own range. We  
>>> get away with container == range for arrays partly because arrays are  
>>> a simple structure, but that only blurs thinking and understanding of  
>>> more complex containers. In fact, ranges do predict that any attempt  
>>> to grow a range will cause topological issues in the owning container;  
>>> that's why SList wisely (IMHO :o)) includes a template parameter that  
>>> tells whether its topology is fixed or flexible.
>>  I'd disagree with regard to a selling point/compelling. My lab  
>> maintains an open source C++ array/slice type pair as part of a larger  
>> robotics package. It's laid outed with an ArrayBase containing all the  
>> implementation. The Array type simply extends ArrayBase and adds memory  
>> management. And Slice extends Arraybase, only adding binding  
>> capabilities. And save for memory allocation, they are identical, i.e.  
>> the container and range are interchangeable.
>
> How about a hashtable? A tree? Are the ranges crawling them identical  
> with the containers? Not at all.
> Arrays are probably the worst example to use as an archetype for a  
> design because they are very simple. Pretty much any design looks a bit  
> baroque when only applied to arrays.

My disagreement was limited to the disagree with regard to a selling  
point/compelling. Otherwise, I agree.
hmm... thinking out loud
Slices of lists, could be lists. But its a recipe for leaks and other  
issues.
Slices of trees, could be trees. Although these 'slices' couldn't actually  
walk the tree. (i.e. aren't ranges) And re-balancing causes logical bug.
But hash tables, queues, dequeues, stacks, etc don't have nice logical  
slices.

>>> (Last but not least, .NET has arrays and slices. D's slices that  
>>> actually have an array testis mesh real bad with .NET because in .NET  
>>> you can't have a disowned slice.)
>>  I've been following the blog. I was surprised that Cristian didn't  
>> just make all D arrays .NET ArraySegments and be done with it, but  
>> there's probably issues I don't know about. I'd like to hear more on  
>> what exactly the issue was.
>
> We discussed at length. Without being an expert in .NET, I can't tell  
> what the problem is, but I do know that if there was a simpler solution,  
> Cristi would have probably found it.
>
>
> Andrei