This idea about using object's memory address is just brilliant! Though I'm afraid I'm still not pro enough to implement it but I would like to find out sth more about this if you don't mind ^^.

I'm not sure how could it work? The server would create an object on its side and would send it to client together with its memory address? Then client would have to create the object in the same memory location, as it had been created on the server, using sth like http://www.parashift.com/c++-faq-lite/placement-new.html? But do I have certainty that the memory address which was free on the server will be free on the client as well? Or maybe I'm completely wrong with my assumptions?

Rather the client would obtain "some number" from the server that it uses to refer to an object. It doesn't know where the server had that number from, the server could have used sequential numbers or pulled a random number out of its rear opening.

The client doesn't need to know, since what the number is or where it came from is entirely irrelevant. If the server tells you "Your friend Joe logged in as 43664", and later "43664 is messaging you", or you tell the server "I am casting a 'heal' spell at 2352978", everybody who is involved knows what to do with the information.

Now, as to where the number came from, this could be just the memory address of the object as stored on the server.

There exists one big problem, however. Imagine "Joe" logs off and "Jim" (whom you do not know at all!) logs in. Joe logging off means the object is destroyed and the allocator puts the now invalid memory location to its free list. As Jim logs in, the allocator spits out the same address again from the top of its free list (this is common allocator behaviour, because it's cache-friendly).

As it happens, Jim is an annoying person who asks random people for cash. So eventually the server sends you "43664 is telling you 'got any cash for me?'". And of course, your client knows that 43664 is your friend Joe. So you see that your friend Joe needs money and you give him some. Bang.

Let's say that your objects have a size of 16 bytes (and the first one is properly aligned), this means that in every object's address the lowest 4 bits are zero.

Therefore, when you free an object and your allocator reclaims the memory address into its free-list, it can increment a 4-bit counter in those useless bits.

When Joe logs off (i.e. Joe's object is destroyed), the allocator puts the memory block at 43664 back to the free-list. But before doing so, it increments the counter, so the pointer becomes 43665. When Jim logs in, the allocator returns 43665 (and on subsequent iterations, 43666, 43667, and so on up to 43679, after which it wraps back to 43664). This could happen in the server's logic outside the allocator too, of course (doesn't matter how it's done).

Now, what's important, the logic in the server knows about this pointer modification, so before doing anything with a pointer obtained from the allocator, it does an & 0xfffffff0 operation on it. This is effectively a no-op on a fresh pointer, and properly aligns any recycled "meddled" pointer back to the correct address. However, the server tells the client "43665", not "43664". Your client doesn't know any of this and doesn't care where the number came from. However, it can tell that 43664 and 43665 are not the same number, so this is most definitely not Joe.

Thanks a lot everybody for answers and sharing your knowledge!

@samoth, thanks for such detailed explanation. It seems not to be as perfect as I made it up in my previous post :P but still does not require server to waste time on searching for appropriate object - only clients have to. Anyway, it's much more clear now and I can even try to implement it on my own :D. Thanks a lot

Using a map (as in C++ std::map) would be one easy and obvious way of reducing "must iterate every element" to "must only touch log2(n) elements".

Another easy way (a hack, but nevertheless) would be to use the object's memory address as ID. There's nothing to look up and nothing to search, and the ID is guaranteed to be unique.

Just make sure you don't free and immediately reuse an address (as it's the case with most allocators) and then assume that the client "magically" knows that this is now a different object. But hey, hacks almost always come with a little "gotcha".

One solution to this issue is, by the way, the same as you use in lockfree concurrent algorithms to combat the ABA problem: Exploit the fact that objects are aligned (most of the time to 8 or so bytes) so the lowest few bits are all zero and you can put a counter into these.

It got me thinking...Instead of go to the burden of using mem address and caring about reusing the same address (which is very likely), why not keep using the indexes, AND a count of reused/changed index? I think I just figured out an osome algorithm \o/..

I also use vectors to store game objects, iterating a map is horrendous, (I decided to always avoid any containers in favor of vectors after testing with A star, seriously, I believe vectors performance are hardly beaten by big O notations, memory use just counts more, thats my current mantra, would you guys opine?)

Anyway, when I kill an object, I do the swap to last element and reduce vector size trick, so what I could do here is count the times a object changed index (store in the object itself). So to communicate to the server, you send not only the index, but the use count, if the server get the count different for the same index, he knows it needs to white for the reliable packet saying stuff changed..

Not sure, it just poped on my head. Isnt it much more intuitive then using mem addresses?

It got me thinking...Instead of go to the burden of using mem address and caring about reusing the same address (which is very likely), why not keep using the indexes, AND a count of reused/changed index?

Using indices instead of pointers to refer to objects is basically the same, maybe more elegant. Indices are contiguous without alignment (i.e. there are no unused bits as in a pointer), after element 5, element 6 follows. Plus, you have the nice property that indices start at zero, so it is easier to do bounds checking (only need to test against the largest allowed index).

However, you still need to be careful that a new object with the same index is recognized as a different object on the other side, so you would need to do something different to make them unique.

This could be done by adding a counter to every object that isn't ever touched by the constructor, but incremented by the destructor. Of course this invokes UB (as the counter is used but never initialized) but it will work, as "uninitalized +1" is still different from "uninitialized" every time, no matter what the value is. You don't care that it's something in particular, you only care that it's different for different objects.

However, the server already knows anyway, it's the client that is troublesome. To communicate the fact that objects A and B are different (although they have the same index) you'd have to send that counter to the client, and there you have exactly the same as with the other approach again.