Re: Re: might be worth your while

Yeah, if you run the range benchmark I checked in with the commit
against your implementation:

1 to 265966072:, whileSum wins, 0.564: foreach 170.689 while 96.223
1 to 265966072:, whileSum wins, 0.572: foreach 170.501 while 97.559
1 to 303961225:, whileSum wins, 0.551: foreach 195.146 while 107.594
1 to 303961225:, whileSum wins, 0.574: foreach 193.256 while 110.876
1 to 303961225:, whileSum wins, 0.531: foreach 213.705 while 113.555

2x slower. The way I checked it in was the only way I found which
offered a dead heat.

1 to 265966072:, foreachSum wins, 0.945: foreach 90.656 while 95.932
1 to 265966072:, whileSum wins, 0.949: foreach 95.106 while 90.275
1 to 303961225:, whileSum wins, 0.986: foreach 111.133 while 109.619
1 to 303961225:, foreachSum wins, 0.985: foreach 111.732 while 113.459
1 to 303961225:, foreachSum wins, 0.911: foreach 106.152 while 116.568
1 to 347384257:, foreachSum wins, 0.991: foreach 125.646 while 126.796

On Tue, Dec 13, 2011 at 09:14, Paul Phillips wrote:
>
> 2x slower.  The way I checked it in was the only way I found which
> offered a dead heat.
>
> 1 to 265966072:,   foreachSum wins, 0.945:  foreach 90.656   while 95.932
> 1 to 265966072:,     whileSum wins, 0.949:  foreach 95.106   while 90.275
> 1 to 303961225:,     whileSum wins, 0.986:  foreach 111.133   while 109.619
> 1 to 303961225:,   foreachSum wins, 0.985:  foreach 111.732   while 113.459
> 1 to 303961225:,   foreachSum wins, 0.911:  foreach 106.152   while 116.568
> 1 to 347384257:,   foreachSum wins, 0.991:  foreach 125.646   while 126.796

I find these numbers pretty impressive -- far better than I could
accomplish myself. I wonder how much of it results from the Int =>
Unit trick, since my own benchmark does pass a Int => Unit method. So
I looked back at the implementation, and I'm now wondering how much of
my own implementation's slow down results from last being a lazy val.

This led me to another line of thought... there seems to be a lot of
special-casing around Range being empty or not, so I wonder if an
Empty range should not be its own class, so that non-empty ranges can
avoid things like lazy vals and (lenght > 0) conditions. And if I
could figure out a way of doing that and preserve inlining at the same
time, I would have tested it already. :-) I might test it anyway, once
I get my benchmarking project to work like I want.

On Tue, Dec 13, 2011 at 4:56 AM, Daniel Sobral wrote:
> This led me to another line of thought... there seems to be a lot of
> special-casing around Range being empty or not, so I wonder if an
> Empty range should not be its own class, so that non-empty ranges can
> avoid things like lazy vals and (lenght > 0) conditions.

This is the right idea; I directly observed the addition of "if
(length < 0)" to be enough to send me over the aforementioned
performance cliff. Unfortunately it is difficult to do in a
backward-compatible way. You need Range's constructor to be private
to be able to assume anything about the relative values of the
constructor parameters. Otherwise people can waltz by your
"EmptyRange" object and directly new Range(5, -5, 1) and we don't have
the luxury of not acting like an empty range in that spot.

If we could write it from scratch, I think that using subclass
polymorphism to encode the initial conditions would yield the best
performance. That's definitely how I'd do that sort of thing now (or
at least it's the first thing I'd try.)

On Tue, Dec 13, 2011 at 12:40, Paul Phillips wrote:
> On Tue, Dec 13, 2011 at 4:56 AM, Daniel Sobral wrote:
>> This led me to another line of thought... there seems to be a lot of
>> special-casing around Range being empty or not, so I wonder if an
>> Empty range should not be its own class, so that non-empty ranges can
>> avoid things like lazy vals and (lenght > 0) conditions.
>
> This is the right idea; I directly observed the addition of "if
> (length < 0)" to be enough to send me over the aforementioned
> performance cliff.  Unfortunately it is difficult to do in a
> backward-compatible way.  You need Range's constructor to be private
> to be able to assume anything about the relative values of the
> constructor parameters.  Otherwise people can waltz by your
> "EmptyRange" object and directly new Range(5, -5, 1) and we don't have
> the luxury of not acting like an empty range in that spot.
>
> If we could write it from scratch, I think that using subclass
> polymorphism to encode the initial conditions would yield the best
> performance.  That's definitely how I'd do that sort of thing now (or
> at least it's the first thing I'd try.)

Well, true. But can't we have it both ways? I'm willing to bet most
Range uses are created by factories, so while Range could remain its
old self, we could subclass it (making methods final in the process)
like that. Only, as I said, I see no way to do that and have foreach
inlined at the same time.