« Return to Thread: [scala] Collections performance
Re: [scala] Collections performance
by David MacIver
::
Rate this Message:
On Wed, Jul 30, 2008 at 12:11 PM, Sean McDirmid <sean.mcdirmid@...> wrote:
>> I'm not sure about the licensing implications of that. The source code
>> for the Java collections is GPLed, and that would definitely count as
>> a derivative work.
>
> Just put it out under the same license. If RMS wants to sue us, we can burn
> that bridge when we get to it. We aren't selling Scala or being commercial
> in anyway, so I don't see any liability there. We just make sure our stuff
> is as open as the stuff we are copying.
No no no. Absolutely not. No way, no how.
I don't know about you, but I *am* being commercial using Scala. And
if you include GPL code in the standard libraries (and any reasonable
collections library should be aiming to eventually become standardised
as part of the standard library) then any code I wish to use Scala in
is getting bundled with GPL derived stuff and I'm screwed.
This would be so massively a deal breaker that I'm fairly horrified
you've even suggested it.
>> Sure. I'm just saying: The availability is hugely biased in the
>> direction of mutable ones.
>
> Of course, mutable collection libraries is where all the payoff is, while
> immutable collection libraries are often seen as novelties. We are very weak
I can't help other peoples misconceptions. :-)
> on mutable libraries right now in Scala, so the bias should benefit us more
> at first. Regardless I think they are fairly orthogonal and shouldn't share
The immutable collections available are generally pretty weak in my
opinion as well.
> so many APIs; e.g., I don't see much use for having both mutable and
> immutable hash maps (mutable works well en
Because immutable collections are nice, sometimes you have a need for
generic map structures, and as I demonstrated in the attached, an
immutable hash map is typically dramatically faster than the tree map
implementation (this isn't just a trivial implementation inadequacy -
it's significantly faster than the JCL TreeMap too)?
>> I'm not clear on how that's a function of immutability vs immutability.
>
> Definitely is. Because Seq[+A], contains in Seq has the signature contains(x
> : Any) : Boolean (thankfully, Set and Map are not covariant). This then
> propagates to ArrayList because it extends Seq, hence we have weakly typed
> contains methods for mutable seq's directly as a consequence of sharing APIs
> between mutable and immutable collections (otherwise, contains would be
> strongly typed).
Fair enough. I hadn't really even noticed that there was a contains
method on Sequence. It seems a dramatically inappropriate place to put
it - Sequences don't have any more efficient way of testing for
containment than just def contains(x : Any) = exists(x=_) (indeed,
that's exactly how it's implemented).
In general I don't agree that sharing interfaces between mutable and
immutable collections is a bad thing. There are a lot of cases where
I'd want to do it, and I much more frequently find myself frustrated
by instances where the APIs are not shared than I do inadequacies
caused by sharing them.
I do think that the way the current hierarchy treats the relationship
between mutable and immutable collections is rather undesirable, but I
have so many complaints with the design of the existing API that this
is quite far down the list of things that bother me. :-)
>> Well, I wasn't thinking of data structures along the lines of "Yet
>> another hash map". There's quite a rich selection of special purpose
>> and interesting data structures out there: Bloom filters, tries,
>> finger trees, a variety of heaps (including interestingly different
>> ones like the soft heap), plus a rich variety of purely functional
>> data structures a la Okasaki's book and future papers. It would be
>> really nice to have a "batteries included" usable collections library
>> containing more exotic data structures. The objective here is not to
>> match the Java collections library in usability, but to beat it.
>
> Great. But that doesn't fill the short term need that we just need more of
> the basics. I'm all for the special stuff, but we have to consider the basic
Well we have most of the basics. They could just use a bit of love in
terms of implementation.
> collections also (a mutable tree map would be a nice start).
Yes, that would be good.
>> I'm not sure about the licensing implications of that. The source code
>> for the Java collections is GPLed, and that would definitely count as
>> a derivative work.
>
> Just put it out under the same license. If RMS wants to sue us, we can burn
> that bridge when we get to it. We aren't selling Scala or being commercial
> in anyway, so I don't see any liability there. We just make sure our stuff
> is as open as the stuff we are copying.
No no no. Absolutely not. No way, no how.
I don't know about you, but I *am* being commercial using Scala. And
if you include GPL code in the standard libraries (and any reasonable
collections library should be aiming to eventually become standardised
as part of the standard library) then any code I wish to use Scala in
is getting bundled with GPL derived stuff and I'm screwed.
This would be so massively a deal breaker that I'm fairly horrified
you've even suggested it.
>> Sure. I'm just saying: The availability is hugely biased in the
>> direction of mutable ones.
>
> Of course, mutable collection libraries is where all the payoff is, while
> immutable collection libraries are often seen as novelties. We are very weak
I can't help other peoples misconceptions. :-)
> on mutable libraries right now in Scala, so the bias should benefit us more
> at first. Regardless I think they are fairly orthogonal and shouldn't share
The immutable collections available are generally pretty weak in my
opinion as well.
> so many APIs; e.g., I don't see much use for having both mutable and
> immutable hash maps (mutable works well en
Because immutable collections are nice, sometimes you have a need for
generic map structures, and as I demonstrated in the attached, an
immutable hash map is typically dramatically faster than the tree map
implementation (this isn't just a trivial implementation inadequacy -
it's significantly faster than the JCL TreeMap too)?
>> I'm not clear on how that's a function of immutability vs immutability.
>
> Definitely is. Because Seq[+A], contains in Seq has the signature contains(x
> : Any) : Boolean (thankfully, Set and Map are not covariant). This then
> propagates to ArrayList because it extends Seq, hence we have weakly typed
> contains methods for mutable seq's directly as a consequence of sharing APIs
> between mutable and immutable collections (otherwise, contains would be
> strongly typed).
Fair enough. I hadn't really even noticed that there was a contains
method on Sequence. It seems a dramatically inappropriate place to put
it - Sequences don't have any more efficient way of testing for
containment than just def contains(x : Any) = exists(x=_) (indeed,
that's exactly how it's implemented).
In general I don't agree that sharing interfaces between mutable and
immutable collections is a bad thing. There are a lot of cases where
I'd want to do it, and I much more frequently find myself frustrated
by instances where the APIs are not shared than I do inadequacies
caused by sharing them.
I do think that the way the current hierarchy treats the relationship
between mutable and immutable collections is rather undesirable, but I
have so many complaints with the design of the existing API that this
is quite far down the list of things that bother me. :-)
>> Well, I wasn't thinking of data structures along the lines of "Yet
>> another hash map". There's quite a rich selection of special purpose
>> and interesting data structures out there: Bloom filters, tries,
>> finger trees, a variety of heaps (including interestingly different
>> ones like the soft heap), plus a rich variety of purely functional
>> data structures a la Okasaki's book and future papers. It would be
>> really nice to have a "batteries included" usable collections library
>> containing more exotic data structures. The objective here is not to
>> match the Java collections library in usability, but to beat it.
>
> Great. But that doesn't fill the short term need that we just need more of
> the basics. I'm all for the special stuff, but we have to consider the basic
Well we have most of the basics. They could just use a bit of love in
terms of implementation.
> collections also (a mutable tree map would be a nice start).
Yes, that would be good.
« Return to Thread: [scala] Collections performance
| Free embeddable forum powered by Nabble | Forum Help |
