ManimCommunity / ManimCommunity/manim
Exponential Time Complexity in OpenGL Renderer
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 40.9k
- Forks
- 3.1k
- Avg merge
- 3d 12h
- Merged PRs (30d)
- 25
Description
(I have no idea if this should be labeled a bug, feel free to relabel it if you need to)
Consider the following (family of) scenes:
```python
class Test1(Scene):
def construct(self):
long = Tex(*["a"] * 1)
self.play(*[m.animate.set_color(BLUE) for m in long])
class Test2(Scene):
def construct(self):
long = Tex(*["a"] * 2)
self.play(*[m.animate.set_color(BLUE) for m in long])
class Test3(Scene):
def construct(self):
long = Tex(*["a"] * 3)
self.play(*[m.animate.set_color(BLUE) for m in long])
class Test4(Scene):
def construct(self):
long = Tex(*["a"] * 4)
self.play(*[m.animate.set_color(BLUE) for m in long])
class Test5(Scene):
def construct(self):
long = Tex(*["a"] * 5)
self.play(*[m.animate.set_color(BLUE) for m in long])
class Test6(Scene):
def construct(self):
long = Tex(*["a"] * 6)
self.play(*[m.animate.set_color(BLUE) for m in long])
class Test7(Scene):
def construct(self):
long = Tex(*["a"] * 7)
self.play(*[m.animate.set_color(BLUE) for m in long])
class Test8(Scene):
def construct(self):
long = Tex(*["a"] * 8)
self.play(*[m.animate.set_color(BLUE) for m in long])
class Test9(Scene):
def construct(self):
long = Tex(*["a"] * 9)
self.play(*[m.animate.set_color(BLUE) for m in long])
class Test10(Scene):
def construct(self):
long = Tex(*["a"] * 10)
self.play(*[m.animate.set_color(BLUE) for m in long])
```
The only difference between them is how long the string is. I then wrote a script to time the compilation of each one:
```bash
#!/bin/bash
time manim test.py Test1 -ql &> /dev/null
time manim test.py Test2 -ql &> /dev/null
time manim test.py Test3 -ql &> /dev/null
time manim test.py Test4 -ql &> /dev/null
time manim test.py Test5 -ql &> /dev/null
time manim test.py Test6 -ql &> /dev/null
time manim test.py Test7 -ql &> /dev/null
time manim test.py Test8 -ql &> /dev/null
time manim test.py Test9 -ql &> /dev/null
time manim test.py Test10 -ql &> /dev/null
```
I then ran this for both the cairo and opengl renderers, and the results were quite different. Here's the results for cairo:
```
real 0m2.231s
user 0m1.368s
sys 0m0.732s
real 0m1.209s
user 0m1.224s
sys 0m0.634s
real 0m1.654s
user 0m1.328s
sys 0m0.991s
real 0m1.268s
user 0m1.307s
sys 0m0.645s
real 0m1.690s
user 0m1.346s
sys 0m1.051s
real 0m1.280s
user 0m1.352s
sys 0m0.683s
real 0m1.319s
user 0m1.403s
sys 0m0.756s
real 0m1.319s
user 0m1.378s
sys 0m0.711s
real 0m1.368s
user 0m1.475s
sys 0m0.721s
real 0m1.383s
user 0m1.467s
sys 0m0.770s
```
And here's the results for opengl:
```
real 0m1.381s
user 0m1.382s
sys 0m0.846s
real 0m1.502s
user 0m1.503s
sys 0m1.031s
real 0m1.510s
user 0m1.602s
sys 0m0.856s
real 0m1.921s
user 0m1.970s
sys 0m1.015s
real 0m2.718s
user 0m2.799s
sys 0m1.045s
real 0m4.518s
user 0m4.469s
sys 0m1.251s
real 0m9.322s
user 0m9.165s
sys 0m1.379s
real 0m20.216s
user 0m19.945s
sys 0m1.492s
real 0m57.139s
user 0m55.769s
sys 0m2.355s
real 2m7.733s
user 2m4.805s
sys 0m3.651s
```
As you can see, while the cairo times were pretty constant, the opengl times started to exponentially increase. Based on a bit of testing that I've done, it seems that it's spending all of its time copying (I ran into this issue in a real project where it got so bad I hit the Python recursion limit, and it crashed in copying functions). I'm guessing that the way that the opengl renderer does things ends up causing some kind of exponential copying.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Run the supplied test.py scenes with both Cairo and OpenGL, then profile the copying path in the OpenGL renderer as suggested by the report. Compare timing as the number of Tex elements grows and verify that the renderer no longer shows exponential scaling or reaches Python's recursion limit.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- computer-graphics, performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100