8000 Minor Vector cleanup by l0rinc · Pull Request #5545 · scala/scala · GitHub
[go: up one dir, main page]
Skip to content

Minor Vector cleanup #5545

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 7 commits into from
Dec 8, 2016
Merged

Minor Vector cleanup #5545

Changes from 1 commit
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
f4ae496
Removed redundant casts from Vector
l0rinc Nov 18, 2016
6af55b0
Unified masks in Vector
l0rinc Nov 18, 2016
fd338a7
Deleted leftover debug method from Vector
l0rinc Nov 22, 2016
95a29f2
Deleted leftover code-comments from Vector
l0rinc Nov 18, 2016
5ae77a7
Applied suggestions to Vector cleanup
l0rinc Nov 18, 2016
e06d383
Changed >> to >>> in Vector to unify style
l0rinc Nov 22, 2016
74db1d3
Applied further cleanup to Vector
l0rinc Nov 23, 2016
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Deleted leftover code-comments from Vector
  • Loading branch information
@l0rinc
l0rinc committed Dec 6, 2016
commit 95a29f2ab3c2d5e52624720c375ef8977516a9fc
113 changes: 20 additions & 93 deletions src/library/scala/collection/immutable/Vector.scala
View file
Open in desktop
F438
Original file line number Diff line number Diff line change
Expand Up @@ -23,7 +23,7 @@ object Vector extends IndexedSeqFactory[Vector] {
ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]
private[immutable] val NIL = new Vector[Nothing](0, 0, 0)
override def empty[A]: Vector[A] = NIL

// Constants governing concat strategy for performance
private final val Log2ConcatFaster = 5
private final val TinyAppendFaster = 2
Expand Down Expand Up @@ -71,12 +71,7 @@ extends AbstractSeq[A]
with CustomParallelizable[A, ParVector[A]]
{ self =>

override def companion: GenericCompanion[Vector] = Vector

//assert(startIndex >= 0, startIndex+"<0")
//assert(startIndex <= endIndex, startIndex+">"+endIndex)
//assert(focus >= 0, focus+"<0")
//assert(focus <= endIndex, focus+">"+endIndex)
override def companion: GenericCompanion[Vector] = Vector

private[immutable] var dirty = false

Expand All @@ -100,8 +95,6 @@ override def companion: GenericCompanion[Vector] = Vector
s
}


// can still be improved
override /*SeqLike*/
def reverseIterator: Iterator[A] = new AbstractIterator[A] {
private var i = self.length
Expand All @@ -113,16 +106,12 @@ override def companion: GenericCompanion[Vector] = Vector
} else Iterator.empty.next()
}

// TODO: reverse

// TODO: check performance of foreach/map etc. should override or not?
// Ideally, clients will inline calls to map all the way down, including the iterator/builder methods.
// In principle, escape analysis could even remove the iterator/builder allocations and do it
// with local variables exclusively. But we're not quite there yet ...

def apply(index: Int): A = {
val idx = checkRangeConvert(index)
//println("get elem: "+index + "/"+idx + "(focus:" +focus+" xor:"+(idx^focus)+" depth:"+depth+")")
getElem(idx, idx ^ focus)
}

Expand All @@ -137,7 +126,7 @@ override def companion: GenericCompanion[Vector] = Vector
// If we have a default builder, there are faster ways to perform some operations
@inline private[this] def isDefaultCBF[A, B, That](bf: CanBuildFrom[Vector[A], B, That]): Boolean =
(bf eq IndexedSeq.ReusableCBF) || (bf eq collection.immutable.Seq.ReusableCBF) || (bf eq collection.Seq.ReusableCBF)

// SeqLike api

override def updated[B >: A, That](index: Int, elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That =
Expand Down Expand Up @@ -227,7 +216,7 @@ override def companion: GenericCompanion[Vector] = Vector
val again = if (!that.isTraversableAgain) that.toVector else that.seq
again.size match {
// Often it's better to append small numbers of elements (or prepend if RHS is a vector)
case n if n <= TinyAppendFaster || n < (this.size >> Log2ConcatFaster) =>
case n if n <= TinyAppendFaster || n < (this.size >> Log2ConcatFaster) =>
var v: Vector[B] = this
for (x <- again) v = v :+ x
v.asInstanceOf[That]
Expand All @@ -243,8 +232,6 @@ override def companion: GenericCompanion[Vector] = Vector
else super.++(that.seq)
}



// semi-private api

private[immutable] def updateAt[B >: A](index: Int, elem: B): Vector[B] = {
Expand All @@ -257,7 +244,6 @@ override def companion: GenericCompanion[Vector] = Vector
s
}


private def gotoPosWritable(oldIndex: Int, newIndex: Int, xor: Int) = if (dirty) {
gotoPosWritable1(oldIndex, newIndex, xor)
} else {
Expand Down Expand Up @@ -286,33 +272,27 @@ override def companion: GenericCompanion[Vector] = Vector
s
} else {

val freeSpace = ((1<<5*(depth)) - endIndex) // free space at the right given the current tree-structure depth
val shift = freeSpace & ~((1<<5*(depth-1))-1) // number of elements by which we'll shift right (only move at top level)
val shiftBlocks = freeSpace >>> 5*(depth-1) // number of top-level blocks
val freeSpace = ((1 << (5 * depth)) - endIndex) // free space at the right given the current tree-structure depth
val shift = (freeSpace & ~((1 << (5 * (depth - 1))) - 1)) // number of elements by which we'll shift right (only move at top level)
val shiftBlocks = (freeSpace >>> (5 * (depth - 1))) // number of top-level blocks
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Spaces are good. Gratuitious parens around the entire expression are not good--just visual clutter that doesn't aid anything. Internal parens that make one not rely upon knowing operator precedence are good.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

understood, will remove external ones in other places also :)


//println("----- appendFront " + value + " at " + (startIndex - 1) + " reached block start")
if (shift != 0) {
// case A: we can shift right on the top level
//println("shifting right by " + shiftBlocks + " at level " + (depth-1) + " (had "+freeSpace+" free space)")

if (depth > 1) {
val newBlockIndex = blockIndex + shift
val newFocus = focus + shift

val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex)
s.initFrom(this)
s.dirty = dirty
s.shiftTopLevel(0, shiftBlocks) // shift right by n blocks
s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // maybe create pos; prepare for writing
s.display0(lo) = value.asInstanceOf[AnyRef]
//assert(depth == s.depth)
s
} else {
val newBlockIndex = blockIndex + 32
val newFocus = focus

//assert(newBlockIndex == 0)
//assert(newFocus == 0)

val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex)
s.initFrom(this)
s.dirty = dirty
Expand All @@ -323,19 +303,15 @@ override def companion: GenericCompanion[Vector] = Vector
}
} else if (blockIndex < 0) {
// case B: we need to move the whole structure
val move = (1 << 5*(depth+1)) - (1 << 5*(depth))
//println("moving right by " + move + " at level " + (depth-1) + " (had "+freeSpace+" free space)")

val move = (1 << (5 * (depth + 1))) - (1 << (5 * depth))
val newBlockIndex = blockIndex + move
val newFocus = focus + move


val s = new Vector(startIndex - 1 + move, endIndex + move, newBlockIndex)
s.initFrom(this)
s.dirty = dirty
s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // could optimize: we know it will create a whole branch
s.display0(lo) = value.asInstanceOf[AnyRef]
//assert(s.depth == depth+1)
s
} else {
val newBlockIndex = blockIndex
Expand All @@ -346,10 +322,8 @@ override def companion: GenericCompanion[Vector] = Vector
s.dirty = dirty
s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex)
s.display0(lo) = value.asInstanceOf[AnyRef]
//assert(s.depth == depth)
s
}

}
} else {
// empty vector, just insert single element at the back
Expand All @@ -363,28 +337,22 @@ override def companion: GenericCompanion[Vector] = Vector
}

private[immutable] def appendBack[B>:A](value: B): Vector[B] = {
// //println("------- append " + value)
// debug()
if (endIndex != startIndex) {
val blockIndex = endIndex & ~31
val lo = endIndex & 31

if (endIndex != blockIndex) {
//println("will make writable block (from "+focus+") at: " + blockIndex)
val s = new Vector(startIndex, endIndex + 1, blockIndex)
s.initFrom(this)
s.dirty = dirty
s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex)
s.display0(lo) = value.asInstanceOf[AnyRef]
s
} else {
val shift = startIndex & ~((1<<5*(depth-1))-1)
val shiftBlocks = startIndex >>> 5*(depth-1)

//println("----- appendBack " + value + " at " + endIndex + " reached block end")
val shift = startIndex & ~((1 << 5 * (depth - 1)) - 1)
val shiftBlocks = startIndex >>> 5 * (depth - 1)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should surround multiplication with parens for clarity


if (shift != 0) {
//println("shifting left by " + shiftBlocks + " at level " + (depth-1) + " (had "+startIndex+" free space)")
if (depth > 1) {
val newBlockIndex = blockIndex - shift
val newFocus = focus - shift
Expand All @@ -394,15 +362,10 @@ override def companion: GenericCompanion[Vector] = Vector
s.shiftTopLevel(shiftBlocks, 0) // shift left by n blocks
s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex)
s.display0(lo) = value.asInstanceOf[AnyRef]
//assert(depth == s.depth)
s
} else {
val newBlockIndex = blockIndex - 32
val newFocus = focus

//assert(newBlockIndex == 0)
//assert(newFocus == 0)

val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex)
s.initFrom(this)
s.dirty = dirty
Expand All @@ -420,7 +383,6 @@ override def companion: GenericCompanion[Vector] = Vector
s.dirty = dirty
s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex)
s.display0(lo) = value.asInstanceOf[AnyRef]
//assert(s.depth == depth+1) might or might not create new level!
s
}
}
Expand Down Expand Up @@ -461,8 +423,6 @@ override def companion: GenericCompanion[Vector] = Vector
}

private def copyLeft(array: Array[AnyRef], right: Int): Array[AnyRef] = {
// if (array eq null)
// println("OUCH!!! " + right + "/" + depth + "/"+startIndex + "/" + endIndex + "/" + focus)
val a2 = new Array[AnyRef](array.length)
java.lang.System.arraycopy(array, 0, a2, 0, right)
a2
Expand Down Expand Up @@ -583,7 +543,7 @@ override def companion: GenericCompanion[Vector] = Vector
}

private def requiredDepth(xor: Int) = {
if (xor < (1 << 5)) 1
if (xor < (1 << 5)) 1
else if (xor < (1 << 10)) 2
else if (xor < (1 << 15)) 3
else if (xor < (1 << 20)) 4
Expand All @@ -596,20 +556,7 @@ override def companion: GenericCompanion[Vector] = Vector
val blockIndex = cutIndex & ~31
val xor = cutIndex ^ (endIndex - 1)
val d = requiredDepth(xor)
val shift = (cutIndex & ~((1 << (5*d))-1))

//println("cut front at " + cutIndex + ".." + endIndex + " (xor: "+xor+" shift: " + shift + " d: " + d +")")

/*
val s = new Vector(cutIndex-shift, endIndex-shift, blockIndex-shift)
s.initFrom(this)
if (s.depth > 1)
s.gotoPos(blockIndex, focus ^ blockIndex)
s.depth = d
s.stabilize(blockIndex-shift)
s.cleanLeftEdge(cutIndex-shift)
s
*/
val shift = (cutIndex & ~((1 << (5 * d)) - 1))
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Don't need outer parens


// need to init with full display iff going to cutIndex requires swapping block at level >= d

Expand All @@ -626,13 +573,8 @@ override def companion: GenericCompanion[Vector] = Vector
val blockIndex = (cutIndex - 1) & ~31
val xor = startIndex ^ (cutIndex - 1)
val d = requiredDepth(xor)
val shift = (startIndex & ~((1 << (5*d))-1))
val shift = (startIndex & ~((1 << (5 * d)) - 1))
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Don't need outer parens


/*
println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")")
if (cutIndex == blockIndex + 32)
println("OUCH!!!")
*/
val s = new Vector(startIndex-shift, cutIndex-shift, blockIndex-shift)
s.initFrom(this)
s.dirty = dirty
Expand All @@ -641,14 +583,12 @@ override def companion: GenericCompanion[Vector] = Vector
s.cleanRightEdge(cutIndex-shift)
s
}

}


class VectorIterator[+A](_startIndex: Int, endIndex: Int)
extends AbstractIterator[A]
with Iterator[A]
with VectorPointer[A @uncheckedVariance] {
extends AbstractIterator[A]
with Iterator[A]
with VectorPointer[A @uncheckedVariance] {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This style makes it hard to tell at a glance where the class signature ends and where the body begins. The style is all over the place in practice, but I recommend left-justifying everything; vertical whitespace should always be used to separate classes so there is no need to indent them to indicate that they all belong to VectorIterator. Failing that, the previous version was preferable because at least all the extended classes/traits are lined up.


private var blockIndex: Int = _startIndex & ~31
private var lo: Int = _startIndex & 31
Expand Down Expand Up @@ -739,7 +679,6 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP
}



private[immutable] trait VectorPointer[T] {
private[immutable] var depth: Int = _
private[immutable] var display0: Array[AnyRef] = _
Expand Down Expand Up @@ -819,7 +758,7 @@ private[immutable] trait VectorPointer[T] {
if (xor < (1 << 5)) { // level = 0 (could maybe removed)
} else
if (xor < (1 << 10)) { // level = 1
display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]]
display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]]
} else
if (xor < (1 << 15)) { // level = 2
display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]]
Expand Down Expand Up @@ -847,14 +786,12 @@ private[immutable] trait VectorPointer[T] {
}
}



// USED BY ITERATOR

// xor: oldIndex ^ index
private[immutable] final def gotoNextBlockStart(index: Int, xor: Int): Unit = { // goto block start pos
if (xor < (1 << 10)) { // level = 1
display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]]
display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]]
} else
if (xor < (1 << 15)) { // level = 2
display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]]
Expand Down Expand Up @@ -935,8 +872,6 @@ private[immutable] trait VectorPointer[T] {
}
}



// STUFF BELOW USED BY APPEND / UPDATE

private[immutable] final def copyOf(a: Array[AnyRef]) = {
Expand All @@ -946,13 +881,11 @@ private[immutable] trait VectorPointer[T] {
}

private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int) = {
//println("copy and null")
val x = array(index)
array(index) = null
copyOf(x.asInstanceOf[Array[AnyRef]])
}


// make sure there is no aliasing
// requires structure is at pos index
// ensures structure is clean and at pos index and writable at all levels except 0
Expand Down Expand Up @@ -997,7 +930,6 @@ private[immutable] trait VectorPointer[T] {
}



/// USED IN UPDATE AND APPEND BACK

// prepare for writing at an existing position
Expand Down Expand Up @@ -1110,16 +1042,13 @@ private[immutable] trait VectorPointer[T] {
}




// USED IN APPEND
// create a new block at the bottom level (and possibly nodes on its path) and prepares for writing

// requires structure is clean and at pos oldIndex,
// ensures structure is dirty and at pos newIndex and writable at level 0
private[immutable] final def gotoFreshPosWritable0(oldIndex: Int, newIndex: Int, xor: Int): Unit = { // goto block start pos
if (xor < (1 << 5)) { // level = 0
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should leave a comment that we're already at the block start.

//println("XXX clean with low xor")
} else
if (xor < (1 << 10)) { // level = 1
if (depth == 1) {
Expand Down Expand Up @@ -1185,12 +1114,10 @@ private[immutable] trait VectorPointer[T] {
}
}


// requires structure is dirty and at pos oldIndex,
// ensures structure is dirty and at pos newIndex and writable at level 0
private[immutable] final def gotoFreshPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = {
stabilize(oldIndex)
gotoFreshPosWritable0(oldIndex, newIndex, xor)
}
}

}
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Add a newline at the end to keep things happy that like newlines at the end!

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

:)) sir, yes sir!

0