I am a big fan of metaprogramming and until shortly I have done most of metaprogramming in C++ which i really like. The only problem I have with C++ is that the compile times quickly blow up.
Here is the a small blog post about an entity component system in C++ https://maikklein.github.io/2016/01/14/Entity-Component-System/
I have also implemented it in D and the compile times are much better, they are still at around 1 sec where the C++ version is already at 20+ seconds.
I quite like the idea of metaprogamming with types, can this also be done in Nim? Would you say Nim might even have better metaprogramming capabilities than D? If so could you explain why?
How are the compile times compared to D for example?
I know that nim uses a thread local, incremental GC, but is it practical to avoid it most of the time while still be able to use the std library?
Is it possible to manage the lifetime of objects? An example would be std::weak_ptr + std::shared_ptr in C++.
Does Nim have ownership semantics?
How is Nim's tooling? I deeply care about renaming types, functions, variables etc. I saw that http://nim-lang.org/docs/idetools.html seems to be able to support renaming with "--usages" but I haven't seen any editor/ide that supports refactoring.
I'll let someone else answer specifics on metaprogramming.
On C++, I have to say that compiling templates with gcc is very slow. Microsoft VisualStudio can speed that, but not enough. boost.python, boost.serialization, and boost.mpl are all nice ideas but horrible in practice because of compile-times.
here is an example of Nim metaprogramming which generate glue code so Nim can be accessible from Lua
https://github.com/jangko/nimLUA
it's a bit messy, because I expand the macro multiple level, and using string instead of generate the AST directly by macro API. but in the end I confidently can say Nim macros is very powerful
I never like doing the same thing in C++, but writing Nim macro is a whole different experience. you can easily inspect type implementation, function implementation, and generate a very close to hand written glue code at compile-time.
I never use D before, but after reading the D template and compile-time feature documentation, I believe Nim macros capabilities is better than D. at least D cannot inspect the body of other function/type from it's template. (some call it reflection?)
Both D and Nim have excellent compile time evaluation, if you can create compile time raytracer in D http://h3.gd/ctrace/, that can also be done in Nim
Nim compiler compiles very quickly, but because it also call another compiler(C/C++), large portions of compile times spent by C/C++ compiler, except you are targeting JS backend
and... you don't need to be an über-guru to start writing Nim macro, the syntax is the same with the rest of Nim
maikklein: Would you say Nim might even have better meta-programming capabilities than D?
I would, but mostly because D lacks proper AST-based macros (last I checked) and relies heavily on string mixins to do anything close to what is very natural and type-safe in Nim (Nim has string mixins too, BTW). For instance, it's very difficult in D to do a "static foreach" over a tuple of types.. you can do somethings with CTFE here, but there are some limitations and you can be forced to use recursive template calls, which obfuscates the code a lot. Compared to Nim where such things are easy to do in a macro. (Disclaimer: it's been over a year since I've used D and these limitations might have changed).
One area that Nim is 'behind' D/C++ however, is it currently lacks Variadic Generics. This isn't really a limitation, since you can accomplish the same thing with a macro + varargs[typed], but it will force you to approach some situations a bit differently than you might in D or C++ (and indeed, looking at your example you use this feature a bit). Also, note: variadic generics where (at one point) being worked on for Nim. See this issue on github. I'm not sure of it's current status or priority.
maikklein: How are the compile times compared to D for example?
Nim actually compiles surprisingly fast, even though it compiles to C, and has extensive meta-programming features. Nim can compile fast partially because of the way it compiles and links the C code. Nim produces a single C file per module (without any header files), and stores these (and their compiled obj counterparts) into a cache directory. Without headers there's no C inter-dependencies GCC/Clang/etc need to consider (beyond C libs you explicitly link too). Because the results are cached, Nim only needs to recompile modules that where modified (and their dependencies), invoke a C compiler on those files individually, and then link all the obj files together as a final step.
Here's a benchmark posted to Hacker News ~1 year ago that compares multiple languages (including both Nim & D) with their compile times. Nim compiles in 893ms compared to D's 1613ms.. and it's resulting executable is faster as well.
Secondly, Nim's VM (responsible for executing macros, CTFE, etc) is very fast. Last I heard, it was "faster than Python". So even if your code is heavy on macros compile times don't suffer too much. As a personal example, I have a project ~5k LOC which pumps ~60% of that through 1-2 macros.. it compiles (with no cache) in <3s, and <4s in release mode.. modifying a single file and compiling with an existing cache takes ~1.5-2s (depending on the file modified).
maikklein: is it practical to avoid [the GC] most of the time while still be able to use the std library?
Yes & No, depending on what you mean by "avoid".. For instance if you compile with --gc:none to disable the GC altogether than you're in a similar situation as D where much of the standard libs are unusable due to leaks (namely those dealing with strings and lists). However, unlike D, Nim's default GC is thread-local and soft real-time.. so leaving it on and using unmanaged memory where you need it is less of a problem (because it's easier to avoid GC-induced stutter). You can do that in D too, of course, but for some applications you might want to do things like avoid using managed memory on specific threads, etc (to avoid D's STW GC pausing them every time it needs to collect). Again, be warned my knowledge of D here is a bit dated.
Also note, last I heard Nim had some level of leak detection built-in to be used with --gc:none.. but I've never personally used that, and don't know much beyond that it once existed. So if you're interested perhaps ask the community about it specifically to find out more.
maikklein: Is it possible to manage the lifetime of objects? ... Does Nim have ownership semantics?
I'm not sure exactly what you're asking here, but I can explain how memory management works in Nim. First, Nim doesn't have Rust's concepts of compile-time ownership/borrowing.. nor does it need a weak/strong reference distinction to prevent leaks. All ref type variables share ownership of the object they point to. Also, Nim has multiple GCs with slightly different features & performance characteristics.
With Nim's default GC any ref type uses ref-counting to track lifetime (this is deferred, meaning you don't pay for counting from references on the stack). Any type capable of containing cyclic references is additionally scanned for them, which is why there's no need for 'weak' refs. (Note: you can mark potentially cyclic types as {.acyclic.} to avoid the cyclic detection, but that's an unsafe optimization).
Thanks for the answers, they helped me a lot.
One area that Nim is 'behind' D/C++ however, is it currently lacks Variadic Generics. This isn't really a limitation, since you can accomplish the same thing with a macro + varargs[typed]
I was reading though Nim's std and because I did a lot of with ranges in C++ and D I was specifically looking at seqUtils.
Is this what you mean with varags?
proc concatT: seq[T]
To me this looks as it might be limited to just T? Which of course is what we want for concat.
proc zipS, T: seq[tuple[a: S, b: T]]
But zip is limited to 2 types instead of N. Is this the limitation you were talking about? Can zip be implemented so that it would zip N ranges into a tuple?
As for the GC. I really don't care about the GC much. For example in my ECS it would own most objects. They would live in a giant array without any indirection. In C++ I gave out indices with to those objects with a shared and weakptr.
I did this because I want to ECS to be able to delete an object, and if other objects have references to the object, they would be nulled. In a GC language they would still live because an object only gets destroyed if all references to it are gone.
D has the same problem but I was able to work around it, by implementing a weakptr.
I also don't care if the GC is running in the background but I usually don't want to produce any garbage at all. To me it always seemed that languages with a GC tend to produce more garbage than they really needed to.
As for memory management / ownership, think of std::unique_ptr for example. So you would delete the copy and assignment operator.
To transfer the unique_ptr to another object/function you would need to move it in c++. The move constructor would take care of transferring the ptr behind the scenes in a correct way.
D has also problems to express this.
It is really difficult for a language to have both GC and a GC-less mode. The reason is that GC-less operation requires that module interfaces are (implicitly or explicitly) encumbered with additional information; and only a small minority of developers work in a domain where there are benefits that offset this cost and the additional micromanagement required by manual memory management.
Nim is probably more amenable to GC-less operation than the majority of programming languages (it has in part be designed to be a better C also), but its stdlib modules are mostly designed for use with GC, so you'd have to implement a lot of stdlib material from scratch.
If you're dead set on not using a GC at all, C++ is probably still your best bet, because it has the strongest ecosystem and the best language support for working without one (with Rust in second place).
filwit: One area that Nim is 'behind' D/C++ however, is it currently lacks Variadic Generics.
One more is that Nim lacks wrt D/C++ is template template parameters which is a bit of a shame. Rust also lacks this. When people moan about HKT in Rust, this is the issue. I'd love to see Nim get this feature. Simple use case in future Nim:
type
Table[K, V, A] = object
keys: A[K]
values: A[V]
@maikklein
But zip is limited to 2 types instead of N. Is this the limitation you were talking about?
Yes.
Can zip be implemented so that it would zip N ranges into a tuple?
Yes, via a macro with a varargs[typed] parameter. But, rather than showing you how I might implement an arbitrary zip function in Nim so that you can better understand how your ECS might be ported, let me instead show you a working prototype of an ECS written in Nim which I modeled after your design:
"Brim" - Nim version of maikklein's 'Breeze' ECS
A couple of Notes:
I did this because I want to ECS to be able to delete an object, and if other objects have references to the object, they would be nulled. In a GC language they would still live because an object only gets destroyed if all references to it are gone.
Yeah, maintaining safe pointers to objects in continuous-memory arrays is a challenge I'm still trying to find the best solution for. Instead of doing an ECS specific smart-pointer type like you're talking about, I've been mulling over how to use Nim's macros to ensure/proof an entity's lifetimes so components can just use ptr (unsafe) references to each other without worry.
My potential solution here is somewhat related to an idea I had about being able to define an entity's possible "states" (and their potential transitions to other states), including from which state an entity could "die" from. The design might consider each state as a unique component group (even if it has identical component types as another group) which would allow you to [1] move some component data to the state structure (eg, if you know each 'Enemy' in the 'Angry' state is going to be flashing red, then you don't need to store color/shader/etc details per entity.. you can just infer that from their state when rendering), and [2] you could model the lifetime of entities (since "dying" would just be a 'transition' some states where capable of).
For example, some entities could be "global" with no 'death' state per level/scene/etc, so any other component could point to them without worry for the duration of that level/etc. Other state groups might lock up when some component is referencing an entity/component within them, etc.. But, my ideas here aren't entirely solid yet.
That is awesome, it is remarkably similar to my ECS.
I can also call arbitrary functions with world, you call it
world.call(..)
world.update!(Position, Velocity)((ref Position p, ref Velocity v){..}); //D version
The advantage of a System is state, functions are not enough I think. For example apply damage to all enemies in a radius of N meters around player2.
You would create a new System at runtime that holds the pointer to "player2" and it then calls world.update or world.call.
struct ApplyDamangeAroundPlayer{
Player* player;
float dmg;
void update(float dt){
//simplified
world.update<Player>(ref Player p){
if(player != player && player.isEnemy(p){
//apply dmg here
}
});
}
}
After that it should be removed, because you only wanted to apply dmg one time. But there a literally thousands of possibilities to express the same thing.
Player is just some combination of components, maybe (Position, Health, Input, TeamId) etc.
For the ptr stuff I intend to have something like this
Handle<Position, Velocity> h;
it would consist of two "id's" of some component group. The problem with lifetimes about your idea is I think that it has to be dynamic. At least for my problem.
For example if I destroy something in a ComponentGroup, all pointers should be nulled. If I destroy something in the middle I need to swap the last element in its place so that it will still be contiguous. That means that you might need to update the ptr of the last element if there was one.
Also you might have to transfer components to a different component group. For example you have (Position, Velocity) but you now want to add another component at runtime like (Position, Velocity, Foo) you would then have to move the components to the new component group, but you also need to update the ptr now.
You can do this in any language, you just have an Array<Objects> objects and Array<Indices> indices and then you store the index of objects somewhere in indices and then you give out the index from indices.
You then have to make sure that you handle "deleted" ptrs. You usually do this with some hash or counter in your handle.
struct Handle{
size_t index;
short counter;
}
You increment the counter every time you delete an object in your ECS. You then have to compare the counter to make sure that the Handle is still valid.
This I think could get much easier if you just had a smart ptr. You wouldn't have to look up anything because you have a ptr and it gets nulled correctly when it is no longer valid.
I honestly have to say that I don't understand much of your code, I have never written Nim code before.
And I don't think that I want to switch to Nim because I am a big fan of ownership semantics like in C++ and Rust.
D also sort of has ownership semantics but there is not much in the std to support this, which means I have to write most things from scratch. So I think I will stay with D for now but I am still very interested in what you come up with.
I mean I have basically no idea what I am doing here.
I don't think that I want to switch to Nim because I am a big fan of ownership semantics..
Hehe, not trying to rope you into using Nim or anything. Just thought your project was cool, and implementing "Brim" helped me get around an obstacle in my own similar ECS project. BTW, Nim can have ownership semantics via destructors.. but it's still experimental and tricky to work with.
The advantage of a System is state, functions are not enough I think. For example apply damage to all enemies in a radius of N meters around player2.
Yeah I know that Systems commonly need state, but you can do that with a slight modification of my prototype. Eg, Something like:
proc applyDamageAroundPlayer(p,player:Player, dmg:float) =
if player != p and player.isEnemyOf(p):
# apply dmg here
if layBombButton.isPressed:
# call using both world components & these parameters
world.call(applyDamageAroundPlayer, { player:player2, dmg:7.5 })
For the ptr stuff I intend to have something like this...
Thanks for the explanation of how your component handles work! That is a good solution, and one I will adopt where my state-based lifetime proofing doesn't work. I think my proofing idea might have some merit, at least for more behaviorally rigid entities (ones who's states of behavior determine which other entities they interact with), but there are certainly many situations where components need dynamic references.
I honestly have to say that I don't understand much of your code ... I have basically no idea what I am doing here
No worries man, thanks for sharing your thoughts on game engine design with us.
Hey guys, just wanted to say I enjoy reading about your ECS designs as I'm writing one myself. It'd be awesome if any of you ended up releasing a generic ECS for gamedev!
I wonder if anyone could critique my own ECS approach as it's not as performant as I want:
In my ECS an entity is just an int ID and the data and tasks/systems are looked up with this ID against hash tables.
It's my first ECS so I believe this is probably a naive solution to be honest.
In order to reduce scanning for entities that run a particular task, each new entity gets it's ID added to a hashtable of entities for that task. My thought being, okay now I can retrieve the list of entities for that task by iterating over the hashtable.
Only thing is it's not got the speed I'd like; creating hundreds of entities and updating the hash tables for the tasks they use seems to take up huge amounts of time according to the profiler :( Having said that, my data storage is a global variable right now and am moving it into a state object, though not sure if that'll make any difference.
Am I wasting my time with this approach? I'd like to have the entities fully dynamic so I can add or remove components on the fly, so I'd rather not constrain it at compile time which would obviously be hugely faster.
Also, any ideas for a good data structure for dynamic spatial partitioning? I'm simply using a grid at the moment (ie; divide coords by grid size and stuff entity IDs into a seq for each grid point), which works okay I guess, but since my game involves loads of stuff flying all over the place it'd be nice to have a more dynamic structure. I tried a quadgrid but because positions are so dynamic it ends up being slower. Right now I'm just regenerating the grid each frame!
Anyway, just wanted to say I see a lot of interest in gamedev with Nim and I love all the stuff you guys are coming up with :)
Hehe, not trying to rope you into using Nim or anything. Just thought your project was cool, and implementing "Brim" helped me get around an obstacle in my own similar ECS project.
I probably learn Nim one day for fun but as of know I have already wasted too much time learning way too many languages and their limitations :). This will be a good example for metaprogramming for me once I start with Nim.
BTW, Nim can have ownership semantics via destructors.. but it's still experimental and tricky to work with.
RAII is sadly not enough to express onwership semantics. You also need a way to transfer them. For example std::unqiue_ptr you can not copy a unique_ptr or it wouldn't be unique anymore, so you need to move it. C++ can do this with move semantics, I don't suppose Nim has something similar?
Thanks for the explanation of how your component handles work! That is a good solution, and one I will adopt where my state-based lifetime proofing doesn't work. I think my proofing idea might have some merit, at least for more behaviorally rigid entities (ones who's states of behavior determine which other entities they interact with), but there are certainly many situations where components need dynamic references.
I think the general idea of my ECS design is pretty neat, but to implement dynamic handles/ptrs is a bit trickier. You would need to track down the correct component group and the correct index. And you lose this information if you just iterate over every component, at least in my implementation. Not sure how I will solve this problem yet.
In order to reduce scanning for entities that run a particular task, each new entity gets it's ID added to a hashtable of entities for that task. My thought being, okay now I can retrieve the list of entities for that task by iterating over the hashtable.
Sounds similar to https://github.com/libgdx/ashley . You can probably get some inspiration from this project.
Only thing is it's not got the speed I'd like; creating hundreds of entities and updating the hash tables for the tasks they use seems to take up huge amounts of time according to the profiler
Do you need to store every entity in a map? Maybe not every entity needs to be reached by ID. If you are using thousands of something that needs to be fast, you might put it outside the entity system.
The way i do it is this: Every component has a pointer to the next and previous component. Also a pointer to its entity and every entity has a list of components. I do this because wasting memory is not a problem to me, but i might have thousands of components and i want to remove/add fast. Also, certain systems perform updates that takes several ticks (think AI). These systems have an special iterator which only contains the current component. When a component is removed, every iterator in use is updated.
@coffeepot
Another good ECS refrence is EntityX. As for spacial partitioning, I'm pretty sure most physics engines use Bounding Volume Hierarchies over Quad/Octrees.. but don't quote me on that. The best way to optimize component processing via spacial partitioning is something I've thought about but don't have any concrete solutions for.. but it's certainly a discussion I'm interested in having in the future.
@maikklein
I don't suppose Nim has something similar?
It does.. we can overload the = operator. Unfortunately, the parameter signature for doing so currently prevents the RHS from being mutable, so it's impossible to use that for move semantics directly. However we can make = an error for a specific type and provide an alternative assignment proc/operator (like say =>) which preforms a move where appropriate. Example:
{.experimental.}
type Unique[T] = distinct ptr T
proc isNil[T](u:Unique[T]): bool = cast[ptr T](u).isNil
proc destroy[T](u:var Unique[T]) {.override.} =
# NOTE: need to cast to `var ptr T` to avoid calling `=`
if not u.isNil:
cast[var ptr T](addr u) = cast[ptr T](u).resize(0)
echo "I'm Free!"
proc `=`[T](a:var Unique[T], b:Unique[T]) =
{.error.} # prevent Unique from using `=`
proc `=>`[T](a:var Unique[T], b:T) =
## Copies `b` to `a`, plus allocates if needed.
if a.isNil: cast[var ptr T](addr a) = createU(T)
cast[var ptr T](addr a)[] = b
proc `=>`[T](a, b:var Unique[T]) =
## Moves `b` to `a`.
cast[var ptr T](addr a) = cast[ptr T](b)
cast[var ptr T](addr b) = nil
proc `$`[T](u:Unique[T]): string =
if u.isNil: "nil"
else: $cast[ptr T](u)[]
# --- --- --- #
proc main =
var a: Unique[int]
var b: Unique[int]
#var x = 123
#a = addr(x) # Error: type mismatch: ...
#a = Unique[int] addr(x) # Error: usage of `=` is a user-defined error
a => 123
b => a # moves `a`
echo a # prints 'nil'
echo b # prints '123'
main()
# nil
# 123
# I'm Free!
It does.. we can overload the = operator. Unfortunately, the parameter signature for doing so currently prevents the RHS from being mutable, so it's impossible to use that for move semantics directly. However we can make = an error for a specific type and provide an alternative assignment proc/operator (like say =>) which preforms a move where appropriate. Example:
Interesting, but what happens if you need to pass Unique to a function? Or what happens if you put Unique into a container? Would it still work?
That is currently the problem I have in D. The language has sort of move semantics but the whole std isn't designed for this. I can't use anything in the std => no array, no tuple not even writeln, because it was designed for a GC and it copies all the time, which is no problem if your type is just a pointer but a big problem if you pass in a value type with a disabled copy constructor.
what happens if you need to pass Unique to a function?
Well that seems to work just fine, however..
what happens if you put Unique into a container? Would it still work?
No.. unfortunately. I played with it for awhile to try and get it to work, but any seq[Unique[T]] will cause an error on assignment (since it apparently invokes = internally, or at lease inherits the {.error.} restriction).
That said, I could probably create my own container type with a "toSeq" converter to get it to work seamlessly with the std libs, but ultimately the real solution here would be to remove the immutability restriction on the RHS of a = operator. I'm not sure if that restriction is due to a safety concern, or just a currently missing feature.