Re: Proposal for Requiring Save/Restore of Sets and Tags
On 10/20/2010 06:43 AM, Jason Kraftcheck wrote:
On 10/05/2010 10:35 AM, Carl Ollivier-Gooch wrote:
These are things that one generally creates from a (undirected cyclic) graph of the individual entities (of a given type) in the mesh. So the only way I'm seeing a graph of sets here is if you create sets with exactly one entity apiece and string them together into a graph.
While our current use of tests is limited to tree-like graphs (geometric topology, spatial subdivision trees, etc.) I'm hesitant to agree with the premise that it will never be a useful capability to be able to construct more general graphs of groups of entities.
It's possible that it's a useful capability, but it's semantically incompatible with either of the two mechanisms we currently have (subset/set membership and parent/child). Semantically, the only way to have a cycle there is something as silly as set A is an improper subset of B is an improper subset of A --- with A and B necessarily identical sets. Parent-child relationships can't semantically have cycles at all. So anything that's got cycles will fail to have a set-theoretic meaning that's compatible with what we currently have in the data model. Allowing cycles would necessarily change the semantics of one of those two relationships, and I'm not prepared to do that because we -might- -someday- identify a use case for it.
Of course, if one really wanted to construct graphs of iBase_EntityHandle type entities, thandle-type tags might be a better choice. But it wouldn't use a lot more memory to use sets in MOAB.
I don't dispute that a general graph capability --- which isn't what our current data model supports --- would support this.
But why would anyone ever do this this way? I mean, using iMesh sets to represent this graph is going to super-expensive because of the overhead of having a graph of -sets- instead of a graph of entities (unless there's some ultra-light-weight way to represent sets that I can't imagine). And the traversal isn't going to be any easier than representing the set in some other way, and is again going to be significantly more expensive. So you'll have to come up with some other example to convince me there's a realistic use case here.
Well, as I said above, we do use sets for some graphs now. It is actually much cheaper if one is creating graphs from groups of entities. But our spatial search trees perform quite well constructed from sets and in that case the non-leaf nodes don't have any entities. Our data model doesn't really have anything else suitable to use for such graph nodes.
Whether it's cheaper to use sets or some other, non-iMesh method to create the graph is going to depend heavily on the set implementation, I suspect. I'm sure my implementation of sets would use more memory for this than a purpose-built ADT (and frankly I'm surprised it's possible to beat the purpose-built ADT with any set implementation). Not saying that creating the graph this way is a bad thing, or that it doesn't make like easier for an app programmer...
But there very well could be in the future. We didn't imagine using sets for spatial search trees when initially considering the data model.
If and when a use case arises, we should discuss it then, IMO, rather than breaking well-defined semantics for a possibility.
I agree that embedding these types of graphs into a data model that seems more geared to directed graphs is a stretch. But, in my view, we should keep the possibility of embedding general graphs in the data model, even if accessing those types of graphs is somewhat unnatural.
If we're going to embed general graphs of entities in the data model, let's do that, instead of distorting a set data model with well-defined semantics to cover something it wasn't originally intended to (or at least, that I don't recall us ever discussing as an original intent). If nothing else, we can surely implement general graphs of entities in a much lighter-weight way than general graphs of sets, because we lose the set overhead.
I don't have a strong opinion about this. But I am adamantly opposed to requiring implementations to check for and refuse to create cyclic graphs. We do some stuff involving very large graphs (e.g. millions of sets). The performance penalty would be significant. And we already correctly handle cyclic graphs in queries.
My memory is that we had already agreed that an implementation is free to skip expensive (and even cheap) checks when compiled in release mode, though it should do all checks in debug mode. The latter is very important to help developers debug code, but once it's working (i.e., nothing stupid being done by accident), a lot of those checks are unnecessary, so turning them off for release code is no problem. Conditionally-defined macros will do this. As Mark said, there are run-time configurable methods for this, too, though I suspect they add a small amount of overhead in practice. Carl -- ------------------------------------------------------------------------ Dr. Carl Ollivier-Gooch, P.Eng. Voice: +1-604-822-1854 Professor Fax: +1-604-822-2403 Department of Mechanical Engineering email: [email protected] University of British Columbia http://www.mech.ubc.ca/~cfog Vancouver, BC V6T 1Z4 http://tetra.mech.ubc.ca/ANSLab/ ------------------------------------------------------------------------
On Thu, 2010-10-21 at 09:35, Carl Ollivier-Gooch wrote:
My memory is that we had already agreed that an implementation is free to skip expensive (and even cheap) checks when compiled in release mode,
So, I don't recall there being an ITAPS-wide, agreed upon config-time switch names to control this. Do we have any defined? I know projects like HDF5 use something like --enable-production or --enable-debug but I don't honestly know what the adopted 'ITAPS-way' for this is, if there is one. If not, we might ought to propose one ASAP.
though it should do all checks in debug mode. The latter is very important to help developers debug code, but once it's working (i.e., nothing stupid being done by accident), a lot of those checks are unnecessary, so turning them off for release code is no problem. Conditionally-defined macros will do this. As Mark said, there are run-time configurable methods for this, too, though I suspect they add a small amount of overhead in practice.
There are indeed config-time ways of managing the amount of work a library is required to perform for error-checking, etc. And, honestly, if the ITAPS project as a whole wants to do it using ONLY a config-time control mechanism, I think that would be ok. My very strong personal preference, based on a lot of experience with this kind of thing though, is a run-time check the default behavior of which is controlled at config-time. If you config for 'release mode', the checks are OFF by default but can be turned ON at run-time. If you config for 'development mode', the checks are ON by default but can be turned off at run-time. Finally, the run-time controls consist of a) a function in the library an application can call to affect ON/OFF control and b) an env. variable or command line argument a user can set to override everything else (note that a command-line argument appraoch would require a change to iMesh_newMesh to accept argc/argv from the command line much like MPI_Init does). Yeah, there is probably a tiny, imperceptable, run-time cost associated with doing it this way. However, the flexibility it affords has always trumped concerns for that ;) Mark -- Mark C. Miller, Lawrence Livermore National Laboratory ================!!LLNL BUSINESS ONLY!!================ [email protected] urgent: [email protected] T:8-6 (925)-423-5901 M/W/Th:7-12,2-7 (530)-753-8511
On 10/21/2010 11:35 AM, Carl Ollivier-Gooch wrote:
It's possible that it's a useful capability, but it's semantically incompatible with either of the two mechanisms we currently have (subset/set membership and parent/child). Semantically, the only way to have a cycle there is something as silly as set A is an improper subset of B is an improper subset of A --- with A and B necessarily identical sets. Parent-child relationships can't semantically have cycles at all.
So we have a capability to construct graphs of sets (parent/child links). We have functions for querying and manipulating such links named in accordance with or initial intended uses. Your argument is to constrain the functionality based on a semantic argument about the function names. Wouldn�t it be better (cost nothing and not limit future functionality) to just rename the functions? By why even do that? I just don't see the problem with a) having this functionality (or at least not prohibiting us from providing it) and b) naming the functions in such a way as to be least confusing for the majority of uses.
My memory is that we had already agreed that an implementation is free to skip expensive (and even cheap) checks when compiled in release mode, though it should do all checks in debug mode. The latter is very important to help developers debug code, but once it's working (i.e., nothing stupid being done by accident), a lot of those checks are unnecessary, so turning them off for release code is no problem. Conditionally-defined macros will do this. As Mark said, there are run-time configurable methods for this, too, though I suspect they add a small amount of overhead in practice.
You are stating that implementations must conform to a standard behavior of prohibiting cyclical links. And then recommending that we disable such restrictions in the version/build of the code that will be used in practice. Then why even make this a requirement? What's the point of making us jump through hoops implementing a "strict conformance" build that will only be used in practice with the conformance tests? How much code can we change between the two? Would instead building a copy of the reference implementation if strict conformance is requested be okay? - jason
So, I think we're agreed that cycles in the set inclusion structure are out, right? I mean, I am not seeing any strong opposition there. And, I have to say that I strongly agree with Carl's observation that the only 'legitimate' case of cycles in set inclusion structure is for some, possibility arbitrary long, chain of sets which are all equal to each other. What value can allow that possibly serve? What use case requires that and which NOT allowing cycles in set inclusion cause undue hardship for? So, the real issue is with cycles int the Prnt/Chld structure, right? Jason, you mention below "...naming the [Prn/Chld] functions in such a way as to be least confusing for the majority of uses..." I have to say that the whole concept of Prnt/Chld functions in the interface was a major confusion to me when I first started learning it. My source of confusion was that I thought the set inclusion structure already imposed which sets were 'parents' of other sets by virtue of their containment relationships. So, as far as naming these functions go, I think Prnt/Chld is actually MORE confusing that something like void addSetGraphDirectedLink(iMesh_instance inst, iBase_EntitySetHandle tail_set, iBase_EntitySetHandle head_set int *err); void addSetGraphUndirectedLink(iMesh_instance inst, iBase_EntitySetHandle one_set, iBase_EntitySetHandle another_set, int *err); And, I'd really, like to put tag data on graph links too. So, if were going to say "hey even though we call these functions 'parent' and 'child' thingies, we're really handling a general graph', then I'd like to see the functions renamed to something more appropriate and the words 'parent' and 'child' stricken from the iMesh.h header file (replaced, of course, with 'direct' or 'undirected link') And, if its a general graph, then I don't see any reason cycles should NOT be supported. Mark On Thu, 2010-10-21 at 10:04, Jason Kraftcheck wrote:
On 10/21/2010 11:35 AM, Carl Ollivier-Gooch wrote:
It's possible that it's a useful capability, but it's semantically incompatible with either of the two mechanisms we currently have (subset/set membership and parent/child). Semantically, the only way to have a cycle there is something as silly as set A is an improper subset of B is an improper subset of A --- with A and B necessarily identical sets. Parent-child relationships can't semantically have cycles at all.
So we have a capability to construct graphs of sets (parent/child links). We have functions for querying and manipulating such links named in accordance with or initial intended uses. Your argument is to constrain the functionality based on a semantic argument about the function names. WouldnοΏ½t it be better (cost nothing and not limit future functionality) to just rename the functions? By why even do that? I just don't see the problem with a) having this functionality (or at least not prohibiting us from providing it) and b) naming the functions in such a way as to be least confusing for the majority of uses.
My memory is that we had already agreed that an implementation is free to skip expensive (and even cheap) checks when compiled in release mode, though it should do all checks in debug mode. The latter is very important to help developers debug code, but once it's working (i.e., nothing stupid being done by accident), a lot of those checks are unnecessary, so turning them off for release code is no problem. Conditionally-defined macros will do this. As Mark said, there are run-time configurable methods for this, too, though I suspect they add a small amount of overhead in practice.
You are stating that implementations must conform to a standard behavior of prohibiting cyclical links. And then recommending that we disable such restrictions in the version/build of the code that will be used in practice. Then why even make this a requirement? What's the point of making us jump through hoops implementing a "strict conformance" build that will only be used in practice with the conformance tests? How much code can we change between the two? Would instead building a copy of the reference implementation if strict conformance is requested be okay?
- jason -- Mark C. Miller, Lawrence Livermore National Laboratory ================!!LLNL BUSINESS ONLY!!================ [email protected] urgent: [email protected] T:8-6 (925)-423-5901 M/W/Th:7-12,2-7 (530)-753-8511
I like to think of it as the Harrison Bergeron test (http://en.wikipedia.org/wiki/Harrison_Bergeron)... - tim On 10/21/2010 12:04 PM, Jason Kraftcheck wrote:
On 10/21/2010 11:35 AM, Carl Ollivier-Gooch wrote:
My memory is that we had already agreed that an implementation is free to skip expensive (and even cheap) checks when compiled in release mode, though it should do all checks in debug mode. The latter is very important to help developers debug code, but once it's working (i.e., nothing stupid being done by accident), a lot of those checks are unnecessary, so turning them off for release code is no problem. Conditionally-defined macros will do this. As Mark said, there are run-time configurable methods for this, too, though I suspect they add a small amount of overhead in practice.
You are stating that implementations must conform to a standard behavior of prohibiting cyclical links. And then recommending that we disable such restrictions in the version/build of the code that will be used in practice. Then why even make this a requirement? What's the point of making us jump through hoops implementing a "strict conformance" build that will only be used in practice with the conformance tests? How much code can we change between the two? Would instead building a copy of the reference implementation if strict conformance is requested be okay?
- jason
-- ================================================================ "You will keep in perfect peace him whose mind is steadfast, because he trusts in you." Isaiah 26:3 Tim Tautges Argonne National Laboratory ([email protected]) (telecommuting from UW-Madison) phone: (608) 263-8485 1500 Engineering Dr. fax: (608) 263-4499 Madison, WI 53706
participants (4)
-
Carl Ollivier-Gooch -
Jason Kraftcheck -
Mark Miller -
Tim Tautges