From b689b912caa0e1bcd981c1a0092857ac83fb1e1d Mon Sep 17 00:00:00 2001 From: Aleksandar Pokopec Date: Wed, 20 Oct 2010 20:20:08 +0000 Subject: Some serious hash tries bugs fixed. Plus one wild goose chase and test fixes. No review. --- .../parallel-collections/IntOperators.scala | 2 +- .../parallel-collections/ParallelArrayCheck.scala | 2 + .../ParallelHashMapCheck.scala | 11 ++- .../ParallelIterableCheck.scala | 108 +++++++++++++++------ .../parallel-collections/ParallelMapCheck1.scala | 67 +++++++++++++ .../parallel-collections/ParallelRangeCheck.scala | 2 + .../files/scalacheck/parallel-collections/pc.scala | 5 +- 7 files changed, 164 insertions(+), 33 deletions(-) create mode 100644 test/files/scalacheck/parallel-collections/ParallelMapCheck1.scala (limited to 'test') diff --git a/test/files/scalacheck/parallel-collections/IntOperators.scala b/test/files/scalacheck/parallel-collections/IntOperators.scala index e330bec985..bd937808db 100644 --- a/test/files/scalacheck/parallel-collections/IntOperators.scala +++ b/test/files/scalacheck/parallel-collections/IntOperators.scala @@ -11,7 +11,7 @@ trait IntOperators extends Operators[Int] { def existsPredicates = List(_ >= 0, _ < 0, _ % 2 == 0, _ == 55, _ == 505, _ == 5005) def findPredicates = List(_ >= 0, _ % 2 == 0, _ < 0, _ == 50, _ == 500, _ == 5000) def mapFunctions = List(-_) - def partialMapFunctions = List({case x => -x}, { case 0 => -1; case x if x > 0 => x + 1}) + def partialMapFunctions = List({case x => -x}, { case 0 => -1; case x if x > 0 => x + 1}, {case x if x % 3 == 0 => x / 3}) def flatMapFunctions = List( (n: Int) => if (n < 0) List() else if (n % 2 == 0) List(1, 2, 3) else List(4, 5, 6), (n: Int) => List[Int](), diff --git a/test/files/scalacheck/parallel-collections/ParallelArrayCheck.scala b/test/files/scalacheck/parallel-collections/ParallelArrayCheck.scala index 394dc6b370..01e40ed62b 100644 --- a/test/files/scalacheck/parallel-collections/ParallelArrayCheck.scala +++ b/test/files/scalacheck/parallel-collections/ParallelArrayCheck.scala @@ -22,6 +22,8 @@ abstract class ParallelArrayCheck[T](tp: String) extends ParallelSeqCheck[T]("Pa def isCheckingViews = false + def hasStrictOrder = true + def instances(vals: Seq[Gen[T]]): Gen[Seq[T]] = sized { sz => val a = new mutable.ArrayBuffer[T](sz) val gen = vals(rnd.nextInt(vals.size)) diff --git a/test/files/scalacheck/parallel-collections/ParallelHashMapCheck.scala b/test/files/scalacheck/parallel-collections/ParallelHashMapCheck.scala index 1224ec8d4d..51c35140dd 100644 --- a/test/files/scalacheck/parallel-collections/ParallelHashMapCheck.scala +++ b/test/files/scalacheck/parallel-collections/ParallelHashMapCheck.scala @@ -14,7 +14,7 @@ import scala.collection._ import scala.collection.parallel.ops._ -abstract class ParallelHashMapCheck[K, V](tp: String) extends ParallelIterableCheck[(K, V)]("immutable.ParHashMap[" + tp + "]") { +abstract class ParallelHashMapCheck[K, V](tp: String) extends ParallelMapCheck[K, V]("immutable.ParHashMap[" + tp + "]") { ForkJoinTasks.defaultForkJoinPool.setMaximumPoolSize(Runtime.getRuntime.availableProcessors * 2) ForkJoinTasks.defaultForkJoinPool.setParallelism(Runtime.getRuntime.availableProcessors * 2) @@ -22,6 +22,8 @@ abstract class ParallelHashMapCheck[K, V](tp: String) extends ParallelIterableCh def isCheckingViews = false + def hasStrictOrder = false + def instances(vals: Seq[Gen[(K, V)]]): Gen[Iterable[(K, V)]] = sized { sz => var hm = new immutable.HashMap[K, V] val gen = vals(rnd.nextInt(vals.size)) @@ -53,6 +55,13 @@ with PairValues[Int, Int] val intoperators = new IntOperators {} def voperators = intoperators def koperators = intoperators + + override def printDataStructureDebugInfo(ds: AnyRef) = ds match { + case pm: ParHashMap[k, v] => + pm.printDebugInfo + case _ => + println("could not match data structure type: " + ds.getClass) + } } diff --git a/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala b/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala index bc08947af4..ea42e5efa3 100644 --- a/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala +++ b/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala @@ -21,6 +21,11 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col def instances(valgens: Seq[Gen[T]]): Gen[Traversable[T]] def fromTraversable(t: Traversable[T]): CollType def isCheckingViews: Boolean + def hasStrictOrder: Boolean + + def printDataStructureDebugInfo(cf: AnyRef) { + // can be overridden in subclasses + } val rnd = new scala.util.Random @@ -94,18 +99,26 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col results.reduceLeft(_ && _) } + def areEqual(t1: Traversable[T], t2: Traversable[T]) = if (hasStrictOrder) { + t1 == t2 + } else (t1, t2) match { // it is slightly delicate what `equal` means if the order is not strict + case (m1: Map[_, _], m2: Map[_, _]) => m1 == m2 + case (i1: Iterable[_], i2: Iterable[_]) => i1.toSet == i2.toSet + case _ => t1 == t2 + } + property("mappings must be equal") = forAll(collectionPairs) { case (t, coll) => val results = for ((f, ind) <- mapFunctions.zipWithIndex) yield { val ms = t.map(f) val mp = coll.map(f) - if (ms != mp) { + if (!areEqual(ms, mp)) { println(t) println(coll) println("mapped to: ") println(ms) println(mp) } - ("op index: " + ind) |: ms == mp + ("op index: " + ind) |: areEqual(ms, mp) } results.reduceLeft(_ && _) } @@ -114,26 +127,39 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col val results = for ((f, ind) <- partialMapFunctions.zipWithIndex) yield { val ps = t.collect(f) val pp = coll.collect(f) - if (ps != pp) { + if (!areEqual(ps, pp)) { println(t) println(coll) println("collected to: ") println(ps) println(pp) } - ("op index: " + ind) |: ps == pp + ("op index: " + ind) |: areEqual(ps, pp) } results.reduceLeft(_ && _) } property("flatMaps must be equal") = forAll(collectionPairs) { case (t, coll) => (for ((f, ind) <- flatMapFunctions.zipWithIndex) - yield ("op index: " + ind) |: t.flatMap(f) == coll.flatMap(f)).reduceLeft(_ && _) + yield ("op index: " + ind) |: areEqual(t.flatMap(f), coll.flatMap(f))).reduceLeft(_ && _) } property("filters must be equal") = forAll(collectionPairs) { case (t, coll) => - (for ((p, ind) <- filterPredicates.zipWithIndex) - yield ("op index: " + ind) |: t.filter(p) == coll.filter(p)).reduceLeft(_ && _) + (for ((p, ind) <- filterPredicates.zipWithIndex) yield { + val tf = t.filter(p) + val cf = coll.filter(p) + if (tf != cf || cf != tf) { + println(t) + println(coll) + println("filtered to:") + println(cf) + println(tf) + println("tf == cf - " + (tf == cf)) + println("cf == tf - " + (cf == tf)) + printDataStructureDebugInfo(cf) + } + ("op index: " + ind) |: tf == cf && cf == tf + }).reduceLeft(_ && _) } property("filterNots must be equal") = forAll(collectionPairs) { case (t, coll) => @@ -155,15 +181,15 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col }).reduceLeft(_ && _) } - property("takes must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) => + if (hasStrictOrder) property("takes must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) => ("take " + n + " elements") |: t.take(n) == coll.take(n) } - property("drops must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) => + if (hasStrictOrder) property("drops must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) => ("drop " + n + " elements") |: t.drop(n) == coll.drop(n) } - property("slices must be equal") = forAll(collectionPairsWith2Indices) + if (hasStrictOrder) property("slices must be equal") = forAll(collectionPairsWith2Indices) { case (t, coll, fr, slicelength) => val from = if (fr < 0) 0 else fr val until = if (from + slicelength > t.size) t.size else from + slicelength @@ -187,7 +213,7 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col ("slice from " + from + " until " + until) |: tsl == collsl } - property("splits must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) => + if (hasStrictOrder) property("splits must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) => val tspl = t.splitAt(n) val cspl = coll.splitAt(n) if (tspl != cspl) { @@ -200,64 +226,88 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col ("splitAt " + n) |: tspl == cspl } - property("takeWhiles must be equal") = forAll(collectionPairs) { case (t, coll) => - (for ((pred, ind) <- takeWhilePredicates.zipWithIndex) - yield ("operator " + ind) |: t.takeWhile(pred) == coll.takeWhile(pred)).reduceLeft(_ && _) + if (hasStrictOrder) property("takeWhiles must be equal") = forAll(collectionPairs) { case (t, coll) => + (for ((pred, ind) <- takeWhilePredicates.zipWithIndex) yield { + val tt = t.takeWhile(pred) + val ct = coll.takeWhile(pred) + if (tt != ct) { + println("from: " + t) + println("and: " + coll) + println("taking while...") + println(tt) + println(ct) + } + ("operator " + ind) |: tt == ct + }).reduceLeft(_ && _) } - property("spans must be equal") = forAll(collectionPairs) { case (t, coll) => + if (hasStrictOrder) property("spans must be equal") = forAll(collectionPairs) { case (t, coll) => (for ((pred, ind) <- spanPredicates.zipWithIndex) yield { val tsp = t.span(pred) val csp = coll.span(pred) if (tsp != csp) { println("from: " + t) println("and: " + coll) + println("span with predicate " + ind) println(tsp) println(csp) + println("---------------------------------") + println(coll.span(pred)) + println("---------------------------------") } ("operator " + ind) |: tsp == csp }).reduceLeft(_ && _) } - property("dropWhiles must be equal") = forAll(collectionPairs) { case (t, coll) => + if (hasStrictOrder) property("dropWhiles must be equal") = forAll(collectionPairs) { case (t, coll) => (for ((pred, ind) <- dropWhilePredicates.zipWithIndex) yield { ("operator " + ind) |: t.dropWhile(pred) == coll.dropWhile(pred) }).reduceLeft(_ && _) } property("folds must be equal for assoc. operators") = forAll(collectionPairs) { case (t, coll) => - (for (((first, op), ind) <- foldArguments.zipWithIndex) - yield ("operator " + ind) |: t.foldLeft(first)(op) == coll.fold(first)(op)).reduceLeft(_ && _) + (for (((first, op), ind) <- foldArguments.zipWithIndex) yield { + val tres = t.foldLeft(first)(op) + val cres = coll.fold(first)(op) + if (cres != tres) { + println("from: " + t) + println("and: " + coll) + println("folds are: ") + println(tres) + println(cres) + } + ("operator " + ind) |: tres == cres + }).reduceLeft(_ && _) } property("++s must be equal") = forAll(collectionTriplets) { case (t, coll, colltoadd) => val toadd = colltoadd - val tr = t ++ toadd - val cr = coll ++ fromTraversable(toadd).iterator - if (!tr.toList.iterator.sameElements(cr.iterator)) { + val tr = t ++ toadd.iterator + val cr = coll ++ toadd.iterator + if (areEqual(tr, cr)) { println("from: " + t) println("and: " + coll.iterator.toList) println("adding: " + toadd) println(tr.toList) println(cr.iterator.toList) } - ("adding " |: tr == cr) && + ("adding " |: areEqual(tr, cr)) && (for ((trav, ind) <- (addAllTraversables).zipWithIndex) yield { val tadded = t ++ trav - val cadded = coll ++ fromTraversable(trav.toList) - if (tadded != cadded) { + val cadded = coll ++ collection.parallel.mutable.ParArray(trav.toSeq: _*) + if (!areEqual(tadded, cadded)) { println("----------------------") println("from: " + t) - println("and: " + coll.iterator.toList) + println("and: " + coll) println("adding: " + trav) - println(tadded.toList) - println(cadded.iterator.toList) + println(tadded) + println(cadded) } - ("traversable " + ind) |: (tadded) == (cadded) + ("traversable " + ind) |: areEqual(tadded, cadded) }).reduceLeft(_ && _) } - property("copies to array must be equal") = forAll(collectionPairs) { case (t, coll) => + if (hasStrictOrder) property("copies to array must be equal") = forAll(collectionPairs) { case (t, coll) => val tarr = newArray(t.size) val collarr = newArray(coll.size) t.copyToArray(tarr, 0, t.size) diff --git a/test/files/scalacheck/parallel-collections/ParallelMapCheck1.scala b/test/files/scalacheck/parallel-collections/ParallelMapCheck1.scala new file mode 100644 index 0000000000..6b30f61b57 --- /dev/null +++ b/test/files/scalacheck/parallel-collections/ParallelMapCheck1.scala @@ -0,0 +1,67 @@ +package scala.collection.parallel + + + +import org.scalacheck._ +import org.scalacheck.Gen +import org.scalacheck.Gen._ +import org.scalacheck.Prop._ +import org.scalacheck.Properties + +import scala.collection._ +import scala.collection.parallel._ + + + + +abstract class ParallelMapCheck[K, V](collname: String) extends ParallelIterableCheck[(K, V)](collname) { + type CollType <: ParMap[K, V] with Sequentializable[(K, V), Map[K, V]] + + property("gets iterated keys") = forAll(collectionPairs) { + case (t, coll) => + val containsT = for ((k, v) <- t) yield (coll.get(k) == Some(v)) + val containsSelf = for ((k, v) <- coll) yield (coll.get(k) == Some(v)) + ("Par contains elements of seq map" |: containsT.forall(_ == true)) && + ("Par contains elements of itself" |: containsSelf.forall(_ == true)) + } + +} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala b/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala index 91296a2030..d2a05a66c9 100644 --- a/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala +++ b/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala @@ -23,6 +23,8 @@ object ParallelRangeCheck extends ParallelSeqCheck[Int]("ParallelRange[Int]") wi type CollType = collection.parallel.ParSeq[Int] + def hasStrictOrder = true + def isCheckingViews = false def instances(vals: Seq[Gen[Int]]): Gen[Seq[Int]] = sized { start => diff --git a/test/files/scalacheck/parallel-collections/pc.scala b/test/files/scalacheck/parallel-collections/pc.scala index 04b7168286..cb57a6e205 100644 --- a/test/files/scalacheck/parallel-collections/pc.scala +++ b/test/files/scalacheck/parallel-collections/pc.scala @@ -17,7 +17,7 @@ class ParCollProperties extends Properties("Parallel collections") { //include(immutable.ParallelRangeCheck) // parallel immutable hash maps (tries) - include(immutable.IntIntParallelHashMapCheck) + //include(immutable.IntIntParallelHashMapCheck) // parallel immutable hash sets (tries) @@ -40,7 +40,8 @@ object Test { org.scalacheck.Test.checkProperties( org.scalacheck.Test.Params( rng = new java.util.Random(5134L), - testCallback = new ConsoleReporter(0) + testCallback = new ConsoleReporter(0), + workers = 1 ), pc ) -- cgit v1.2.3