javakotlin

Why Kotlin submission is significantly slow compared to Java?


I am very new to Kotlin. So to practice, I tried using it to solve problems in LeetCode. Here is one problem that I solved today:
Distinct Subsequence(Leetcode)
First I tried solving the problem in Java:

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[t.length() + 1][s.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= t.length(); i++) {
            for (int j = 1; j <= s.length(); j++) {
                if (t.charAt(i - 1) != s.charAt(j - 1)) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
                }
            }
        }
        return dp[t.length()][s.length()];
    }
}

And here is the runtime of this algorithm:

Runtime: 6 ms
Memory Usage: 39.4 MB

And then I tried solving the problem in Kotlin(Code below):

class Solution {
    fun numDistinct(s: String, t: String): Int {
        var dp = Array(t.count() + 1) {Array(s.count() + 1) {0} }
        for (i in 0 until s.count()) {
            dp[0][i] = 1;
        }
        for (i in 1..t.count()) {
            for (j in 1..s.count()) {
                if (t[i - 1] != s[j - 1]) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
                }
            }
        }
        return dp[t.count()][s.count()]
    }
}

Shockingly the runtime is below for the above Kotlin implemented algorithm:

Runtime: 176 ms
Memory Usage: 34.2 MB

The question is why Kotlin solution is taking so much time to run compared to Java?


Solution

  • I think this can be chalked up to how their backend is spinning up the VM and measuring time. Because this also takes roughly 200ms, which is ridiculous:

    class Solution {
        fun numDistinct(s: String, t: String): Int {
            return 3
        }
    }
    

    I suspect you can count on about 200ms of warm-up time regardless of how simple the code is. Although, weirdly, I tried editing both of these to repeat the algorithm a million times before returning, and the Kotlin code (after adjusting for equivalence as described below) consistently shows a lower runtime.

    Your code isn't exactly equivalent to the Java, though. The other answer mentioned already your inner array type.

    And not performance related, but your first loop fills one more space in Java than in Kotlin.