BLEEDING EDGE SOTA LINE INFO CACHE

Takes line info caching in lnfodwrf.pp to the next level of ascension (in terms of Lode Vandevenne’s Ethereal Farm game) at the cost of 3.3 KB of code (x64). (Could be trivially shared with other formats... well, I’m lazy—you’re welcome.)

As an illustration: I was interested in how the new heaptrc mechanics perform. In particular, I wasn’t completely sure if both stack trace compression and deduplication make sense. So I decided to study the output of heaptrc.Dump at the peak compiler memory usage when compiling itself. This dump (2.2 GB of text :D) was built in 54 minutes after countless rereadings of DWARF debug information (400 GB read; actual debug info is ~20 MB; i.e., 20,000×). With this MR, the same dump takes 4.5 minutes to build and reads 6.5 GB (325×; still a lot honestly, but we all understand the tradeoffs values like 1× would imply).

Trunk cache introduced in 4dfcdeae to solve #38675 (closed) has 2039 cells on 64-bit CPUs, but collisions force eviction of the collided address, and due to the birthday paradox you start getting them at ~50th address on average. My cache stores up to 8,000 addresses regardless of collisions and evicts them using the LRU strategy at either 8,000 addresses, 1,600 strings, or ~38,000 string characters, whichever gets exhausted first. By the way, all compiler allocation traces in that dump had only ~6,000 unique addresses, so such a workload doesn’t even reach the cache capacity. Despite this capacity, my cache uses 1/3.5 of the memory on 64-bit CPUs (290 KB, down from trunk 1050 KB; with a small change this can be scaled up and down arbitrarily—for instance, I used a tiny 8-string, 8-address variation for initial debugging).

This also supposedly (I didn’t test at all) makes lnfodwrf.pp thread-safe (simply by locking everything) because this new cache is a complex structure that would die a horrible death under any races.