Skip to content

Fix compilation slowdown due to controlflow analysis - #6146

Merged
sklam merged 10 commits into
numba:masterfrom
sklam:enh/faster_cfg
Aug 21, 2020
Merged

sklam merged 10 commits into
numba:masterfrom
sklam:enh/faster_cfg

Conversation

@sklam

@sklam sklam commented Aug 18, 2020 •

Copy link
Copy Markdown
Member
  • makes CFG computation lazier.
  • replace backedge algorithm with a DFS based algorithm instead of dominator-based.

@sklam

sklam commented Aug 18, 2020 •

Copy link
Copy Markdown
Member Author

My current reproducer for issue #6133

from pprint import pprint
import numpy as np
import numba

body = """
    for fi in range(0, 10):
        data[fi] += 1
        for index in range(0, 7):
            idx = index
            if idx % 2 == 0:
                data[idx] += fi
            else:
                data[idx] += 1 if data[idx] < 3 else 2
                data[idx] += 1
            data[idx] += 1
"""

wrapper = """
def kernel(data):
    {}
"""

source = wrapper.format(body * 100) # 75
glbs = {}
exec(source, glbs)

arg = np.zeros(100)
argtypes = (numba.typeof(arg),)

kernel = numba.njit(argtypes)(glbs['kernel'])

# 0.48.0 takes 24sec
# 0.51.0 takes 1min13sec

metadata = kernel.get_metadata(kernel.signatures[0])
timings = metadata['pipeline_times']['nopython']
sorttimings = sorted(timings.items(), key=lambda x: sum(x[1]))
for k, v in reversed(sorttimings):
    print(f"{k:40} {sum(v):.3}")

This prints the compiler passes in descending runtime.

With the patch:

13_reconstruct_ssa                       25.3
20_nopython_backend                      13.2
18_nopython_rewrites                     2.36

Without the patch:

13_reconstruct_ssa                       40.1
20_nopython_backend                      13.5
18_nopython_rewrites                     3.23

So the patch trims 20 seconds from SSA

@sklam

sklam commented Aug 18, 2020 •

Copy link
Copy Markdown
Member Author

264665e replaces the backedge algorithm with a simple but faster DFS version. This further speed up the SSA reconstruction:

20_nopython_backend                      15.8
13_reconstruct_ssa                       8.74
18_nopython_rewrites                     2.37

(updated to use output from non-profiled run)

@sklam
sklam marked this pull request as ready for review August 19, 2020 16:09
@esc esc added this to the Numba 0.51.1 milestone Aug 20, 2020
@stuartarchibald

Copy link
Copy Markdown
Contributor

Thanks for the patch. I tested this manually, locally, 10.4->4.73s change in SSA rebuild.

@stuartarchibald stuartarchibald left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Code changes look good, couple of minor comments.

Comment thread numba/core/controlflow.py Outdated
Comment on lines 697 to 698
# A few derived items are checked to makes sure process() has been
# invoked equally.

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can probably remove this comment now, process() has little effect as everything is delayed.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

good catch.

Comment thread numba/core/controlflow.py Outdated
@stuartarchibald stuartarchibald added 4 - Waiting on author Waiting for author to respond to review and removed 3 - Ready for Review labels Aug 20, 2020
@sklam

sklam commented Aug 21, 2020

Copy link
Copy Markdown
Member Author

Resolved all comments.
Merged master and resolved a conflict of missing import

@sklam sklam added 4 - Waiting on reviewer Waiting for reviewer to respond to author and removed 4 - Waiting on author Waiting for author to respond to review labels Aug 21, 2020

@stuartarchibald stuartarchibald left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for the fixes.

@stuartarchibald stuartarchibald added 5 - Ready to merge Review and testing done, is ready to merge and removed 4 - Waiting on reviewer Waiting for reviewer to respond to author labels Aug 21, 2020
@sklam
sklam merged commit dce6993 into numba:master Aug 21, 2020
@sklam
sklam deleted the enh/faster_cfg branch August 21, 2020 22:06
@stuartarchibald stuartarchibald mentioned this pull request Aug 26, 2020
21 tasks done
stuartarchibald pushed a commit to stuartarchibald/numba that referenced this pull request Aug 26, 2020
Fix compilation slowdown due to controlflow analysis
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

5 - Ready to merge Review and testing done, is ready to merge

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants