RFC: naming for FrontTransversal and Transversal ranges

[Robert Jacques]

On Fri, 01 May 2009 14:00:35 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:
> Robert Jacques wrote:
>> Lastly, what you're trying to fix is a bug in the implementation of  
>> arrays (see my posts in this thread) and not a bug in the design.
>
> I think your fix to the array-slice conflation is simply to make slices  
> arrays by adding extra information. This approach is reasonable, but (1)  
> will make slices bigger and slower, and

The extra information is on the heap, not on the stack, so slices are no  
bigger or slower than normal (for GC or reference counted memory; fully  
manual memory management could have a 3 word array type and a 2 word slice  
type)

> (2) will port very poorly to most other containers.

Well, these bugs don't affect other containers.

> Code using ad-hoc arrays in C often had to pass two words around  
> (usually pointers+length). Similarly, code using iterators in C++ must  
> pass two pointers/iterators around (begin+end). With D, we have a 1-1  
> correspondence of that situation with slices, which makes for a great  
> argument on why a slice that contains two boundaries is an awesome way  
> to encapsulate a concept at no efficiency cost. Adding a third word to  
> the slice would mark a step backwards in terms of data being trafficked  
> around, and a questionable increase in expressiveness. An obese  
> three-words slice would avoid stomping over other slices upon append,  
> but would still exhibit a rather unpredictable append behavior: a  
> function taking a slice and appending to it may or may not publish its  
> changes to its caller.

I have not suggested obese 3-slices (in general). Let's look at actual  
costs of your previous array + slice proposal and my array/slice proposal:

GC:
Array       2 words (begin*, end*)
Slice       2 words (begin*, end*)
Array/Slice 2 words (ptr*, length)

Reference counting:
Array       4 words (begin*, end*, end-of-store*, refcount*)
Slice       3 words (begin*, end*, owner*)
Array/Slice 3 words (begin*, end*, memInfo*)

Manual memory managment:
Array       3 words (begin*, end*, end-of-store*)
Slice       2 words (begin*, end*)
Array/Slice 3 words (ptr*, length, memInfo*)

And you known something interesting: a 4-word alice is actually faster  
that a 2 word slice, _if_ you use MMX or SSE instructions (even unaligned,  
though aligned is even faster).

> A good design is to have containers and ranges, not container_ranges.

I agree in general. But, containers don't talk the same language, ranges  
do. So array slices having a few extra features (i.e ~=), doesn't bother  
my abstractions: it's still a range.