Specification #198

iMesh: firm up iterator behavior in presence of modifications to container

Added by Mark Miller over 6 years ago. Updated almost 6 years ago.

Status:ClosedStart date:03/25/2011
Priority:NormalDue date:
Assignee:-% Done:

0%

Category:-Spent time:-
Target version:-

Description

A common concern about an iterator is how it behaves when the container over which it is iterating is modified. For example, in STL, iterators for std::set<> and std::map<> and std::list<> containers are guaranteed to work in the presence of modifications to the associated containers with one exception; they don't handle the case when the container member the iterator is currently pointed at is deleted. However, iterators for std::vector<> are not guaranteed to work under any kinds of modification.

Here, we try to characterize behavior of iMesh iterators in presence of container modifications. There are a number of (subtle) aspects to this.

  • There are set-type (duplicate preventing) sets and list-type (order preserving) sets and iterators may need to behave differently for each. As well, users require clarification on what iterator behavior to expect for each.
  • Sets can have set members and entity members. However, iterators are currently defined to iterate over only the entity members of sets. That said, the question arises as to whether modifications that involve only set members nonetheless effect iterator behavior.
  • There are array-type iterators that upon each step in the iteratation return a whole array of entity member handles and single entity iterators that upon each step return just a single entity member handle.
  • The iterators support type/topology filtering. Iterators do not (always) strictly iterate over all entities in the set; just all entities matching the type/topology criteria. When type/topology specifies either all types or all topologies, then indeed the iterator will iterate over all entities.
  • There are add/remove operations that add/remove entity members or set members to a set
  • There are create/delete operations that create and delete entities from the whole iMesh_Instance
  • There are create/destroy operations that create and destroy sets from the whole iMesh_Instance.
    • We did have an agreement a long time ago to unify some of these disparate operation names (e.g. delete vs. destroy vs. dtor).
  • There is the root set which is special and may have different iterator behavior than all other sets.

The container for an iterator is an iMesh entity set

In all cases, the container associated with an iterator is a given entity set in the iMesh instance. This is the only container type in iMesh for which iterators are defined
  • an entity set may be the only container type defined in iMesh, at all

Modification means addition/removal and/or create/destroy and/or create/delete after iterator initialization

When we talk about container modification here, we are talking about any of the following operations.
  • addition and removal of entity members
      void iMesh_rmvEntFromSet(iMesh_Instance instance,
      void iMesh_rmvEntArrFromSet(iMesh_Instance instance,
      void iMesh_addEntToSet(iMesh_Instance instance,
      void iMesh_addEntArrToSet(iMesh_Instance instance,
    
  • addition and removal of set members
      void iMesh_rmvEntSet(iMesh_Instance instance,
      void iMesh_addEntSet(iMesh_Instance instance,
    
  • deletion of entities from whole iMesh_Instance
      void iMesh_deleteEntArr(iMesh_Instance instance,
      void iMesh_deleteEnt(iMesh_Instance instance,
    
  • creation of entities (effects root set)
      void iMesh_createEntSet(iMesh_Instance instance,
      void iMesh_createVtxArr(iMesh_Instance instance,
      void iMesh_createEntArr(iMesh_Instance instance,
      void iMesh_createVtx(iMesh_Instance instance,
      void iMesh_createEnt(iMesh_Instance instance,
    
  • destruction of entity sets
      void iMesh_destroyEntSet(iMesh_Instance instance,
    

By container modification, we mean that of the above operations occur on the container between iterator initialization and reset.

For purposes of this discussion, there is no distinction between any of these kinds of modifications. What is true for any is true for all. Below, the words add and remove are used to represent any of the modifications that add members or remove members regardless of the kind of operation above.

Iterators not effected by modifications involving set members

Iterators are currently defined to iterate over only the entity members of a container. In particular, if the container is modified by adding/removing or sets from the container, this will have no impact on the iterator. This is true for set-type sets and list-type sets.

Iterator's current position not effected by modification

If the container is modified, the iterator will continue to properly keep track of the member it was currently pointing at. If a modification occurs that removes the member it was currently pointing at, the iterator will be advanced to the next (not already deleted) member it would have proceeded to. In this way, the iterator is guaranteed to always point at a valid member or to the end of the set, in the case that the member being removed is the last one.

Iterator must skip over removed members

If the container is modified by removing members, the iterator will guarentee not to land on (e.g. return) those members as iteration proceeds. This is true of set-type sets and list-type sets.

Iterator on set-type sets may fail to return added members

If the container is a set-type (duplicate preventing) container and it is modified by adding members, the iterator may skip over (e.g. fail to return) members that have been added.

Iterator on list-type sets must return added members

If it is a list-type (order preserving) container, then the iterator must guarentee to return the added members.

Questions

*Is the root set a set-type set or list-type set or niether because its special?
  • I believe that by definition, it is a set-type set. If the root set contains a handle twice, I would interpret those as being separate entities, which violates one of the other parts of the spec.
    *Can we iterate over the root set?
  • Absolutely, and this is probably one of the two most common uses I would expect to see in applications using iterators.

Related issues

Related to ITAPS - Bug #281: swapping code doesn't run with FMDB Closed 05/20/2011
Related to ITAPS - Bug #298: swapping code doesn't run with MOAB Closed 05/20/2011
Duplicated by ITAPS - Feature #308: [FMDB] Swapping failure due to invalid iterator after ent... Closed 09/28/2011

History

#1 Updated by Tim Tautges over 6 years ago

Mark Miller wrote:

A common concern about an iterator is it behaves when the container over which it is iterating is modified. For example, in STL, iterators for std::set<> and std::map<> containers work in the presence of modifications to the associated containers. However, the same is not true for STL iterators for std:vector<> or std::list<> containers.

Clarification: set/map/list container iterators work except if member pointed to is deleted; vectors don't.

Here, we try to characterize behavior of iMesh iterators in presence of container modifications. There are a number of (subtle) aspects to this.

  • There are set-type (duplicate preventing) sets and list-type (order preserving) sets and iterators may need to behave differently for each. As well, users require clarification on what iterator behavior to expect for each.
  • Sets can have set members and entity members. However, iterators are currently defined to iterate over only the entity members of sets. That said, the question arises as to whether modifications that involve only set members nonetheless effect iterator behavior.
  • There are array-type iterators that upon each step in the iteratation return a whole array of entity member handles and single entity iterators that upon each step return just a single entity member handle.
  • There are add/remove operations that add/remove entity members or set members to a set
  • There are create/delete operations that create and delete entities from the whole iMesh_Instance
  • There are create/destroy operations that create and destroy sets from the whole iMesh_Instance.
    • We did have an agreement a long time ago to unify some of these disparate operation names (e.g. delete vs. destroy vs. dtor).
  • There is the root set which is special and may have different iterator behavior than all other sets.

Notwithstanding that you can't add/remove entities from the root set, I don't think the iterator behavior should be different here.

The container for an iterator is an iMesh entity set

In all cases, the container associated with an iterator is a given entity set in the iMesh instance. This is the only container type in iMesh for which iterators are defined
  • an entity set may be the only container type defined in iMesh, at all

Should clarify here that the iterator also has type/topology qualifications, so it doesn't (always) strictly iterate over all entities in the set.

Modification means addition/removal and/or create/destroy and/or create/delete after iterator initialization

When we talk about container modification here, we are talking about any of the following operations.
  • addition and removal of entity members
    [...]
  • deletion of entities from whole iMesh_Instance
    [...]
  • creation of entities (effects root set)
    [...]
  • destruction of entity sets
    [...]

Add addition and removal of set-type members to/from the set being iterated.

By container modification, we mean any of these operations occur on the container between iterator initialization and reset.

For purposes of this discussion, there is no distinction between any of these kinds of modifications. What is true for any is true for all. Below, the words add and remove are used to represent any of the modifications that add members or remove members regardless of the kind of operation above.

Iterators not effected by modifications involving set members

Iterators are currently defined to iterate over only the entity members of a container. In particular, if the container is modified by adding/removing or sets from the container, this will have no impact on the iterator. This is true for set-type sets and list-type sets.

Iterator's current position not effected by modification

If the container is modified, the iterator will continue to properly keep track of the member it was currently pointing at. If a modification occurs that removes the member it was currently pointing at, the iterator will be advanced to the next (not already deleted) member it would have proceeded to. In this way, the iterator is guaranteed to always point at a valid member.

Or to the end of the set, in the case that the member being removed is the last one.

Iterator must skip over removed members

If the container is modified by removing members, the iterator will guarentee not to land on (e.g. return) those members as iteration proceeds. This is true of set-type sets and list-type sets.

Iterator on set-type sets may fail to return added members

If the container is a set-type (duplicate preventing) container and it is modified by adding members, the iterator may skip over (e.g. fail to return) members that have been added.

Question: under arbitrary conditions? Or, just in specific cases? Does iMesh specify anything about ordering of a set-type set?

Iterator on list-type sets must return added members

If it is a list-type (order preserving) container, then the iterator must guarentee to return the added members.

Questions

*Is the root set a set-type set or list-type set or niether because its special?

I believe that by definition, it is a set-type set. If the root set contains a handle twice, I would interpret those as being separate entities, which violates one of the other parts of the spec.

*Can we iterate over the root set?

Absolutely, and this is probably one of the two most common uses I would expect to see in applications using iterators.

#2 Updated by Mark Miller over 6 years ago

Tim Tautges wrote:

  • There is the root set which is special and may have different iterator behavior than all other sets.

Notwithstanding that you can't add/remove entities from the root set, I don't think the iterator behavior should be different here.

Hmm. Confused here. You can in fact add/remove entities from the root set by iMesh_createEnt/iMesh_createVtx and iMesh_deleteEnt. Above, I assert that that is a kind of mofication an iterator must support.

If the container is a set-type (duplicate preventing) container and it is modified by adding members, the iterator may skip over (e.g. fail to return) members that have been added.

Question: under arbitrary conditions? Or, just in specific cases?

Since the statement is a may statement, I don't understand how arbitrary or specific cases matter.

Does iMesh specify anything about ordering of a set-type set?

Hmm. Confused again. list-type sets guarantee a kind of order and that is that you get things back in the order they were added. Is that what you mean by ordering here? Or, are you talking about how the members in a set-type set are sequenced in the container. I haven't seen anything in the spec. regarding that yet.

#3 Updated by Carl Ollivier-Gooch over 6 years ago

In today's telecon, there was some discussion of this point.

The real problem, implementation-wise, is for std::vector implementations of list-type sets (SVILTS).

Jim suggested the notion of telling an iterator, at creation time, "the set you're iterating over is/is not going to be modified during your lifetime". This would allow more efficient implementation of iterators of SVILTS.

Carl pointed out that, again for a SVILTS, wrapping an integer index into the vector rather than a std::vector<>::iterator seems likely to get you out of jail basically free. Your iterator doesn't go invalid if the vector is reallocated. You can increment (and decrement) through the vector as before. Your only cost is some pointer arithmetic before you return the proper handle. Now, I've not analyzed this in detail, but on the face of it, this seems to solve the problem with SVILTS without changing anything about implementations other than how the iMesh iterator wrapper code works (and mine would be on the list for change here, I'm almost certain).

#4 Updated by Jason Kraftcheck over 6 years ago

And what should the value of said index be if it is at location N and between the last access to the iterator and the current access the caller removed items at positions N-4, N-3, and N-1?

Also, it probably isn't a big deal, but the cost isn't just "some pointer arithmetic before you return the proper handle" but also the slightly more expensive test that the index isn't past the end of the array/vector.

- jason

#5 Updated by Tim Tautges over 6 years ago

And the cost isn't restricted to just the iterator functions, it's also incurred for the set member removal functions.

Finally, remember here that it's not strictly stl::vector that's used to implement these things, it may be any number of things depending on the underlying implementation. MOAB uses a number of things, depending on the size of the member list, for example.

All that said, this is made significantly easier by representing the iterator as an index into the container.

#6 Updated by Carl Ollivier-Gooch over 6 years ago

Jason Kraftcheck wrote:

And what should the value of said index be if it is at location N and between the last access to the iterator and the current access the caller removed items at positions N-4, N-3, and N-1?

If you're not deleting the entity that's being pointed to, you should still be pointing to it afterwards. And the order is guaranteed to be preserved, so any removal of entities before the iterator would have to decrement the integer.

Also, it probably isn't a big deal, but the cost isn't just "some pointer arithmetic before you return the proper handle" but also the slightly more expensive test that the index isn't past the end of the array/vector.

Fair enough. That test also applies to the std::iterator, though, and it's harder to do for the iterator.

#7 Updated by Seegyoung Seol over 6 years ago

Mark Miller wrote:

Tim Tautges wrote:

  • There is the root set which is special and may have different iterator behavior than all other sets.

Notwithstanding that you can't add/remove entities from the root set, I don't think the iterator behavior should be different here.

Hmm. Confused here. You can in fact add/remove entities from the root set by iMesh_createEnt/iMesh_createVtx and iMesh_deleteEnt. Above, I assert that that is a kind of mofication an iterator must support.

Rootset can be modified through iMesh_createEnt/iMesh_createVtx. The iterator behavior should n't be different between rootset and entity set. FMDB iterator does exactly what Mark M summarized above (equivalent to the spec of standard iterator) both for entity set and rootset. Without up-to-date iterator, how can we do mesh modification? I don't think GRUMMP iterator is much different from FMDB's.

If the container is a set-type (duplicate preventing) container and it is modified by adding members, the iterator may skip over (e.g. fail to return) members that have been added.

Question: under arbitrary conditions? Or, just in specific cases?

Since the statement is a may statement, I don't understand how arbitrary or specific cases matter.

Does iMesh specify anything about ordering of a set-type set?

Hmm. Confused again. list-type sets guarantee a kind of order and that is that you get things back in the order they were added. Is that what you mean by ordering here? Or, are you talking about how the members in a set-type set are sequenced in the container. I haven't seen anything in the spec. regarding that yet.

By definition, set data structure stores objects of type key where the objects are sorted based on key comparison function. So the order of set element is not what the user can arbitrarily control by his own discretion. iMesh doesn't have to specify anything about ordering of a set-type set.

#8 Updated by Seegyoung Seol over 6 years ago

Carl Ollivier-Gooch wrote:

In today's telecon, there was some discussion of this point.

The real problem, implementation-wise, is for std::vector implementations of list-type sets (SVILTS).

Jim suggested the notion of telling an iterator, at creation time, "the set you're iterating over is/is not going to be modified during your lifetime". This would allow more efficient implementation of iterators of SVILTS.

This is completely against the standard concept of iterator, especially with set or list container.

I understand there might be some mesh implementations which use vector or array for entity set implementation for some good reasons such as performance but I don't think that can be the rationale for changing iterator behavior to be non-standard or infeasible for the support for modification. itaps entity set is set-type or list-type, which means the user might expect (or assume) its iterator behavior as what standard iterator does. I believe FMDB and GRUMMP implemented the ITAPS iterator based on standard iterator behavior.

Mark M's summary above convinced me that standard iterator spec is what we have presumed so far for itaps iterator although itaps set iterator spec is not exactly identical to stl set iterator. (stl set has theproperty that inserting a new element into a set does not invalidate iterators that point to existing elements. Erasing an element from a set also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.)

Carl pointed out that, again for a SVILTS, wrapping an integer index into the vector rather than a std::vector<>::iterator seems likely to get you out of jail basically free. Your iterator doesn't go invalid if the vector is reallocated. You can increment (and decrement) through the vector as before. Your only cost is some pointer arithmetic before you return the proper handle. Now, I've not analyzed this in detail, but on the face of it, this seems to solve the problem with SVILTS without changing anything about implementations other than how the iMesh iterator wrapper code works (and mine would be on the list for change here, I'm almost certain).

I would suggest to leave MOAB iterator as it is if supporting modification is too much for its iterator and mark it as not meeting ITAPS iterator requirement wrt modification instead of lessening itaps iterator requirement by making it non-standard.

#9 Updated by Mark Miller over 6 years ago

Seegyoung Seol wrote:

I would suggest to leave MOAB iterator as it is if supporting modification is too much for its iterator and mark it as not meeting ITAPS iterator requirement wrt modification instead of lessening itaps iterator requirement by making it non-standard.

These setiments touch on a broader issue of interoperable interface design and adoption that I think we could benefit from having a separate discussion on; that is

  • whether performance concerns ought to be allowed to trump interperability concerns
  • whether the whole of the interface needs to be able to map 1:1 with each and every implementation's internal representations and operations or whether impedance mismatches between interface and implementation are allowed to be introduced as well as be resolved by implementation-specific impedance matching wrapper logic.

#10 Updated by Mark Miller over 6 years ago

Carl Ollivier-Gooch wrote:

Jim suggested the notion of telling an iterator, at creation time, "the set you're iterating over is/is not going to be modified during your lifetime". This would allow more efficient implementation of iterators of SVILTS.

Based on past experiences with different mesh database projects and modification of the objects (meshes) in the databases, I do believe there is value in informing the database of the beginning as well as completion of a modification phase of interactions with the database. Having a way of informing the database of these demarkaions during interaction with the database allows the database to optimize itself internal for subsequent operations.

#11 Updated by James Porter over 6 years ago

Seegyoung Seol wrote:

Carl Ollivier-Gooch wrote:

In today's telecon, there was some discussion of this point.

The real problem, implementation-wise, is for std::vector implementations of list-type sets (SVILTS).

Jim suggested the notion of telling an iterator, at creation time, "the set you're iterating over is/is not going to be modified during your lifetime". This would allow more efficient implementation of iterators of SVILTS.

This is completely against the standard concept of iterator, especially with set or list container.

The "standard" iterator behavior, assuming you're referring to the Gang of Four design pattern, makes no guarantees (that I am aware of) for the behavior of iteration under modification. If you are referring to the specification for lists and sets in the C++ STL, that is a false equivalence, since the ITAPS standard certainly doesn't mandate that set-type sets be implemented as std::sets, or even that an ITAPS implementation be written in C++. Indeed, C++ iterators aren't even the same thing as GoF or ITAPS iterators (C++ iterators don't contain an internal reference to the end of the iteration). In C++ terms, GoF/ITAPS iterators would be called "ranges".

More to the point, there is nothing whatsoever restricting a language/API/whatever from having multiple kinds of iterators with different semantics. ITAPS already does this anyway with iBase_EntityIterator and iBase_EntityArrIterator.

#12 Updated by Tim Tautges over 6 years ago

Seegyoung Seol wrote:

This is completely against the standard concept of iterator, especially with set or list container.

What standard concept of iterator? iMesh? STL? If the latter, it depends on container type.

I would suggest to leave MOAB iterator as it is if supporting modification is too much for its iterator and mark it as not meeting ITAPS iterator requirement wrt modification instead of lessening itaps iterator requirement by making it non-standard.

I think what we need here is another type of iterator, or at least an option to the iterator create function, that is for iterators that can assume non-changing mesh. Based on some earlier profiling I did on the performance test, I was seeing in the range of 10% of runtime for checking validity of entity handles. I'd have to rerun those checks to say for sure if it was still that. But, I'd call that a pretty severe penalty that some apps won't want to pay.

Also, I personally don't like a moded database, where you switch on and off stuff for the whole database. I'd rather have an iterator that has certain characteristics, like being able to assume a non-changing mesh, and if the application violates that without creating a new iterator, then it's their problem.

#13 Updated by Tim Tautges over 6 years ago

Tim Tautges wrote:

Based on some earlier profiling I did on the performance test, I was seeing in the range of 10% of runtime for checking validity of entity handles. I'd have to rerun those checks to say for sure if it was still that. But, I'd call that a pretty severe penalty that some apps won't want to pay.

I should qualify by stating I was profiling MOAB's implementation of iMesh, but you all knew that right? :)

#14 Updated by Seegyoung Seol over 6 years ago

Tim Tautges wrote:

Seegyoung Seol wrote:

This is completely against the standard concept of iterator, especially with set or list container.

What standard concept of iterator? iMesh? STL? If the latter, it depends on container type.

Yes, it depends on the container type but I meant iterator behavior with STL list and STL set since we are talking about itaps iterator which runs on list-type or set-type container.

I would suggest to leave MOAB iterator as it is if supporting modification is too much for its iterator and mark it as not meeting ITAPS iterator requirement wrt modification instead of lessening itaps iterator requirement by making it non-standard.

I think what we need here is another type of iterator, or at least an option to the iterator create function, that is for iterators that can assume non-changing mesh. Based on some earlier profiling I did on the performance test, I was seeing in the range of 10% of runtime for checking validity of entity handles. I'd have to rerun those checks to say for sure if it was still that. But, I'd call that a pretty severe penalty that some apps won't want to pay.

Allow the user to choose the iterator type: const or non-const is one thing and changing the current (non-const) iterator spec wrt modification is the other. I assume you meant the first; both const and non-const iterator shall also be supported in MOAB.

Also, I personally don't like a moded database, where you switch on and off stuff for the whole database. I'd rather have an iterator that has certain characteristics, like being able to assume a non-changing mesh, and if the application violates that without creating a new iterator, then it's their problem.

Wait a min. I don't think you mean iterator only for iMesh. We use iterator in iMeshP, iGeom, and probably iRel and iField.

#15 Updated by Seegyoung Seol over 6 years ago

Tim Tautges wrote:

Seegyoung Seol wrote:

This is completely against the standard concept of iterator, especially with set or list container.

What standard concept of iterator? iMesh? STL? If the latter, it depends on container type.

We surely mean iterator behavior with STL list and STL set as per the standard iterator spec since itaps iterator runs on list-type or set-type container.

#16 Updated by Mark Miller over 6 years ago

Tim Tautges wrote:

I think what we need here is another type of iterator, or at least an option to the iterator create function, that is for iterators that can assume non-changing mesh.

I assert that this need exists in general and is not specific to iterating over entities in an entity set. The need is to somhow indicate whether an iMesh object is read-only (e.g. modifications are not currently allowed) or read-write (modifications are currently allowed). In fact, this notion is a very common and natural feature of most database technology. Related concepts include mutability, const-ness, locking and concurrency (multiple processes' access), etc. I believe a similar need for this kind of thing has arisen in iMeshP and also in iField and I suspect iRel may have such a need as well.

The granulatiry of objects upon which read-write vs. read-only access may be granted is also important. The whole discussion here is focused on the granularity of a given entity set. But, we could also talk about a given iMesh instance, a whole subtree in the set inclusion hierarchy, an individual entity and maybe a tag too. So, I believe we in fact could benefit from an iMesh_lock() and iMesh_unlock() on the granularity of a whole mesh instance and iMesh_lockEntSet()/iMesh_unlockEntSet() on the granularity of a given entity set. By default, everything we currently do is by definition unlocked and modifications can occur at any time and on anything. Fine, lets keep that as a default. But, we could add the ability to lock/unlock various objects within an iMesh instance thereby addressing the current problem with iterators as well as enabling future implementations to optimize for read-only access. For example, VisIt does not need iMesh_load to result in a modifieable iMesh instance.

On the specfic topic of entity sets and their iterators, here, the notion of modification is associated with the entity set not an iterator. So, trying to somehow fold that notion into iterator creation seems like a loose fit. Also, the notion of constness of an iterator applies to the objects the iterator points at (e.g. in iMesh the entities) and not the container over which it is iterating.

#17 Updated by James Porter over 6 years ago

Mark Miller wrote:

So, I believe we in fact could benefit from an iMesh_lock() and iMesh_unlock() on the granularity of a whole mesh instance and iMesh_lockEntSet()/iMesh_unlockEntSet() on the granularity of a given entity set.

Assuming we want this (and I'm not 100% convinced we do yet), it would probably suffice to have iMesh_(lock|unlock)EntSet, and then pass in the root set to lock/unlock the whole mesh.

#18 Updated by James Porter over 6 years ago

James Porter wrote:

Mark Miller wrote:

So, I believe we in fact could benefit from an iMesh_lock() and iMesh_unlock() on the granularity of a whole mesh instance and iMesh_lockEntSet()/iMesh_unlockEntSet() on the granularity of a given entity set.

Assuming we want this (and I'm not 100% convinced we do yet), it would probably suffice to have iMesh_(lock|unlock)EntSet, and then pass in the root set to lock/unlock the whole mesh.

I should amend this to say I'm not 100% convinced we don't want it either. I'll have to think about it a bit...

#19 Updated by Mark Miller over 6 years ago

James Porter wrote:

Mark Miller wrote:

So, I believe we in fact could benefit from an iMesh_lock() and iMesh_unlock() on the granularity of a whole mesh instance and iMesh_lockEntSet()/iMesh_unlockEntSet() on the granularity of a given entity set.

Assuming we want this (and I'm not 100% convinced we do yet), it would probably suffice to have iMesh_(lock|unlock)EntSet, and then pass in the root set to lock/unlock the whole mesh.

That'll certainly work to address iterator issues raised here. But, to be clear, locking root set is not same as locking iMesh instance as the latter includes adjacency table, coordinate data, tags, tag data, parent/child links, etc.

#20 Updated by Mark Miller over 6 years ago

Also, if we go down the path of having iMesh_lockEntSet()/iMesh_unlockEntSet() we will need to distinguish between a lock on just the entity set and a lock on the entire tree of entity sets rooted at the given entity set. I believe those are different things. For example, locking the root set will prevent/ensure no new creation of vertex entities, for example. But, will it prevent/ensure existing vertex entities cannot be moved/re-arranged within entity sets below the root?

Also, I guess we would need to think about whether 'locking' is (just) a promise by the application to not change a given iMesh object and all bets are off if the application does change something that is locked or whether it is also a requirement of the implementation to then detect and prevent attempts to modify objects that are locked. I personally would prefer/assume the latter interpretation. But, its concievable others might opt for the weaker, former interpretation.

#21 Updated by Tim Tautges over 6 years ago

Mark Miller wrote:

Also, if we go down the path of having iMesh_lockEntSet()/iMesh_unlockEntSet() we will need to distinguish between a lock on just the entity set and a lock on the entire tree of entity sets rooted at the given entity set. I believe those are different things. For example, locking the root set will prevent/ensure no new creation of vertex entities, for example. But, will it prevent/ensure existing vertex entities cannot be moved/re-arranged within entity sets below the root?

Also, I guess we would need to think about whether 'locking' is (just) a promise by the application to not change a given iMesh object and all bets are off if the application does change something that is locked or whether it is also a requirement of the implementation to then detect and prevent attempts to modify objects that are locked. I personally would prefer/assume the latter interpretation. But, its concievable others might opt for the weaker, former interpretation.

I think the issue of a const-type iterator on a non-changing mesh is much more localized to the implementation of the iterator itself; the notion of locking a database is far broader, and touches a far greater fraction of the implementation. I can think of many cases where an application is iterating over a mesh and that mesh isn't changing, and where a const-type iterator would have a large impact compared to the effort required to implement it. The justification for a more general locking mechanism is much more tenuous, IMO.

#22 Updated by Mark Miller over 6 years ago

I think the issue of a const-type iterator on a non-changing mesh is much more localized to the implementation of the iterator itself; the notion of locking a database is far broader, and touches a far greater fraction of the implementation. I can think of many cases where an application is iterating over a mesh and that mesh isn't changing, and where a const-type iterator would have a large impact compared to the effort required to implement it. The justification for a more general locking mechanism is much more tenuous, IMO.

I think we're mixing terminology here. You mention two orthogonal concepts; const-ness of iterator an non-changing mesh. Currently, iMesh supports neither in any context. Lets take the second concept first.

By definition, an iMesh instance can be modified in any way and at any time. There is no such thing as a non-changing mesh in iMesh. So, what do you mean by that and how do you intend to affect that?

Const-ness of an iterator has nothing to do with the container being const (modifieable) or not. Const-ness of an iterator has to do with the modifieability of the thing you get back when you de-reference the iterator. For a const-iterator, when you de-reference it and get back the thing it points at, that thing is a const thing. So, what do you mean by a const-type iterator w.r.t. the container over which it iterates?

#23 Updated by Tim Tautges over 6 years ago

Mark Miller wrote:

I think we're mixing terminology here. You mention two orthogonal concepts; const-ness of iterator an non-changing mesh. Currently, iMesh supports neither in any context. Lets take the second concept first.

By definition, an iMesh instance can be modified in any way and at any time. There is no such thing as a non-changing mesh in iMesh. So, what do you mean by that and how do you intend to affect that?

Const-ness of an iterator has nothing to do with the container being const (modifieable) or not. Const-ness of an iterator has to do with the modifieability of the thing you get back when you de-reference the iterator. For a const-iterator, when you de-reference it and get back the thing it points at, that thing is a const thing. So, what do you mean by a const-type iterator w.r.t. the container over which it iterates?

Right, so poor terminology on my part. What I really want is an iterator over a set with a guarantee that the set contents have not changed since the iterator was reset. That will also imply that the things you get from dereferencing the iterator still exist in the mesh. I don't think this implies anything about tags on those entities, at least for what I have in mind here.

#24 Updated by Mark Miller over 6 years ago

Tim Tautges wrote:

Right, so poor terminology on my part. What I really want is an iterator over a set with a guarantee that the set contents have not changed since the iterator was reset. That will also imply that the things you get from dereferencing the iterator still exist in the mesh. I don't think this implies anything about tags on those entities, at least for what I have in mind here.

Well, why are focusing on the issues of constness and unchanging mesh solely in the context of iteration? Why are we not also concerned about these same issues in the context of any calls that query handles from an iMesh instance? I guess that is where I am the most confused by this discussion. If we care about whether a mesh is changing or not and if we care about whether the entities we're talking about are changing or not, don't we care about that regardless of how (e.g. which iMesh functions) we are querying an iMesh instance to obtain the handles? I assert that iteration is only the first case that has brought these issues to the forefront but that with a small amount of effort, these same issues can be resolved in all contexts regardless of how the iMesh instance is being queried.

Now, I am willing to concede that iteration is a bit different query mechanism as the process of obtaining a handle via iteration is split across several iteration-related functions, init, next, reset, end, and so the question of whether the iMesh instance is constant across all these calls is slightly more applicable than the question of whether the iMesh instance is constant across say getEntities, or getEntArr(). But is there really enough of a distinction to cull out iteration as special and therefore the only case where constness of an iMesh instance (or ent set therein) is at all relevant? Certainly, iMesh_lockEntSet()/iMesh_unlockEntSet() addresses both of these issues. However, some iteration-specific solution addresses only iteration then and I am concerned we'll then just hit this issue again later on in a non-iterator context.

#25 Updated by Seegyoung Seol over 6 years ago

Mark Miller wrote:

Also, if we go down the path of having iMesh_lockEntSet()/iMesh_unlockEntSet() we will need to distinguish between a lock on just the entity set and a lock on the entire tree of entity sets rooted at the given entity set. I believe those are different things. For example, locking the root set will prevent/ensure no new creation of vertex entities, for example. But, will it prevent/ensure existing vertex entities cannot be moved/re-arranged within entity sets below the root?

Also, I guess we would need to think about whether 'locking' is (just) a promise by the application to not change a given iMesh object and all bets are off if the application does change something that is locked or whether it is also a requirement of the implementation to then detect and prevent attempts to modify objects that are locked. I personally would prefer/assume the latter interpretation. But, its concievable others might opt for the weaker, former interpretation.

We should consider iMeshP and iRel in this "locking" spec. E.g. locking will surely affect parallel mesh modification and relation modification. In parallel, mesh is modified either by migration, ghosting and load balancing; FMDB does migrate partition object type entity sets as well as entities and tag data attached to them during migration.

#26 Updated by Seegyoung Seol over 6 years ago

Seegyoung Seol wrote:

Mark Miller wrote:

Also, if we go down the path of having iMesh_lockEntSet()/iMesh_unlockEntSet() we will need to distinguish between a lock on just the entity set and a lock on the entire tree of entity sets rooted at the given entity set. I believe those are different things. For example, locking the root set will prevent/ensure no new creation of vertex entities, for example. But, will it prevent/ensure existing vertex entities cannot be moved/re-arranged within entity sets below the root?

We should consider iMeshP and iRel in this "locking" spec. E.g. locking will surely affect parallel mesh modification and relation modification. In parallel, mesh is modified either by migration, ghosting and load balancing; FMDB does migrate partition object type entity sets as well as entities and tag data attached to them during migration.

The definition of Partition Object is the following:

The basic unit to which a destination part id is assigned for migration. The full set of partition objects is
a set of mesh entities that are not part of the boundary of any higher order mesh entities and entity sets containing unique mesh entities. In a 3D mesh, this includes all mesh regions, the mesh faces not bounded by any mesh regions,
the mesh edges not bounded by any mesh faces or regions, and mesh vertices not bounded by any mesh edges, faces or regions and entity sets designed as "partition object" at creation time.

#27 Updated by Carl Ollivier-Gooch about 6 years ago

  • Status changed from New to Feedback

#28 Updated by Mark Miller almost 6 years ago

  • Description updated (diff)

#29 Updated by Carl Ollivier-Gooch almost 6 years ago

  • Status changed from Feedback to Closed

Also available in: Atom PDF