Here we go again: I'm searching for a performant, convenient solution for dependency injection in Kotlin. Koin got my attention, because it seems to be simple and straightforward. Since it uses a lot of small inline functions and seems to have only a few hotspots where performance suckers could lurk, it seemed very promising. But I wouldn't want to use it in my game engine project until I can be sure that the performance impact would be negligible. So I did a ... probably totally flawed microbenchmark, that doesn't show anything, but I want to dump it here nonetheless.
So we have a simple service class and another service class that depends on the first service. The main module depends on the seconds service, so the chain has to be fulfilled.
Using Koin, one can simply write a few lines and everything is wired together automatically. Note that the Koin context has to be started and stopped, which has to be excluded from the benchmark later.
Even though I'm aware that this is an artificial benchmark that may be flawed, it's pretty much clear that using Koin will have a huge impact on performance, that could make program infrastrucutre slower by a factor of 100. Of course, we're talking about dependency injection at object creation time, which should be a rare case in a game engine. Nonetheless, not too good from my sight.
My last post was about an approach to use Kotlin's scoped extension methods to implement an application with data oriented design paradigm. Yes, I'm still coding that game engine, that's why I had to do a simple benchmark, just to get a feeling how performance could get better or worse. See it as a brain dump. Very unprofessional benchmark with the println statement, but I wanted to get the relation between the simple baseline implementation and the extension method version, like this:
I described the basics about the two-phase occlusion culling
technique in the first part post, but there is one thing, that doesn't
work well with this simple setup: Instancing or sometimes viewed as batching.
The problem is very simple, the solution however is not.
Only a few engines managed to implement the technique, but it is
unavoidable if one needs to render large batches or large amounts of
instances. Quick recap, under the assumption that we compromise
flexibility in favor of speed and use OpenGL 4.5 level graphics APIs:
Avoid buffer changes one, two different vertex layouts (for example for static and animated meshed)
Avoid program changes well defined firstpass program (deferred rendering) or subroutines in a global attribute buffer
Minimize drawcalls Usage of instanced and indirect rendering
The
usage of draw commands and indirect rendering is nice enough. The
amount of drawcommands is reduced by using instanced rendering for
entities that have different uniform attributes but the same vertices
and indices. This results in the command and entitiy buffers of the
following form:
Entities
uint entityId
678
mat4 transform
000...
uint materialIndex
18
uint entityId
1566
mat4 transform
000...
uint materialIndex
2
Commands
vertexOffset
0
indexOffset
0
indexCount
99
instanceCount
2
vertexOffset
1200
indexOffset
99
indexCount
33
instanceCount
3
Firing indirect rendering call is now done with a
count of two, because we have two commands. 5 objects will be drawn. The
shaders are invoked several times and the entity data can be accessed
with an index and fetched from the entities buffer. The resulting
indices in the shader will look like
Shader Invocations
DrawId
InstanceId
Entity buffer index
0
0
0
0
1
1
1
0
???
1
1
???
1
2
???
As mentioned in the previous blog post, there's no
chance for us to know the entity index when the second command is
executed, because the current offset is based on the amount of instances
the previous commands draw. The solution is to use an additional offset
buffer with size of the draw command buffer. For every command, we set
the offset to the appropriate value when creating the commands on the
cpu side. With instance based culling, this problem intensifies, because
the cpu doesn't know the offset anymore. The calculation has to be done
on the GPU now. My solution is still based on vertex shader kernels,
but I will tell you later why this is probably problematic. First how it
is done, because conceptionally, it will be the same for compute
shaders. The layout now looks like this:
Shader Invocations
DrawId
InstanceId
Entity buffer index (command offset + InstanceId)
Offset of the command
0
0
0
0
0
1
1
0
1
0
2
2
1
1
3
2
1
2
4
2
The first step is to determine the
visibility for every single instance. Vertex shader kernels have an
advantage here, because they can be arbitrarily large (compute shader
groups are limited to 1024 or so). A single draw call can determine
visibility for dozens of thousands of instances or entities. Combined
with instancing, we can use DrawId and InstanceId to index into the
command buffer and offset buffer (DrawId) and into the entity buffer
(offset + InstanceId). Since the same kernel sizes are applied to every
command, invocations are wasted if few commands have many more
instances as others. So you might want to launch draw calls without
instancing, one per command, which could be faster here.
The
visibility is again stored into the visibility buffer, which has to be
as large as the entity buffer now. With non-instanced culling, size of
the command buffer was sufficient. One important thing has to be done
now: Every visible entity thread has to increase a counter that is
associated with the corresponding command - since this is done per
invocation, atomic operations are needed. So we need another int buffer
(just like the offset buffer), that holds the visible instances count
per command.
The reason why this is so important is,
that this is the bit of information that is used in a second step to
append entity data and draw commands in parallel. This is done by an algorithm similar/equal to parallel prefix sum - you can google it. Tldr: Each command has to know how many visible instances all previous commands produce in total, so that it can append its own instances there.
I call the seconds step appending step, while the first one is the visibility computation step,
that actually calculates the visibility of an instance. For a massive
amount of instanced commands, one would probably want to launch a
two-dimensional kernel of the size n*m where n is the amount of commands
and m is max(maxInstanceCount, someArbitraryValue) or something. Again,
with vastly different instanceCounts per command, multiple shader calls
could give a benefit.
So now we need a target buffer
that holds the entity data, a target buffer for the commands and a
target buffer for the entity data offsets. Additionally, we need an
atomic counter for the target command index and then an atomic counter
per command, that is the current index of the entities per command. Each
shader invocation has its own command index in the DrawID built-in and
the instance index in the InstanceID built-in. So we can calculate all
information that is needed on the fly:
struct oldCommand = read from the bound command buffer with DrawID
uint oldCommandEntityOffset = read from the oldOffsetBuffer with DrawID
uint oldEntityIndex = oldCommandEntityOffset + InstanceID
uint visibilityBufferIndex = oldEntityIndex
uint targetCommandIndex = atomicAdd(commandConuter, 1)
uint targetInstanceIndex = atomicAdd(commandCounters[targetCommandIndex], 1)
uint targetEntityIndex = sumOfVisibleInstancesOfAllCommandsBeforeCurrentCommand
The
current entity data can then be written to the targetEntityDataBuffer,
as well as the offset for the instance/command. The command can be written by the first active
thread (InstanceID == 0). The resulting buffers contain only the visible
instances, offsets of the visible instances and drawcommands that can
be used to only draw exactly those instances.
Here's a video demonstrating occlusion and frustum culling with this technique:
Bonus: For the visibility computation step, it's nice to launch a vertex shader kernel, since the kernel can be arbitrarily large in two dimensions at max. Since there's no shared memory involved, this will probably perform better than the compute shader equivalent, maybe at the same speed, but it shouldn't be slower. The appending step needs an atomic operation per invocation, because every invocation increments the counter if the corresponding instance is visible (which the other invocations couldn't know). Instead of "global" shared memory, one could use shared memory of a compute shader group. Shared memory in a group is much faster than atomic operations between a gazillion vertex shader invocations, so I will implement this at some time and may be able to show a performance comparison.
Some problems just stick in my mind forever. I searched for a nice way to enforce the presence of a static method via an interface. C# has type constrtaints for this need, but I find the syntax rather ugly. For example, one could require that a static factory method is present on the class of a given instance. A problem regularly solved with factories or factory methods, or even factory methods as parameters.
In Kotlin, interfaces can have companions. However, they are not part of the contract of the interface, that means it's not abstract and you don't have to override it/can't override it. Methods defined on the companion can't be overriden either, so the following code doesn't do what one expects it does:
interfaceSomeInterface{companionobject{funxxx(){println("Base method by SomeInterface")}}}classMyImpl:SomeInterface{funSomeInterface.Companion.xxx(){println("Overriden static method by MyImpl")}}funtest(impl:SomeClass.SomeInterface){with(impl){SomeClass.SomeInterface.xxx() // surprise here!}}
This prints ... Base method by SomeInterface ...
The corresponding bytecode piece in the test function is
Since the goal is to enforce the presence of a static method, it's likely that there is no base implementation at all, so no default implementation in the interface. In this case, we can only define a companion object in the interface without any methods. It's then possible to define interface methods for the companion object, just like fun SomeInterface.Companion.myMethod(). This is similar to include extension functions in an interface's contract, as described in my last blog post. Implementing interfaces would then need to implement this method. Here's a complete example on how to do this.
classSomeClass{interfaceSomeInterface{companionobjectfunSomeInterface.Companion.xxx()}classMyImpl:SomeInterface{overridefunSomeInterface.Companion.xxx(){println("Overriden static method by MyImpl")}}classMyOtherImpl:SomeInterface{overridefunSomeInterface.Companion.xxx(){println("Overriden static method by MyOtherImpl")}}companionobject{funtest(impl:SomeClass.SomeInterface){with(impl){SomeClass.SomeInterface.xxx()}}}}funmain(args:Array<String>){test(SomeClass.MyImpl())test(SomeClass.MyOtherImpl())}
It will print ... Overriden static method by MyImpl Overriden static method by MyOtherImpl ...
The corresponding bytecode of the test function now looks like this:
So the old invokevirtual became an invokeinterface. This most likely comes with a small performance overhead. But hey, can't have everything.
This construct allows for factory-like constructor functions. Sadly, operator functions are not allowed to be declared on interfaces. That means, the constructor method has to be named create or something, leading effectively to an interface function signature of
This eliminates the sense in all this for me, because I would then rather type
println("Created ${impl.create().javaClass}")
The only worth-it syntax that would satisfy me would be this - based on an invoke operator function defined in the interface, usable through the interfaces companion object.
CAUTION: This post got somewhat long :/ TLDR: You can effectively use Kotlin's delegation if you want to mimic ad-hoc polymorphism.
I was always fascinated by ad-hoc polymorphism. The clear separation between data and behavior that can for example be achieved with tools like Scala's type classes, is especially useful when combined with data oriented design, which is important for game development as well for example.
I realized, that the usefulness depends heavily on how this feature can be integrated and supported by the programming language you work with.
For example in Go, you don't have to implement an interface explicitly - if your 'class' (Go doesn't have classes) satisfies the contract of the interface, it is virtually implemented. That means you can safely pass your instance of your class into a method that expects an interface. I like that this is called static duck typing. This is a form of structural typing, because your instance is typed by parts of its definition. Structural typing has many advantages, but also the disadvantage that code can break or fail at runtime, when said interfaces change visibly or invisibly. Also, there's the potential of naming clashes, for example if two interfaces have methods with the same name/signature. Although I don't know anyhing about the internal implementation of Go's structural typing, I suggest that the whole system works without creating wrappers under the hood.
In languages like Java and Scala, we don't have this luxury, or rather we have to solve slightly different problems here. I find Scala's solution a very good one - but I don't know too many comparable others :) The type classes combined with implicits are a very good example of how to integrate this feature into a statically typed language (This is a very nice post that pretty much answers all questions about how those type classes and implicits in Scala work).
And here's the big but (and I can not lie..): The feature is very infamous by people that don't use Scala and even infamous by some people who do use it. My humble opinion is, that it boils down to the old problem: As a programmer, you read more code than you write. That should imply, that the ability to read code more easily is more important than the ability to write code easily. I would like to correct this statement slightly: It's more important to be able to easily read and understand what's happening. Very concise code is nice to read, because it hides a large amount of information - but there is a thin red line that should not be crossed when hiding information. Problem here is, that this is very subjective to a degree. One of the biggest critics to Scala is the complex implicit resolution, where people really struggle to understand it and even the compile times suffer drastically from it. This weakness is so clearly a problem not only for mediocre programmers, non-library developers but also for code quality of a project in general, that the Kotlin creators decided to leave ad-hoc polymorphism out of the language until now.
At the time of writing this, similar blog posts to my thoughts were created here and here. And in fact, even after reading the whole language improvement suggestion for ad-hoc polymorphism, I'm not quite sure if ad-hoc polymorphism without something comparable to Scala's implicits makes sense at all. Here's a small example of a situation where the usage of ad-hoc polymorphism would be appropriate: You have an interface and some implementations of this interface. The interface is consumed by some methods, one of them is someFrameWorkFunction:
interfaceMyInterface{funmyInterfaceMethod()}classMiOwnImplementation:MyInterface{overridefunmyInterfaceMethod()=println("This is my own implementation")}funsomeFrameWorkFunction(parameter:MyInterface)=parameter.myInterfaceMethod()funmain(args:Array){someFrameWorkFunction(MiOwnImplementation())}
Everything is fine until you have to integrate code that's outside of your control. As the following class, that may already have the functionality you need implemented, but with a wrong method signature and without your interface (because where should people get your interface from...):
classForeignImplementation{funprintSomething()=println("This is a foreign implementation")}
Irrelevant which solution you take to integrate this foreign implementation, one thing is for sure: you need a description how the needed functions are implemented, hence a mapping from interface methods to implementation methods.
With an implicit resolution algorithm, one could write
someFrameWorkFunction(ForeignImplementation())
instead of explicitly instantiating one's own facade.
The question here is: Is the implicit resolution worth the hassle that one now has to search for the conversion definition? Is the example with the explicit conversion that much worse readable? In my opinion, until now, there's no reason to not state the conversion explicitly. Only with taking the feature even further, it makes sense to have it - for example because you are used to using contextual objects as implicit parameters, as they are embedded in the language, like in Scala. For example it's possible to provide default implementations that can be imported by the user of your library. Without such a feature, one would have to provide overloads of a method that takes types as parameters. Kotlin won't benefit from it, instead it would be an artificial feature that is limited to one situation.
Swift on the other side allows for extensions, that can have an existing class implement an interface with some limitations I don't know in particular. Extensions are automatically available through module import. So they are somewhat comparable to what Scala can do, because your module can contain all the default extensions and make them available for the user.
In general, the separation of state and behavior could become the default option and ad-hoc polymorphism could be the default over parametric polymorphism. But on the JVM, you will have to pay for the wrapping class, so this is probably not the most wise idea. Extension functions on the other hand seem to extend a class's interface but does it via syntactic sugar and static dispatch. That means the extension can be imported on the callee's side, whereas class extensions or type classes are chosen by the caller.
So let's think about a more complex scenario. The interface our framework method accepts is a more complex one, that extends the List interface and provides a getLast() method that doesn't throw an exception if the list is empty, but returns a nullable reference. This can be a default implementation that uses an abstract property. Additionally, a real interface method is declared for prettyprinting, that classes have to implement.
Since one can only delegate to constructor parameters and new instances in Kotlin, there is no way to have MyList provide default implementations for all List methods just by delegating to the abstract property list. This limitation prohibits using a simple inline object declaration in a method that consumes a MyList interface because you would have to implement all methods of the List interface or create a local list outside of the statement.
A solution would be to create a simple Implementation (as one could and should typically with heavy use of delegation), that implements the List interface by itself with delegation, like:
While this is not ad-hoc polymorphism by definition, under the hood it's equivalent to comparable solutions. Delegation can help to overcome many of the pain points when the need to satisfy interfaces with existing classes emerge. As for a general purpose usage of type classes, one has to keep in mind that delegation has a small runtime overhead, as it creates objects and delegates method calls.
Another very clean solution would be to use scopes extension methods to achieve the same thing. Usage of with can bring extensions defined on a interface into scope. Using a singleton would prevent us from creating objects, but obviously, one would have to pass the extension provider explicitly as a parameter.
Some weeks ago, I implemented GPU skinning in my engine. As mentioned in my posting about multithreading and high performance stuff, you could face a problem with animated objects: Depending on the max amount of weights per vertex you want to support (usually 4 or 8), you have a different vertex layout to support now. Additionally, your entity contains a bone hierarchy that can be arbitrarily shaped. I implemented a second entity data buffer additionally to the main entity buffer that contains model matrix, material index etc. This has the advantage, that we now have a buffer that only contains equally sized nodes of all scene object's bone hierarchies....means that we can freely do index access into this global array from all shaders.
So in the vertex shader for animated objects, the corresponding bone (matrix) can be fetched from the structured buffer by index. The retrieved data structure contains its parent node index if present or -1 if the bone is the top of the hierarchy. Here we have a hierarchical data strucutre traversable by the GPU.
Per entity, it is now necessary to define a maximum count of animations that can run at the same time. Since vec4s are nicely aligned by the GPU, I chose 4. So each entity data now contains an additional vec4 that contains 4 float values, indicating the weight of the 4 active animations. I wanted to avoid an additional indirection here, so I didn't define the animation data in their own buffer. On the CPU side of things, an animation controller can play an animation and only has to update a single value in the entity data buffer (which is lockfree and unsynchronized, so extremely fast, read my post about multithreaded engines).
The vertex shader already has the actual entity data structure and can do the animation blending now on the GPU directly.
Recapture: The CPU updates the animation controller. The result is a float value per animation... the current weight of the animation. Since bones are precalculated on model import, everything is ready for the GPU now. The GPU only has to do some buffer fetches and some matrix multiplications. Combined with instanced rendering, where the animation controller is part of the per-instance data, one can have thousands of independent animations, for example to simulate people crowds. Or many Hellknights:
Keep in mind that there's no culling right now - neither instance cluster wise, nor instance based.
I really love rendering technique performance enhancements that work with existing asset pipelines and don't need artists to tweak and configure scene objects. Occlusion culling is a technique that is necessary for every engine that should be able to render interior scenes or outdoor scenes with much foilage. Some existing techniques require the user to mark occluder objects explicitely - which is not sufficient for outdoor scenes where ocludees are occluders too, some techniques are fast, but introduce sync points between cpu and gpu and therefore introduce latency and with it popping artifacts.
This papter describes a super nice algorithm very briefly: Two-phase occlusion culling. This technique has some advantages: It is blazingly fast, because it's GPU-only. Culling dozens of thousands of objects and even single instances is possible. It introduces no latency, so no popping artifacts. And it doesn't need hand-tweaking, no need to differenciate between occluders and occludees - every object can be both. The disadvantage is, that the technique requires a fairly new GPU with indirect rendering.
The algorithm
We need some buffers first:
A source command buffer, containing n commands.
A target command buffer of size n.
A visibility buffer, containing n ints, an entry for each source command.
A atomicCounter buffer.
All scene objects produce draw commands that are put into a buffer. Take a look at my other posts to see how to implement a lock-free multithreading engine with unsynchronized buffers. The entity data is put into a buffer as well. Part of this data is a AABB, calculated on the CPU side. The CPU only needs to calculate the AABB and put the latest data into a buffer.
The GPU-side now performs the following steps for rendering: A thread per draw command is executed. The corresponding entity data is fetched from the other buffer. The AABB is culled against the hierarchical depth buffer of the last frame (or an empty one if current frame is the first frame, doesn't matter). If the AABB is occluded, the command saves visibilityBuffer[index] = 1. Now another shader is executed with n threads. Every thread takes a look at it's visibilityBuffer index. If it contains a 1, the entity is visible and the sourceCommand is fetched and written to the targetCommand buffer. The index is the result of an atomicAdd on the atomicCounterBuffer. Now the atomicCounterBuffer contains the drawCount, while the targetCommand buffer contains the commands we need to render. Rendering is done with directRendering, so no readback to the CPU at all. Afterwards, the highz buffer is updated. Now the procedure is repeated, but only the invisible objects of the current frame are tested against the updated depth buffer. All visible marked objects were falsely culled and have to be rendered now. So all the algorithm needs is two indirect drawcommands, as well as the culling and buffer copying steps.
Here's an example of a scene, where 7-8 cars with roughly a million vertices is rendered. When behind a plane, they are occluded and therefore, no draw commands are comitted and the framerate goes through the roof.
Implementation
Normally, you are already rendering depth somehow, at least in the regular depth buffer. Here's the most generic compute shader way to create a highz buffer with OpenGL:
The culling shader code can be found on rastergrid, where you can find very much information about highz culling in general. I experienced some strange bugs with compute shaders, that seemed to be executed twice on my machine. Since I wasn't able to get rid of them, I used a vertex shader trick to execute arbitrary kernels on the GPU: Have some dummy vertex buffer bound (needed by specification) and use glDrawArrays with (commands.size + 2) / 3 * 3 (we need a multiple of 3 here). No fragment shader is needed for the shader program. In the vertex shader, gl_VertexID can be used as the invocation index. The following shadercode copies draw commands from visible entities to the target buffer. It's just an extract, but you get the idea:
There is some aspect missing yet: With instanced rendering, one has to introduce a offset buffer, where every entry gives the offset into a instanced entity buffer for a draw command. My current implementation has a AABB for an instance cluster, grouping several isntances into a draw command that can be culled. The next post will hopefully show, how this tecchnique can be extended to cull single instances, in order to have perfect culling for example for thousands of foilage objects.
