<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/54199>54199</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Adding Objective-C methods to the global pool requires O(n) traversal of a linked list
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          saagarjha
      </td>
    </tr>
</table>

<pre>
    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.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyVVctu4zgQ_Br5QsSQ9bDjgw7eZAIMMIsc9gtaYstmQpEaknLWf7_VtJ2ZLLCHBYxIIrub1VXVTO_1pXvxQZGyFI6s5uDfeEjKj8ovIRbVk4p-YjVYckfZHThGjirO7DSyojk6M5qBXFI0-cXl1GSQUlSPkirvUS2zSl7ty6Jqi2pTVHtFWhuURMDJ6yi76cTqaH1PVlkT01q9BD_JmaOxCBUsEmJiXFjRPDOFnNdjzWHLRDV4zUV9UKeU5oiXonrB72jSaenXg5_wYe35_ni4dYvPHufisW22O73R1a7dbMtqX1HbD7of2l27b6rthre1prbRNUIzI1LISOJfPNHt8cyDfe3fntbDPBdV_aOuq6Yon4vycP17iJ9NU2DhgfW_2p-9t9d2zT1YSXdkLWIDo_XE2l4khqCDd4ppOIGGsx8oGXybpFKgMwdRS3RyR3t5AI_vqCD0glhO6aKmBYkjLCDnR2_hgSXMPrIIORqXVZI9S0hiyxM7aPPqBpZDtBc3-Ls4jj_ugI-cYpbJSYOU8j4-JHSi91tZnHPvJ1tCwEf1CvO4ov1WwSnr38n7ntSHX6wW0Z0RCGM2KJhCvThRSBxAlJMA7R2rEwdeq-9gw_DVsdNsxZ3VTOkEx0wgIkYciyWJGt7VhyQhJyYfRBwAT2RstrYwIfRly0l50lmDrFVk0JPVPLGdpdN-STIJ1vvcMWiYfEz3Souog_diW4pl_szM_ZDyWJEpAcNSM-LMd_49dfrkwfGIqFFmhdQZdoaWoBRNQairGQI6ZVEYvGDSf5ngixbA72cO15Rsq5wFhiYsDCRYRwpAAXJ4xNSbbIXDdZkiGBPmE1srEIPMKljdJeCBdS8oepHXiHJXx5n7AH9BJSwhHuvR6GzfwS8imlCRjawW9wXWVTDjIoer-6NQq4X5DAQgouIzu1xrEgurSJfPvvHjv1OAeKgdSBLyJRW9OAfeer_fLzfv0X18sgnBGvqZSGbiw7j1Sne13td7WiWTLHeH610HiSGPOfPD03_cezL4YOjnYiDfbQoA4zbJlB34harVEmz3v2-7fIXicn9pm81-vzp1dTmMVbvTDe22u7rsN2Vbb9pt2T7WuP-248pSzzZ2RftH0T6vTFeVVVXWZbNp6qbcr9uKH5uqbjfDZqvHoS-aEjehsWs5eO3DcRW6jKFfjhGbAj3-2qQo_0eY7_VpATmhi0RHCm8nWmXAXUb7D0joTa0">