A team member claimed that comparing strings representing points was quicker than comparing points. As this seemed unbelievable (string comparisons are slow, right?) I wrote a small test for this:
import org.apache.logging.log4j.kotlin.Logging
import java.awt.Point
public object Comparisons : Logging {
private fun comparePoints(count: Int) {
val start = System.currentTimeMillis()
val set = mutableSetOf<Point>()
repeat(count) {
set.add(Point(it,it))
}
val setCreation = System.currentTimeMillis()
logger.debug { "Point set creation: ${setCreation - start}ms (${set.size})" }
val found = (0 .. count * 2).count { int ->
set.contains(Point(int, int))
}
val comparison = System.currentTimeMillis()
logger.debug { "Point comparison: ${comparison - setCreation}ms ($found)" }
}
private fun compareStrings(count: Int) {
val start = System.currentTimeMillis()
val set = mutableSetOf<String>()
repeat(count) {
set.add("x $it y $it")
}
val setCreation = System.currentTimeMillis()
logger.debug { "String set creation: ${setCreation - start}ms (${set.size})" }
val found = (0 .. count * 2).count { int ->
set.contains("x $int y $int")
}
val comparison = System.currentTimeMillis()
logger.debug { "String comparison: ${comparison - setCreation}ms ($found)" }
}
@JvmStatic fun main(args: Array<String>) {
comparePoints(10000)
compareStrings(10000)
}
}
And the results I got surprised me:
12:43:01.573 [main] DEBUG Comparisons - Point set creation: 6ms (10000)
12:43:01.580 [main] DEBUG Comparisons - Point comparison: 393ms (10000)
12:43:01.588 [main] DEBUG Comparisons - String set creation: 8ms (10000)
12:43:01.595 [main] DEBUG Comparisons - String comparison: 7ms (10000)
Maybe something to do with the implementation of Point.
If I use a simpler implementation of Point
internal class CPoint(val x: Int, val y: Int) {
private val hash = 31 * x + y
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (javaClass != other?.javaClass) return false
other as CPoint
if (x != other.x) return false
if (y != other.y) return false
return true
}
override fun hashCode(): Int = hash
}
The results you’re seeing might be because strings are interned on the JVM, meaning that small strings will be compared by reference and thus will be equal by reference.
Also please use something like JMH or kotlinx-benchmarks for such micro-benchmarks
Now onto a more kotlin-y solution:
@JvmInline value class Point(private val underlying: Long){
constructor(x: Int, y: Int): this((y.toLong() shl Int.SIZE_BITS) or x.toLong())
val x: Int get() = underlying.toInt()
val y: Int get() = (underlying shr Int.SIZE_BITS).toInt()
override fun toString() = "Point($x, $y)"
}
I suggest not to use java.awt.Point. It is not a general-purpose point class, this class is from an almost 30-year old UI toolkit. However, by looking at the source code, it is just a simple 2-integers data class with proper hashCode() and equals(), so it is probable it doesn’t cause performance degradation.
Use a proper benchmarking framework, e.g. JMH. Such simple benchmarks as you did provide pretty random results.
I think it is actually possible strings are faster in this case. Even if technically speaking it has to compare more data, there are still just a few bytes and comparing two flat memory regions is super fast. For your own data class it has to execute a custom code for comparison, which may be in fact slower. Also, JVM could implement optimizations targeted specifically at strings.
edit:
Also, do I read your second post correctly, that after increasing the number of repetitions, even that java.awt.Point became faster than String? If yes, then well, this is why you should use JMH
Thanks for that. Interning short strings could explain the difference.
And using a partitioned int is something I had thought of, but not got round to. (thanks for alerting me to Int.SIZE_BITS - that gets rid of a magic number and future-proofs the code somewhat).
inline value class will not work in my actual implementation - I need more properties with fields - but a great idea.
As for using proper profiling tools - I was expecting a huge difference in the performance with strings being slower. This was just a quick sniff test to check my assumptions.
My team-mate’s assertion was that even with the cost of creating strings for each comparison the use of strings was faster. It seems that he may have justification.
Yep Java is nearly 30 years old - and I have been using almost the entire time (I even did a stint on developing Java itself in IBM’s Java Technology Center in the late 90’s). I still use swing for all my proof-of-concept and prototype GUIs.
This was just a sniff-test and reality check. It elicited the kind of answers I wanted so no need to tool-up with profilers.
Interesting points. So strings could be faster inherently or by targeted optimisation.
Really appreciate the answers folks. I am still learning interesting stuff.
But why was the Kotlin implementation so much faster than the one for Java? To understand why Kotlin was faster required a look at the byte code of the class file. The primary difference was that Java compared strings by calling virtual method (using JVM instruction invokevirtual) equals(Object) in class String, but Kotlin compared strings by making a static call (using JVM instruction invokestatic) to a method named areEqual(Object, Object) in package kotlin.jvm.internal.Intrinsics.
How could Intrinsics.areEqual() be faster than the native equals()? Whatever optimizations Kotlin provides, underneath it has to use either Java code or Java stdlib. It could be potentially a little faster if they would provide a method specifically for (String, String), but if it is for Object then it has to either check runtime types or use equals() internally.
As a matter of fact, it does the latter - it invokes equals(): kotlin/Intrinsics.java at 02bd26562c98d4438f245b3fe3fbe47b08aa0762 · JetBrains/kotlin · GitHub. It seems the main/only reason to use intrinsics here is to support comparing nullable strings without throwing NPE. That means Intrinsics.areEqual() should be actually a little slower than equals(), although the difference is probably negligible.
Even if Intrinsics.areEqual() would be somehow faster than equals(), it wouldn’t be at all used in the above case. Sets are generic, they don’t know types of items, so they can’t optimize for specific types - internally they use just hashCode() and equals(). To optimize strings in this case, Kotlin would have to provide its own implementations of collections which would be not generic and would work with strings specifically.
Thank you for the detailed feedback to my answer. You are correct, of course, and I am embarrassed. I had benchmarked different string search algorithms in both Java and Kotlin, and while most algorithms showed comparable times, there was one algorithm where the Kotlin implementation was surprisingly much faster than the Java implementation. I tried to discover why, and I quit looking when I saw the static call to areEqual(Object, Object) from package kotlin.jvm.internal.Intrinsics. I need to go back and continue looking for the reason why Kotlin was faster for that particular algorithm.
Intrinsics.areEqual is small enough and hot path enough to be inlined by the JVM, thus possibly not incurring in redundant upcasts of Strings to Objects.
Since Intrinsics.areEqual is called many times with String arguments and the second argument is guarded against being null, maybe the JIT compiler can trace that information and create a specialized version of String.equals for non-nullable String arguments that omits the instanceof check? (Key here is that the instanceof check also acts as a non-null check at the same time.)
It’s obviously going to depend on which JVM implementation, and it’d be useful to know how the benchmark in the book had been conducted. Without more information, this is just an hazardous guess.
FYI: I looked in more detail for the reason Kotlin was so much faster than Java for that particular algorithm. I was trying to illustrate several different algorithms, including some that were not very efficient. The algorithm in question had a large multiway if-else if-else if-... structure. The Java compiler transformed it as expected, but the Kotlin compiler was smart enough to turn it into an equivalent when statement using a lookup table, and that was the reason for the performance improvement. It had very little to do with Intrinsics.areEqual. I modified that section of my book accordingly.
There are several issues with the java.awt.Point class that makes it slower than necessary.
It’s not final, so all method calls including equals and hashCode are virtual calls
hashCode is defined in Point2D on doubles and thus slower than necessary, doing int to double and then double to long conversions and then compressing the long into an int again:
public int hashCode() {
long bits = java.lang.Double.doubleToLongBits(getX());
bits ^= java.lang.Double.doubleToLongBits(getY()) * 31;
return (((int) bits) ^ ((int) (bits >> 32)));
}
x and y fields are mutable, so they probably aren’t suitable for inlining or other optimizations.
I would expect it doesn’t matter if we store points in a standard implementation of a set/map. These implementations are generic, so they work on Object/Any anyway - they always use virtual calls.
I don’t think that’s relevant. Due to type erasure, a collection or whatever contains Object/Any values and when calling list.get(0) or whatever, these are implicitly casted to the concrete type, which in this case would be Point. And any further calls on that variable could be static.
Edit: I misunderstood you. You’re right, calls from inside the map implementation would be virtual, correct. However other calls, like the getX from the hashCode method could possible be statically inlined if the class were final.
