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.
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.
There is this one question since beginning of multicore processors: How to multithread your game engine? I can't answer this question in general, but I can answer the question How to multithread the rendering part of my game engine?
Problem
The most simple case is a single-threaded game engine that does this:
while(true) {
simulateWorld();
renderWorld();
}
The update step produces a consistent state of the world. After each update, the rendering is done. After the rendering is done, the next cycle is processed. No synchonization needed, everything works. The bad thing: simulateWorld is a cpu-heavy task, renderWorld is a gpu-heavy task. So while the world is updated, the gpu idles, while the gpu renders, the cpu idles (more or less). And the worst thing: Your framerate is limited by both the cpu and the gpu. Your frametime is timeOf(simulateWorld) + timeOf(renderWorld). Our target frametime is timeOf(renderWorld) and to keep this time as low as possible. More precisely the target is timeOf(renderWorld).
Foundations
Okay I lied: The above mentioned problem is only the overall-globally-problem we solve. There's a shitload of other problems, that mostly depend on the language platform, graphics api, hardware, your skillset and so on. Since our lifetime is limited, and I want to give practical, real-world-relevant help, I make some assumptions. One of these is, that you use OpenGL and a pretty new version of it. Let's say 4.3. Multithreaded rendering could probably be done better and faster with DX 12 or Vulkan, but let's stay cross-platform and simpler with OpenGL.
I assume that you already have at least a little bit knowledge about how game engines work, timesteps, scene representations and so on.
Multiple gpu contexts
In order to be able to issue commands to OpenGL, you have to use a thread that has an OpenGL context bound to it. Architecture-wise, there is the CPU, the OpenGL driver and the GPU. The driver holds a queue, where the commands from the SPU are buffered somehow (implementation dependend). Then again, there is a queue for the GPU - that again buffers commands that came from the driver (implementation dependend). First, all commands the CPU issue are asynchronous, which means there's no actual work done on the GPU yet, but the command is queued by the driver. The order is preserved, that's what you can count on. The implementation can decide how many commands are queued up, until the cpu thread will block on command issuing. And the implementation can decide how many commands are buffered on the GPU side of things.
Now, having that said, let's think about multithreading. What we can control is the CPU side (unless you write your own driver, which I doubt you want to do). Multiple cpu threads would require multiple gpu contexts - one for each thread. While this is theoretically possible with OpenGL, it is a very dumb idea in 19 out of 20 cases. As with traditional multithreading, context switching comes with a very high overhead - so you have to ensure that context switching overhead doesn't eat up the performance you gained from using multiple threads. And here's what's wrong: It seems that all OpenGL drivers (where you issue your comamnds at) except the one for iOS, are implemented singlethreaded. That means you can issue commands from multiple cpu threads, but on the driver thread, those commands are processed sequentially, with a context switch in between. You can find a more detailled explanation here, so that I don't have to lose many further words, but: Don't use multiple contexts for anything else than asynchronous resource streaming.
I assume we only use one OpenGL context. That means, all OpenGL calls must happen on a single thread. The construct used for this is the command pattern. A few hints: You should issue as few commands to OpenGL as possible. You should issue as lightweight commands as possible. Obviously, using only one thread for command execution limits the amount of work that can be done by this (cpu) thread. Nonetheless, you want a single, inifintely running worker thread that owns your OpenGL context and takes commands out of a non-blocking command queue. For convenience, you can seperate commands that should return a result (hence block) or should just be fired and forgotten. It's not nessecary that all commands are properly implemented by yout context wrapper/worker thread class, even though it makes your application more predictable in terms of performance. I implemented a non-blocking, generic command queue in Java here that uses Runnables and Callables as Commands. The principle is also explained more detailed here.
Extractor pattern
Extractor pattern is a term one never finds on the internet when searching for information about rendering. The first time I heard this, was when a (professional graphics programming) collegue of mine explained the basics of renderer architectures to me many many years ago. Fancy name for a simple thing: If you share data between two consumers (not exactly threads in this case), you either have to synchronize the access somehow, or you extract a copy of the data to pass it to the renderer in this case. That implies, that you need a synchronized/immutable command-like data structure, that represents all the information you need to push a render command. That plays nicely with the chapter above, you know, command queue etc. In languages other than Java where you have true value types, the implementation could be easier - although having very large renderstate objects copied over and over might be a drawback here. The chapter below shows another way of handling this problem.
Multibuffering
Let's assume that the GPU only consumes renderstate, but doesn't alter it. That means if the GPU calculates any fancy physic, or results that should be passed to the next render cycle, than it isn't seen as part of our traditional renderstate for now.
That means the only producer of renderable state is the CPU. Since we don't want to render a scene where the first half objects are in timestep n and the second half is still in n-1, we have to be able to access a state of our gamestate, that is concise somehow. This is easily achievable with a task-based architecture, that basically has only one update thread, that sequentially crunches down what you want to do in parallel. For example if you have 10 game objects, the updatethread pushes 10 update-commands into a pool of worker threads and after all of them returned a result, we have a concise world state we can use and used all threads our system can push. I don't think, there's an alternative approach to multithreading that can be used in a general purpouse game engine, but I may be wrong. Instead of creating a new renderstate object and pushing a command to the renderqueue, we use something that's known in multithreading environments for ages: multibuffering.
This should be confused with double or triple buffering that is used to display images on your monitor, although the principle behind it is the same.
I skip explaining why double buffering isn't enough to satisfy our needs. Just use triple buffering and be happy, if you can afford the additional memory consumption. This works the following way.
You have three instances of your renderstate. You have a wrapper, that encapsulates these three instances. Instance A is the currently readable state. The renderer uses this state for rendering, so while rendering is in progress, this instance mustn't be touched by anyone else than the renderer. Instance B is the current staging copy of the renderstate. It is the next state, that the renderer will use for the next frame, after the current frame is finished. Copy C is the isntance the update is currently applied on.
Now while this sounds simple, the important thing is, how to swap those instances correctly. Our main purpouse is to keep the GPU busy and to be able to render maximum fps, although one could theoretically (and practically) limit the framerate somehow (vsync, fps cap etc.).
I realized this with a ever-running thread that does push and wait for a render-scene-drawcall constantly. After the frame is finished, the read copy is swapped with the staging copy. It's important, that the renderer get's a fresh copy on every swap. If the update thread isn't fast enough to provide a new updated renderstate copy, the renderer would render a state that is older than the one just drawn. This will cause flickering objects. I realized this with an ongoing counter, and I prevent swapping to a state with a lower number then the current state has. Let's assume your engine and the machine is capable of pushing 60cps update and 60fps framerate.
Let's face the other swap: The update thread updates the write copy C constantly as fast as possible. When finished, the write state becomes the new staging state B, so we have to swap them. We can't do this if the renderer is currently swapping his read and the staging state. So we need a lock for swap(A,B) and a lock for swap(B,C). If rendering can be done with okayish framerates (which we assume), the updatethread can wait (block) until swap(A, B) is finished. If you are using only coherent memory access, than you're donw here. But you wouldn't search for state-of-the-art rendering, if you don't use incoherent access. So let's get to the final ingredient we need for our super fast renderer.
Lowering draw calls and persistent mapped buffers synchronization
At the very beginning, there is the need to reduce the amount of work the gpu has to do, in order to render your scene. There are paths thorugh the OpenGL API that are more expensive than others, and there are paths with very very small overhead, if you can afford the loss of flexibility that comes with using it. This can give you a rough overview about how costly API calls are. I suggest we skip a long explenation and you read this. Summed up: You want unsynchronized buffers for all your data and handle synchronization by yourself. This results in no driver or gpu work for the synchronization, which is crucial for maxing out your performance. Remember that Vulkan was designed to exactly kill the driver overhead of OpenGL. Furthermore, we reduce draw calls and state changes with bindless resources and one of the most important things: indirect and instanced rendering.
Having all these things implemented, there's one last thing to add to our triple buffering: synchronization. Since the driver works asynchronous and the gpu, too, there's no guarantee that the gpu doesn't use the buffer of our current write copy, that the update threads currently writes to. To adress this, one has to insert a fence sync object into the pipeline and associate it with the state, whenever a state becomes the current write state. When the render thread uses this thread and pushing all render commands of the current frame are pushed, the fence signal is pushed. Whenever this signal is processed by the gpu, the update thread can write to the associated state without any problems. The update thread can prepare the renderstate update and wait until the prepared data can be applied. This effectively blocks the update thread, if the renderer is more than 2 frames behind the update thread.
Special care has to be taken if you have any timestep-dependent calculations in your rendeirng step: Since rendering is decoupled form the update-step, you have to calculate the timestep by yourself somehow in the renderthread, based on the last tick and the time passed since then.
That's it
Using the fastest possible paths through the OpenGL API. You need shader
storage buffers and indirect (and inntanced) rendering, probably
combined with bindless textures
Model a renderstate class that can be your complete draw command
Run a thread permanently, that permanently pushes rendercommands
Someone has to fight the battle against the "Java is so slow, all Java games have low fps" myth. Maybe Java is not the best language for game development because it lacks value types and easy and zero overhead native code integration .... but the results one could achieve with using a zero-driver-overhead path like modern graphics APIs recommend for so many years, can be on par with what you can achieve in C or C++ as in Unreal, CryEngine or Unity. The secret is: Bindless ressources, indirect and instanced rendering, persistent mapped buffers, direct state access and of course good old multithreading.
So, the most important things first: Use indirect rendering (to minimize calls the cpu has to issue!) and a shared global vertex buffer (to reduce state changes). Use large uniform or shader storage buffers for your object's properties and material properties. For each object, push a command into the buffer. Massive object counts cause massive command counts and large command buffers, so one can now use instancing to further reduce command count. With a clever structure (a offset buffer for example), one can easily have unique properties per object instance (for example dedicated textures per instance!) sourced from a large uniform buffer, when it's okay to share a common geometry (vertices). Et voila, 2ms cpu time to fire a render command that draws 340.000 instanced cubes with 4 million triangles at 60 fps in Java. Each object can have it's own textures and properties etc.
During my 3d engine project, the demand to load arbitrary image formats came up. My choice was ImageIO since it's shipped with Java. Short time ago, I realized that there is a cool Apache lib called commons imaging. The main goal would be to speed up the loading processes, so finally I have a reason to do some microbenchmarks, yey.
Since there are only very few tools for micro benchmarking and most of them offer poor features and documentation, I recommend to use JMH. As always, documentation and examples are kind of confusing, so here's the workflow I used.
First of all, you need two dependencies - the jmh core lib and the annotation processor.
Now a piece of software is needed that runs all your annotated methods. This can be done with some command line stuff, I prefer a solution that can be packaged as a jar or directly run from the IDE. Embedding your benchmark config in a class and write a small main method can do the job. The class you pass into the benchmark via the options is scanned for annotated methods.
Run the main method from your IDE or export a package. Note: If you export a jar, you have to provide the dependencies - if you don't want them to reside in your classpath, create a fat jar with the maven-assembly-plugin. Tested it, works fine. Here's the result:
