This is an archive of the discontinued LLVM Phabricator instance.

[clang-tidy] Add performance-inefficient-array-traversal check
AcceptedPublic

Authored by njames93 on Jan 8 2022, 7:43 PM.

Details

Summary

Adds a check that detects 2D array traversals where the array is traversed column wise instead of row wise.
These patterns harm cache performance as well as prevent auto-vectorisation opportunities.

Diff Detail

Event Timeline

njames93 created this revision.Jan 8 2022, 7:43 PM
njames93 requested review of this revision.Jan 8 2022, 7:43 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 8 2022, 7:43 PM
Herald added a subscriber: cfe-commits. · View Herald Transcript
Eugene.Zelenko added inline comments.Jan 8 2022, 9:43 PM
clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp
60

I think will be reasonable to check for += and -=.

clang-tools-extra/docs/ReleaseNotes.rst
124

Please highlight for with double back-ticks. Same in documentation.

clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-array-traversal.rst
16

Excessive newline.

27

Excessive newline.

njames93 updated this revision to Diff 398404.Jan 9 2022, 1:24 AM
njames93 marked 4 inline comments as done.

Address comments

njames93 added inline comments.Jan 9 2022, 1:29 AM
clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp
64

Thoughts on this, prefetchers are often able to detect strided access so is forcing increment to be 1 removing potential functionality.

92

Any ideas on a nicer way to say this? I feel like this message isn't as descriptive as I'd like, and non-native English speakers could struggle to understand it.

Eugene.Zelenko added inline comments.Jan 9 2022, 6:39 AM
clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.cpp
64

Theoretically index changes may be other than 1. For example, in some electronic simulation each block/device store matrix indexes to contribute (but sparse, not dense, matrix is used). It'll be good idea to look on BLAS and LAPACK (through both are written in Fortran).

njames93 updated this revision to Diff 400266.Jan 15 2022, 2:28 AM

Add support for array access Arr[I * JExtent + J]

Except for a couple nits, LGTM.

clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h
26–27

If you're not doing anything different, I believe you can just do
using ClangTidyCheck::ClangTidyCheck;

Also, shouldn't you be explicitly overriding the d'tor?
~InefficientArrayTraversalCheck() override = default;

This revision is now accepted and ready to land.Jan 16 2022, 1:59 PM
njames93 marked an inline comment as done.Jan 19 2022, 7:39 AM
njames93 added inline comments.
clang-tools-extra/clang-tidy/performance/InefficientArrayTraversalCheck.h
26–27

No need to explicitly override the d'tor

njames93 updated this revision to Diff 401234.Jan 19 2022, 7:39 AM
njames93 marked an inline comment as done.

Use inheriting constructor for check

njames93 updated this revision to Diff 401241.Jan 19 2022, 7:57 AM

Uploaded wrong diff

njames93 updated this revision to Diff 403050.Jan 25 2022, 3:18 PM

Simplify check logic to only detect loop inits with 0 and incriment with 1.
Functionality can be introduced with later patches.

shafik added a subscriber: shafik.Sep 26 2023, 2:06 PM

Is this change still relevant or can we close the PR?

Herald added a project: Restricted Project. · View Herald TranscriptSep 26 2023, 2:06 PM
Herald added a subscriber: PiotrZSL. · View Herald Transcript