Proposal for primitive generics

[determinant]

Auto-boxing is a known performance concern on Android which caused many people to implement multiple versions of classes (1 for each primitive type).

I would like to propose the ability to define primitive generics:

class MyList<primitive T> {
    private var values: Array<primitive T>() // primitive array of the same type
    
    fun add(value: T) {
        ....
    }
}

fun test() {
    val optimizedList = MyList<primitive Int>() // primitive Int version of MyList
}

So with this proposal, the Kotlin compiler would auto-generate the primitive-specific version of that class depending on which primitive is used.

In addition to avoiding auto-boxing / unboxing, this would also eliminate the need for the implicit casts that the compiler adds. Another benefit would be that we no longer experience type erasure with these classes for the class-level generic type (eg. similar to reified types). Lastly, this would also enable more cache-friendly collections since the data would be stored in a contiguous chunk rather than chasing references.

Would it be possible to get something like this in a future Kotlin release?

[Radzell]

I mean you can’t use primitives in collections anyway

[jstuyts]

A few suggestions:

primitive can be dropped here. There should be no confusion, because the IDE should indicate whether MyList use type-erasure or primitive generics:

fun test() {
    val optimizedList = MyList<primitive Int>() // primitive Int version of MyList
}

How about being able to specify the requirement that it must be numbers, integer numbers or floating point numbers? This way you can apply a limited set of operators on the values.

[determinant]

@Radzell This proposal would enable the use of primitives in collections. It eliminates the need for auto-boxing / unboxing, removes the compiler type casts, enables reified types for the entire class (instead of just inlined functions), and also results in more cache-friendly collections since the data would be stored in a contiguous array instead of chasing references.

[determinant]

@jstuyts You might be right. I was trying to think of the easiest way to modify the existing Array class to turn it into a primitive-enabled Array without breaking backwards compatibility (in case you actually want to store wrapper objects) so that existing code would behave the same way.

Forcing the user to decide when an optimized type should be generated also avoids large combinations of classes especially with multiple type parameters (eg. Map<Long, Double>).

I do like the idea of not having to specify “primitive” when creating an instance so I could be convinced either way (perhaps the creator of the class knows best which type parameters should always be optimized).

[ice1000]

@determinant Maybe we can make the primitive modifier function-only, just like reified (but primitive doesn’t need to be inlined).

In this way Kotlin won’t need to support generic collections, but we still have a lot of use cases.

[determinant]

@ice1000 Can you provide an example of what you’re suggesting? Would it also prevent auto-boxing?

[reisi007]

One example would be Arrays.

Arrays<Int> should be translated to an int[], Array<Int?> however should be translated to Integer[].

There is a JEP for that available as well: http://openjdk.java.net/jeps/218

The problem is, that using generics one has the object methods “toString,hashcode,equals”. When it is possible to have a primitive type there, we might be able to compare (note to self: is false < true valid?).

Following the suggestion in the first post: If we had a special keyword, we could optimize more. But that sounds more like templating in C. Which means: The compiler has to create the following classes automatically on compile

MyList<primitive T> -> BooleanMyList IntMyList LongMyList FloatMyList ... MyList<T> The generation of these different classes must happen from a Java POV. I guess that from the Kotlin side those can be hidden, but nevertheless they must exist.

I hope I understood this proposal correctly.

[slovarik]

JetBrains left a support for creating primitive arrays for the performance purposes.
Here is an Andrey Breslav answer on stackoverflow regarding that.

Please refer to the Kotlin’s Java Arrays documentation section.

Also, there are few similar questions on stack overflow like this asking about a difference of Array<primitive> and PrimitiveArray classes.

And the section 6.3.5 of Kotlin in action book covering this topic. Here is a helpful quote for you from the mentioned section:

Alternatively, if you have an array or a collection holding boxed values of a primitive
type, you can convert them to an array of that primitive type using the corresponding
conversion function, such as toIntArray.

[ice1000]

Like this.

Supported

inline fun <primitive T> whatEver(what: T) = what

In this way, whatEver will be compiled to a private JVM function (or just AST stored in the @Metadata of the generated class), when it’s inlined, it’s specialized. We don’t need to generate multiple specializations for each primitive types.

No boxing, no specializations.

Unsupported

fun <primitive T> whatEver(what: T) = what

Oh, it’s not inlined! Either boxing or specialization is required.

class WhatEver<primitive T>(private val what: T)

Oh, it’s a class! Either boxing or specialization is required.

In the two cases above, we’ll have to generate specializations for each primitive types. That’s bad, 'cause the bytecode size is gonna increase, and the use cases of short and byte is far rarer considering int or char, it’s wasting space.

[ice1000]

I was stupid. This is exactly reified…

[determinant]

@reisi007 Yes, this is exactly what I’m proposing. I’m hoping that the Kotlin compiler will generate separate classes for each primitive type.

One optimization would be to only generate classes for the primitive types that are actually used at compile time (instead of all 8 of them).

[reisi007]

@determinant: I fear that the optimization is not valid…

Think of a library written in Kotlin. You don’t know what will be used and what not…

[Wasabi375]

In that case it might still be a valid idea to have a compiler flag which would when set only created the used classes.

[determinant]

@reisi007 I wonder if Kotlin could add custom metadata to the generated class file which is only used by the Kotlin compiler. This way, a Kotlin library would contain metadata with the primitive generic type information in the generated class files. The Kotlin compiler would notice the primitive type information and hopefully have enough information to generate specialized versions of that class.

How to add custom metadata:
http://www.informit.com/articles/article.aspx?p=26872&seqNum=8

[pdvrieze]

Given that Kotlin still does the byteCode manipulation dance for inline code (where the same metadata could provide an alternative) I’m quite confident that the problem isn’t how to add metadata (it could even be a custom attribute in the class file) and serializing an AST is not rocket science either (making it a stable format is harder though).
Beyond the technical issues, what you are asking for is effectively a limited form of a template(as in C++). That is a language design decision that may have quite some consequences - it is not quite as extensive as C++ templates, but is not easily undone.

[determinant]

@pdvrieze Hmm, perhaps they could release it under an experimental flag for several releases (similar to coroutines). This would allow them to tinker with implementation choices and even remove it if it doesn’t work out.

[determinant]

Another possibility would be to use the “inline” keyword instead of “primitive” which avoids creating a new keyword in the language

class OptimizedList<inline T> {
    ...
}

What are your thoughts?