ManimCommunity / ManimCommunity/manim

Exponential Time Complexity in OpenGL Renderer

Open
#2,463 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

issue:bug
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.