JitMemStats diff:

-                   SSA |   36352868 |   1.97%
+                   SSA |   90515140 |   4.92%
            ValueNumber |  345182286 |  18.75%
-              LvaTable |   86994265 |   4.72%
+              LvaTable |   86994265 |   4.73%
             UnwindInfo |     197280 |   0.01%
                 hashBv |    5911128 |   0.32%
                 bitset |   26976168 |   1.47%
           FixedBitVect |       7028 |   0.00%
-               Generic |  141367200 |   7.68%
+               Generic |   43900160 |   2.38%
         IndirAssignMap |     139904 |   0.01%
          FieldSeqStore |    4820344 |   0.26%
                LoopOpt |      66360 |   0.00%
              LoopHoist |    1615000 |   0.09%
                Unknown |   18985445 |   1.03%
             RangeCheck |    9590968 |   0.52%
+              CopyProp |   42872960 |   2.33%

So SSA memory usage is more than double than previously recorded. And judging by the changes I have made most of this additional memory usage comes from dominance computation, that one uses JitHashTable as if it's the only data structure in the galaxy...

So SSA memory usage is more than double than previously recorded. And judging by the changes I have made most of this additional memory usage comes from dominance computation, that one uses JitHashTable as if it's the only data structure in the galaxy...

Do we have any hacks to use std:: structs for local experiments? I miss them so much.

Do we have any hacks to use std:: structs for local experiments? I miss them so much.

Interesting idea. I suppose that if you include the compiler's own std headers and define jitstd as std it might work... or get a zillion compilation errors.

The JIT is really in a bad spot with regards to data structures. jitstd is usable but incomplete and out of date - list has emplace (heh, I think I added that) but vector does not, allocator is an old style allocator that's kind of horrible etc. Improving jitstd isn't easy (I'm not even sure who had the courage to write all that to begin with). We also have non-jitstd containers like JitHashTable, JitExpandArray, ArrayStack, SmallHashTable - some better, some worse and none really good. Oh well.

But in the specific case of SSA dominance computation the data structure implementation is less of a problem, JitHashTable is reasonable. The problem is the choice of data structure - hashtables are used when faster and smaller data structures would do - vectors, plain arrays, maybe a hashbv here and there.

Working on it, preliminary results look pretty good.

One example of improvement in #14965. The dominator tree is currently something like map<bb*, map<bb*, bool>> - maps each block to its children in the dominator tree. map<bb*, bool> can be vector<bb*> because:

• Dominator tree walkers just don't need anything more sophisticated than that.
• The dominator tree is built by visiting each block exactly once and adding it to its immediate dominator's children "set". That excludes the possibility of adding the same block twice to a given set.

Changes in this PR looks good to me.

I think @BruceForstall knows the historical context of these jitstd structs decisions, maybe some of them are outdated and we can change them now.

cc @dotnet/jit-contrib

It looks like there's still some memory that's not properly accounted for. Both SSA and CopyProp use ArrayStack and that one doesn't use CompAllocator, it goes directly to Compiler and always allocates CMK_ArrayStack memory. I'll look into changing ArrayStack to use CompAllocator but that will be another PR.

Another bit of memory that belongs to SSA but ends up in the CMK_Generic bucket is the "PerSsaArray". That too is something I'll look at in a future PR.

We generally can't use STL (aka std::) in code that links with the PAL (including the JIT). Trying to do so leads to a zillion compilation errors on various platforms, related to utilcode. One of the biggest issues is that wchar_t is 32-bits on Linux and 16-bits on Windows, and that shows through with std::string/std::wstring. ToolBox\SOS\Strike actually does use it, with some number of hacks. I tried to use it for superpmi, but then gave up and added even more stuff in src\inc\clr_std (namely, string).

Historically, we also had issues with compiling using toolsets that didn't support STL. And issues with the STL exception handling mode, too, I think.