zhengruifeng commented on pull request #30468:
URL: https://github.com/apache/spark/pull/30468#issuecomment-735749329
performance test between `GuavaOrdering` and `BoundedPriorityQueue`
```
test("BoundedPriorityQueue vs GuavaOrdering") {
import com.google.common.collect.{Ordering => GuavaOrdering}
import org.apache.spark.util.BoundedPriorityQueue
for (n <- Seq(512, 1024, 2048, 4096, 8192); k <- Seq(5, 10, 20, 40, 80))
{
val rng = new Random(123)
val indices = Array.range(0, n)
val values = Array.fill(n)(rng.nextFloat)
val zipped = indices.zip(values)
val pq0 = new BoundedPriorityQueue[(Int, Float)](k)(Ordering.by(_._2))
val pq1 = new BoundedPriorityQueue[Int](k)(Ordering.by(values.apply))
val ord0 = GuavaOrdering.from(Ordering[(Int, Float)])
val ord1 = new GuavaOrdering[Int] {
override def compare(left: Int, right: Int): Int = {
Ordering[Float].compare(values(left), values(right))
}
}
val tic0 = System.currentTimeMillis()
(0 until 100000).foreach { i =>
pq0.clear()
var j = 0
while (j < n) { pq0 += indices(j) -> values(j); j += 1 }
val res0 = pq0.iterator.size
}
val toc0 = System.currentTimeMillis()
val tic1 = System.currentTimeMillis()
(0 until 100000).foreach { i =>
pq1.clear()
pq1 ++= Iterator.range(0, n)
val res1 = pq1.iterator.map(j => (indices(j), values(j))).size
}
val toc1 = System.currentTimeMillis()
val tic2 = System.currentTimeMillis()
(0 until 100000).foreach { i =>
val res2 = ord0.greatestOf(zipped.iterator.asJava,
k).asScala.iterator.size
}
val toc2 = System.currentTimeMillis()
val tic3 = System.currentTimeMillis()
(0 until 100000).foreach { i =>
val res3 = ord1.greatestOf(Iterator.range(0, n).asJava, k).asScala
.iterator.map(j => (indices(j), values(j))).size
}
val toc3 = System.currentTimeMillis()
println(s"n=$n, k=$k:" +
s" pq0=${toc0 - tic0}," +
s" pq1=${toc1 - tic1}," +
s" ord0=${toc2 - tic2}," +
s" ord1=${toc3 - tic3}")
}
}
```
results:
n=512, k=5: pq0=1040, pq1=823, ord0=1236, ord1=726
n=512, k=10: pq0=1929, pq1=1076, ord0=2548, ord1=1066
n=512, k=20: pq0=1506, pq1=1366, ord0=1763, ord1=968
n=512, k=40: pq0=2257, pq1=1940, ord0=1658, ord1=1261
n=512, k=80: pq0=3583, pq1=3161, ord0=1673, ord1=2087
n=1024, k=5: pq0=1573, pq1=1545, ord0=3019, ord1=1110
n=1024, k=10: pq0=1787, pq1=1714, ord0=3248, ord1=1298
n=1024, k=20: pq0=2369, pq1=2282, ord0=3547, ord1=1580
n=1024, k=40: pq0=3480, pq1=2978, ord0=3230, ord1=1961
n=1024, k=80: pq0=5526, pq1=4695, ord0=3292, ord1=3305
n=2048, k=5: pq0=2962, pq1=2983, ord0=5968, ord1=2098
n=2048, k=10: pq0=3195, pq1=3129, ord0=6568, ord1=2317
n=2048, k=20: pq0=4016, pq1=3879, ord0=6590, ord1=2743
n=2048, k=40: pq0=5231, pq1=4729, ord0=6524, ord1=3148
n=2048, k=80: pq0=7875, pq1=6909, ord0=6375, ord1=4417
n=4096, k=5: pq0=5819, pq1=5868, ord0=11899, ord1=4077
n=4096, k=10: pq0=6066, pq1=6051, ord0=12956, ord1=4336
n=4096, k=20: pq0=6958, pq1=6777, ord0=13209, ord1=4755
n=4096, k=40: pq0=8632, pq1=8163, ord0=13133, ord1=5439
n=4096, k=80: pq0=12020, pq1=10876, ord0=12785, ord1=7215
n=8192, k=5: pq0=11553, pq1=11491, ord0=23747, ord1=8105
n=8192, k=10: pq0=11761, pq1=11926, ord0=25972, ord1=8291
n=8192, k=20: pq0=12752, pq1=12602, ord0=26304, ord1=8766
n=8192, k=40: pq0=14854, pq1=14401, ord0=25708, ord1=9817
n=8192, k=80: pq0=18953, pq1=17644, ord0=25601, ord1=11764
It seems that `ord1`(using guava.ordering to select topK by indices, based
on quickselect algorithm) is stably faster than existing impl `pq0` by a factor
of about 40%~100%.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
