On Wed, 22 Dec 2010 23:22:56 -0600
Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> I'm thinking what to do about iota, which has good features but exacts too much cost on tight loop performance. One solution would be to define iota to be the simple, forward range that I defined as Iota2 in my previous post. Then, we need a different name for the full-fledged iota (random-access, has known length, iterates through the same numbers forward and backward etc). Ideas?

I would keep length and add an opIn: if (e in interval) {...}. (I'm unsure whether it's worth allowing different types for bounds and/or for step; I'd rather make things simple.) Then, you could call it Interval, what do you think?

Note: The result would be very similar to python (x)ranges. D has a notation for a slightly narrower notion: '..'. Thus, what about:
	Interval!int interval = 1..9;
or else:
	auto interval = Interval!int(1..9);
?

What kind of thingie does "i..j" actually construct as of now?

Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

bearophile <bearophileHUGS@lycos.com> wrote:

> Simen kjaeraas:
>
>> With floating-point numbers, the above solution does not always work.
>
> The type is known at compile time, so you can split the algorithm in two with a "static if", and do something else if it's an integral type.

Absolutely. However, in this example doubles were used.

Also, though it may be doable for integers, other types may also want
that optimization (BigInt comes to mind). A behavesAsIntegral!T might
fix that.

-- 
Simen

On Thursday 23 December 2010 05:22:55 spir wrote:
> On Wed, 22 Dec 2010 23:22:56 -0600
> 
> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> > I'm thinking what to do about iota, which has good features but exacts too much cost on tight loop performance. One solution would be to define iota to be the simple, forward range that I defined as Iota2 in my previous post. Then, we need a different name for the full-fledged iota (random-access, has known length, iterates through the same numbers forward and backward etc). Ideas?
> 
> I would keep length and add an opIn: if (e in interval) {...}. (I'm unsure whether it's worth allowing different types for bounds and/or for step; I'd rather make things simple.) Then, you could call it Interval, what do you think?
> 
> Note: The result would be very similar to python (x)ranges. D has a
> notation for a slightly narrower notion: '..'. Thus, what about:
> Interval!int interval = 1..9;
> or else:
> 	auto interval = Interval!int(1..9);
> ?
> 
> What kind of thingie does "i..j" actually construct as of now?

I believe that the only place that .. works is within []. If an object overrides an opSlice() which takes parameters, then that syntax can be used. I don't believe that it works on its own at all.

- Jonathan M Davis

spir <denis.spir@gmail.com> wrote:

> On Wed, 22 Dec 2010 23:22:56 -0600
> Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>
>> I'm thinking what to do about iota, which has good features but exacts
>> too much cost on tight loop performance. One solution would be to define
>> iota to be the simple, forward range that I defined as Iota2 in my
>> previous post. Then, we need a different name for the full-fledged iota
>> (random-access, has known length, iterates through the same numbers
>> forward and backward etc). Ideas?
>
> I would keep length and add an opIn: if (e in interval) {...}. (I'm unsure whether it's worth allowing different types for bounds and/or for step; I'd rather make things simple.) Then, you could call it Interval, what do you think?
>
> Note: The result would be very similar to python (x)ranges. D has a notation for a slightly narrower notion: '..'. Thus, what about:
> 	Interval!int interval = 1..9;
> or else:
> 	auto interval = Interval!int(1..9);
> ?
>
> What kind of thingie does "i..j" actually construct as of now?

Nothing. The syntax only works in foreach and opSlice.

However, this works:

final abstract class Intervals {
    struct Interval( T ) {
        T start, end;
    }
    static Interval!T opSlice( T )( T start, T end ) {
        return Interval!T( start, end );
    }
}

auto intInterval = Intervals[1..2];
auto stringInterval = Intervals["foo".."bar"];



-- 
Simen

On Thu, 23 Dec 2010 05:29:32 -0800
Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On Thursday 23 December 2010 05:22:55 spir wrote:
> > On Wed, 22 Dec 2010 23:22:56 -0600
> > 
> > Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> > > I'm thinking what to do about iota, which has good features but exacts too much cost on tight loop performance. One solution would be to define iota to be the simple, forward range that I defined as Iota2 in my previous post. Then, we need a different name for the full-fledged iota (random-access, has known length, iterates through the same numbers forward and backward etc). Ideas?
> > 
> > I would keep length and add an opIn: if (e in interval) {...}. (I'm unsure whether it's worth allowing different types for bounds and/or for step; I'd rather make things simple.) Then, you could call it Interval, what do you think?
> > 
> > Note: The result would be very similar to python (x)ranges. D has a
> > notation for a slightly narrower notion: '..'. Thus, what about:
> > Interval!int interval = 1..9;
> > or else:
> > 	auto interval = Interval!int(1..9);
> > ?
> > 
> > What kind of thingie does "i..j" actually construct as of now?
> 
> I believe that the only place that .. works is within []. If an object overrides an opSlice() which takes parameters, then that syntax can be used.

;-) There's also
	foreach(n ; i..j) {...}
Precisely, that's what I was thinking at when stating that D has a notation for a very close (but narrower) notion. Slicing is related, but much farther since it does not necessarily resuire iteration (bit it's result does allow it).
Note: Iota is right-side exclusive like i..j . (I've just been caught by this trap ;-)

>  I don't believe that it works on its own at all.

Certainly not. This would be a syntactic addition. The reason why I asked what "i..j" currently yield --if it yield anything (could just rewrite).


denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

On Thu, 23 Dec 2010 14:40:13 +0100
"Simen kjaeraas" <simen.kjaras@gmail.com> wrote:

> > What kind of thingie does "i..j" actually construct as of now?
> 
> Nothing. The syntax only works in foreach and opSlice.
> 
> However, this works:
> 
> final abstract class Intervals {
>      struct Interval( T ) {
>          T start, end;
>      }
>      static Interval!T opSlice( T )( T start, T end ) {
>          return Interval!T( start, end );
>      }
> }
> 
> auto intInterval = Intervals[1..2];
> auto stringInterval = Intervals["foo".."bar"];

Nice! (even impressive :-)

Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com

On 12/22/10 11:40 PM, Brad Roberts wrote:
> Since the timing code isn't here, I'm assuming you guys are doing the
> testing around the whole app.  While that might be interesting, it's
> hiding an awfully large and important difference, application startup
> time.
>
> C has very little, D quite a bit more, and I don't know what Lua looks
> like there.  If the goal is to test this math code, you'll need to
> separate the two.
>
> At this point, I highly suspect you're really measuring the runtime costs.

One thing I didn't mention is that I also measured with 10x the counter limit. That brings the run time to seconds, and the relative difference persists. So application startup time is negligible in this case.

Andrei

On 12/23/10 2:52 AM, bearophile wrote:
> Andrei:
>
>> I'm thinking what to do about iota, which has good features but exacts
>> too much cost on tight loop performance. One solution would be to define
>> iota to be the simple, forward range that I defined as Iota2 in my
>> previous post. Then, we need a different name for the full-fledged iota
>> (random-access, has known length, iterates through the same numbers
>> forward and backward etc). Ideas?
>
> Is improving the compiler instead an option?

It's more of a separate matter than an option. Iota currently does a fair amount of work for floating-point types, and a contemporary optimizer cannot be reasonably expected to simplify that code.

Andrei

On 12/22/10 8:16 PM, Andrei Alexandrescu wrote:
> On 12/22/10 4:04 PM, Andreas Mayer wrote:
>> To see what performance advantage D would give me over using a
>> scripting language, I made a small benchmark. It consists of this code:
>>
>>> auto L = iota(0.0, 10000000.0);
>>> auto L2 = map!"a / 2"(L);
>>> auto L3 = map!"a + 2"(L2);
>>> auto V = reduce!"a + b"(L3);
>>
>> It runs in 281 ms on my computer.
>
> Thanks for posting the numbers. That's a long time, particularly
> considering that the two map instances don't do anything. So the bulk of
> the computation is:
>
> auto L = iota(0.0, 10000000.0);
> auto V = reduce!"a + b"(L3);

Oops, I was wrong. The two instances of map do something, I thought they're all applied to L when in fact they are chained. So my estimates are incorrect. At any rate, clearly iota incurs a 2x cost, which probably composes with other similar costs incurred by map.

Andrei

On 12/23/10 6:22 AM, spir wrote:
> On Wed, 22 Dec 2010 20:16:45 -0600
> Andrei Alexandrescu<SeeWebsiteForEmail@erdani.org>  wrote:
>
>> Thanks for posting the numbers. That's a long time, particularly
>> considering that the two map instances don't do anything. So the bulk of
>> the computation is:
>>
>> auto L = iota(0.0, 10000000.0);
>> auto V = reduce!"a + b"(L3);
>>
>> There is one inherent problem that affects the speed of iota: in iota,
>> the value at position i is computed as 0.0 + i * step, where step is
>> computed from the limits. That's one addition and a multiplication for
>> each pass through iota. Given that the actual workload of the loop is
>> only one addition, we are doing a lot more work. I suspect that that's
>> the main issue there.
>>
>> The reason for which iota does that instead of the simpler increment is
>> that iota must iterate the same values forward and backward. Using ++
>> may interact with floating-point vagaries, so the code is currently
>> conservative.
>
> There is a point I don't understand here: Iota is a range-struct template, with
>      void popFront()
>      {
>          current += step;
>      }

You need to look at this specialization:

http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/range.d#L3800

and keep in mind Simen's explanation.


Andrei