Two compile-time defects in the C (-gen gcc) backend (fbc 1.20.0)

[PaulSquires]

Bug 1 — ir-hlc.bas accumulates the emitted C in a STRING, making emission O(n²)

fb_StrConcatAssign() calls fb_hStrRealloc( dst, dst_len+src_len, TRUE ), and fb_hStrRealloc() (src/rtlib/str_core.c:97) over-allocates by only 12.5 %:
12.5 % headroom on a multi-megabyte block, on a heap already holding the whole symbol table and AST, means realloc() cannot extend in place and copies the buffer. The result is Θ(n²) bytes memcpy'd over the emission of an n-byte listing.
Instrumenting sectionWriteLine() on an 11.8 MB listing: 308,130 calls, 10.6 MB of text written, 19.6 s spent inside that one sub out of a 31.5 s run. The mean .text length at append time was 116 KB, so the appends alone moved ≈ 35 GB.

Bug 2 — fbc passes -Wall to gcc without -Wno-misleading-indentation, and that warning is quadratic on gcc < 10

On gcc 9.3 that warning is quadratic in the size of the translation unit — it resolves source lines through the front end's line cache, and on a large file the repeated non-monotonic lookups degrade badly.

Note: These problems exist on fbc compilers even before version 1.20.0

The changes/patches pass all FBC's unit tests.
I have personally experienced my large FB projects dropping from 40+ seconds to 3.5 seconds compile times.

Attachments:

REPORT.md - the actual bug report
0001-ir-hlc-section-buffer.patch - Bug 1 fix, -p1 against master
0002-gcc-wno-misleading-indentation.patch - Bug 2 fix, -p1 against master
gen.txt - gen.bas - self-contained reproducer generator, no includes (I had to change the name to gen.txt because github does not allow attaching .bas files)

(Full disclosure: I had my ai track down the source of this bug but that does not diminish the findings)

[countingpine]

Just some quick thoughts...

Firstly, these seem like separate issues.

Bug 1: I'm not sure what difference "only 12.5%" makes. It's still exponential growth (the same as if it were doing +100%), which I believe should still mean O(n log n).

If a reallocate is happening on every string append (even if it's within the 12.5% buffer), then that is probably best thought of as a bug in how the compiler/rtlib handles string appends in general.

Bug 2: I've not fact-checked what you've said, but it seems reasonable. The warning is perhaps "nice to have", and it's worth knowing if FBC is emitting badly indented code, but not ideal if it slows down compiles.

[PaulSquires]

Bug 1: I'm not sure what difference "only 12.5%" makes. It's still exponential growth (the same as if it were doing +100%), which I believe should still mean O(n log n).
Agreed. The 12.5% is probably inconsequential to the overall issue itself.

If a reallocate is happening on every string append (even if it's within the 12.5% buffer), then that is probably best thought of as a bug in how the compiler/rtlib handles string appends in general.
I don't think this is the case. There is not a reallocate "on every string append", but when the buffer does fill and an append is triggered, then a huge amount of data needs to moved in memory.

Bug 2: I've not fact-checked what you've said, but it seems reasonable. The warning is perhaps "nice to have", and it's worth knowing if FBC is emitting badly indented code, but not ideal if it slows down compiles.
Agreed. It is a simple fix, one that seems confirmed via results from old Google searches on the subject. We lose nothing by implementing it.

[countingpine]

I'm not sure how much of the report or the code is written by AI here..

But if (as stated in the report/patch) there are O(n^2) bytes being copied around, then that suggests a reallocate is happening on every string append. That would be a more fundamental problem.

If the problem really is that it's only adding 12.5%, then if you are able to modify the compiler's own rtlib to add 100% instead of 12.5%, you should see similar performance gains.

Have you checked to see how much each patch contributes to your overall compile times?
(fbc -r will prevent it calling GCC, allowing you to more easily time the impact of the first issue by itself.)

We wouldn't lose "nothing" by fixing issue 2 - we would lose the ability to catch if FBC is emitting badly indented code, which could hint at a significant problem internally. That doesn't mean it's not generally a good tradeoff.
I've not worked much with the GCC side of things. I don't know if FBC is capable of detecting the GCC version.
I guess if it is, then it would be worth keeping on GCC >= 10.

Hopefully Jeff will weigh in here as well. (I'm not really very active here, I just check out notifications when they come into my Github inbox.)

[PaulSquires]

Yes, the stats in bug 1 are as reported by the ai. I did not instrument and measure those values myself.

The patch dramatically fixes my compile times. I have a very large unity build that normally took 45 seconds on -gen gcc. It became about 4.5 seconds with gas64, and with this patch applied, gcc is also about 5 seconds. This slow gcc compiling on large source code bases has been discussed several times on the FB forums, with an allusion that it was related to the large strings being generated by the c output.

[countingpine]

It's not clear yet if the compile times are improved predominantly by the first fix or the second, or if it's about even.

Did AI implement the code fix, or did you do that? Is the O(n^2) assertion in the comment coming from AI?

Are you able to check if increasing the string overhead from +12.5% to +100% causes similar speedups to the ir-hlc changes?