(not) abstracting over variance and etc.

On Sat, Nov 13, 2010 at 11:24 PM, Paul Phillips <paulp@improving.org> wrote:

I closed this ticket:

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

And it was reopened because "Since the source codes for HashSet and
HashMap are almost perfect duplicates, fixing the bug in HashSet alone
leaves this bug intact." And sure enough.  Well, I can tolerate all
kinds of tedium, but one thing which drives me up the wall is having to
fix the same bugs repeatedly.  So rather than make the tiny change to
fix it in a second place I went for making it unhappenable.

Man, that was hard.

So I understand why it wasn't done in the first place, even before we
get to whatever performance argument may exist (and I don't think there
is one, but I always have to leave wiggle room.) It is a real nightmare
trying to reuse code in classes with different variances, and type
matching and abstract types don't mix, neither do Arrays and abstract
types.  I won't bore you with details, but if anyone wants to look at
it, here:

https://github.com/scala/scala/commit/3356949fbab722f669ebaf25327a3ae76e0d9ed4

And it WAS satisfying that when I was done there was no bug there
because THERE WAS NO THERE THERE.

I will tell you the two best things to emerge:

1) The "covariance resurrection":

 class CovariantTrieIterator[A, +B](elems: Array[HashMap[A, B]]) extends Iterator[(A, B)] {
   private[this] val it = new TrieIterator[A, B](elems)
   def next = it.next
   def hasNext = it.hasNext
 }

2) The best implicit money can buy:

 private implicit def fixCC[U <: CC](x: CC): U = x.asInstanceOf[U]

I propose to change the name of the implicit from "fixCC" to "wedge"
 

Now who wants to kick over my sand castle?

--
Paul Phillips      | Christ died for our sins.  Dare we make his martyrdom
Imperfectionist    | meaningless by not committing them?
Empiricist         |     -- Jules Feiffer
i pull his palp!   |----------* http://www.improving.org/paulp/ *----------

--
Viktor Klang,
Code Connoisseur
Work:   Scalable Solutions
Code:   github.com/viktorklang
Follow: twitter.com/viktorklang
Read:   klangism.tumblr.com

Actually "shim" is the term used by Matthew Wilson in Imperfect C++.   I assume a book of similar name for Scala authored by Paul Phillips to be forthcoming...

On Sat, Nov 13, 2010 at 5:28 PM, √iktor Klang <viktor.klang@gmail.com> wrote:

On Sat, Nov 13, 2010 at 11:24 PM, Paul Phillips <paulp@improving.org> wrote:

I closed this ticket:

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

And it was reopened because "Since the source codes for HashSet and
HashMap are almost perfect duplicates, fixing the bug in HashSet alone
leaves this bug intact." And sure enough.  Well, I can tolerate all
kinds of tedium, but one thing which drives me up the wall is having to
fix the same bugs repeatedly.  So rather than make the tiny change to
fix it in a second place I went for making it unhappenable.

Man, that was hard.

So I understand why it wasn't done in the first place, even before we
get to whatever performance argument may exist (and I don't think there
is one, but I always have to leave wiggle room.) It is a real nightmare
trying to reuse code in classes with different variances, and type
matching and abstract types don't mix, neither do Arrays and abstract
types.  I won't bore you with details, but if anyone wants to look at
it, here:

https://github.com/scala/scala/commit/3356949fbab722f669ebaf25327a3ae76e0d9ed4

And it WAS satisfying that when I was done there was no bug there
because THERE WAS NO THERE THERE.

I will tell you the two best things to emerge:

1) The "covariance resurrection":

 class CovariantTrieIterator[A, +B](elems: Array[HashMap[A, B]]) extends Iterator[(A, B)] {
   private[this] val it = new TrieIterator[A, B](elems)
   def next = it.next
   def hasNext = it.hasNext
 }

2) The best implicit money can buy:

 private implicit def fixCC[U <: CC](x: CC): U = x.asInstanceOf[U]

I propose to change the name of the implicit from "fixCC" to "wedge"
 

Now who wants to kick over my sand castle?

--
Paul Phillips      | Christ died for our sins.  Dare we make his martyrdom
Imperfectionist    | meaningless by not committing them?
Empiricist         |     -- Jules Feiffer
i pull his palp!   |----------* http://www.improving.org/paulp/ *----------

--
Viktor Klang,
Code Connoisseur
Work:   Scalable Solutions
Code:   github.com/viktorklang
Follow: twitter.com/viktorklang
Read:   klangism.tumblr.com

I've been experimenting with variations on the underlying HAMT data structure to see if I can improve its performance any, and I have been able to factor out not just the iterator, but also most of the rest of the implementation of HashSet and HashMap (albeit less elegantly than you've done, I think -- I'm still studying your code). Unfortunately, the benchmark numbers I've gotten have not been consistent from one Scala version, Java version, or processor to another, so I don't know that that experiment is going anywhere.

I'll go out on a limb and claim that there is also an abstraction common to all immutable Sets and Maps that can be factored out as a supertype that further reduces source code redundancy. But it's not clear the JVM wouldn't impose a performance penalty on an implementation based on such an abstraction.

If I ever get enough control of my schedule to work on these things further, I'll try to write them up so that there are more sand castles to kick over.

A

> Date: Sat, 13 Nov 2010 14:24:20 -0800
> From: paulp@improving.org
> To: scala-internals@listes.epfl.ch
> Subject: [scala-internals] (not) abstracting over variance and etc.
>
> I closed this ticket:
>
> https://lampsvn.epfl.ch/trac/scala/ticket/3984
>
> And it was reopened because "Since the source codes for HashSet and
> HashMap are almost perfect duplicates, fixing the bug in HashSet alone
> leaves this bug intact." And sure enough. Well, I can tolerate all
> kinds of tedium, but one thing which drives me up the wall is having to
> fix the same bugs repeatedly. So rather than make the tiny change to
> fix it in a second place I went for making it unhappenable.
>
> Man, that was hard.
>
> So I understand why it wasn't done in the first place, even before we
> get to whatever performance argument may exist (and I don't think there
> is one, but I always have to leave wiggle room.) It is a real nightmare
> trying to reuse code in classes with different variances, and type
> matching and abstract types don't mix, neither do Arrays and abstract
> types. I won't bore you with details, but if anyone wants to look at
> it, here:
>
> https://github.com/scala/scala/commit/3356949fbab722f669ebaf25327a3ae76e...
>
> And it WAS satisfying that when I was done there was no bug there
> because THERE WAS NO THERE THERE.
>
> I will tell you the two best things to emerge:
>
> 1) The "covariance resurrection":
>
> class CovariantTrieIterator[A, +B](elems: Array[HashMap[A, B]]) extends Iterator[(A, B)] {
> private[this] val it = new TrieIterator[A, B](elems)
> def next = it.next
> def hasNext = it.hasNext
> }
>
> 2) The best implicit money can buy:
>
> private implicit def fixCC[U <: CC](x: CC): U = x.asInstanceOf[U]
>
> Now who wants to kick over my sand castle?
>
> --
> Paul Phillips | Christ died for our sins. Dare we make his martyrdom
> Imperfectionist | meaningless by not committing them?
> Empiricist | -- Jules Feiffer
> i pull his palp! |----------* http://www.improving.org/paulp/ *----------

On Sat, Nov 13, 2010 at 11:24 PM, Paul Phillips <paulp@improving.org> wrote:

2) The best implicit money can buy:

 private implicit def fixCC[U <: CC](x: CC): U = x.asInstanceOf[U]

Now who wants to kick over my sand castle?

me! me! wouldn't you rather play with @uncheckedVariance anyway?
adriaan

On Tue, Nov 16, 2010 at 04:50:50PM +0100, Adriaan Moors wrote:
> me! me! wouldn't you rather play with @uncheckedVariance anyway?

I probably should have saved the intermediate implementations, but I
found this overwhelming in the quantity of fiddliness it entailed, and I
still couldn't get it all working. Or, concretely, where can you place
@uncheckedVariance in the enclosed implementation to avoid the
covariance restoring class? Keep in mind I can't make the method
signatures generic as they are being shared with Set. (Or: I COULD make
them generic, but that quickly stops looking like a superior solution
and looks more like variance dragging everyone down with it.)

By the way, the current implementation uses uncheckedVariance AND has
the casts that implicit exists to address, e.g.

this.updated0(hm.key, hm.hash, level, hm.value.asInstanceOf[B1], hm.kv, merger)
case c: HashMapCollision1[a, b] => arrayToIterators(collisionToArray(c.asInstanceOf[HashMapCollision1[A, B]]))

and etc.

"The enclosed implementation":

class CovariantTrieIterator[A, +B](elems: Array[HashMap[A, B]]) extends Iterator[(A, B)] {
private[this] val it = new TrieIterator[A, B](elems)
def next = it.next
def hasNext = it.hasNext
}

class TrieIterator[A, B](elems: Array[HashMap[A, B]]) extends TrieIteratorBase[(A, B), HashMap[A, B]](elems) {
import TrieIteratorBase._

private[immutable] type ContainerType = HashMap1[A, B]
private[immutable] type TrieType = HashTrieMap[A, B]
private[immutable] type CollisionType = HashMapCollision1[A, B]
private[immutable] def determineType(x: HashMap[A, B]) = x match {
case _: HashMap1[_, _] => CONTAINER_TYPE
case _: HashTrieMap[_, _] => TRIE_TYPE
case _: HashMapCollision1[_, _] => COLLISION_TYPE
}

private[immutable] def getElem(cc: ContainerType) = cc.ensurePair
private[immutable] def getElems(t: TrieType) = t.elems
private[immutable] def collisionToArray(c: CollisionType) = c.kvs map (x => HashMap(x)) toArray
private[immutable] def newThisType(xs: Array[HashMap[A, B]]) = new TrieIterator(xs)
private[immutable] def newDeepArray(size: Int) = new Array[Array[HashMap[A, B]]](size)
private[immutable] def newSingleArray(el: HashMap[A, B]) = Array(el)
}