7

I'm writing in C++, but this problem applies to any language without GC and even to languages with a GC as well.

I have a structure in memory in which I create/add objects. The structure takes ownership of those objects. I should never need to use an object after it's removed from the structure.

When I first implemented this data structure, it seemed natural to use an ID/key/name/handle for the objects stored in it. I'm using it like this:

id1 = structure.addObj(new Square());
id2 = structure.addObj(new Square());
id3 = structure.addObj(new Circle());

obj3 = structure.getObj(id3);
obj3.addFriend( id1 );
obj3.addFriend( id2 );

idMax = structure.findObjWithMostFriends();
objMax = structure.getObj(idMax);
print(objMax.name);

After using it for a while, I'm thinking that it would be better to forget about the IDs and always use references to the objects instead. This way I wouldn't need to pass a reference to the structure around every time.

I'm thinking about refactoring everything to only use references but I'm afraid of regretting it. I'd like to know more about what are the pros and cons of using IDs to decide whether I should proceed.

Memory details:

The objects are allocated on the heap and their address never changes.

The structure deallocates those objects when they're removed (they could be released to the caller instead, but I don't need this at the moment).

I'm not supposed to ever use objects that don't belong to the structure. If my program is correct, I should never end up with a dangling ID or pointer. But it could happen if the program has bugs.

What are your experiences switching from IDs to references for similar problems? Which solution should I use?

6
  • Why the downvotes? I can try to fix the problems with this question if someone explains what's wrong with it.
    – Helloer
    Aug 23, 2020 at 15:47
  • 1
    You're using some structure ( a list, a collection, an array, etc.) for some reason. Usually it's because the programmer's intention is traversing it for processing or something. What is exactly that you want to gain with your proposal? Aug 23, 2020 at 16:33
  • My structure holds a graph. Some nodes reference others (see obj3.addFriend()). Every referenced node should be in the same structure as well. The structure maintain ownership of all nodes. . . I'm not trying to gain anything by using IDs to identify the objects in the structure: it just felt natural while designing it. I'd like to switch to only using pointers/references, but I fear that it might create problems. I posted this question in order to learn from other more experienced programmers who might have run into the same problem.
    – Helloer
    Aug 23, 2020 at 16:53
  • 2
    I really hate this line: obj3.addFriend( id1 ); That indicates that Circle knows about structure and id's. That's evil and wrong. Give me a system that doesn't need the ID'd objects to know about it. Aug 24, 2020 at 5:51
  • @candied_orange ... and I'll give you a system that doesn't use a database. Aug 24, 2020 at 15:17

3 Answers 3

2

The pros and cons of pointer vs ids depend on the context in which they are used. A general recommendation it therefore not possible.

Typically, ids make sense if they are associated with a "container", such as a repository, or an object that acts as an owning aggregate. In this case, the id allows to abstract from the memory layout, define more encapsulated interfaces, and serialize easily the container. In the context of graphs, a whole graph would be good candidate for being the "container" for its nodes and its edges.

However, if you start to use ids globally, by assuming a gloabl default container, you are building code which will be tightly coupled to the underlying global structure, difficult to reuse, and I suspect, difficult to maintain in the long run. The first impact of this problem is the kind of mixed API you are using:

  • you have to use the reference of an object to change it, but you have to use ids to create them or pass them as arguments.
  • you leak the reference associated to an id, so that you are bound to the memory layout you want to abstract from, and the context may keep track of the reference which forbids any moving of the object (and the risk of dangling pointer in case of bugs).
  • if you'd make some temporary copy of an object, it would end-up in the global structure.

All this seems to me very error-prone as it is. Especially if you add the risk of confusion between references and ids when declaring variables using the modern auto style.

Conclusion: Either reengineer completely your API to make it fully id-based, and making explicit the container (i.e. your currently global structure), or switch to a consistent shared_ptr-based API instead of ids, the id being then only an element that could help to find the share_ptr when it is not known (and for serializing your data).

5

IDs or handles are generally preferable in the following cases:

  • memory locations might not be fix, e.g. when pointing into C++ standard library containers or when transferring objects between processes
  • you know you'll have few IDs compared to the pointer's address space (can significantly reduce memory requirements)
  • objects are managed via reference counting and the object graph might have cycles
  • you need indirection but the language doesn't support first-class pointers (e.g. Python, Java)
  • you are concerned about object lifetimes, e.g. deterministic deallocation of the entire object graph or use-after-free vulnerabilities

The point with lifetimes is important. In C/C++ it is your responsibility to know whether a pointed-to object is still alive so that you're allowed to dereference the pointer. There are two strategies to address this: use reference counting or GC to keep the object alive as long as you have a pointer, or carefully think about lifetimes like the Rust compiler does (which incidentally requires the use of IDs for complex object graphs).

IDs are a partial solution to the lifetime problem because an ID alone cannot be dereferenced, but needs some context that contains the actual object graph. The lifetime of this context is usually easier to reason about, especially when the context is represented by a stack-allocated object and never directly referenced from heap-allocated objects.

But this is not airtight, e.g. you might dereference an ID in the wrong context. Again, there are two approaches: you can expect that ID resolution might fail and therefore return a nullable pointer from the resolution function, or you try to detect this error. Detection can be made more likely by assigning a short ID to each context and encoding it into each object ID/handle.

I'm currently thinking about moving a smart-pointer-based system to an ID-based system because this makes richer queries through the object graph more feasible and can do away with reference counting overhead. However, potential reuse of IDs could lead to hard to detect bugs (also a kind of use-after-free).

2
  • My main problem with using IDs is that I need to pass (a reference to) the structure everywhere, because an ID is not enough to access an object and I don't want to make the structure a singleton. That unnecessarily complicates all the functions, methods and many classes too. Is there any easy way to avoid this annoyance? I could use pairs of (structureRef, ID) instead of a simple ID, but this would waste even more space than a pointer and reintroduce some kind of lifetime problems.
    – Helloer
    Aug 23, 2020 at 17:58
  • @Helloer yes you need to make the structure/context available to all operations on your object graph. In some cases this is straightforward, in particular when you're passing the context only as a function parameter. Then, the space overhead is also irrelevant (linear with the call stack depth, but constant in the number of graph edges). Tradeoffs!
    – amon
    Aug 23, 2020 at 19:03
0

Ids work very well for persistence. So you store an id in the database, and you have an API for giving you the object given an id. Very much preferable if it is the same object for multiple calls. You mostly use this when reading items from persistent storage.

Once in memory, using a reference counted pointer (shared pointer in C++) is a lot easier and a lot more efficient.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.