| Issue |
54199
|
| Summary |
Adding Objective-C methods to the global pool requires O(n) traversal of a linked list
|
| Labels |
|
| Assignees |
|
| Reporter |
saagarjha
|
For a large project of ours, some clang processes spend a significant amount of time (sometimes up to 90%!) adding methods to the global list. From profiling, the issue appears to be in this code: https://github.com/llvm/llvm-project/blob/6467d1d275160292a5bcdbc57594261e63da54d3/clang/lib/Sema/SemaDeclObjC.cpp#L3324
As methods are added to the global pool, this method is called repeatedly, and on each invocation it traverses a singly-linked list pretty much for the sole purpose of finding the last element. Once it does so, the new method gets appended at the end, making these repeated additions O(n^2).
It would be nice if something smarter can be done here. I tried a simple "path compression" trick where I stored the tail of the list in the head and this seemed to help, but (looking at most of the uses of `ObjCMethodList `) it seems like most of them would benefit from a vector representation rather than a linked list, making this operation and other common cases far more efficient. As far as I can tell there isn't really any reason for this to be a linked list at all besides a couple seemingly uncommon cases where insertion is used (there's even a comment saying this is extremely rare!) so I think this could be a pretty nice performance win.
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
