• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>2011 ACM international conference on object oriented programming, systems, languages and applications >Flow-Sensitive Type Recovery in Linear-Log Time
【24h】

Flow-Sensitive Type Recovery in Linear-Log Time

机译：线性对数时间的流量敏感型恢复

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The flexibility of dynamically typed languages such as JavaScript, Python, Ruby, and Scheme comes at the cost of run-time type checks. Some of these checks can be eliminated via control-flow analysis. However, traditional control-flow analysis (CFA) is not ideal for this task as it ignores flow-sensitive information that can be gained from dynamic type predicates, such as JavaScript's instance of and Scheme's pair?, and from type-restricted operators, such as Scheme's car. Yet, adding flow-sensitivity to a traditional CFA worsens the already significant compile-time cost of traditional CFA. This makes it unsuitable for use in just-in-time compilers. In response, we have developed a fast, flow-sensitive type-recovery algorithm based on the linear-time, flow-insensitive sub-0CFA. The algorithm has been implemented as an experimental optimization for the commercial Chez Scheme compiler, where it has proven to be effective, justifying the elimination of about 60% of run-time type checks in a large set of benchmarks. The algorithm processes on average over 100,000 lines of code per second and scales well asymptotically, running in only O(n log n) time. We achieve this compile-time performance and scalability through a novel combination of data structures and algorithms.
机译：动态类型语言（如JavaScript，Python，Ruby和Scheme）的灵活性是以运行时类型检查为代价的。这些检查中的一些可以通过控制流分析消除。但是，传统的控制流分析（CFA）对于此任务而言并不理想，因为它忽略了可从动态类型谓词（例如JavaScript的Scheme和Scheme的pair？以及类型受限的运算符，例如作为Scheme的车。但是，向传统CFA添加流量敏感度会使传统CFA本身已经相当可观的编译时成本恶化。这使其不适用于即时编译器。作为响应，我们开发了一种基于线性时间，对流量不敏感的sub-0CFA的快速，对流量敏感的类型恢复算法。该算法已实现为商业Chez Scheme编译器的实验性优化，在实践中已证明是有效的，证明在大量基准测试中消除了约60％的运行时类型检查。该算法平均每秒处理超过100,000行代码，并且渐近扩展，并且仅在O（n log n）时间内运行。我们通过数据结构和算法的新颖结合来实现这种编译时性能和可伸缩性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号