itaps-parallel Proposal for Requiring Save/Restore of Sets and Tags

[Jason Kraftcheck]

On 10/21/2010 03:36 PM, Carl Ollivier-Gooch wrote:

> 
> I was referring to the case of requesting an -iterator- over faces that
> are also prisms.  That's pretty clearly a malformed call.  Retrieving
> the faces of a prism is equally clearly not.
> 

And that is a request that an implementation cannot fulfill (sanely)
regardless of whether or not the spec explicitly prohibits it.

> 
> Okay, I'll concede that one can construct a graph for which this test
> would be O(n) --- a graph that can be mapped onto a straight line.

Searching for cycles in a graph is O(n).

>  And
> for balanced trees, I guess the check is still O(log n), for total
> complexity of O(n log n).  That still isn't great, but it's no worse
> than the complexity for constructing the tree itself.

And how do you verify that it is a tree as opposed to a more general graph
in better than O(n)?

>>
>> This isn't keeping interoperability.  It is requiring implementations do
>> interoperability checks for applications.  If they want those checks then
>> they can test with reference implementation.
> 
> Huh?  If the spec says that X must happen, and all implementations but
> one do that, then an implementation that doesn't isn't interoperable
> with the others, in the sense that code written to exploit that feature
> of that implementation fails on the others.  As you've all probably
> gathered, I'm in favor of narrowing down the possibilities of this sort
> of thing in the API; after all, we're advertising interoperability as a
> major selling point.
> 

Yes, tautologically, if the spec mandates that implementations check this,
then implementations are not conforming if they do not check it. However,
your argument for adding this check is to ensure that all applications using
the API do not use it in some way that not all implementations support.  So
what you're asking is that all implementations perform a very expensive
check to do conformance testing for the application.


>>> 2.  Change the current semantics, rendering the check irrelevant.  If
>>> we're going to do this, we face the issue of supporting both directed
>>> and undirected graphs, presumably.  Here the interoperability problem
>>> would be limited to a transition period when we have some
>>> implementations that don't fully support undirected and/or cyclic
>>> graphs.  I think I could support cyclic directed graphs by removing a
>>> check.  Undirected graphs could be really easy or could require
>>> significant re-write; I'm not sure without dissecting the code.
>>>
>>
>> 3.  Don't mandate that implementations refuse to create cyclic graphs.
> 
> If this is made interoperable, in the sense of my last paragraph, how
> does it differ from 2 (leaving aside the directed/undirected issue)?
> 

There are two separate issues.  The first is whether or not to mandate the
check.  As I said way at the start of this thread: I am adamantly opposed to
this because because the computational cost to great.  The second is whether
or not, if we do not mandate the check, which of the other two alternatives
we choose:
  - implementations are allowed to chose between allowing cyclic graphs or
    returning an error code or the full-blown
  - all implementations must support cyclic graphs.

I'd prefer the latter, but I am not in opposition to the former.

> For what it's worth, I can imagine a use case for -undirected- cyclic
> graphs of sets of entities: lumped partitioning and related tasks.
> That's two changes in semantics, but we actually get a use case for our
> trouble this way.
> 

Well, you could use the existing links for that.  Just create parent links
both ways and traverse only parent links.  Of course, if you prohibit cycles
then we need a different type of link.

- jason