Towards a revised collection API

[Erik Engbrecht]

David,

  How's that new map coming?

https://lampsvn.epfl.ch/trac/scala/ticket/854

-Erik

On Mon, Apr 21, 2008 at 10:49 AM, David MacIver <david.maciver@...> wrote:

On Mon, Apr 21, 2008 at 3:27 PM, Jamie Webb <j@...> wrote:
>
> On 2008-04-21 14:26:32 David MacIver wrote:
>  > On Mon, Apr 21, 2008 at 11:26 AM, David MacIver
>  > <david.maciver@...> wrote:
>  > >  You can take a look at the tests here:
>  > >  http://freehg.org/u/DRMacIver/alt.collections/file/53f65c4f9249/perftests.scala
>  >
>  > The astute observer will note that I shouldn't be allowed to write
>  > performance tests while half awake. These are backwards...
>
>  Not only that, you're probably measuring interpreted performance, and

Hm. that's possible. Because each test gets compiled into a separate
method and run multiple times, I assumed hotspot would JIT compile the
method after the first few invocations, but it should really be
running a bunch of cold starts first I suppose.

I freely admit to not being very good at benchmarking Java programs
though, so I could have completely the wrong end of the stick. :-)

>  the work will probably be dwarfed by GC time...

Well, I force a garbage collection between tests, so any GC time that
is measured should actually be significant numbers.

>  Here are the numbers I get (-s is Scala, -d is you):
>
>     listmap-s   listmap-d  arraymap-s  arraymap-d  listfilter-s  listfilter-d  arrayfilter-s  arrayfilter-d
>   -------------------------------------------------------------------------------------------------------------
>           901        1133        1124        1778           586           718            705           1592
>           904        1132        1117        1771           605           737            730           1555
>           912        1126        1110        1768           602           744            715           1569
>           923        1110        1087        1785           601           744            731           1560
>           897        1135        1106        1837           609           734            737           1592
>           897        1129        1108        1774           605           725            727           1548
>           892        1160        1148        1784           612           733            707           1565
>           942        1186        1100        1745           589           764            720           1606
>           909        1160        1141        1734           589           733            720           1553
>           902        1156        1131        1782           588           733            722           1574
>   -------------------------------------------------------------------------------------------------------------
>    Avg    908 ms     1143 ms     1117 ms     1776 ms        599 ms        736 ms         721 ms        1571 ms
>   -------------------------------------------------------------------------------------------------------------
>
>  This is for a list/array of 1000 elements, with timings given for 45000
>  repetitions.

That does look rather bleaker than I'd hoped. :-) I don't find the
list numbers too bad, particularly as I expect they'll improve
slightly if List implements traversable directly rather than using a
wrapper. If the performance works well in other cases (which has yet
to be tested) I'm ok with that level of slowdown for something like
this - given that the design is intended to eliminate intermediate
structures it's not surprising it doesn't give much advantage when
there are none.

The array numbers are more of an issue, but I think I know how to
improve those.

How do the numbers change if you increase the size of the list/array?

>  Sorry, you can't repeat it until I publish my benchmarking library in
>  Scalax (need to update dependencies; I'll try to do it tomorrow).

I look forward to it.

--
http://erikengbrecht.blogspot.com/

[David MacIver]

It hasn't been, really. I've been thinking about the API more than the
implementations.

Curiously, it looks like that's a compiler bug. I'll add a comment to
the ticket.

On Wed, May 7, 2008 at 3:59 AM, Erik Engbrecht <erik.engbrecht@...> wrote:

> David,
>   How's that new map coming?
>
> https://lampsvn.epfl.ch/trac/scala/ticket/854
>
> -Erik
>
>
>
>  On Mon, Apr 21, 2008 at 10:49 AM, David MacIver <david.maciver@...>
> wrote:
> >
> > On Mon, Apr 21, 2008 at 3:27 PM, Jamie Webb <j@...> wrote:
> > >
> > > On 2008-04-21 14:26:32 David MacIver wrote:
> > >  > On Mon, Apr 21, 2008 at 11:26 AM, David MacIver
> > >  > <david.maciver@...> wrote:
> > >  > >  You can take a look at the tests here:
> > >  > >
> http://freehg.org/u/DRMacIver/alt.collections/file/53f65c4f9249/perftests.scala
> > >  >
> > >  > The astute observer will note that I shouldn't be allowed to write
> > >  > performance tests while half awake. These are backwards...
> > >
> > >  Not only that, you're probably measuring interpreted performance, and
> >
> > Hm. that's possible. Because each test gets compiled into a separate
> > method and run multiple times, I assumed hotspot would JIT compile the
> > method after the first few invocations, but it should really be
> > running a bunch of cold starts first I suppose.
> >
> > I freely admit to not being very good at benchmarking Java programs
> > though, so I could have completely the wrong end of the stick. :-)
> >
> >
> > >  the work will probably be dwarfed by GC time...
> >
> > Well, I force a garbage collection between tests, so any GC time that
> > is measured should actually be significant numbers.
> >
> >
> > >  Here are the numbers I get (-s is Scala, -d is you):
> > >
> > >     listmap-s   listmap-d  arraymap-s  arraymap-d  listfilter-s
> listfilter-d  arrayfilter-s  arrayfilter-d
> > >
> -------------------------------------------------------------------------------------------------------------
> > >           901        1133        1124        1778           586
> 718            705           1592
> > >           904        1132        1117        1771           605
> 737            730           1555
> > >           912        1126        1110        1768           602
> 744            715           1569
> > >           923        1110        1087        1785           601
> 744            731           1560
> > >           897        1135        1106        1837           609
> 734            737           1592
> > >           897        1129        1108        1774           605
> 725            727           1548
> > >           892        1160        1148        1784           612
> 733            707           1565
> > >           942        1186        1100        1745           589
> 764            720           1606
> > >           909        1160        1141        1734           589
> 733            720           1553
> > >           902        1156        1131        1782           588
> 733            722           1574
> > >
> -------------------------------------------------------------------------------------------------------------
> > >    Avg    908 ms     1143 ms     1117 ms     1776 ms        599 ms
> 736 ms         721 ms        1571 ms
> > >
> -------------------------------------------------------------------------------------------------------------
> > >
> > >  This is for a list/array of 1000 elements, with timings given for 45000
> > >  repetitions.
> >
> > That does look rather bleaker than I'd hoped. :-) I don't find the
> > list numbers too bad, particularly as I expect they'll improve
> > slightly if List implements traversable directly rather than using a
> > wrapper. If the performance works well in other cases (which has yet
> > to be tested) I'm ok with that level of slowdown for something like
> > this - given that the design is intended to eliminate intermediate
> > structures it's not surprising it doesn't give much advantage when
> > there are none.
> >
> > The array numbers are more of an issue, but I think I know how to
> > improve those.
> >
> > How do the numbers change if you increase the size of the list/array?
> >
> >
> > >  Sorry, you can't repeat it until I publish my benchmarking library in
> > >  Scalax (need to update dependencies; I'll try to do it tomorrow).
> >
> > I look forward to it.
> >
> >
>
>
>
> --
> http://erikengbrecht.blogspot.com/