On Friday, September 20, 2013 10:47:15 Andrei Alexandrescu wrote:
> On 9/20/13 10:02 AM, Szymon Gatner wrote:
> > On Friday, 20 September 2013 at 16:57:43 UTC, Jonathan M Davis wrote:
> >> If an object is const, then all of its members are const, which means
> >> that any
> >> ranges you get from its members will be const, making such ranges
> >> useless.
> > 
> > That is so weird to hear considering I added ranges to my C++ code and my Vector<T>::all() const can easily return non-const range even tho container is itself const. This kinda looks like D is more limited in that area than C++... Or I really am not getting something.
> 
> Yah, it should be possible for a const container to offer ranges over
> its (non-modifiable) elements.

That's probably easy to do if the container is well-written, because the container creates the range. The problem is converting a const range to tail const one, which is what you have to do if you ever end up with a const range for any reason, and if you're using const much, that's trivial to do (especially if you ever have a range as a member variable). Unfortunately, in practice, that conversion is quite difficult to do with user-defined types even though it works just fine with arrays.

- Jonathan M Davis

On 20.09.2013 19:45, Andrei Alexandrescu wrote:
> On 9/20/13 9:51 AM, Piotr Szturmaj wrote:
>> On 20.09.2013 17:28, Andrei Alexandrescu wrote:
>>> On 9/20/13 2:36 AM, bearophile wrote:
>>>> In D it's often better to use std.algorithm/range instead of raw
>>>> foreach
>>>> loops (despite probably unlike C++ in D a heavy use of ranges leads
>>>> to a
>>>> lower performance, even if you use the LDC2 compiler).
>>>
>>> Why would there be a performance loss?
>>
>> Because range concept underutilize current CPUs. I don't know if all
>> empty/front/popFront are inlined. I suppose some templated functions
>> are, but surely not all of them.  What will be faster, calling all of
>> those functions for each element or traversing memory using a loop?
>
> This is just a supposition. Inlining is automatic and just works subject
> to the constraints chosen by the implementers. It's not like there's a
> guy sitting there and getting bored of inlining.

This was not my point. I know that inlining is automatic, but certainly not all functions are automatically inlined and all of those non-inlined carry some overhead.

>> Of course 2nd option will be faster, because the act of traversing
>> (cached) memory does not have the overhead of a function call.
>
> No, no.
>
>> Some time ago I proposed a hybrid range concept where the front() is an
>> array. All algorithms would first traverse the memory in this array,
>> then call popFront to get another array (slice). In this way, function
>> call overhead is minimized because it's paid sparsely rather than for
>> each range element.
>
> That's a good idea but for completely different reasons.

Could you elaborate? :)

On Friday, September 20, 2013 19:02:22 Szymon Gatner wrote:
> On Friday, 20 September 2013 at 16:57:43 UTC, Jonathan M Davis
> 
> wrote:
> > If an object is const, then all of its members are const, which
> > means that any
> > ranges you get from its members will be const, making such
> > ranges useless.
> 
> That is so weird to hear considering I added ranges to my C++ code and my Vector<T>::all() const can easily return non-const range even tho container is itself const. This kinda looks like D is more limited in that area than C++... Or I really am not getting something.

The container isn't the problem. It's converting a const range to a tail-const one (e.g. const(Range!int) to Range!(const int).

In D, const is transitive, whereas in C++, const only affects the top level. So, if you have

class C
{
    auto foo() const { return i; }
    private int* i;
}

then foo is going to return a const(int*). Thanks to the fact that const int* is implicitly convertible to const(int)*, you could also return const(int)*, if you chose, but you could never return int*, whereas C++ would let you do that just fine, because in C++ it's only the member variable itself which is considered const, not the whole thing, whereas in D, once an object is const, it and everything it refers to is const when accessed through it.

So, in D, if you have a member function that returns a range, the only way that it can return a non-const range is if it's able to convert the fully const range to a tail-const one (i.e. the range itself is non-const but what it refers to is still const). That can easily be done by creating an entirely new range from the original (e.g. convert it to an array and return that), but converting a const range to a tail-const one is very difficult to do with user- defined types.

To do that, we need to be able to convert const(Range!Foo) to Range!(const Foo), and thanks to how templates work those are completely different template instantations (meaning that technically, they don't necessarily have anything do with each other - e.g. their internal layout could be completely different), so the compiler can't assume that that conversion will work. You have to write it yourself, which quickly runs into problems with recursive template instantiations and the like. I believe that it can be done with the proper use of static if, but it does mean that you have to know what you're doing. It's not straightforward, and the last time that I attempted it, I failed.

This is in stark contrast to arrays, where the compiler knows fulwell that it can convert const(int[]) to const(int)[] without causing any problems.

- Jonathan M Davis

On 20/09/13 19:41, Andrei Alexandrescu wrote:
> On 9/20/13 9:28 AM, Joseph Rushton Wakeling wrote:
>> The canonical example would be something like,
>>
>>      foreach (i; iota(10)) { ... }
>>
>> which in theory shouldn't be any slower than,
>>
>>      foreach (i; 0 .. 10) { ... }
>>
>> but in practice is, no matter what the compiler.
>
> I think I know how to fix that. I hypothesize it's about using actual increment
> instead of a stored value "step" for the particular case when step is 1.

Excellent, that'll be great to see :-)

On 9/20/2013 10:45 AM, Andrei Alexandrescu wrote:
> It's not like there's a guy sitting there and getting bored of inlining.

The nice thing about modern optimizers is they are indefatigable. They don't get bored, go on strike, come to work high, :-)

On Fri, Sep 20, 2013 at 05:42:03PM +0200, Joseph Rushton Wakeling wrote:
> On 20/09/13 17:22, H. S. Teoh wrote:
> >Which makes it even more confusing, since newbies would probably equate arrays (the container) with ranges from their frequent use in range examples.
> 
> Yes, it's completely non-obvious.  I think the first time I realized the range/container distinction was when I tried experimentally replacing some built-in arrays with std.container.Array and discovered that I couldn't use them in a foreach loop.

Sad to say, I encountered a good number of Phobos bugs caused by the conflation between built-in arrays and ranges. Code would inadvertently assume array behaviour on ranges, and break when you pass in a non-array range. Some of these have been fixed; I'm pretty sure there are still more lurking around.


> >Perhaps it's more useful to think of T[] not as an array per se, but as a *slice* of the underlying array data which is managed by druntime. I think I'm OK with saying that arrays (i.e. the underlying data) are containers, while slices (what we think of today as "arrays") are ranges.
> 
> It's not a bad description, but I'm not sure that takes into account
> the const(T[]) case.

Actually, it helps you understand the const(T[]) case. To iterate over a
const array, you need a range over it (i.e., a slice); and indeed,
writing arr[] on an array of type const(T[]) gives you a tail-const
slice of type const(T)[], which *is* an iterable range.

The confusion really just stems from the conflation between T[] and a range over T[] in the non-const case.


T

-- 
People tell me I'm stubborn, but I refuse to accept it!

On 9/20/13 10:52 AM, Jonathan M Davis wrote:
> On Friday, September 20, 2013 10:47:15 Andrei Alexandrescu wrote:
>> On 9/20/13 10:02 AM, Szymon Gatner wrote:
>>> On Friday, 20 September 2013 at 16:57:43 UTC, Jonathan M Davis wrote:
>>>> If an object is const, then all of its members are const, which means
>>>> that any
>>>> ranges you get from its members will be const, making such ranges
>>>> useless.
>>>
>>> That is so weird to hear considering I added ranges to my C++ code and
>>> my Vector<T>::all() const can easily return non-const range even tho
>>> container is itself const. This kinda looks like D is more limited in
>>> that area than C++... Or I really am not getting something.
>>
>> Yah, it should be possible for a const container to offer ranges over
>> its (non-modifiable) elements.
>
> That's probably easy to do if the container is well-written, because the
> container creates the range. The problem is converting a const range to tail
> const one, which is what you have to do if you ever end up with a const range
> for any reason, and if you're using const much, that's trivial to do
> (especially if you ever have a range as a member variable). Unfortunately, in
> practice, that conversion is quite difficult to do with user-defined types even
> though it works just fine with arrays.

I'm not sure such a conversion is needed all that often.

Andrei

On 9/20/13 11:21 AM, Joseph Rushton Wakeling wrote:
> On 20/09/13 19:41, Andrei Alexandrescu wrote:
>> On 9/20/13 9:28 AM, Joseph Rushton Wakeling wrote:
>>> The canonical example would be something like,
>>>
>>>      foreach (i; iota(10)) { ... }
>>>
>>> which in theory shouldn't be any slower than,
>>>
>>>      foreach (i; 0 .. 10) { ... }
>>>
>>> but in practice is, no matter what the compiler.
>>
>> I think I know how to fix that. I hypothesize it's about using actual
>> increment
>> instead of a stored value "step" for the particular case when step is 1.
>
> Excellent, that'll be great to see :-)

http://d.puremagic.com/issues/show_bug.cgi?id=11077

Andrei

On Fri, Sep 20, 2013 at 11:04:10AM -0700, Jonathan M Davis wrote: [...]
> So, in D, if you have a member function that returns a range, the only way that it can return a non-const range is if it's able to convert the fully const range to a tail-const one (i.e. the range itself is non-const but what it refers to is still const). That can easily be done by creating an entirely new range from the original (e.g. convert it to an array and return that), but converting a const range to a tail-const one is very difficult to do with user- defined types.
> 
> To do that, we need to be able to convert const(Range!Foo) to Range!(const Foo), and thanks to how templates work those are completely different template instantations (meaning that technically, they don't necessarily have anything do with each other - e.g. their internal layout could be completely different), so the compiler can't assume that that conversion will work. You have to write it yourself, which quickly runs into problems with recursive template instantiations and the like. I believe that it can be done with the proper use of static if, but it does mean that you have to know what you're doing. It's not straightforward, and the last time that I attempted it, I failed.
> 
> This is in stark contrast to arrays, where the compiler knows fulwell
> that it can convert const(int[]) to const(int)[] without causing any
> problems.
[...]

Yeah, this is one of the areas of D's const system that irks me. It's annoying to deal with even outside of ranges. For example, if you want to traverse the container (from inside a member function), if the member function is const, then all references to the container's internal objects are const:

	class Tree {
		Node* root;
		const(Node)* find() const {
			// curNode is inferred as const(Node*), i.e.,
			// the pointer itself is const, since root is a
			// member of const(Tree).
			auto curNode = root;
			while (someCond) {
				// NG: can't modify a const ptr
				curNode = curNode.left;
			} else {
				// NG: can't modify a const ptr
				curNode = curNode.right;
			}
			...
			// NG: can't convert const(Node*) to
			// const(Node)*.
			return curNode;
		}
	}

The workaround is to explicitly state the type of curNode as tail-const:

	const(Node)* curNode = root;
	...

This is a very simple case, and it's already ugly. Once the code gets more complex, the problem becomes uglier. For example, because inout is treated just like const, inout member functions suffer from the same problem. When you then throw in user-defined types that have const/immutable members, the waters get even murkier.


T

-- 
Bare foot: (n.) A device for locating thumb tacks on the floor.

On Friday, September 20, 2013 12:29:33 Andrei Alexandrescu wrote:
> On 9/20/13 10:52 AM, Jonathan M Davis wrote:
> > On Friday, September 20, 2013 10:47:15 Andrei Alexandrescu wrote:
> >> On 9/20/13 10:02 AM, Szymon Gatner wrote:
> >>> On Friday, 20 September 2013 at 16:57:43 UTC, Jonathan M Davis wrote:
> >>>> If an object is const, then all of its members are const, which means
> >>>> that any
> >>>> ranges you get from its members will be const, making such ranges
> >>>> useless.
> >>> 
> >>> That is so weird to hear considering I added ranges to my C++ code and my Vector<T>::all() const can easily return non-const range even tho container is itself const. This kinda looks like D is more limited in that area than C++... Or I really am not getting something.
> >> 
> >> Yah, it should be possible for a const container to offer ranges over
> >> its (non-modifiable) elements.
> > 
> > That's probably easy to do if the container is well-written, because the container creates the range. The problem is converting a const range to tail const one, which is what you have to do if you ever end up with a const range for any reason, and if you're using const much, that's trivial to do (especially if you ever have a range as a member variable). Unfortunately, in practice, that conversion is quite difficult to do with user-defined types even though it works just fine with arrays.
> 
> I'm not sure such a conversion is needed all that often.

Every time that there's a member variable which is a range, you end up needing it if you ever need to iterate over the members of that range when the object itself is const - the prime example being when the range is returned from a getter or property function.

I think that you tend to be able to avoid it if you're not doing much OO and your code is very functional in nature, but if you've got many objects with data, then you start running into it (probably forcing you to move the contents of the range into an array in many cases).

Also, there are plenty of folks who tend to try and use const and/or immutable as much as possible in their code, and when you do that, ranges become useless pretty quickly, whereas if you could easily get a tail-const version of the range when slicing it, ranges can then still be useful in code that uses const and immutable heavily.

As it stands, you pretty much have to avoid const or immutable when doing much with ranges thanks to the lack of tail-const conversion for user-defined ranges, and while that certainly isn't a fatal restriction, it's certainly frustrating when const and immutable are supposed to be major advantages of D. I suspect that the main reason that we don't get more complaints about it is because arrays don't have the problem, but the problem does still come up from time to time.

- Jonathan M Davis