Created attachment 143957 [details] C test case The attached test program repeatedly mmaps/munmaps a 2GB chunk of memory. Without `--track-origins=yes`, it runs in about 0.7 seconds. But with origin tracking enabled, it takes 95.5 seconds, that is, it runs 137 times slower. The problem occurs because the 2GB mmaps/munmaps cause Memcheck to perform a set-address-range-perms operation on the area, changing it to "defined" and then back to "noaccess". Large-range SARPs are (highly) optimised for the V/A-bit (normal) Memcheck shadow memory, but they are very inefficient for the origin-tracking shadow area. Origin-tracking shadows are kept in a 64MB 2-way set associative cache, which is pretty fast. But lines ejected from that are kept in a OSet (AVL-tree) based backing store. Because these SARP lengths greatly exceed the size of the cache, a huge AVL tree is created, which is very time- and space-inefficient. This was initially noticed in https://bugzilla.mozilla.org/show_bug.cgi?id=1742851.
Created attachment 144170 [details] Proposed patch (needs commit message) Attached is a proposed fix. It makes gigabyte-sized SARPs about 3 x faster, when --track-origins=yes. Note, from comment 0: > a huge AVL tree is created This was speculation and is totally wrong. The slowdowns were for other reasons.
Fixed, 8ee1656165902125c414d598cff788c7bb0b1556.