Bug 24700 – MsCoffObj_getsegment is really slow O(n^2)

Code generation of an internal dub project at SARC takes way longer than necessary: objflush_pointerRefs is called on an .obj file with ~4600 000 pointer refs. This calls MsCoffObj_getsegment(".dp$B") for each of them, which does a linear scan over all sections: ``` for (segidx_t seg = 1; seg < SegData.length; seg++) { if (strcmp(...)) ... ``` https://github.com/dlang/dmd/blob/05b2c0dfe27f0797151e7c6f7c7db43f700c1edc/compiler/src/dmd/backend/mscoffobj.d#L1364 SegData.length is 61000 here. ElfObj_getsegment uses a hash table for this, MsCoff_getsegment should do this as well.

N.b. even a dumb patch like this would mostly fix it, since it's trying to get the same section over and over: ``` --- a/compiler/src/dmd/backend/mscoffobj.d +++ b/compiler/src/dmd/backend/mscoffobj.d @@ -1357,16 +1357,29 @@ int MsCoffObj_jmpTableSegment(Symbol *s) @trusted segidx_t MsCoffObj_getsegment(const(char)* sectname, uint flags) { + __gshared segidx_t lastFind = 1; //printf("getsegment(%s)\n", sectname); assert(strlen(sectname) <= 8); // so it won't go into string_table if (!(flags & IMAGE_SCN_LNK_COMDAT)) { + if (lastFind < SegData.length) + { + seg_data *pseg = SegData[lastFind]; + if (!(ScnhdrTab[pseg.SDshtidx].Characteristics & IMAGE_SCN_LNK_COMDAT) && + strncmp(cast(const(char)* )ScnhdrTab[pseg.SDshtidx].Name, sectname, 8) == 0) + { + //printf("\t%s\n", sectname); + return lastFind; // return existing segment + } + } + for (segidx_t seg = 1; seg < SegData.length; seg++) { seg_data *pseg = SegData[seg]; if (!(ScnhdrTab[pseg.SDshtidx].Characteristics & IMAGE_SCN_LNK_COMDAT) && strncmp(cast(const(char)* )ScnhdrTab[pseg.SDshtidx].Name, sectname, 8) == 0) { //printf("\t%s\n", sectname); + lastFind = seg; return seg; // return existing segment } } ```

Here's a test case to artificially produce similar Symbol / pointer ref counts: ``` static foreach (i; 0 .. 8_000) { mixin("struct S"~i.stringof~" {float x;}"); } __gshared int*[64_000] x; ``` Compile times goes from 35.5s => 2.4s after applying the patch I mentioned.

@dkorpel created dlang/dmd pull request #16780 "Bugzilla 24700 - Don't search for mscoff .dp$B section over and over" mentioning this issue: - Bugzilla 24700 - Don't search for mscoff .dp$B section over and over https://github.com/dlang/dmd/pull/16780

dlang/dmd pull request #16780 "Bugzilla 24700 - Don't search for mscoff .dp$B section over and over" was merged into master: - 23d0c3dbf140ab6eb3ffa82dfddba03ac19b4861 by Dennis Korpel: Bugzilla 24700 - Don't search for mscoff .dp$B section over and over https://github.com/dlang/dmd/pull/16780

@veelo created dlang/dmd pull request #17029 "Bugzilla 24700 - Don't search for mscoff .dp$B section over and over …" mentioning this issue: - Bugzilla 24700 - Don't search for mscoff .dp$B section over and over (#16780) (cherry picked from commit 67227f03e04368654d40ff707be7ee424b490e3b) https://github.com/dlang/dmd/pull/17029

dlang/dmd pull request #17029 "Bugzilla 24700 - Don't search for mscoff .dp$B section over and over …" was merged into stable: - 36b6061ce0c0fc1bd5497b1d83e30fb5215b2e2c by Dennis: Bugzilla 24700 - Don't search for mscoff .dp$B section over and over (#16780) (cherry picked from commit 67227f03e04368654d40ff707be7ee424b490e3b) https://github.com/dlang/dmd/pull/17029

@kinke created dlang/dmd pull request #17069 "Merge stable" mentioning this issue: - Bugzilla 24700 - Don't search for mscoff .dp$B section over and over (#16780) (cherry picked from commit 67227f03e04368654d40ff707be7ee424b490e3b) https://github.com/dlang/dmd/pull/17069

dlang/dmd pull request #17069 "Merge stable" was merged into master: - 2a63416b43cdf876e8818501f56a4ec441f053bf by Dennis: Bugzilla 24700 - Don't search for mscoff .dp$B section over and over (#16780) (cherry picked from commit 67227f03e04368654d40ff707be7ee424b490e3b) https://github.com/dlang/dmd/pull/17069

THIS ISSUE HAS BEEN MOVED TO GITHUB https://github.com/dlang/dmd/issues/20495 DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB