Challanges in game development by Kotlin

Language Design
1

I recently attempted to write a kotlin based minimal game engine. However I ran into efficiency problems. I found that if I replaced all lists by arrays in my code I got a got a more efficient solution. However Kotlin doesnt support arrays that much since they are considered a low level feature. I implemented vectors and other baic math using value classes and endid up implementing the List interface that has the highest level of support.

I suggest that typed and primitive arrays also implement List to bind them into the ecosystem.
This way we get the efficiency and the flexibility together.

I also ran into problems regarding mutability and value classes.

By using mutable collections I ran into efficiency problems and hidden bugs, by using lists I ran into efficiency problems, by arrays I ran into hidden bugs. Therefor I implemented immutable arrays that are safe and efficient. However I can’t make arrays a subtype of immutable arrays similar to lists and mutable lists.

I suggest that immutable arrays should exist so efficency and immutability can be forced in advanced libraries for gaming and AI without value classes and other adapters.

When I try to use my custom collections (value classes) with json libraries they dont recognize them as the wrapped class.
I consider this sumwhat a bug.
I ended up creating a data class without the custom collections just to load the json and then convert it to the other class.

I suggest that value classes should be seen also as the original class regarding equals, hash and serialization

When I implement an extention for typed arrays I implement it for all primitive arrays as well.
This means I have to make 9 implementations for all extentions.
It would be nice to get common interfaces for these types.

When implementing the value classes many functions are delegated to the wrapped class.
It would be nice to get better support for this delegation.
Like:
fun f(a:A):B by wrappedClass

Value classes should be able to extend the wrapped class even if it is not open!

2

First of all, the main compilation target of Kotlin is JVM, so you need to be aware Kotlin is partially limited to what JVM supports. This is why arrays don’t implement List, this is why there are no read-only arrays or why there are separate primitive arrays - this is all due to design of the underlying JVM. Kotlin tries to hide some of the JVM-specific features, however, this is always tricky and the language is generally highly dependent on the design of JVM.

How do you observe the difference in the performance? Which target do you use: JVM? Testing the performance of JVM applications is tricky, so if you simply executed some code and compared the timings, it is very probable you got entirely meaningless results.

Did you switch from lists to arrays only, not changing any other code and that improved the performance?

If we create a small wrapper over an array that implements the List interface then we just re-invented ArrayList which is the main/default implementation of lists in Kotlin/Java. For most use cases using ArrayList provides comparable performance to arrays, although technically it requires 2 vs 1 heap allocations per a single list/array. I have doubts if that really caused performance issues in your case and I would generally look for another reason, but it is possible that was in fact the case.

Value class implementing List is a different story though. I expect in most cases that should actually… degrade the performance compared to ArrayList. The problem is that whenever we try to use our class as a List, Kotlin will have to box and unbox it (meaning: additional heap allocations). So instead of a single extra allocation per list, we get additional allocation per each operation on a list - much more allocations. Maybe the only way to benefit from typing our class as a List and not degrading the performance is by using standard inline extension functions - that could/should avoid boxing.

Not exactly what you asked, but you can use variance, e.g.: Array<out String>.

Could you provide more details? Which JSON library, how do you use it? I would expect the JSON library to not even know about the wrapper class. In the bytecode an inline class is represented as the wrapped type only. However, I see Kotlin doesn’t properly pass the T to wrapped arrays. Array<String> is compiled into [Ljava/lang/String;, but MyArrayList<String> is compiled to [Ljava/lang/Object;. I would consider this a bug of some sort.

Common interface is Array<T>. Primitive arrays exist to opt-out of common types and get a better performance by utilizing more specialized data structures. Having said that, it would be nice to be able to generate functions for all primitive types without duplicating the code.

I wouldn’t limit this to value classes. It would be nice as a general delegation feature.

Why should they? Value classes are conceptually wrappers, not subtypes. Also, that would break the type system. Final classes are final for a reason.

1 Like
3

First of all, the main compilation target of Kotlin is JVM, so you need to be aware Kotlin is partially limited to what JVM supports. This is why arrays don’t implement List , this is why there are no read-only arrays or why there are separate primitive arrays - this is all due to design of the underlying JVM. Kotlin tries to hide some of the JVM-specific features, however, this is always tricky and the language is generally highly dependent on the design of JVM.

Yes, thats true however Kotlin in the past could get around a lot of limitations by clever code generation. Like in case of the properties and so on. Thats why I expect it to be capable of a lot of what I mentioned. Ofcorse I am not a full on expert and this is just brain storming.

How do you observe the difference in the performance? Which target do you use: JVM? Testing the performance of JVM applications is tricky, so if you simply executed some code and compared the timings, it is very probable you got entirely meaningless results.

I had a code that runs millions of cycles.
The code is intantiation and read heavy.
So it itarates through arrays millions of times.
Can you send me resources of examples or books how you would do it more precisely?

Did you switch from lists to arrays only, not changing any other code and that improved the performance?

Yes, that was all. Should I experience something different with Kotlin 1.9? (I can repeat the experiments)

If we create a small wrapper over an array that implements the List interface then we just re-invented ArrayList which is the main/default implementation of lists in Kotlin/Java. For most use cases using ArrayList provides comparable performance to arrays, although technically it requires 2 vs 1 heap allocations per a single list/array. I have doubts if that really caused performance issues in your case and I would generally look for another reason, but it is possible that was in fact the case.

In my case even the double heap allocations are noticable in the some of my projects. For example I have an AI (not NN based) that runs millions of iterations and each iteration makes millions of array operations. Also ArrayLists are mutable making them less safe. We need an immutable version so I can force efficiency and immutability together in my classes. The nice thing about immutability is that it only removes functions. So you can introduce immutability that is only compile time and the class can compile to the mutable variant. That way you could introduce immutable arrays. This hiding functions could be also a value class functionality.

Value class implementing List is a different story though. I expect in most cases that should actually… degrade the performance compared to ArrayList . The problem is that whenever we try to use our class as a List , Kotlin will have to box and unbox it (meaning: additional heap allocations). So instead of a single extra allocation per list, we get additional allocation per each operation on a list - much more allocations. Maybe the only way to benefit from typing our class as a List and not degrading the performance is by using standard inline extension functions - that could/should avoid boxing.

Like if I use a List extention function on it? That’s an interesting consideration! I didn’t know it boxes every time. Thats a big problem because people consider it more efficient than wrapper classes. I will try that. Value classes should either not support this or support it as efficiently as wrapper classes. This seems unsolvable.

Not exactly what you asked, but you can use variance, e.g.: Array.

Thats a good idea. I will test it.

Could you provide more details? Which JSON library, how do you use it? I would expect the JSON library to not even know about the wrapper class. In the bytecode an inline class is represented as the wrapped type only. However, I see Kotlin doesn’t properly pass the T to wrapped arrays. Array<String> is compiled into [Ljava/lang/String; , but MyArrayList<String> is compiled to [Ljava/lang/Object; . I would consider this a bug of some sort.

I tried multiple libaries. I tried gson, jackson, javax json and even Moshi. They all head problem with value classes when the value class was a property of another class. Interestingly they work when the instance of the value class is passed directly.
Yes that must be a bug!

Common interface is Array<T> . Primitive arrays exist to opt-out of common types and get a better performance by utilizing more specialized data structures. Having said that, it would be nice to be able to generate functions for all primitive types without duplicating the code.

Array<T> is not a common interface of BooleanArray, ByteArray… If I implement something for Array I can not use it for BooleanArray and that can not be passed to a function expecting Array

I wouldn’t limit this to value classes. It would be nice as a general delegation feature.

Good point!

Why should they? Value classes are conceptually wrappers, not subtypes. Also, that would break the type system. Final classes are final for a reason.

They should be able to because they compile to the given class. This would be basicly syntactic sugar for wrapping the class than creating its functions, delegate them all to the wrapped instance, and extending it with new functionality. It is very painful to list all useful functions from the original class, delegate them per function and than make everything inline…

I love Kotlin because it is a middle ground where nice syntax, safety and efficiency meets. However it has to bring efficiency and safety closer together. If these safety features happen only during compilation that should be ok. Efficiency unfortunately starts always at the collection types. Therefore extending the available types is always reasonable in my opinion while it is intuitive for the programmers. Rust for example added the mut keyword. If you add it before a local variable declaration, than all its fields become var otherwise they are val. These kind of features matter a lot in high efficiency scenarios. I know that many things are already solvable in Kotlin. However we need intuitive and beginner friendly alternatives so it is harder to write inefficient code.

4

Yes, and I believe they could technically e.g. make arrays implement List. Wherever we use List functions on an array, compiler would generate a relevant bytecode and if we pass an array where List is required, it would be boxed. That would be similar to what they did with primitives, so we have a single Int and it is automatically converted to either int or Integer. I don’t know if there is any specific reason they didn’t do this. Maybe the problem was with what I mentioned above - that might degrade the performance due to a lot of implicit boxing/unboxing.

Generally, use proper tools like JMH and read its docs. But if you executed millions of iterations already then your measurements could be actually right. I don’t know what may be the reason for degradation.

If you really need to allocate huge numbers of objects, then I guess this is a bigger problem itself than choosing arrays or list. Did you consider/try reusing arrays/lists? Either directly or by using a pool of objects.

I doubt it.

We can’t represent type A as an incompatible type B without some kind of a wrapper. Value classes make sense if we use them directly most of the time and maybe only sometimes we upcast them. Implementing a value class that subtypes List because “the List interface that has the highest level of support” kind of kills the purpose of value classes.

See this example:

fun main() {
    val list = MyArrayList(arrayOf(0, 1, 2))
    repeat(50) {
        list.foo()
    }
}

fun List<Int>.foo() {
    println("${System.identityHashCode(this)}.foo()")
}

@JvmInline
value class MyArrayList(private val arr: Array<Int>): List<Int> { ... }

Output:

2046562095.foo()
933699219.foo()
2121055098.foo()
2084435065.foo()
...

That means each time we call foo(), we allocate a new MyArrayList object, construct it and pass it to a function. We can see this in the decompiled code:

Integer[] list = MyArrayList.constructor-impl(new Integer[]{0, 1, 2});
byte var1 = 50;

for(int var2 = 0; var2 < var1; ++var2) {
    int var4 = false;
    foo(MyArrayList.box-impl(list));
}

I’m not sure extension functions from stdlib could do it differently, but I doubt it as even if we make foo() inline, it still boxes with each call. If we make MyArrayList a regular, not inlined class (or use default ArrayList), it is allocated only once.

If you did something similar, then I’m even more surprised you got a better performance than by using regular lists.

Wait, do you mean you wanted to use serializers, etc. specific to the value class? It can’t work this way because JSON libraries don’t even know about the value class - they see the wrapped class only. You would have to use some JSON library which is Kotlin-value-classes-aware. Maybe kotlinx.serialization?

Yes, I know. My point is: if we need common types, then we need objects. We can write a function for e.g. Array<out Any>, Array<*>, etc. and then pass Array<Int> to it. If we need performance, then we have the specialized IntArray, etc. which opted-out of objects specifically to get a better performance. But again, I think there is a room for improvement here.

I don’t really see your point. Only because in your specific case you would like to use value classes to extend a class with additional functionality, doesn’t mean this is the only or main use case of value classes. Value classes don’t differ here from any other case where we use wrappers, delegation or composition in general. Sometimes, we would like to replicate members of the wrapped type, sometimes extend it, sometimes maybe hide some functions or rename them and sometimes create entirely different API.

Also, even if we “simulate” subtyping, it won’t be a true subtype and that will be visible e.g. through reflection, Java interop, etc. That would be confusing.

5

Yes, and I believe they could technically e.g. make arrays implement List . Wherever we use List functions on an array, compiler would generate a relevant bytecode and if we pass an array where List is required, it would be boxed. That would be similar to what they did with primitives, so we have a single Int and it is automatically converted to either int or Integer . I don’t know if there is any specific reason they didn’t do this. Maybe the problem was with what I mentioned above - that might degrade the performance due to a lot of implicit boxing/unboxing.

True. However it would be a nice feature in general to extend final classes in general. They cause a lot of head ache when we use libs and want to somewhat extend the functionality.

I don’t know what may be the reason for degradation.

I expect that it does not use automatically the most efficient structures in the background.
Even if they use ArrayList it will consist of multiple blocks in the background adding a cost logarithmically proportional to the array size.

If you did something similar, then I’m even more surprised you got a better performance than by using regular lists.

The value class based solution is a new iteration. I got better performance compared to lists, but did not make experiments compared to arrays yet. However I accapt your reasoning. Instead of implementing lists I will move towards extention function based solutions without List as a common interface.

Wait, do you mean you wanted to use serializers, etc. specific to the value class?

No. I wanted to serialise it as the class it wraps. However if I serialize a class that has a property with the value class as a Type, than it fails.

I don’t really see your point. Only because in your specific case you would like to use value classes to extend a class with additional functionality, doesn’t mean this is the only or main use case of value classes. Value classes don’t differ here from any other case where we use wrappers, delegation or composition in general. Sometimes, we would like to replicate members of the wrapped type, sometimes extend it, sometimes maybe hide some functions or rename them and sometimes create entirely different API.

The problem is that when we want to alter the behaviour of a class we have multiple conflicting goals. We want to restrict it and extend it at the same time… but without any additional costs. Value class makes it possible to restrict without any additional cost however it is too hard include all functionality that we don’t want to hide. This is the core problem with value classes. It would be so useful in case of any final classes to have a mechanism that allows us to extend and restrict easily. You are right that we should not call it implementation or extention. It’s more like blueprinting. I have an idea!

What if instead of extending the wrapped class it just has its functions if the value is public. Like:

class MyClass{
fun myFun() {  }
}

value class MyValueClass(val value: MyClass)

...
val v : MyValueClass = ...
v.myFun()
...

but also:

class MyClass{
fun myFun() {  }
}

value class MyValueClass(private val value: MyClass)

...
val v : MyValueClass = ...
v.myFun() //compilation error
...

This makes it very flexible and convenient!

6

ArrayList doesn’t split the data, it always uses a single array underneath. It is really simply a wrapper around an array. If you meant multiple blocks due to growing, then ArrayList doesn’t do this neither - it allocates a new array, copies all data and deallocates the old one.

However, that brings another question: did you grow lists? You naturally couldn’t do this while using arrays, so if you pre-allocated arrays, but didn’t pre-allocate lists, then actually this is a difference in your logic that might cause a big performance hit.

1 Like