Issue 981 in include-what-you-use: Qt mapping file causes major slowdown

[notifi...@include-what-you-use.org]

New issue 981 by firewave: Qt mapping file causes major slowdown
https://github.com/include-what-you-use/include-what-you-use/issues/981

I am using the `iwyu` package in version `8.17-1` on Kali Linux rolling (based on Debian) and generated a Qt mapping file using

```
python3 /iwyu-mapgen-qt.py /usr/include/x86_64-linux-gnu/qt5/ > qt5.imp
```

Without additional parameters:
```
real 0m1.843s
user 0m0.844s
sys 0m0.188s
```

With `--mapping_file=qt5.imp`:
```
real 0m37.874s
user 0m36.703s
sys 0m0.313s
```

The file is question is not even using Qt at all. The file is `tinyxml2.cpp` from https://github.com/danmar/cppcheck/tree/main/externals/tinyxml2. It is not related to the file it is just the first file which is being analyzed when using the compilation database and already shows the problem.

A few versions back I did not recognize such a slowdown.

[notifi...@include-what-you-use.org]

Comment #0 on issue 981 by kimgr: Qt mapping file causes major slowdown
https://github.com/include-what-you-use/include-what-you-use/issues/981

Interesting. The Qt mappings are heavy on regex mappings to cover for `<>` and `""` transparency, and they are pretty exhaustive. Qt 5.11 mappings in tree contain about 2300 include mappings and 1500 symbol mappings.

I suspect the regex form causes a linear scan for each include mapping. I wonder if it's time to think through removing quotes from mappings. I've been putting it off because it feels like it might turn into an impossible problem.

[notifi...@include-what-you-use.org]

Comment #1 on issue 981 by kimgr: Qt mapping file causes major slowdown

https://github.com/include-what-you-use/include-what-you-use/issues/981

Interesting. The Qt mappings are heavy on regex mappings to cover for `<>` and `""` transparency, and they are pretty exhaustive. Qt 5.11 mappings in tree contain about 2300 include mappings and 1500 symbol mappings.

I suspect the regex form causes a linear scan for ~each include mapping~ every time a header mapping is attempted. I wonder if it's time to think through removing quotes from mappings. I've been putting it off because it feels like it might turn into an impossible problem.

[notifi...@include-what-you-use.org]

Comment #1 on issue 981 by firewave: Qt mapping file causes major slowdown
https://github.com/include-what-you-use/include-what-you-use/issues/981

FYI It's so slow it's essentially broken. With other files it takes 10+ minutes until the first result even shows up whereas without the mappings the whole bunch is done in less than 3.

> Interesting. The Qt mappings are heavy on regex mappings to cover for `<>` and `""` transparency, and they are pretty exhaustive. Qt 5.11 mappings in tree contain about 2300 include mappings and 1500 symbol mappings.

In my case it is Qt 5.15.2 and the mappings files contains 2973 lines.

> I suspect the regex form causes a linear scan for ~each include mapping~ every time a header mapping is attempted. I wonder if it's time to think through removing quotes from mappings. I've been putting it off because it feels like it might turn into an impossible problem.

That's what I thought as well while looking at the file.

I am curious why this just started happening with the one of the previous versions. It was still working fine in April (I don't know which version it was since Kali/Debian is usually a bit behind - this time they updated extremely fast).

[notifi...@include-what-you-use.org]

Comment #2 on issue 981 by kimgr: Qt mapping file causes major slowdown
https://github.com/include-what-you-use/include-what-you-use/issues/981

You could try patching the iwyu-mapgen-qt.py script to generate only <> mappings. I think that should generate a better mapping table, but I'm not sure.

[notifi...@include-what-you-use.org]

Comment #4 on issue 981 by kimgr: Qt mapping file causes major slowdown
https://github.com/include-what-you-use/include-what-you-use/issues/981

> I am curious why this just started happening with the one of the previous versions. It was still working fine
> in April (I don't know which version it was since Kali/Debian is usually a bit behind - this time they updated
> extremely fast).

Oh, I just remembered this change: https://github.com/include-what-you-use/include-what-you-use/commit/a5d8408c5f2cd8579d6cb12fddc7a9727ea83f21

I wonder if std::regex is significantly slower than llvm::Regex.

[notifi...@include-what-you-use.org]

Comment #5 on issue 981 by firewave: Qt mapping file causes major slowdown
https://github.com/include-what-you-use/include-what-you-use/issues/981

> Oh, I just remembered this change: [a5d8408](https://github.com/include-what-you-use/include-what-you-use/commit/a5d8408c5f2cd8579d6cb12fddc7a9727ea83f21)

👍

> I wonder if std::regex is significantly slower than llvm::Regex.

> Oh, I just remembered this change: [a5d8408](https://github.com/include-what-you-use/include-what-you-use/commit/a5d8408c5f2cd8579d6cb12fddc7a9727ea83f21)

>
> I wonder if std::regex is significantly slower than llvm::Regex.

I was told by a former colleague that early `std::regex` implementations were so slow that they are actually unusable and you should use `boost::regex` instead (which we did). I never got around to doing any comparison tests between those two and different compiler versions so I can't tell for sure. Giving this regression it seems quite possible it is still the case for recent versions.

[notifi...@include-what-you-use.org]

Comment #6 on issue 981 by kimgr: Qt mapping file causes major slowdown
https://github.com/include-what-you-use/include-what-you-use/issues/981

Yep, that's it. Reverting a5d8408c5f2cd8579d6cb12fddc7a9727ea83f21 takes analysis of a file including `<string>` from 22s to 0.4s on my machine. Sigh.

The reason I switched to `std::regex` was to get support for negative lookaround for #935. That's quite a nice feature for tricky mappings that don't generate huge mapping tables, so I'm reluctant to revert it.

Maybe we should just patch the Qt mappings to repeat `""` and `<>` headers instead of using regexes.

[notifi...@include-what-you-use.org]

Comment #7 on issue 981 by firewave: Qt mapping file causes major slowdown
https://github.com/include-what-you-use/include-what-you-use/issues/981

Maybe you could default to `llvm::Regex` and put the `std::regex` usage behind a `--extended-regex` or `--use-std-regex` switch. The support was just added in the last version and it seems only necessary for custom but not "official" (as in provided by this repo) mappings so this shouldn't break too much existing setups yet.