Paolo Invernizzi wrote:
> kris wrote:
> 
>>> On Wed, 23 Aug 2006 00:33:08 -0700, Paolo Invernizzi  <arathorn@NOSPAM_fastwebnet.it> wrote:
>>> can you post us the performance difference you  have noticed using the char[] version versus the delegate version?
>>
>>
>> As for performance differences, I suspect you're missing the bigger picture, Paolo?
> 
> 
> I've followed the discussion.
> 
> While I agree that ambiguities must be avoided if possible, and that compiler-made decision are sometimes frustrating (but we all are happy about class-all-virtual-methods!), I was just curious of the performance impact of such a change...


That's simple ~ time a trivial function by calling it several million times. Now add a malloc(40) or thereabouts to the same function and time it again. There's your performance hit. Note that multithreaded apps will run afoul of mutex-contention also.

As for virtual methods; you can choose which are virtual and which are not. Seriously though, virtual methods do not allocate from the heap when they are called. Imagine if they did ...

Sean Kelly wrote:
> Walter Bright wrote:
>>
>> I've struggled to get people to accept the {} version ever since D adopted anonymous delegates. Haven't made much headway in getting such used or in it having any sort of significant impact. How many have made a "dotimes(n, exp)" function or any sort of syntax extension using it? None that I've seen.
> 
> I've been working on a predicate-oriented algorithm module on and off for the past few weeks.  A few looping constructs have been left out because foreach seems a preferable solution in D, but the rest is coming along nicely.  

Interesting. I have been doing some of this myself too, but my available time has been limited. I have also been looking at the concept of iterators. I agree that foreach is the preferable solution, but in some cases, only supporting foreach is too limited. For example, only using foreach, you can not iterate over two collections simultaneously.

It would be great if we could come up with a standardized Iterator concept for D that supported both foreach style iteration (opApply) and some kind of single step iteration (maybe Java-style next/hasNext).

Here is a sample of how it could look (but this particular sample seems to give a segfault on DMD 0.165 for some reason):

template opApplyMixin() {
  int opApply(int delegate(inout ValueType v) dg) {
    ValueType *t;
    while(hasNext()) {
      t = next();
      if (auto status = dg(*t))
	return status;
    }
    return 0;
  }
}

/// Simple array iterator wrapper
struct ArrayIterator(T) {
  T[] arr;
  alias T ValueType;

  T* next() { T* r = arr.ptr; arr = arr[1..$]; return r; }
  bool hasNext() { return arr.length > 0; }
  mixin opApplyMixin;
}


I have been looking at implementing many of my functional algorithms as array views/iterators. For example:

foreach(word; read!(char)("file.txt").splitIterate(&isSpace)) {
	writefln("%s",word);
}

where splitIterate is implemented just as the regular split, but instead of allocating and returning char[][] array, it is implemented as an iterator returning the next char[] slice for each iteration without allocating any extra data.

read could probably be implemented in a smart way, reading the file a certain chunk at a time. Never using more than a constant amount of memory.

Other functions as iterators I have been implementing are:

split(array,predicate|substring|element)
select(array,predicate|element)
reverse(array)
range(start,stop,next)
generate(init,next)
map(array,func)
indexmap(array,indexarray|nextindexfunc)
and so on...

> About the only problem I had was inlining delegates passed to the functions, so the default operations are passed as structs with opCall defined instead.

I've encountered this too. Delegates passed to functions are often called in tight inner loops. So far, I've never seen DMD doing a good job at inlining those cases. Structs with opCall is an excellent idea, that I will steal right away. :) It would be interesting to know if we in the future can count on const delegates being inlined just as efficiently.

/Oskar

Chris Nicholson-Sauls wrote:
> Stewart Gordon wrote:
>> Frank Benoit wrote:
<snip>
>>> This is the first example, showing a ambiguity
>>> func( char[] a ) vs. func( char[] delegate() dg )
>>
>> If one overload matches exactly, it goes without saying that that's the one that's called.  As such, the programmer would do
>> 
>>     func("qwert");
>> 
>> to call the first, and
>> 
>>     func({ return "qwert"; });
>> 
>> to call the second.  Just like in any other case.
> 
> That's what I would have thought as well, but its already been said that these cases are considered ambiguous...  For example, the following code:

Said by whom, where exactly?  Moreover:

http://www.digitalmars.com/d/function.html

"In D, function overloading is simple. It matches exactly, it matches with implicit conversions, or it does not match. If there is more than one match, it is an error."

The irony is that this seems to be a case of what this sentence says, rather than what it was actually supposed to mean.

<snip>
>> The '=>' doesn't look anything like an array initialiser either.  Unless there's some other kind of array initialiser that I haven't discovered yet....
>> Wasn't it obvious that I was talking about the bit to the left of those two characters?
> 
> The only thing I can think of is the PHP format:
> # $foo = array(
> #   'Alpha' => 3 ,
> #   'Beta'  => 6
> # );

Well I don't speak PHP, so no wonder I didn't think of that.

> As far as I know, the D way is to use a colon (:) for this sort of thing.  Although the bit on the left doesn't look like an array initialiser either, in terms of D, as they use brackets rather than braces.
> # const int[] foo = [3, 6, 9] ;
<snip>

Of course!  I'm normally more fluent in D than to confuse these notations.  So a struct initialiser is what it looks confusingly like.

Stewart.

-- 
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:-@ C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++++ h-- r-- !y
------END GEEK CODE BLOCK------

My e-mail is valid but not my primary mailbox.  Please keep replies on the 'group where everyone may benefit.

Stewart Gordon wrote:
> Chris Nicholson-Sauls wrote:
> 
>> Stewart Gordon wrote:
>>
>>> Frank Benoit wrote:
> 
> <snip>
> 
>>>> This is the first example, showing a ambiguity
>>>> func( char[] a ) vs. func( char[] delegate() dg )
>>>
>>>
>>> If one overload matches exactly, it goes without saying that that's the one that's called.  As such, the programmer would do
>>>
>>>     func("qwert");
>>>
>>> to call the first, and
>>>
>>>     func({ return "qwert"; });
>>>
>>> to call the second.  Just like in any other case.
>>
>>
>> That's what I would have thought as well, but its already been said that these cases are considered ambiguous...  For example, the following code:
> 
> 
> Said by whom, where exactly?  Moreover:
> 
> http://www.digitalmars.com/d/function.html
> 
> "In D, function overloading is simple. It matches exactly, it matches with implicit conversions, or it does not match. If there is more than one match, it is an error."
> 
> The irony is that this seems to be a case of what this sentence says, rather than what it was actually supposed to mean.
> 
> <snip>
> 

I know I've read it, don't recall exactly by whom or suchlike.  However, it speaks for itself, try it with DMD 0.165 and behold the error.  Mind you I'm in agreement that it shouldn't be that way: thus I feel the lazy evaluation feature, while nifty and full of Trendy Cooltasticism (TM), is essentially b0rked in DMD165.  I do look forward to the next version and the 'lazy' parameter class.

-- Chris Nicholson-Sauls

Oskar Linde wrote:
> Sean Kelly wrote:
>> Walter Bright wrote:
>>>
>>> I've struggled to get people to accept the {} version ever since D adopted anonymous delegates. Haven't made much headway in getting such used or in it having any sort of significant impact. How many have made a "dotimes(n, exp)" function or any sort of syntax extension using it? None that I've seen.
>>
>> I've been working on a predicate-oriented algorithm module on and off for the past few weeks.  A few looping constructs have been left out because foreach seems a preferable solution in D, but the rest is coming along nicely.  
> 
> Interesting. I have been doing some of this myself too, but my available time has been limited.  I have also been looking at the concept of iterators. I agree that foreach is the preferable solution, but in some cases, only supporting foreach is too limited. For example, only using foreach, you can not iterate over two collections simultaneously.
> 
> It would be great if we could come up with a standardized Iterator concept for D that supported both foreach style iteration (opApply) and some kind of single step iteration (maybe Java-style next/hasNext).

I agree.  And given D's somewhat limited overloading mechanism, there may simply be no point in trying to support pointers as iterators (ie. to use traits templates).  This suggests that some sort of self-contained design may be best, but I haven't thought about the issue enough to comment on the details.

> Here is a sample of how it could look (but this particular sample seems to give a segfault on DMD 0.165 for some reason):
> 
> template opApplyMixin() {
>   int opApply(int delegate(inout ValueType v) dg) {
>     ValueType *t;
>     while(hasNext()) {
>       t = next();
>       if (auto status = dg(*t))
>     return status;
>     }
>     return 0;
>   }
> }
> 
> /// Simple array iterator wrapper
> struct ArrayIterator(T) {
>   T[] arr;
>   alias T ValueType;
> 
>   T* next() { T* r = arr.ptr; arr = arr[1..$]; return r; }
>   bool hasNext() { return arr.length > 0; }
>   mixin opApplyMixin;
> }

So this would cover unidirectional iterators (forward and reverse) but not bidirectional iterators?  Perhaps we need a hasPrev as well?  And then there's random access iterators...

> I have been looking at implementing many of my functional algorithms as array views/iterators. For example:
> 
> foreach(word; read!(char)("file.txt").splitIterate(&isSpace)) {
>     writefln("%s",word);
> }
> 
> where splitIterate is implemented just as the regular split, but instead of allocating and returning char[][] array, it is implemented as an iterator returning the next char[] slice for each iteration without allocating any extra data.

I think Matthew played with this idea a bit in DTL, but I don't think he got quite this far.  It's a great idea however.  I can't recall if he had a name for it, but "view" seems to fit.

> read could probably be implemented in a smart way, reading the file a certain chunk at a time. Never using more than a constant amount of memory.
> 
> Other functions as iterators I have been implementing are:
> 
> split(array,predicate|substring|element)
> select(array,predicate|element)
> reverse(array)
> range(start,stop,next)
> generate(init,next)
> map(array,func)
> indexmap(array,indexarray|nextindexfunc)
> and so on...

That's a solid proof of concept :-)


Sean

Sean Kelly wrote:
> Oskar Linde wrote:
> 
>> Sean Kelly wrote:
>>
>>> Walter Bright wrote:
>>>
>>>>
>>>> I've struggled to get people to accept the {} version ever since D adopted anonymous delegates. Haven't made much headway in getting such used or in it having any sort of significant impact. How many have made a "dotimes(n, exp)" function or any sort of syntax extension using it? None that I've seen.
>>>
>>>
>>> I've been working on a predicate-oriented algorithm module on and off for the past few weeks.  A few looping constructs have been left out because foreach seems a preferable solution in D, but the rest is coming along nicely.  
>>
>>
>> Interesting. I have been doing some of this myself too, but my available time has been limited.  I have also been looking at the concept of iterators. I agree that foreach is the preferable solution, but in some cases, only supporting foreach is too limited. For example, only using foreach, you can not iterate over two collections simultaneously.
>>
>> It would be great if we could come up with a standardized Iterator concept for D that supported both foreach style iteration (opApply) and some kind of single step iteration (maybe Java-style next/hasNext).
> 
> 
> I agree.  And given D's somewhat limited overloading mechanism, there may simply be no point in trying to support pointers as iterators (ie. to use traits templates).  This suggests that some sort of self-contained design may be best, but I haven't thought about the issue enough to comment on the details.
> 
>> Here is a sample of how it could look (but this particular sample seems to give a segfault on DMD 0.165 for some reason):
>>
>> template opApplyMixin() {
>>   int opApply(int delegate(inout ValueType v) dg) {
>>     ValueType *t;
>>     while(hasNext()) {
>>       t = next();
>>       if (auto status = dg(*t))
>>     return status;
>>     }
>>     return 0;
>>   }
>> }
>>
>> /// Simple array iterator wrapper
>> struct ArrayIterator(T) {
>>   T[] arr;
>>   alias T ValueType;
>>
>>   T* next() { T* r = arr.ptr; arr = arr[1..$]; return r; }
>>   bool hasNext() { return arr.length > 0; }
>>   mixin opApplyMixin;
>> }
> 
> 
> So this would cover unidirectional iterators (forward and reverse) but not bidirectional iterators?  Perhaps we need a hasPrev as well?  And then there's random access iterators...
> 
>> I have been looking at implementing many of my functional algorithms as array views/iterators. For example:
>>
>> foreach(word; read!(char)("file.txt").splitIterate(&isSpace)) {
>>     writefln("%s",word);
>> }
>>
>> where splitIterate is implemented just as the regular split, but instead of allocating and returning char[][] array, it is implemented as an iterator returning the next char[] slice for each iteration without allocating any extra data.
> 
> 
> I think Matthew played with this idea a bit in DTL, but I don't think he got quite this far.  It's a great idea however.  I can't recall if he had a name for it, but "view" seems to fit.
> 
>> read could probably be implemented in a smart way, reading the file a certain chunk at a time. Never using more than a constant amount of memory.
>>
>> Other functions as iterators I have been implementing are:
>>
>> split(array,predicate|substring|element)
>> select(array,predicate|element)
>> reverse(array)
>> range(start,stop,next)
>> generate(init,next)
>> map(array,func)
>> indexmap(array,indexarray|nextindexfunc)
>> and so on...
> 
> 
> That's a solid proof of concept :-)
> 
> 
> Sean

I still think a good move would be to allow delegates as foreach aggregates.  Then a class could expose "iterators" in the form of methods, and algorithms could be represented as member delegates.

-- Chris Nicholson-Sauls