Performance issue with pidigits

[hanabi1224]

Describe the bug Background: Pidigits is a problem that mainly measures the performance of big integer implementation, here or here are benchmarks for popular languages.

I was trying to benchmark kotlin native with source code here and found it SUPER slow, like 10x+ slower than other implementations. Not sure if I'm just simply using it incorrectly. Thanks!

To Reproduce Use source code here or attached binary (compiled on ubuntu 20.04) pidigits.zip

# 1000 digits of PI
./pidigits.kexe 1000 

Expected behavior Be comparable to java implementation?

Platform

• kotlin native 1.4.31 + ubuntu 20.04

[ionspin]

Hi @hanabi1224, A s far as I can tell, without going into details of your benchmark code, you are doing everything right. I tried running your benchmark as well, and running the native test resulted in 16.5s seconds, js - legacy was 12.4s, js - ir was 16.5s, and jvm was 810ms :smiley:

The multiplatform bignum library has probably a lot of space to improve performance-wise, I already spent some time on optimizing memory and processing usage, but theres defintiely more (i.e. #61 which I will probably never get to at this pace).

To answer your question:

Library source code for all platforms (jvm, native, js) is completely the same. (that not entirely true, there is only one difference when comparing number in JS, but that's it)

The differences in performance you are seeing are caused by kotlin compiler (or transpiler in case of legacy js)

As far as I could gather from different threads and posts regarding Kotlin/Native and it's sluggishnes, is that it's primary goal is application development and it's not really expected that it will be breaking any speed records at the moment. I would expect as the compiler matures that there will be less and less difference between jvm and native, but we'll have to wait and see.

Keep in mind that Kotlin/Native is in Beta state since 1.3, and Kotlin Multiplatform is Alpha since September of 2020.

With that said, if I was building a speed critical application and wanted to use Kotlin/Native or Kotlin Multiplatform, I would just use expect/actual mechanism and probably use GMP. I would expect that to bring results more in line with JVM.

There is still a plan (https://github.com/ionspin/kotlin-multiplatform-bignum/projects/4) to provide a version of the multiplatform-bignum library with platform specific implementations (i.e. Java BigInteger on JVM, GMP on native, whatever is fast on JS) that would be more performance oriented, but I simply don't have time to do that at the moment.

So I'll close this issue as there is nothing to do in the current completely shared bignum code that could help improve the native performance except waiting for compiler to improve.

[avently]

native test resulted in 16.5s seconds, js - legacy was 12.4s, js - ir was 16.5s, and jvm was 810ms

After looking at these results I started to wait 0.3 version with GNU MP library support:) I hope you find some time on adapting it and maybe it will be even faster than Java version.

Did you test performance of linked GMP in kotlin/native? I just curios will kotlin/native ruin C performance or not.

[ionspin]

I hope you find some time on adapting it and maybe it will be even faster than Java version. This would be a lot of work, and at the moment I have very limited time to work on the library. Also in the development roadmap this is planned for 0.4.0

To implement native versions you would need to map the current api into actual/expect form, add GMP build process to produce libraries for all targets (there is 12 native targets at the moment supported by bignum at the moment), see if there is a emscripten version of GMP for JS or some other JS library, and then write the wrappers expect for all platforms (JVM, JS, Native).

So pull requests to help out on this are welcome :)

Did you test performance of linked GMP in kotlin/native? I just curios will kotlin/native ruin C performance or not.

That is a very interesting question, and I haven't directly compared the two, but I wrote a libsodium wrapper library where I could actually run the comparison, once I have some time. I'll ping you when I do this at some point.

Cheers!

[avently]

I would say that results @hanabi1224 got is not because of Kotlin/Native but because of the lib itself. Maybe, of course, Kotlin/Native gives negative impact but it's minimal. Take a look at the following tests on JVM:

@Test
    fun compareRandom1() {
        val modes = RoundingMode.values().filterNot { it == RoundingMode.UNNECESSARY }
        val res = measureTimeMillis {
            for (i in 0..100_000) {
                val rand1 = Random.nextDouble(-12313.0, 1233123.0)
                val rand2 = Random.nextDouble(-12313.0, 1233123.0)
                if (rand2 == 0.0) continue
                val randScale = Random.nextInt(0, 80)
                val randMode = modes.random()
                assertEquals(
                    rand1.toString().toBigDecimal().divide(rand2.toString().toBigDecimal(), randScale, randMode).stripTrailingZeros().toPlainString(),
                    rand1.toString().toBigDecimal().divide(rand2.toString().toBigDecimal(), randScale, randMode).stripTrailingZeros().toPlainString()
                )
            }
        }
        println("BigDecimal/BigDecimal " + res)
    }

    @Test
    fun compareRandom2() {
        val modes = RoundingMode.values().filterNot { it == RoundingMode.UNNECESSARY }
        val res = measureTimeMillis {
            for (i in 0..100_000) {
                val rand1 = Random.nextDouble(-12313.0, 1233123.0)
                val rand2 = Random.nextDouble(-12313.0, 1233123.0)
                if (rand2 == 0.0) continue
                val randScale = Random.nextInt(0, 80)
                val randMode = modes.random()
                val randModeBN = randMode.toBNMode()
                assertEquals(
                    rand1.toString().toBigDecimal().divide(rand2.toString().toBigDecimal(), randScale, randMode).stripTrailingZeros().toPlainString(),
                    BN.parseString(rand1.toString())
                        .divide(BN.parseString(rand2.toString()), DecimalMode(100 + randScale.toLong(), randModeBN, randScale.toLong()))
                        .toPlainString()
                )
            }
        }
        println("BigDecimal/BN " + res)
    }

    @Test
    fun compareRandom3() {
        val modes = RoundingMode.values().filterNot { it == RoundingMode.UNNECESSARY }
        val res = measureTimeMillis {
            for (i in 0..100_000) {
                val rand1 = Random.nextDouble(-12313.0, 1233123.0)
                val rand2 = Random.nextDouble(-12313.0, 1233123.0)
                if (rand2 == 0.0) continue
                val randScale = Random.nextInt(0, 80)
                val randMode = modes.random()
                val randModeBN = randMode.toBNMode()
                assertEquals(
                    BN.parseString(rand1.toString())
                        .divide(BN.parseString(rand2.toString()), DecimalMode(100 + randScale.toLong(), randModeBN, randScale.toLong()))
                        .toPlainString(),
                    BN.parseString(rand1.toString())
                        .divide(BN.parseString(rand2.toString()), DecimalMode(100 + randScale.toLong(), randModeBN, randScale.toLong()))
                        .toPlainString()
                )
            }
        }
        println("BN/BN " + res)
    }

And the results on old Intel i3 CPU:

BigDecimal/BigDecimal 3770
BigDecimal/BN 68615
BN/BN 118259

Java's BigDecimal is x31 times faster than BigNum library in multiple tasks (divide, parse, toPlainString). So there is definitely a room for optimizations. Not now since you don't have a time but just added this tests as a new information.

[ionspin]

Hi @avently,

I would say that results @hanabi1224 got is not because of Kotlin/Native but because of the lib itself.

I disagree. Running the same test on jvm took 810 miliseconds, while running it on native took 16.5 seconds. It's significant.

Java's BigDecimal is x31 times faster than BigNum library in multiple tasks (divide, parse, toPlainString)

The toString in my library is absolutely terribly implemented, it's probably whats taking the most time in your examples. But I would expect this library to be around 10 or 20 times slower than Java BigInteger.

[avently]

@ionspin yep, kotlin native is slow. Actually I'll rewrite a server part of my app using Nim (I've being working on the server part three years, imaging how large the codebase. But benefits are so sweet). What can be better than real native performance? Nothing :)