主要观点:今晚用 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
遍历整个输入文件。 - 本地数据用自实现哈希表存储以节省时间。
- 使用
#%declare
和filtered-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
存在契约检查和复制字节的开销问题,希望有更高效的共享不可变字节支持。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。