Racket 中的十亿行挑战 —— defn.io

主要观点:今晚用 Racket 解决十亿行挑战并给出解决方案,在 2023 年 12 核 Apple M2 Max 机器上约 45 秒完成,与挑战仓库README中优化的 Java 解决方案低端水平相当;解决方案通过在多个place间分配工作,每个place遍历整个输入文件,避免主place读取整个文件并分发工作的高开销,以及主place直接发送单个工作单元到工作place的高开销;启动时每个place获得输入文件路径等信息,数据按 10MB 块读取,本地数据用自实现的开放寻址哈希表存储以避免复制位置名的开销;代码还使用#%declare禁用一些契约检查和filtered-in重命名导入;对结果不完全满意,未来可能尝试让代码更快。
关键信息:

  • 解决方案在 2023 年 12 核 Apple M2 Max 机器上约 45 秒完成。
  • 通过多个place分配工作,每个place遍历整个输入文件。
  • 本地数据用自实现哈希表存储以节省时间。
  • 使用#%declarefiltered-in
    重要细节:
  • 最初主place读取整个文件到shared-bytes值再分发工作,有高开销。
  • place直接发送单个工作单元到工作place,被place-channel-put的开销杀死。
  • 每个place只处理匹配其分片编号的输入条目,减少每个place的工作量。
  • 数据按 10MB 块读取,缓冲区大小 1MB 及以上差异可忽略。
  • 最初用常规 Racket 哈希表存储本地数据,后改为自实现哈希表节省约 10 - 15 秒时间。
  • 每个place启动时获得输入文件路径等信息,最后合并各place数据。
  • 代码中使用#%declare禁用一些契约检查,filtered-in重命名导入。
  • 机器上为每个两个 CPU 核心创建一个place更高效,推测是减少place间同步开销。
  • 猜测主place直接发送字节到工作place存在契约检查和复制字节的开销问题,希望有更高效的共享不可变字节支持。
阅读 9
0 条评论