Advertisement Jump to content
Sign in to follow this  
TheChubu

Thread-safe unique sequential index per class

This topic is 1802 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi! So I was hacking a bit the Java Artemis ECS framework  (ECS = Entity component system) and noticed something: There are two parts of it that require unique integer indices per class, not per object instance.

 

It needs an unique index for each class that extends Component (ComponentType serves this purpose) and for each class that extends EntitySystem (the SystemIndexManager static inside EntitySystem serves this purpose).

 

Both solutions more or less rely on a HashMap storing the relationship between a class and its index.

 

(EntitySystem class source and ComponentType source for reference)

 

Both are unsafe in multi threading usage, meaning that if you either add components of the same type to two separate entities in different threads or create EntitySystem objects in different threads, you get non-deterministic results.

 

First instinct was to replace the static ints for AtomicIntegers, yet that doesn't makes it thread safe since there is a whole method and a HashMap in the middle.

 

So I am asking how would I implement an unique index per class. It doesn't has to be unique in itself but unique indices for EntitySystems and unique indices for ComponentTypes separately. It has to be sequential since those are used for direct array access on various places (so I can't have an EntitySystem with an index of 3 million for example).

 

I could use synchronized methods and ConcurrentHashMap, following the same ideas of Artemis, but its possible that there is a lock-free way to do this? Or at least least intrusive than synchronizing related methods? As I mentioned, I'm using Java so there are quite a bit of threading stuff to use.

Share this post


Link to post
Share on other sites
Advertisement
This generally isn't a problem that happens in practice. All the code that initializes the list of available components or whatever would run in the main thread during early engine initialization before any threads are even created. I have no experience with Artemis or Java games specifically, but that's how I'd expect it to be done in any language.

Share this post


Link to post
Share on other sites

Random crazy thought:

Each concrete function has it's own address in memory. Would it be possible to do something like using a function known to exist uniquely for each component (like the class constructor) and use its address as a unique ID?

 

Or if you have an overridden 'getID()' function (like your getTypeFor() function), have that function just return its own address?

 

(C++-inspired pseudocode)

//typedef uintptr_t ComponentID; //If you want.
 
class MyComponent : public BaseComponent
{
     //overrides virtual BaseComponent::getID()
     uintptr_t getID() override 
     {
          //Not sure if this does what I think it does or even compiles:
          return reinterpret_cast<uintptr_t>(&MyComponent::getID);
     }
}

This would only work at runtime, and the IDs couldn't be saved to file or anything, but it would be constant for the duration of the program's execution and maybe(?) across threads (do functions change their addresses for each thread?).

Share this post


Link to post
Share on other sites


Random crazy thought:
Each concrete function has it's own address in memory. Would it be possible to do something like using a function known to exist uniquely for each component (like the class constructor) and use its address as a unique ID?

 

How is that usable as an array index, or in Java?

Share this post


Link to post
Share on other sites

How is that usable as an array index, or in Java?

 
Oops, I missed the part of the sequential indices and was focusing on the cross-thread consistency problem. I saw the hashmaps in the ComponentType Java code, so I figured any unique integers would suffice. biggrin.png

Share this post


Link to post
Share on other sites

The problem here is that in a multi threaded environment different classes could be assigned the same index, right?

So I guess the AtomicInteger wold be the right solution, no? Am I missing something?

 

Edit: Should have read the code first...

 

Edit2: What about static initialization blocks? I haven't done extensive java programming but they seem like a better solution. Initialization is done *once* the class is first loaded. They are thread safe.

Edited by Madhed

Share this post


Link to post
Share on other sites

I'm not following how exactly would you use the static initializer in this case, could you provide an example?

 

The idea is not to burden the user of the library with generating their own indices. ie, the indices can be generated with information that is inside Artemis, outside users shouldn't touch the indices. When you extend EntitySystem, you should already get an index for the class you created.

 

This is what I came up with: http://pastebin.com/g6mgRah5

 

EDIT: Whoops, typo, it should be 

synchronized (ClassIndexer.class)
{
i = Integer.valueOf( getNextIndex( superType ) );
indexMap.put( type, i );
return i.intValue();
}
(note the lack of type.getClass() )

 

The mapping isn't straightforward because the indices depend on the superclass. You want to start counting from a particular superclass, ie: A counter for EntitySystem sublcasses and another one for Component subclasses.

 

The synchronized hit comes the first time the index is required, otherwise it should return before getting to the synchronized block.

Edited by TheChubu

Share this post


Link to post
Share on other sites

Well since they must be strictly sequential it would seem kind of difficult to make sure there are no gaps or repeats without synchronizing the counter (or just doing the setup work in a single thread). Do the classes even need to know what their index is? The sequential requirement is regrettable, otherwise there would be interesting solutions to the problem, for instance encoding the class name as an arbitrary unique integer, which could let you map that index to the class and vice versa in a completely stateless fashion sad.png

Share this post


Link to post
Share on other sites

I think their system's use of a ConcurrentHashMap is probably the right idea. 

 

Why are you doing this?

 

Is this for serialization or anything that sticks around between runs? Storing class-specific details based on an arbitrarily assigned integer at runtime is a really bad idea. What happens if later in development you need to add a new class? Are you going to go through every save file, every game asset, every tool, every piece of code, and modify the values to simply +1 everything that came after it? What if you add more than one, and they are in different places in code?

 

Is there some actual performance reason you are trying to address? There are many good solutions to the problem of object lookup depending on your specific needs.

 

There are other, much better ways to get a unique identifier for each class.  A simple run of foo.getClass().getName() would work for a unique class identifier. If you need to see if it is an EntityType of CompoenentType (not sure how you would have lost that information in the first place) a simple cast would either return the object or null, so you're covered.

 

A unique reference to an object's type is a solved problem in the language. Every non-anonymous class has a unique canonical type. 

 

Making a list of every object in the system is also fairly easy with reflection and you get all their canonical names.

 

What exactly are you doing that absolutely must have unique consecutive integers that never change between runs?

Share this post


Link to post
Share on other sites

 for instance encoding the class name as an arbitrary unique integer, which could let you map that index to the class and vice versa in a completely stateless fashion sad.png

You say as encoding the class name on runtime with a function?

 

Anyway, I asked because I thought there would be some simpler solution with AtomicInteger (or maybe some initialization trick like Madhed suggested).

 

 


What exactly are you doing that absolutely must have unique consecutive integers that never change between runs?

The better question would be, did you read the OP and followed the links? biggrin.png

 

As I mentioned, I don't need an unique identifier for each class (String or otherwise). I need a sequential index, its used for what it looks like, indexing.

 

The actual thing (its there in the links, BSD, you can poke it biggrin.png) uses Component and EntitySystem indices for two things AFAIK:

 

1. Generating aspects. Bit fields are used to mark which Components a system might be interested in, each component type has its own index, thus there can be Aspects that have marked which components are interested in with bitfields (with other kind of relations like, "only if it has this kind of component" or "only if it doesn't has this kind of component" and so on).

 

2. Entities have bit fields for marking what kind of components they have and what kind of systems they can be processed on. Again, Component and EntitySystem indices are used for marking those bits. ie, component Position has index 4, so in Entity, if the fourth bit is ticked, then it has a Position.

 

Most of the relations are actually implicit, not direct. ie, you can't instantiate Entities, you can ask for them via a World instance (so World owns entities), Entities don't actually have a collection of components, they're stored separately.

 

The framework exposes it as if it was all like you'd expect, Systems have all the entities they process, Entities are sacks of components. As an user, that's all you see. But inside the framework, it doesn't works like that.

 

New classes would be simply another bit in the BitSet, it shouldn't pose a problem. You shouldn't serialize the indices anyway, the whole idea is to generate them on runtime as they are needed.

 

Now, I didn't designed the framework, all I know is that it works (been ported to various languages, used in a few games) so I'm not going to redesign the whole thing because bit fields with per-class indices aren't the best thing to do. I'm not in the best position to do so either since I didn't figure out exactly how all interconnects yet.

 

I do care that if I do relatively "innocent" things like creating components on separate threads, and assign them to entities on separate threads, it should work as expected.

 

BTW, I'll check ConcurrentHashMap biggrin.png

 

EDIT2: Now I think what I did on the pastebin isn't thread safe at all. ConcurrentHashMap it is!

 

EDIT3: ... I'm out of ideas, seriously, can somebody help me with this one? http://pastebin.com/g6mgRah5 I'm not sure replacing HashMap with ConcurrentHashMap is enough.

Edited by TheChubu

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!