René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Use double caching for re._compile()","articleBody":"The caching algorithm for `re._compile()` is one of the hottest sites in the stdlib. It was rewritten many times (it is not all changes):\r\n* https://github.com/python/cpython/issues/76519\r\n* https://github.com/python/cpython/issues/72480\r\n* https://github.com/python/cpython/issues/66700\r\n* https://github.com/python/cpython/issues/60593\r\n* https://github.com/python/cpython/issues/57436\r\n* https://github.com/python/cpython/commit/d9e8cc6249c7ff4ceeff3217a7671bee623d88a7\r\n* https://github.com/python/cpython/issues/53642\r\n* https://github.com/python/cpython/commit/5a63183a8b8a9e177f97feac975850df5e6f98aa\r\n\r\nThe patch for using `lru_cache()` was repeatedly applied and reverted 3 times! Eventually it turned out to be slower than a simple dict lookup. It does not fit very well in this case, because some results should be not cached, and additional checks should be added before calling the cached function, adding significant overhead.\r\n\r\nBut the LRU caching algorithm can have advantage over the current simple algorithm if not all compiler patterns fit in the cache. It removes entries from the cache more smarty.\r\n\r\nI tested with random keys with exponential distribution. With the cache size 512, the largest difference is for lambda between 1/70 and 1/80. The LRU caching algorithm has 3 times less misses: 0.16% to 0.33% against 0.5 to 1.1% misses in the current algorithm. For significantly larger (almost no misses) or smaller (tens percent of misses) lambda both algorithms gives almost the same result.\r\n\r\nDirect implementation of the LRU caching algorithm using OrderedDict or just dict would be slower, because every hit requires moving the found entry to the end. But we can use double caching. The primary smaller and faster cache does not reorder entries. But if the key is not found in the primary cache, we look it up in the secondary LRU cache. This algorithm has the same number of misses as the LRU caching algorithm, but it has faster hits.","author":{"url":"https://github.com/serhiy-storchaka","@type":"Person","name":"serhiy-storchaka"},"datePublished":"2022-08-27T20:14:29.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":3},"url":"https://github.com/96346/cpython/issues/96346"}