月度归档:2019年07月

Swift语言的随机数:运行效率和安全性(cryptographically good)

Apple推出Swift语言已经很多年了,如今,Swift语言已经进化到了5.1版本,很多细节也越来越完善了,不过,总的来说,Swift语言的overhead仍然较大,具体到随机数上,Swift内置的运行时生成随机数效率低,不适用于模拟,测试和游戏等对于cryptographically good要求不高的场景。

如果读者需要大量生成随机数的话,建议用arc4random或者arc4random_uniform,不要使用arc4random_buf或者Swift语言的random方法。对于测试,模拟和游戏等不需要cryptographically good/secure的情况,可以直接引入C语言类库的rand方法,运行效率更高。

Swift对于内置的Double, Int等类型提供了random方法,用以生成指定的开闭区间内的随机数。然而,经过实际测试,我发现,一方面,Swift语言本身的overhead很大,另一方面,Swift内置的SystemRandomNumberGenerator使用的是arc4random_buf,该方法比arc4random和arc4random_buf慢很多。所以,如果效率非常重要,那么,请不要使用Swift类库的随机数,应该在Swift中调用C/C++语言实现的随机数库。


       var i = 0;
        while(i<100000000){
 //1亿个随机数,每个随机数在闭区间[0,11]内取值,随机数独立同分布
            let _ = arc4random_uniform(11)
            i += 1;
        }
       var i = 0;
        while(i<100000000){
//1亿个随机数,每个随机数在闭区间[0,2^32-1]内取值,随机数独立同分布
            let _ = arc4random()
            i += 1;
        }
       var i = 0;
        while(i<100000000){
            var b:UInt32 = 0;
//1亿个随机数,每个随机数在闭区间[0,2^32-1]内取值
            arc4random_buf(&b, 4)
            i += 1;
        }
        var i = 0;
        while(i<100000000){
            var b:UInt32 = 0;
            b = UInt32.random(in: 0...10)
            i += 1;
        }

以下为一个特别简单的模n同余的Linear Congruent伪随机数生成器,实际测试发现,生成1亿个32位随机数的话,Debug模式下需要耗时29.31秒, Release模式下需要5.06秒。

struct LCG: RandomNumberGenerator {
    var seed:UInt64
    
    init() {
        self.seed = mach_absolute_time()
    }
    
    init(seed:UInt64) {
        self.seed = seed;
    }
    
    mutating func next() -> UInt64 {
        self.seed = 32479 &+ self.seed
        return self.seed
    }
    
}

var i = 0;
while(i<100000000){
    var b:UInt32 = 0;
    b = UInt32.random(in: 0...10, using: &lcg)
    i += 1;
}

经过实际测试,结果如下
1亿个随机数,

随机数生成方法 debug release
rand 11.21秒 0.52秒
arc4random 3.09秒 2.34秒
arc4random_uniform 3.41秒 2.67秒
arc4random_buf 19.69秒 18.79秒
UInt32.random 47.98秒 19.27秒
自定义LCG 29.31秒 5.06秒

UInt32.random实际上会使用Swift内置的SystemRandomNumberGenerator,实际上最终调用了arc4random_buf,然而,与直接调用arc4random_buf相比,UInt32.random在Debug模式下慢了近30秒,Release模式下则慢了16秒,因此,我们可以得出结论,即便是Release模式下,Swift的overhead还是很大的。因此,如果需要高效率生成很多随机数的话,不建议直接使用Swift的Double, Int的random方法。不过很特别的是,rand函数在Debug模式下竟然比arc4random慢很多,甚至和arc4random_buf差不多了,但是,在Release模式下,rand还是最快的,0.52秒就可以生成1亿个伪随机数。

接下来,我们来看看为什么arc4random_buf比arc4random和arc4random_uniform慢这么多。

经过查看苹果的具体实现 https://opensource.apple.com/source/Libc/Libc-1272.200.26/gen/FreeBSD/arc4random.c.auto.html

我们不难发现,arch4random方法的具体代码如下,其中CACHE_LENGTH的值为64

uint32_t
arc4random(void)
{
	int ret;
	os_unfair_lock_lock(&arc4_lock);
	arc4_init();
	if (arc4_count <= 0) {
	    arc4_stir();
	}
	if (cache_pos >= CACHE_LENGTH) {
		ret = ccdrbg_generate(&rng_info, rng_state, sizeof(rand_buffer), rand_buffer, 0, NULL);
		os_assert_zero(ret);
		cache_pos = 0;
	}
	uint32_t rand = rand_buffer[cache_pos];
	// Delete the current random number from buffer
	memset_s(rand_buffer+cache_pos, sizeof(rand_buffer[cache_pos]), 0, sizeof(rand_buffer[cache_pos]));
	arc4_count--;
	cache_pos++;
	os_unfair_lock_unlock(&arc4_lock);
	return rand;
}

而arc4random_uniform实际调用arc4random方法,并且通过多次循环避免modulo bias

/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by trying successive ranges of bits from the random
 * value, each large enough to hold the desired upper bound, until a range
 * holding a value less than the bound is found.
 */
uint32_t
arc4random_uniform(uint32_t upper_bound)
{
	if (upper_bound < 2)
		return 0;

	// find smallest 2**n -1 >= upper_bound
	int zeros = __builtin_clz(upper_bound);
	int bits = CHAR_BIT * sizeof(uint32_t) - zeros;
	uint32_t mask = 0xFFFFFFFFU >> zeros;

	do {
		uint32_t value = arc4random();

		// If low 2**n-1 bits satisfy the requested condition, return result
		uint32_t result = value & mask;
		if (result < upper_bound) {
			return result;
		}

		// otherwise consume remaining bits of randomness looking for a satisfactory result.
		int bits_left = zeros;
		while (bits_left >= bits) {
			value >>= bits;
			result = value & mask;
			if (result < upper_bound) {
				return result;
			}
			bits_left -= bits;
		}
	} while (1);
}

也就是说,arc4random和arc4random_uniform由于rand_buffer[64]的存在,每生成64个32位随机数,才需要调用一次ccdrbg_generate,而arc4random_buf每一次调用,都需要调用一次ccdrbg_generate。所以,如果读者需要大量生成随机数的话,建议用arc4random或者arc4random_uniform,不要使用arc4random_buf或者Swift语言的random方法。

对于测试,模拟和游戏等不需要cryptographically good/secure的情况,可以直接引入C语言类库的rand方法,运行效率更高。

说说退休父母投靠在京独生子女落户北京的流程

本人落户在北京朝阳区,前往户口所在派出所咨询了父母投靠的详细细节,于2018年12月底正式向派出所提交材料,2019年5月14日拿到准迁证。准迁证的签发日期是2019年5月9日。

提交材料后,其实没别的事,就是一个“等”字。但是,提交材料以前,花了大量时间理解政策,收集材料。

需要准备的材料中,首先要准备的是我的档案部分,到存档部门直接索要就可以了,现在回想起来,当初我还是犯了一些错误。1. 没有事先准备一个文字的清单,导致第一次去的时候没有拿到查档证明,这个查档证明的内容就是XXX为我处存档人员,根据XX档案,父母为XXX,无兄弟姐妹。我为此不得不第二次去人才办理查档证明,多跑了一次。2. 自己的档案管理不及时,等到要办事用到档案了,才发现档案中缺少高中的毕业生登记表,最后不得不抽空回了老家到了当年上学的高中翻了好多档案,才最终找到。据说当年应该是高考后,到大学时就应该转移的。

在准备材料的过程中,问题最大的就是我父母在广西,父亲退休的时候广西已经不再对企业退休人员发放退休证了,而北京的文件仍然要求退休证,当初我也是感到很麻烦,也到本版进行了咨询。这里要说明的是,在广西的国家干部和事业单位退休人员,还是有退休证的,但是企业职工,不管你是高管还是工人,通通不发退休证,只发待遇资格证了。

最后,我采用的解决办法如下
1 复印了我父亲的“享受养老保险待遇资格证”
2 通过广西省一级的政府信息公开,要到了盖章的红头文件,该文件表
明广西确实不对2008年以后退休的企业职工发放退休证了。

为了政府信息公开,我请人专门去南宁了一趟。之所以专门去南宁一趟,主要是之前我的父母和政府打交道的时候发现,大量政府人员认为“你们要这个文件有什么用,有资格证就行了”,当政府认为一个东西没有必要的时候,根本就不会给你办理,如果你不亲自出面,工作人员感受不到必要性。

还有一个就是独生子女证,这个证件的主要问题就是子女姓名和我的姓名不一致,最后采取的办法是父母到了当地街道的计生办,去了数次,体现了自己的诚意,表明了重新办证的必要性和自己确实只有一个子女的事实,最后,街道计生办颁发了新证件。

以上就是我在办理父母投靠进京落户的时候遇到的一些难点和问题。其余的材料,在我看来,都是按照派出所的文件按部就班就好了,唯独以上几个问题是一开始很困扰我的。

最后说点题外话,由于这次父母投靠事情,我看到了自己和父母的大量原始档案,对于中国的历史问题有了更深刻的理解。

我终于明白身份证的生日和实际生日不一样是怎么回事了。新闻中说的档案中农历和公历生日混为一谈,生日填错的情形,真实发生在我父母的档案中,最后,这些问题都通过手写一份材料解决了。