ChuanqiXu9 wrote: > I got to the bottom of it. The problem is that our hash function for 64 bit > ints is [not very > good](https://github.com/llvm/llvm-project/blob/d5297b72aa32ad3a69563a1fcc61294282f0b379/llvm/include/llvm/ADT/DenseMapInfo.h#L140). > > It will have a lot of collision when lower 32 bits are the same and the > higher 32 bits of a 64 bit value change. Coincidentally, this is quite common > in this case because collisions in low bits of `GlobalDeclID` are very much > expected. > > I tried replacing it with a variant of MurmurHash I found randomly on the > internet and performance went back to normal. @ChuanqiXu9 I think changing > the default hash function for ints might have some far-reaching effects for > LLVM code using `DenseSet` and would warrant a bigger discussion on what that > function should be (I am not an expert in hash functions myself). I will be > happy to start that discussion on Monday, but feel free to jump into it > earlier, if you have time. > > In the meantime, I would again propose to revert the change until we can fix > the hash function. (Alternatively, we can change the hash function for > `GlobalDeclID` specifically to workaround more locally, but we surely want a > better hash function for uint64 in general)
Thanks for the analysis. It's pretty helpful. For reverting, on the one hand, we've already targeted the root issue. I think then it is not so rationale to me to block the patch to problems in that level. On the other hand, (I think) the patch (series) is pretty important for named modules (and probably clang explicit modules). And I really want to make that in 19. Given 19 is going to be branched in the end of the next month. From my experience, it is not very hopeful to land such a fundamental change quickly. So I propose to change the hash function in Serialization locally as a workaround and propose a discussion about replacing the hash function in discussion parallelly. https://github.com/llvm/llvm-project/pull/92083 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
