Increased memory consumption in ParentMapContext after clang-19

[michael-jabbour-sonarsource]

The memory increase can be observed when enabling any check that uses ASTContext::getParents in clang-tidy. By plotting the memory consumption when analyzing a sample file, I got the following chart which shows around 10x increase in memory consumption in clang-tidy-19 compared to clang-tidy-18 when the number of elements in the array is large enough:

When the number of elements is close to 10M, memory consumption goes from about 3GB before clang-tidy-19 to about 30GB on clang-19.

Here is a script that generates the above plot:

import matplotlib.pyplot as plt
import subprocess

def generate_cpp_file(file_name, num_elements):
  elements = [100] * num_elements
  elements_str = ', '.join(map(hex, elements))
  with open(file_name, 'w') as f:
    f.write(f"""
            const char large_array[] = {{
              {elements_str}
            }};
            """)


def measure_memory_consumption_with(clang_tidy_bin, num_elements):
  file_name = f'file_{num_elements}.cpp'
  generate_cpp_file(file_name, num_elements)
  process = subprocess.run(['/usr/bin/time', '-f', '%M', clang_tidy_bin, '-checks=readability-magic-numbers', file_name, '--', '-std=c++17'], check=True, capture_output=True)
  memory_kb = int(process.stderr)
  return memory_kb // 1024


def plot_memory_consumption():
  num_elements = [10 ** 1, 10 ** 2, 10 ** 3, 10 ** 4, 10 ** 5, 10 ** 6, 3 * 10 ** 6, 5 * 10 ** 6, 8 * 10 ** 6]

  memory_consumption_17 = [measure_memory_consumption_with('clang-tidy-17', n) for n in num_elements]
  memory_consumption_18 = [measure_memory_consumption_with('clang-tidy-18', n) for n in num_elements]
  memory_consumption_19 = [measure_memory_consumption_with('clang-tidy-19', n) for n in num_elements]
  plt.plot(num_elements, memory_consumption_17, label='clang-tidy-17')
  plt.plot(num_elements, memory_consumption_18, label='clang-tidy-18')
  plt.plot(num_elements, memory_consumption_19, label='clang-tidy-19')
  plt.xlabel('Number of elements')
  plt.ylabel('Memory consumption (MB)')
  plt.legend()
  plt.show()


if __name__ == '__main__':
  plot_memory_consumption()

I have installed clang-tidy binaries in this test from apt.llvm.org on an Ubuntu machine.

[llvmbot]

@llvm/issue-subscribers-clang-frontend

Author: Michael Jabbour (michael-jabbour-sonarsource)

The memory increase can be observed when enabling any check that uses `ASTContext::getParents` in `clang-tidy`. By plotting the memory consumption when analyzing a sample file, I got the following chart which shows around 10x increase in memory consumption in clang-tidy-19 compared to clang-tidy-18 when the number of elements in the array is large enough:

When the number of elements is close to 10M, memory consumption goes from about 3GB before clang-tidy-19 to about 30GB on clang-19.

Here is a script that generates the above plot:

import matplotlib.pyplot as plt
import subprocess

def generate_cpp_file(file_name, num_elements):
  elements = [100] * num_elements
  elements_str = ', '.join(map(hex, elements))
  with open(file_name, 'w') as f:
    f.write(f"""
            const char large_array[] = {{
              {elements_str}
            }};
            """)


def measure_memory_consumption_with(clang_tidy_bin, num_elements):
  file_name = f'file_{num_elements}.cpp'
  generate_cpp_file(file_name, num_elements)
  process = subprocess.run(['/usr/bin/time', '-f', '%M', clang_tidy_bin, '-checks=readability-magic-numbers', file_name, '--', '-std=c++17'], check=True, capture_output=True)
  memory_kb = int(process.stderr)
  return memory_kb // 1024


def plot_memory_consumption():
  num_elements = [10 ** 1, 10 ** 2, 10 ** 3, 10 ** 4, 10 ** 5, 10 ** 6, 3 * 10 ** 6, 5 * 10 ** 6, 8 * 10 ** 6]

  memory_consumption_17 = [measure_memory_consumption_with('clang-tidy-17', n) for n in num_elements]
  memory_consumption_18 = [measure_memory_consumption_with('clang-tidy-18', n) for n in num_elements]
  memory_consumption_19 = [measure_memory_consumption_with('clang-tidy-19', n) for n in num_elements]
  plt.plot(num_elements, memory_consumption_17, label='clang-tidy-17')
  plt.plot(num_elements, memory_consumption_18, label='clang-tidy-18')
  plt.plot(num_elements, memory_consumption_19, label='clang-tidy-19')
  plt.xlabel('Number of elements')
  plt.ylabel('Memory consumption (MB)')
  plt.legend()
  plt.show()


if __name__ == '__main__':
  plot_memory_consumption()

I have installed clang-tidy binaries in this test from apt.llvm.org on an Ubuntu machine.

[llvmbot]

@llvm/issue-subscribers-clang-tidy

Author: Michael Jabbour (michael-jabbour-sonarsource)

The memory increase can be observed when enabling any check that uses `ASTContext::getParents` in `clang-tidy`. By plotting the memory consumption when analyzing a sample file, I got the following chart which shows around 10x increase in memory consumption in clang-tidy-19 compared to clang-tidy-18 when the number of elements in the array is large enough:

When the number of elements is close to 10M, memory consumption goes from about 3GB before clang-tidy-19 to about 30GB on clang-19.

Here is a script that generates the above plot:

import matplotlib.pyplot as plt
import subprocess

def generate_cpp_file(file_name, num_elements):
  elements = [100] * num_elements
  elements_str = ', '.join(map(hex, elements))
  with open(file_name, 'w') as f:
    f.write(f"""
            const char large_array[] = {{
              {elements_str}
            }};
            """)


def measure_memory_consumption_with(clang_tidy_bin, num_elements):
  file_name = f'file_{num_elements}.cpp'
  generate_cpp_file(file_name, num_elements)
  process = subprocess.run(['/usr/bin/time', '-f', '%M', clang_tidy_bin, '-checks=readability-magic-numbers', file_name, '--', '-std=c++17'], check=True, capture_output=True)
  memory_kb = int(process.stderr)
  return memory_kb // 1024


def plot_memory_consumption():
  num_elements = [10 ** 1, 10 ** 2, 10 ** 3, 10 ** 4, 10 ** 5, 10 ** 6, 3 * 10 ** 6, 5 * 10 ** 6, 8 * 10 ** 6]

  memory_consumption_17 = [measure_memory_consumption_with('clang-tidy-17', n) for n in num_elements]
  memory_consumption_18 = [measure_memory_consumption_with('clang-tidy-18', n) for n in num_elements]
  memory_consumption_19 = [measure_memory_consumption_with('clang-tidy-19', n) for n in num_elements]
  plt.plot(num_elements, memory_consumption_17, label='clang-tidy-17')
  plt.plot(num_elements, memory_consumption_18, label='clang-tidy-18')
  plt.plot(num_elements, memory_consumption_19, label='clang-tidy-19')
  plt.xlabel('Number of elements')
  plt.ylabel('Memory consumption (MB)')
  plt.legend()
  plt.show()


if __name__ == '__main__':
  plot_memory_consumption()

I have installed clang-tidy binaries in this test from apt.llvm.org on an Ubuntu machine.

[shafik]

CC @AaronBallman @erichkeane

[michael-jabbour-sonarsource]

Bisects to c54afe5.

Before (about 50 seconds, 3.5GB memory):

$ git checkout 04bf1a4090c5
HEAD is now at 04bf1a4090c5 Update `LowerContractionToSMMLAPattern` to ingnore matvec (#88288)
$ ninja -C build clang-tidy && /usr/bin/time build/bin/clang-tidy -checks=-*,readability-magic-numbers file_10000000.cpp -- -std=c++17
ninja: Entering directory `build'
ninja: no work to do.
47.17user 2.20system 0:49.38elapsed 99%CPU (0avgtext+0avgdata 3415304maxresident)k
0inputs+0outputs (0major+1101314minor)pagefaults 0swaps

After (about 1 minute, 30GB memory):

$ git checkout c54afe5c33ca
Previous HEAD position was 04bf1a4090c5 Update `LowerContractionToSMMLAPattern` to ingnore matvec (#88288)
HEAD is now at c54afe5c33ca Fix quadratic slowdown in AST matcher parent map generation (#87824)
$ ninja -C build clang-tidy && /usr/bin/time build/bin/clang-tidy -checks=-*,readability-magic-numbers file_10000000.cpp -- -std=c++17
ninja: Entering directory `build'
[11/11] Linking CXX executable bin/clang-tidy
46.48user 14.41system 1:00.92elapsed 99%CPU (0avgtext+0avgdata 29352044maxresident)k
0inputs+0outputs (0major+7585685minor)pagefaults 0swaps

Where file_10000000.cpp contains the same test case used in the chart above (large_array with 10M explicit initializers).

[AaronBallman]

CC @higher-performance

[erichkeane]

Ah, woah, I vaguely remember that patch, but don't recall thinking that the parent map was so widely used!

Actually, based on the size (we pre-set it to be size 2?), I find myself wondering if the quadratic search it was trying to fix is even worth solving and we should just revert that. Secondly, since the purpose of Seen is simply to unique the Items list, a 'search' through Items is probably sufficient (OR, if we could find some sort of alternative structure/representation).

Side note: The ctor of that could probably just do an insert + `std::unique.

@higher-performance : Please put me on the review for fixing this.