Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add cache to Intersection #397

Closed
schillic opened this issue Jul 24, 2018 · 2 comments
Closed

Add cache to Intersection #397

schillic opened this issue Jul 24, 2018 · 2 comments
Assignees
Labels
performance 🐎 More efficient code

Comments

@schillic
Copy link
Member

In #396 we implement the concrete intersection of two hyperrectangles. The issue with the lazy operation (Intersection{N, <:AbstractHyperrectangle, <:AbstractHyperrectangle}) is this: It needs to know whether the intersection is empty in advance. In the worst case this requires to compute the whole intersection, which to some extent breaks the point of the lazy operation.
Given that we have to compute this information with the first support vector query (or other queries like isempty), we should cache this result and only compute it once.
I guess that this observation is general for the intersection (in particular also for #375 and #262), so we should have a general caching mechanism for the lazy Intersection type. I cannot quite foresee how this cache would look like. For the moment it would suffice to have a new field isempty::Tribool. A Tribool would be a (mutable) type that can be true, false, or unknown. The field isempty would be initialized to unknown and later be set to true or false accordingly. (Note that Intersection would still be immutable.)
Later we may require more specific information for intersections, depending on the set types. Then we could replace the isempty field by a general caching field cache::C where C is a new type parameter of type IntersectionCache. The latter would be a new abstract type that we can instantiate for each respective combination of set types. In the instantiation we would store the respective information.

So the question is: Do we want to have the isempty field for now, or directly go for the general IntersectionCache type?

@schillic schillic added discussion 🗣️ Requires human input performance 🐎 More efficient code labels Jul 24, 2018
@mforets
Copy link
Member

mforets commented Jul 24, 2018

I like the idea of the isempty field (*). Besides or complementing this idea, what do you think if we ask that the lazy type at creation (it can be optional and true by default), it runs is_intersection_empty and in the case it is empty, it returns the EmptySet.

(*) not sure about this fields name, because this name is already taken..

@schillic
Copy link
Member Author

(*) not sure about this fields name, because this name is already taken..

For a function only, right? The idea would be that we only use this field internally. And to me it describes perfectly what it should do.

what do you think if we ask that the lazy type at creation (it can be optional and true by default), it runs is_intersection_empty and in the case it is empty, it returns the EmptySet.

If it is optional, it is okay. But I hesitate to make it the default behavior because the is_intersection_empty check can be as expensive as the lazy version, which spoils everything. If you do not run this check, you at least save the computations if you never ask for a support vector - the only benefit I see with the Intersection wrapper.

@schillic schillic removed the discussion 🗣️ Requires human input label Oct 13, 2018
@schillic schillic self-assigned this Oct 13, 2018
@schillic schillic changed the title Add another field to Intersection Add cache to Intersection Oct 14, 2018
schillic added a commit that referenced this issue Oct 14, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
performance 🐎 More efficient code
Projects
None yet
Development

No branches or pull requests

2 participants