{"id":38479,"date":"2019-10-31T22:23:56","date_gmt":"2019-10-31T19:23:56","guid":{"rendered":"https:\/\/prohoster.info\/blog\/put-k-proverke-tipov-4-millionov-strok-python-koda-chast-2\/"},"modified":"2019-10-31T22:23:56","modified_gmt":"2019-10-31T19:23:56","slug":"put-k-proverke-tipov-4-millionov-strok-python-koda-chast-2","status":"publish","type":"post","link":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/put-k-proverke-tipov-4-millionov-strok-python-koda-chast-2","title":{"rendered":"A Journey to Type Checking 4 Million Lines of Python Code. Part 2","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Today we are publishing the second part of the translation of the material on how Dropbox organized type checking for several million lines of Python code.<\/p>\n

\"A<\/a><\/noindex><\/p>\n

\u2192 Read the first part<\/a><\/noindex>
\n<\/a><\/noindex><\/p>\n

Official Support for Types (PEP 484)<\/h2>\n

\nWe conducted our first serious experiments with mypy at Dropbox during Hack Week 2014. Hack Week is an event held by Dropbox for a week when employees can work on anything they want! Some of Dropbox's most famous tech projects started during such events. As a result of this experiment, we concluded that mypy looks promising, although this project is still not ready for widespread use.<\/p>\n

At that time, there was a buzz about standardizing type hinting systems in Python. As I mentioned earlier, starting from Python 3.0, function type annotations could be used, but these were merely arbitrary expressions, lacking specific syntax and semantics. During program execution, these annotations were mostly just ignored. After Hack Week, we began working on standardizing the semantics. This work led to the emergence of PEP 484<\/a><\/noindex> (this document was collaboratively developed by Guido van Rossum, \u0141ukasz Langa, and me).<\/p>\n

Our motivations could be viewed from two perspectives. Firstly, we hoped that the entire Python ecosystem could adopt a common approach to using type hints. This, considering the possible risks, would be better than using multiple incompatible approaches. Secondly, we wanted to openly discuss the mechanisms of type annotation with many representatives of the Python community. Partly, this desire was driven by our reluctance to appear as \"renegades\" from the foundational ideas of the language in the eyes of the wider Python programming community. Python is a dynamically typed language known for its \"duck typing\". Initially, there was some skepticism in the community regarding the idea of static typing. However, this attitude eventually softened \u2014 once it became clear that static typing was not going to be made mandatory (and after people understood how genuinely useful it could be).<\/p>\n

The resulting syntax adopted for the types was very similar to what mypy supported at that time. PEP 484 was released alongside Python 3.5 in 2015. Python was no longer just a dynamically typed language. I like to think of this event as a significant milestone in Python's history.<\/p>\n

Beginning of the migration<\/h2>\n

\nAt the end of 2015, a team of three was formed at Dropbox to work on mypy. This included Guido van Rossum, Greg Price, and David Fisher. From that point on, things began to progress very quickly. The first obstacle to the growth of mypy was performance. As I hinted above, during the early stages of the project I considered translating mypy's implementation into C, but that idea was put on hold for now. We were stuck using the CPython interpreter, which lacks the speed necessary for tools like mypy. (The PyPy project, an alternative implementation of Python with a JIT compiler, didn't help us either.)<\/p>\n

Fortunately, some algorithmic improvements came to our aid. The first powerful \"accelerator\" was the implementation of incremental checking. The idea behind this enhancement was simple: if all dependencies of a module had not changed since the last run of mypy, we could use the data cached during the previous session while working with dependencies. We only needed to perform type checking in modified files and in those files that depended on them. Mypy went even further: if the external interface of a module did not change, mypy considered that other modules importing this module did not need to be checked again.<\/p>\n

Incremental checking was a big help for us when annotating large volumes of existing code. The thing is, this process usually involves numerous iterative runs of mypy as annotations are gradually added to the code and improved over time. The first run of mypy was still very slow, as it required checking a lot of dependencies. To improve the situation, we implemented a remote caching mechanism. If mypy detects that the local cache is likely outdated, it fetches the current snapshot of the cache for the entire codebase from a centralized repository. Then it performs incremental checking using this snapshot. This further advanced our efforts in increasing mypy's performance.<\/p>\n

This was a period of rapid and natural adoption of the type-checking system at Dropbox. By the end of 2016, we had approximately 420,000 lines of Python code with type annotations. Many users were enthusiastic about type checking. At Dropbox, mypy was increasingly used by different development teams.<\/p>\n

Everything looked good at that time, but there was still a lot to be done. We began conducting periodic internal surveys of users to identify pain points in the project and understand which issues needed to be addressed first (this practice is still employed in the company today). It became clear that two tasks were of utmost importance. First, we needed greater coverage of the code with types; second, we needed mypy to run faster. It was evident that our work on speeding up mypy and integrating it into the company's projects was far from complete. Fully aware of the importance of these two tasks, we set to work on resolving them.<\/p>\n

More performance!<\/h2>\n

\nIncremental checks sped up mypy, but the tool was still not fast enough. Many incremental checks took around a minute. The cause of this was cyclic imports. This probably won't surprise anyone who has worked with large codebases written in Python. We had sets of hundreds of modules, each of which indirectly imported all others. If any file in the import cycle was modified, mypy had to process all files involved in that cycle, and often also any modules importing from that cycle. One such cycle was the infamous 'dependency knot,' which caused a lot of trouble at Dropbox. At one point, this structure contained several hundred modules, with many tests directly or indirectly importing it, and it was also used in production code.<\/p>\n

We considered the possibility of 'unwinding' the cyclic dependencies, but we lacked the resources to do so. There was too much code we were unfamiliar with. Ultimately, we turned to an alternative approach. We decided to make mypy work quickly even with 'dependency knots.' We achieved this goal with the mypy daemon. The daemon is a server process that implements two interesting features. First, it keeps information about the entire codebase in memory. This means that on each run, mypy does not need to load cached data related to thousands of imported dependencies. Second, it carefully analyzes dependencies between functions and other entities at a granular level. For instance, if a function foo<\/code> calls function bar<\/code>, there is a dependency foo<\/code> from bar<\/code>. When a file changes, the daemon first processes only the modified file in isolation. Then it examines the changes in that file that are visible externally, such as modified function signatures. The daemon uses detailed import information only to recheck those functions that truly use the modified function. Usually, with this approach, only a few functions need to be checked.<\/p>\n

Implementing all of this was not an easy task, as the original implementation of mypy was heavily focused on processing one file at a time. We had to deal with numerous edge cases that required re-checks whenever something was modified in the code. For example, this occurs when a class is assigned a new base class. After we accomplished what we set out to do, we managed to reduce the execution time of most incremental checks to just a few seconds. We considered this a significant victory.<\/p>\n

Even more performance!<\/h2>\n

\nAlong with the remote caching I mentioned above, the mypy daemon almost completely resolved the issues that arise when a programmer frequently runs type checks after making changes in a small number of files. However, the performance of the system in the least favorable usage scenario was still far from optimal. A clean mypy run could take over 15 minutes. This was far more than we could accept. Each week, the situation worsened as programmers continued to write new code and add annotations to existing code. Our users were still craving more performance, and we were more than happy to meet their demands.<\/p>\n

We decided to revisit one of the early ideas regarding mypy. Specifically, the idea of converting Python code into C code. Experiments with Cython (a system that allows translating code written in Python into C) did not yield any noticeable speedup, so we decided to revive the idea of writing our own compiler. Since the mypy codebase (written in Python) already contained all the necessary type annotations, it seemed worthwhile to try using these annotations to speed up the system. I quickly created a prototype to test this idea. It showed more than a tenfold performance increase across various micro-benchmarks. Our idea was to compile Python modules into C modules using Cython, and to turn type annotations into type checks performed at runtime (typically, type annotations are ignored during program execution and are only used by type checking systems). Essentially, we planned to translate the mypy implementation from Python to a statically typed language that would look (and, for the most part, function) exactly like Python. (This kind of inter-language migration has become something of a tradition for the mypy project. The initial implementation of mypy was written in Alore, then there was a syntactical hybrid of Java and Python).<\/p>\n

Focusing on the CPython extension API was key to not losing project management capabilities. We did not need to implement a virtual machine or any libraries that mypy required. Furthermore, we would still have access to the entire Python ecosystem, with all tools available (such as pytest). This meant we could continue using interpreted Python code during development, allowing us to work with a very fast edit-and-test cycle instead of waiting for code compilation. It felt like we were successfully managing to, so to speak, sit on two chairs, and we enjoyed it.<\/p>\n

The compiler we named mypyc (since it uses mypy for type analysis as its frontend) turned out to be a quite successful project. Overall, we achieved approximately a fourfold acceleration of frequent mypy runs without using caching. The development of the core mypyc project took our small team, which included Michael Sullivan, Ivan Levkyvskyi, Hugh Han, and myself, about four calendar months. This amount of work was much less extensive than what would have been required to rewrite mypy, for example, in C++ or Go. Additionally, we had to make far fewer changes to the project than would have been necessary for a rewrite in another language. Furthermore, we hoped to bring mypyc to a level where other programmers from Dropbox could use it to compile and accelerate their code.<\/p>\n

To achieve such a level of performance, we had to implement some interesting engineering solutions. The compiler can accelerate the execution of many operations by using fast low-level C constructs. For example, a call to a compiled function is translated into a call to a C function. Such a call is executed much faster than a call to an interpreted function. Some operations, such as dictionary lookups, still relied on standard C API calls from CPython, which turned out to be only marginally faster after compilation. We were able to eliminate the extra load on the system that comes from interpretation, but this resulted in only a minor performance gain in this case.<\/p>\n

To identify the most common 'slow' operations, we profiled the code. Armed with the obtained data, we attempted either to adjust mypyc to generate faster C code for such operations or to rewrite the corresponding Python code using faster operations (and sometimes we simply did not have a straightforward solution for each problem). Rewriting the Python code often proved to be an easier solution than implementing automated execution of the same transformation in the compiler. In the long term, we wanted to automate many of these transformations, but at that moment we were focused on speeding up mypy with minimal effort. In pursuit of this goal, we cut a few corners.<\/p>\n

To be continued\u2026<\/p>\n

Dear readers!<\/b> What were your impressions of the mypy project when you first learned about its existence?<\/p>\n

\"A<\/a><\/noindex>
\n\"A<\/a><\/noindex>
\n
Source: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

\u0421\u0435\u0433\u043e\u0434\u043d\u044f \u043f\u0443\u0431\u043b\u0438\u043a\u0443\u0435\u043c \u0432\u0442\u043e\u0440\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430 \u043e \u0442\u043e\u043c, \u043a\u0430\u043a \u0432 Dropbox \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u043b\u0438 \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u044c \u0442\u0438\u043f\u043e\u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0441\u0442\u0440\u043e\u043a Python-\u043a\u043e\u0434\u0430. \u2192 \u0427\u0438\u0442\u0430\u0442\u044c \u043f\u0435\u0440\u0432\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u041e\u0444\u0438\u0446\u0438\u0430\u043b\u044c\u043d\u0430\u044f \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u043a\u0430 \u0442\u0438\u043f\u043e\u0432 (PEP 484) \u041c\u044b \u043f\u0440\u043e\u0432\u0435\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0435 \u0441\u0435\u0440\u044c\u0451\u0437\u043d\u044b\u0435 \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u044b \u0441 mypy \u0432 Dropbox \u0432\u043e \u0432\u0440\u0435\u043c\u044f Hack Week 2014. Hack Week \u2014 \u044d\u0442\u043e \u043c\u0435\u0440\u043e\u043f\u0440\u0438\u044f\u0442\u0438\u0435, \u043f\u0440\u043e\u0432\u043e\u0434\u0438\u043c\u043e\u0435 Dropbox \u0432 \u0442\u0435\u0447\u0435\u043d\u0438\u0435 \u043e\u0434\u043d\u043e\u0439 \u043d\u0435\u0434\u0435\u043b\u0438. \u0412 \u044d\u0442\u043e \u0432\u0440\u0435\u043c\u044f […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":28879,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-38479","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47The path to type-checking 4 million lines of Python code. Part 2 | ProHoster","description":"Today we are publishing the second part of the translation of the material on how Dropbox organized type checking for several million lines of Python code.","canonical_url":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/put-k-proverke-tipov-4-millionov-strok-python-koda-chast-2","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041f\u0443\u0442\u044c \u043a \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0435 \u0442\u0438\u043f\u043e\u0432 4 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0441\u0442\u0440\u043e\u043a Python-\u043a\u043e\u0434\u0430. \u0427\u0430\u0441\u0442\u044c 2 | ProHoster","og:description":"\u0421\u0435\u0433\u043e\u0434\u043d\u044f \u043f\u0443\u0431\u043b\u0438\u043a\u0443\u0435\u043c \u0432\u0442\u043e\u0440\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430 \u043e \u0442\u043e\u043c, \u043a\u0430\u043a \u0432 Dropbox \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u043b\u0438 \u043a\u043e\u043d\u0442\u0440\u043e\u043b\u044c \u0442\u0438\u043f\u043e\u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u0441\u0442\u0440\u043e\u043a Python-\u043a\u043e\u0434\u0430.","og:url":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/put-k-proverke-tipov-4-millionov-strok-python-koda-chast-2","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:23:56+00:00","article:modified_time":"2019-10-31T19:23:56+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"38479","title":null,"description":null,"keywords":null,"keyphrases":{"focus":[],"additional":[]},"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-23 22:13:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 01:08:32","updated":"2026-08-11 12:50:31","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/38479","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/comments?post=38479"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/38479\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/media\/28879"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/media?parent=38479"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/categories?post=38479"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/tags?post=38479"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}