It might be a good idea to have a log message in case some users get a slowdown.
However, with all the other changes it might be hard to track it down to that for a non-expert. At least your benchmark shows that, with the current Env code, the cache is detrimental when there is a large number of functor applications.

Removes a cache around Env.prefix_idents that has been made obsolete by #834 .

The cached function is indeed no longer used to implement open. This does not automatically imply that the cache is useless, for the other use of the function. Are you confident that there can be no cache hit (or that there isn't any in practice)?

Empirical observation shows that there are some cache hits. I'm not opposed to the change, but to gain confidence, it could be interesting to try building an ad hoc counterexample with many cache hits, to see a "worst case" slowdown if we remove the cache. Depending on the outcome, one could decide to use a better implementation for the cache. Btw, do you believe the slowdown in your case with the cache comes from the linear scan (List.assq), or from the fact that the cache keeps more data alive?

Empirical observation shows that there are some cache hits.

Indeed, roughly 1% of the calls are cache hits.
See numbers below.

Btw, do you believe the slowdown in your case with the cache comes from the linear scan (List.assq), or from the fact that the cache keeps more data alive?

The linear scan is of course not great, but it doesn't seem to be a problem often.
One thing that I wasn't able to estimate is how many collisions there are in the hashtbl itself, because that can also degrade to a linear search.

I applied this patch to the compiler:

diff --git a/typing/env.ml b/typing/env.ml
index f49a84780..d7835c3b2 100644
--- a/typing/env.ml
+++ b/typing/env.ml
@@ -1602,13 +1602,18 @@ let prefix_idents root sub sg =
         Hashtbl.add prefixed_sg root sgs;
         sgs
     in
+    let len = List.length !sgs in
     try
-      List.assq sg !sgs
+      let r = List.assq sg !sgs in
+      Printf.eprintf "CACHE HIT %d\n%!" len;
+      r
     with Not_found ->
+      Printf.eprintf "CACHE MISS %d\n%!" len;
       let r = prefix_idents root 0 sub sg in
       sgs := (sg, r) :: !sgs;
       r
   else
+    let () = Printf.eprintf "CACHE MISS (not identity)\n%!" in
     prefix_idents root 0 sub sg

Which when building the compiler itself (make world.opt) gives me the following numbers:

    125 CACHE HIT 1
      3 CACHE HIT 2
   8486 CACHE MISS 0
    120 CACHE MISS 1
     11 CACHE MISS 2
      2 CACHE MISS 3
      1 CACHE MISS 4
      1 CACHE MISS 5
      1 CACHE MISS 6
   4271 CACHE MISS (not identity)

And when building the same part of janestreet's codebase as before gives me:

2207394 CACHE MISS (not identity)

  32226 CACHE HIT 1
    621 CACHE HIT 2
    593 CACHE HIT 3
    228 CACHE HIT 4
    106 CACHE HIT 5
     24 CACHE HIT 6
      8 CACHE HIT 7
     46 CACHE HIT 8
     16 CACHE HIT 9
    305 CACHE HIT 10
      3 CACHE HIT 11
      1 CACHE HIT 12
      2 CACHE HIT 13
      2 CACHE HIT 14
      3 CACHE HIT 15
      1 CACHE HIT 17
     38 CACHE HIT 19

1344248 CACHE MISS 0
  25449 CACHE MISS 1
   6497 CACHE MISS 2
   3415 CACHE MISS 3
   2253 CACHE MISS 4
   1566 CACHE MISS 5
   1124 CACHE MISS 6
    879 CACHE MISS 7
    669 CACHE MISS 8
    564 CACHE MISS 9
    486 CACHE MISS 10
    433 CACHE MISS 11
    344 CACHE MISS 12
    296 CACHE MISS 13
    252 CACHE MISS 14
    212 CACHE MISS 15
    188 CACHE MISS 16
    171 CACHE MISS 17
    158 CACHE MISS 18
    146 CACHE MISS 19
    143 CACHE MISS 20
    133 CACHE MISS 21
    122 CACHE MISS 22
    106 CACHE MISS 23
     96 CACHE MISS 24
     89 CACHE MISS 25
     82 CACHE MISS 26
     76 CACHE MISS 27
     74 CACHE MISS 28
     68 CACHE MISS 29
     60 CACHE MISS 30
     54 CACHE MISS 31
     52 CACHE MISS 32
     51 CACHE MISS 33
     46 CACHE MISS 34
     44 CACHE MISS 35
     39 CACHE MISS 36
     39 CACHE MISS 37
     38 CACHE MISS 38
     38 CACHE MISS 39
     38 CACHE MISS 40
     36 CACHE MISS 41
     36 CACHE MISS 42
     34 CACHE MISS 43
     32 CACHE MISS 44
     32 CACHE MISS 45
     31 CACHE MISS 46
     29 CACHE MISS 47
     29 CACHE MISS 48
     29 CACHE MISS 49
     29 CACHE MISS 50
     29 CACHE MISS 51
     27 CACHE MISS 52
     27 CACHE MISS 53
     26 CACHE MISS 54
     25 CACHE MISS 55
     23 CACHE MISS 56
     23 CACHE MISS 57
     22 CACHE MISS 58
     22 CACHE MISS 59
     20 CACHE MISS 60
     20 CACHE MISS 61
     20 CACHE MISS 62
     20 CACHE MISS 63
     20 CACHE MISS 64
     18 CACHE MISS 65
     18 CACHE MISS 66
     16 CACHE MISS 67
     16 CACHE MISS 68
     16 CACHE MISS 69
     14 CACHE MISS 70
     14 CACHE MISS 71
     14 CACHE MISS 72
     14 CACHE MISS 73
     14 CACHE MISS 74
     14 CACHE MISS 75
     14 CACHE MISS 76
     14 CACHE MISS 77
     13 CACHE MISS 78
     13 CACHE MISS 79
     13 CACHE MISS 80
     13 CACHE MISS 81
     12 CACHE MISS 82
     12 CACHE MISS 83
     12 CACHE MISS 84
     12 CACHE MISS 85
     10 CACHE MISS 86
     10 CACHE MISS 87
     10 CACHE MISS 88
      8 CACHE MISS 89
      8 CACHE MISS 90
      8 CACHE MISS 91
      8 CACHE MISS 92
      8 CACHE MISS 93
      8 CACHE MISS 94
      8 CACHE MISS 95
      8 CACHE MISS 96
      8 CACHE MISS 97
      8 CACHE MISS 98
      8 CACHE MISS 99
      8 CACHE MISS 100
      8 CACHE MISS 101
      8 CACHE MISS 102
      8 CACHE MISS 103
      8 CACHE MISS 104
      6 CACHE MISS 105
      6 CACHE MISS 106
      6 CACHE MISS 107
      5 CACHE MISS 108
      5 CACHE MISS 109
      5 CACHE MISS 110
      5 CACHE MISS 111
      5 CACHE MISS 112
      5 CACHE MISS 113
      5 CACHE MISS 114
      5 CACHE MISS 115
      4 CACHE MISS 116
      4 CACHE MISS 117
      4 CACHE MISS 118
      4 CACHE MISS 119
      4 CACHE MISS 120
      4 CACHE MISS 121
      4 CACHE MISS 122
      4 CACHE MISS 123
      4 CACHE MISS 124
      4 CACHE MISS 125
      4 CACHE MISS 126
      4 CACHE MISS 127
      4 CACHE MISS 128
      4 CACHE MISS 129
      4 CACHE MISS 130
      4 CACHE MISS 131
      4 CACHE MISS 132
      4 CACHE MISS 133
      4 CACHE MISS 134
      4 CACHE MISS 135
      4 CACHE MISS 136
      4 CACHE MISS 137
      4 CACHE MISS 138
      4 CACHE MISS 139
      4 CACHE MISS 140
      4 CACHE MISS 141
      4 CACHE MISS 142
      4 CACHE MISS 143
      4 CACHE MISS 144
      4 CACHE MISS 145
      4 CACHE MISS 146
      4 CACHE MISS 147
      4 CACHE MISS 148
      4 CACHE MISS 149
      4 CACHE MISS 150
      4 CACHE MISS 151
      4 CACHE MISS 152
      4 CACHE MISS 153
      4 CACHE MISS 154
      4 CACHE MISS 155
      4 CACHE MISS 156
      4 CACHE MISS 157
      4 CACHE MISS 158
      4 CACHE MISS 159
      4 CACHE MISS 160
      4 CACHE MISS 161
      4 CACHE MISS 162
      4 CACHE MISS 163
      4 CACHE MISS 164
      4 CACHE MISS 165
      4 CACHE MISS 166
      4 CACHE MISS 167
      4 CACHE MISS 168
      4 CACHE MISS 169
      4 CACHE MISS 170
      4 CACHE MISS 171
      4 CACHE MISS 172
      4 CACHE MISS 173
      4 CACHE MISS 174
      4 CACHE MISS 175
      4 CACHE MISS 176
      4 CACHE MISS 177
      4 CACHE MISS 178
      4 CACHE MISS 179
      4 CACHE MISS 180
      4 CACHE MISS 181
      3 CACHE MISS 182
      3 CACHE MISS 183
      3 CACHE MISS 184
      1 CACHE MISS 185
      1 CACHE MISS 186
      1 CACHE MISS 187
      1 CACHE MISS 188
      1 CACHE MISS 189
      1 CACHE MISS 190
      1 CACHE MISS 191
      1 CACHE MISS 192
      1 CACHE MISS 193
      1 CACHE MISS 194
      1 CACHE MISS 195
      1 CACHE MISS 196
      1 CACHE MISS 197
      1 CACHE MISS 198
      1 CACHE MISS 199
      1 CACHE MISS 200
      1 CACHE MISS 201
      1 CACHE MISS 202
      1 CACHE MISS 203
      1 CACHE MISS 204
      1 CACHE MISS 205
      1 CACHE MISS 206
      1 CACHE MISS 207

it could be interesting to try building an ad hoc counterexample with many cache hits, to see a "worst case" slowdown if we remove the cache.

I don't know... The reason why the cache was added doesn't exist anymore. We don't have any other example of code that would benefit from it in practice. Building some degenerate piece of code which will greatly benefit from the cache will only show that that piece of code greatly benefits from the cache.

What we currently have in this PR is evidence that the cache is

• at best useless on our usual benchmark suite, i.e. the compiler itself. There doesn't seem to be difference in the time needed for make world when removing the cache compared to when it's present (or rather: it's in the noise)
• detrimental on a fairly large code base (27k ml & mli files, roughly 5.2 million lines)

Both of which have the advantage of existing, and being somewhat representative of "typical" ocaml code.

Building some degenerate piece of code which will greatly benefit from the cache will only show that that piece of code greatly benefits from the cache.

Well, if the slowdown of removing the cache is not dramatic even for a specially crafted example, we can blindly remove the cache. If not, this can give an intuition on the affected code style; and it is worth waiting a bit for people to benchmark compilation time on their own code base. We'll do that on ours and share the results here.

@trefis: can you remove other occurrences of prefixed_sg hashtable?

It seems that the cached function is O(n log n) in the number of items in the signature.
(The log n factor coming from the creation of the balanced tree in substitution maps). It seems reasonable to assume that for most signatures, the log factor is negligible..

The only use of prefix_idents is components_of_module_maker, which already does computations proportional to the size of the signature (a List.iter2), so even in the best cases (cache hit, short linear scan), the impact of caching is negligible on the asymptotic complexity (a log n factor).

Did I miss something?

can you remove other occurrences of prefixed_sg hashtable?

Indeed, I had forgotten. I pushed a commit doing just that.

it is worth waiting a bit for people to benchmark compilation time on their own code base. We'll do that on ours and share the results here.

@alainfrisch: have you had an opportunity to run that benchmark yet? :)

(sorry to be pushy, I agree that this PR is not the most important, but that's also why I'm afraid it'd be forgotten if not pinged)

@alainfrisch: have you had an opportunity to run that benchmark yet? :)

We did one benchmark that showed a (small) slowdown when the cache was present (sorry I can't find the exact numbers at the moment), similar to what is described in the PR description.

Thanks @nojb !

I rebased on top of the latest trunk and added a changelog entry (currently only @let-def is marked as a reviewer, but I'd be happy to add more people, in particular the person who ends up clicking on the "Approve" button).

I think this benchmark is enough to convince us that at least for our code base, the impact of removing the cache is at worst neutral and probably slightly positive, so for us, this is good to go.

note that #2228 would have made this very-slightly nicer by factorizing the logic in the reset_* functions. Just sayin'.

😮
Note that I was afraid of conflicts with #2231, not with this one.

I'll add Gabriel to the reviewers and merge (since both CIs appear to be happy).

Thanks everyone!