Comments (11)
I will close this as my testing indicates it's much better now.
from cubical.
That is very strange! There seems to be an exponential blow-up. This does not happen for +-suc, so I think the problem must come from the use of compPath which builds a bunch of hcomp's. The number of them should be linear though, so I would expect this to be linear as well.
@Saizan Thoughts?
from cubical.
I think you are right that the culprit is compPath, it seems more expensive to increase the second argument, which is the one creating more compositions.
Also, using _□_
seems to make things faster regardless.
from cubical.
Ok, it's a problem of sharing for partial elements, basically hcomp has to look at the partial elements to decide if they are a constructor and then recurse. However, because of how partial elements are manipulated, the recusive call has to reduce the original partial element from scratch.
The reason for this inefficiency is that there isn't a good way to generate partial elements during reduction at the moment. Currently the only way to produce non-trivial partial elements on the fly is primPOr
which is a single disjunction, so things might get a little ugly if reducing an hcomp
on an inductive type leads to a term with a bunch of nested primPOr
, though it would be more efficient.
Maybe the solution is an n-ary version of primPOr
.
For naturals and other builtin types with literals we should also have custom implementations that take advantage of the compact representation available for closed terms. E.g., for Nat, hcomp [phi -> 100] 100
should compute to 100
directly rather than going through 1 + hcomp [phi -> 99] 99
.
This is actually orthogonal and would be sufficient for +-comm 4 6
.
from cubical.
I noticed a massive speed-up in cubicaltt when computing hcomp as you suggest for closed terms of datatypes. It's not clear to me how we can utilize this in the presence of open terms though... But if we write an efficient closed term evaluator we should definitely use this optimization.
from cubical.
In agda's internals, 100 is represented as LitNat _ 100
where LitNat :: Range -> Integer -> Literal
, so even in the evaluator for open terms we could have a special case for when all the sides are of the form Literal l
.
from cubical.
Won't this force the sides to always be evaluated? I tried this in cubicaltt and it made things extremely slow because we couldn't rely on laziness to avoid unfolding things
from cubical.
For open computation we have to reduce the sides to WHNF anyway.
For compositions that are known to be closed we can just use the base, that would be a different optimization.
from cubical.
I see. Please try to optimization then! A good benchmark is: https://github.com/agda/cubical/blob/master/Cubical/Experiments/Problem.agda#L69
It should evaluate to refl at pos 0. I cubicaltt it is instant (with the optimization for hcomp in nat) but in Cubical Agda it never terminated for me.
from cubical.
A good benchmark is: https://github.com/agda/cubical/blob/master/Cubical/Experiments/Problem.agda#L69
Might be good, but unless I'm missing something it's not a benchmark involving hcomp
on inductive types much. Seems like it's all about HITs and the universe.
from cubical.
Optimized hcomp
for data types and especially literals in Agda master, agda/agda@fdbe073
Normalizing +-comm 4 6
is much faster, and things scale reasonably to larger numbers (+-comm
can't get better than linear in the second argument).
@wvhulle would you like to test it out?
from cubical.
Related Issues (20)
- Citation.cff HOT 4
- Where should `π₁(RP²)` be? HOT 1
- Duplication of code in the library HOT 3
- Note licence exceptions HOT 2
- Slightly more generalized universes HOT 1
- Remove `isSet` accessors for algebraic structures? HOT 3
- Change the Constructor Name of Sequential Colimits HOT 2
- CI workflow with current agda master HOT 5
- Additions to the powerset module HOT 2
- Some Files are never checked HOT 6
- Suggested heap size for CI HOT 1
- SumMap in Algebra.Ring.BigOps should come from Semirings /Monoids HOT 1
- `make` fails on macOS Sonoma 14.2.1 with Apple Silicon HOT 1
- Algebraic geometry HOT 2
- Figure out why the CommRingSolver doesn't work in this case HOT 5
- Make the CommRingSolver work better with concrete rings
- More elegant construction of ZariskiLattice HOT 2
- Solver for wild categories
- arithmetic operations of Cubical.Data.Rationals is super slow HOT 1
- Naming Convention for Disambiguation HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from cubical.