NotParticularlyFastArrayBuffer

[David MacIver]

So, it might have been true at one point that it was faster than the
scala standard ArrayBuffer, but if that's the case then apparently
it's been fixed. Here are some benchmarks (which are checked into the
repository now, so you can run them yourself). (Nominally numbers are
milliseconds, but the low size numbers should be regarded as pretty
untrustworthy and I wouldn't really trust these as an absolute metric
due to overhead. They seem to be pretty good relative metrics though)

Numbers for reversing a buffer in place:

Size, ArrayBuffer, FastArrayBuffer
10, 3.258, 2.2978
20, 0.4987, 0.5051
30, 0.6404, 0.6784
40, 0.8357, 0.8872
50, 1.0328, 1.1185
60, 1.2255, 1.3265
70, 1.4404, 1.5484
80, 1.6328, 1.7785
90, 1.8418, 1.9832
100, 2.0387, 2.2137
200, 4.0466, 4.4554
300, 6.0575, 6.6008
400, 8.0964, 8.8352
500, 10.1089, 10.9953
600, 12.1277, 13.1384
700, 14.2204, 15.3702
800, 16.123, 17.8492
900, 18.3333, 19.7656
1000, 20.221, 22.164
2000, 57.0286, 58.2423
3000, 90.2857, 93.715
4000, 124.7392, 129.6108
5000, 161.1397, 167.5691
6000, 198.8135, 205.8453
7000, 235.7155, 243.2511
8000, 271.1144, 280.2619
9000, 305.8561, 317.479
10000, 341.403, 354.3688
12000, 420.8776, 436.5691
14000, 498.5422, 510.7208
16000, 570.552, 589.3394
18000, 662.8717, 686.0441
20000, 743.6107, 768.7753

And here are numbers for taking two buffers of a given size and
appending one to the other:

Size, FastArrayBuffer, ArrayBuffer
10, 2.2478, 4.0503
20, 0.6182, 0.2348
30, 0.2806, 0.3512
40, 0.8004, 0.4215
50, 0.6232, 0.8859
60, 0.4136, 0.4787
70, 2.6785, 1.327
80, 1.0499, 1.0741
90, 1.0492, 0.9051
100, 1.0675, 1.1481
200, 2.0545, 2.1388
300, 4.1582, 4.4759
400, 4.5415, 4.5353
500, 4.6886, 4.5181
600, 10.4594, 12.0933
700, 9.3562, 12.2433
800, 10.4363, 9.5442
900, 13.2761, 10.848
1000, 8.9187, 9.5382
2000, 38.1136, 27.7756
3000, 82.8126, 75.2776
4000, 154.6737, 68.0472
5000, 212.6638, 134.5942
6000, 195.2856, 195.2553
7000, 167.9253, 138.2463
8000, 223.8944, 185.4872
9000, 178.1539, 255.1927
10000, 177.6155, 218.4755
12000, 189.322, 199.3202
14000, 202.0151, 199.7248
16000, 208.6898, 204.1837
18000, 923.7989, 943.2565
20000, 939.5282, 931.6668

These aren't intended to benchmark any specific feature (the first
measures both applies and updates, the second iteration and appends),
just to give a general idea of the speed of FastArrayBuffer. And as
you can see from the numbers there's not really a lot in it between it
and ArrayBuffer. Consequently, FastArrayBuffer should probably be
deprecated.

In general, when creating classes to work around deficiencies in
standard library implementations they should probably go in some
central place for such classes and share the name of the class they
replace. That way when the bugs in the standard library that made them
necessary are fixed it becomes a bit easier to deprecate them and for
users to replace them with the "real" versions.

[Jamie Webb-2]

On 2008-09-01 10:12:28 David MacIver wrote:
> So, it might have been true at one point that it was faster than the
> scala standard ArrayBuffer, but if that's the case then apparently
> it's been fixed. Here are some benchmarks (which are checked into the
> repository now, so you can run them yourself). (Nominally numbers are
> milliseconds, but the low size numbers should be regarded as pretty
> untrustworthy and I wouldn't really trust these as an absolute metric
> due to overhead. They seem to be pretty good relative metrics though)

Yes, the optimisation that FastArrayBuffer makes was moved into Scala
by Stepan, sometime around 2.7.0.

> These aren't intended to benchmark any specific feature (the first
> measures both applies and updates, the second iteration and appends),
> just to give a general idea of the speed of FastArrayBuffer. And as
> you can see from the numbers there's not really a lot in it between it
> and ArrayBuffer. Consequently, FastArrayBuffer should probably be
> deprecated.

Possibly, though I have some more ideas to make it faster.

Believe me you will find worse cruft than that in the repo at the
moment. This why I've been reluctant to make a big release.

> In general, when creating classes to work around deficiencies in
> standard library implementations they should probably go in some
> central place for such classes and share the name of the class they
> replace.

Disagree. FastArrayBuffer and ArrayBuffer may do the same thing, but
they are not interchangeable because, well, they aren't the same class.
Giving them the same name would just be confusing.
(java.{util,sql}.Date really pisses me off.)

> That way when the bugs in the standard library that made them
> necessary are fixed it becomes a bit easier to deprecate them and for
> users to replace them with the "real" versions.

To me that's a pretty small difference compared to the disadvantage in
readability.

/J

[David MacIver]

On Mon, Sep 1, 2008 at 8:50 PM, Jamie Webb <j@...> wrote:

> On 2008-09-01 10:12:28 David MacIver wrote:
>> So, it might have been true at one point that it was faster than the
>> scala standard ArrayBuffer, but if that's the case then apparently
>> it's been fixed. Here are some benchmarks (which are checked into the
>> repository now, so you can run them yourself). (Nominally numbers are
>> milliseconds, but the low size numbers should be regarded as pretty
>> untrustworthy and I wouldn't really trust these as an absolute metric
>> due to overhead. They seem to be pretty good relative metrics though)
>
> Yes, the optimisation that FastArrayBuffer makes was moved into Scala
> by Stepan, sometime around 2.7.0.

Looks like it didn't make it into 2.7.1 actually. Or at least 2.7.1
was still suffering from the overly polymorphic array problem, even if
it had other issues fixed.

>> In general, when creating classes to work around deficiencies in
>> standard library implementations they should probably go in some
>> central place for such classes and share the name of the class they
>> replace.
>
> Disagree. FastArrayBuffer and ArrayBuffer may do the same thing, but
> they are not interchangeable because, well, they aren't the same class.
> Giving them the same name would just be confusing.
> (java.{util,sql}.Date really pisses me off.)

Conveniently, things don't live in a global namespace. Particularly in
Scala where you have hierarchical packages and imports and renaming of
imports. The painfullness of doing such things in Java shouldn't
prevent us from doing hem in Scala.

>> That way when the bugs in the standard library that made them
>> necessary are fixed it becomes a bit easier to deprecate them and for
>> users to replace them with the "real" versions.
>
> To me that's a pretty small difference compared to the disadvantage in
> readability.

I don't find it's a significant disadvantage in readability. When I
need to distinguish between them I use one or both partially qualified
(e.g. Map, immutable.Map and mutable.Map).

[Jamie Webb-2]

On 2008-09-01 22:13:15 David MacIver wrote:

> >> In general, when creating classes to work around deficiencies in
> >> standard library implementations they should probably go in some
> >> central place for such classes and share the name of the class they
> >> replace.
> >
> > Disagree. FastArrayBuffer and ArrayBuffer may do the same thing, but
> > they are not interchangeable because, well, they aren't the same
> > class. Giving them the same name would just be confusing.
> > (java.{util,sql}.Date really pisses me off.)
>
> Conveniently, things don't live in a global namespace. Particularly in
> Scala where you have hierarchical packages and imports and renaming of
> imports. The painfullness of doing such things in Java shouldn't
> prevent us from doing hem in Scala.

So you're suggesting that I should name two things the same, just so
that I can rename them to be different again...?

I /want/ a global namespace. I want to be able to look at a name and
know what it means without have to cross-reference against the imports.
I want a class to be named the same everywhere it's imported.

Packages and renaming give us ways to work around naming problems when
they occur, but that doesn't mean it's a good idea to introduce them
deliberately.

> I don't find it's a significant disadvantage in readability. When I
> need to distinguish between them I use one or both partially qualified
> (e.g. Map, immutable.Map and mutable.Map).

As a writer, you sometimes need to distinguish between them. As a
reader, you /always/ need to. So since the qualification is always
necessary, why not bake it into the name and avoid any doubt?

/J