【Rust日报】 2019-03-20

「通告」Rust日报征集投稿

3.21开始预计一周，Rust日报将由Mike和Damody帮忙打理。大家也可以通过Rust日报的GitHub仓库提交issues来投稿每日新闻。来尝试像我一样对你当天看过或学过的资料进行一次总结，也许你会有不一样的感觉？

一周后恢复正常更新。

RustStudy/rust_daily_news

使用Rust实现NES模拟器

#NES #Emulator

文章中作者探讨了如何使用Rust开发一个模拟器。主要涵盖以下问题：

模拟器支持哪些功能？可以玩什么游戏？
如何解决NES模拟器的问题？
Rust的类型系统和借用检查会给开发过程带来哪些干扰？有无性能问题？

作者在文章中分享了三个可以提高FPS的优化，每一个方法都可以提高10％的FPS：

避免使用除法（Division）指令，而用条件减法来代替（conditional subtraction）。
按元素迭代相比于按字节迭代更好。
作者想要尝试LRU缓存，但是通过将最常访问的组件当到第一位也可以达到优化搜索性能的目的。

该作者后续还会有更多关于Rust和NES模拟器开发的文章，包括使用强化学习训练一个代理来玩马里奥游戏，以及如何用Rust实现一个NES游戏等。可以关注。

为什么Hashbrown会进行双重查询

#hashbrown

Alex最近完成了对hashbrown的详细review，可能会成为Rust标注库中std::collections::HashMap的新的实现。Alex发现一个令他惊讶的事实，insert的实现，本质上等价于下面代码：

fn insert(&mut self, key: K, val: V) {
    let hash = self.hash(&key);
    if let Some(old_val) = self.get_mut(hash, &key) {
        *old_val = val;
    } else {
        self.really_insert(hash, key, val);
    }
}

这意味着这个API会在map进行两次查找。刚开始Alex认为这可能造成性能负担，但是经过一些仔细的讨论和审查，他得出hashbrown这个insert实现是合理的。这篇文章就是解释这个合理性。

当前标准库的HashMap实现是基于开放定址加线性探测法（具体也可以参考《Rust编程之道》第八章8.2.2小节HashMap实现原理中关于Robin Hood Hashing的讲解）来处理Hash冲突。但是在处理删除的的时候，使用的是回溯（backshifting），而hashbrown的解决方法在于使用了「墓碑（tombstones）」，顾名思义，就是为删除的元素留下一个空位，并且使用tombstones来标记「已删除」。

（hashbrown是对Google Swiss table算法的实现，该算法使用元表来指示存储桶是空的还是之前已被删除。它使用两位一位保持空/删除和六位七位来缓存哈希值，这样大多数时候它可以找到正确的桶而不查询主桶表。并且因为这个元表很小（每个元素一个字节），就可以使用一些SIMD指令来一次查询16个单元。）

而引入了Tombstones导致插入算法有了一个有趣的属性：能证明某个key不在表的位置（因为需要查找墓碑是不是被删除过），可能会距离实际插入的位置非常远。所以就有两种不同的插入实现策略：双简单循环和单复杂循环。hashbrown使用了双简单循环的方案，正如本文开头那个插入方法所示。而且hashbrown的主要思想是针对SIMD进行优化。「两个循环」经过SIMD优化之后只是「做了两个简单的SIMD操作」而已。

「嵌入式Rust」Oxidizeconf大会日程表

#oxidizeconf

Oxidizeconf大会是以嵌入式Rust开发为主题的大会，可以关注

barrel: 用Rust来编写SQL迁移文件

#database #migration

use barrel::{types, Migration, Pg};
use barrel::backend::Pg;

fn main() {
    let mut m = Migration::new();
    
    m.create_table("users", |t| {
        t.add_column("name", types::varchar(255));
        t.add_column("age", types::integer());
        t.add_column("owns_plushy_sharks", types::boolean());
    });
    
    println!("{}", m.make::<Pg>());
}

可与diesel（1.2.0+）集成使用。

barrel

日报订阅地址：

【Rust日报】 2019-03-20 | Ecency