安全入门之XSS攻击

最近公司在搞安全方面的东西,其实自己对这块本来也很感兴趣,记得上高中的时候也在黑防上发表过文章呢。不过那时候的漏洞现在看起来都很弱,比如sql注入什么的。不过就算是现在,也还是有不少应用仍然存在这种10年前就很流行的漏洞。(一不小心暴露了年龄)

这篇我们就来学习一下XSS攻击。

先来介绍一下什么是XSS吧。全称跨站脚本攻击(Cross Site Scripting)。(为不和层叠样式表(Cascading Style Sheets, CSS)的缩写混淆,故将跨站脚本攻击缩写为XSS。)恶意攻击者往Web页面里插入恶意Script代码,当用户浏览该页之时,嵌入其中Web里面的Script代码会被执行,从而达到恶意攻击用户的目的。

看了定义我们应该知道了,XSS原理就是用户访问了攻击者嵌入了恶意脚本的web页面,主要是js脚本。正常用户访问之后,恶意脚本执行,导致用户损失。(比如盗号、比如窃取用户隐私数据等)

XSS攻击有很多种类型,我们这里介绍几种常用的。当然flash部分也存在,json部分也存在。然而我我也不是做flash的不了解,其实这些原理是一样的。

存储型XSS

就是把XSS脚本存储到了服务器上。怎么存储到服务器上呢?举个例子就懂了。

论坛发帖,攻击者在帖子内容中输入了恶意js攻击脚本,这样攻击脚本被存储在了服务器上,当正常用户访问的时候,就会执行这种恶意脚本。

场景懂了,可以怎么做呢,比如恶意脚本中读取用户隐私cookies。如果这个cookies没有做http-only,那么攻击者写的js可以读取cookies信息,然后发往自己的服务器。这时候正常用户一访问页面就会执行这段js脚本,把自己的cookies信息发往攻击者的服务器。有些网站把登录token存到cookies中,攻击者就可以利用这个token登录被害者帐号进行任意操作了。

同样的,攻击者还可以在js脚本中发起任意请求,比如读取私密信息的请求,将请求的结果发往攻击者服务器。这样当被害用户访问帖子的时候,就会把私密数据发出去,导致用户私密数据泄漏。

说了场景和危害,怎么解决呢,很简单,那就是对页面数据进行转义。对恶意脚本进行转义,这样恶意脚本就算被存储下来,访问的时候也不会执行。另外,也可以不让用户发帖的时候发送恶意脚本包含的一些特殊符号。

存储型XSS是最容易实现攻击的一个漏洞。

反射型XSS

反射型的意思其实很简单,我们说个例子就知道了。

比如搜索功能,我们搜索一个内容,页面会展现我们搜索的关键字,和搜索结果。假如这时候我们搜索的内容换成一段恶意js脚本,这样如果没有对展示进行转义的话,恶意脚本就会执行。

我们把这个搜索的链接发送给被害用户,那么这个用户就会中招。

别以为这个有什么实现难度,想想常见的短网址。还有如果我们对这个域名是比较信任的,是不是不管后面是什么都会轻易的点进去。

如何检测

直接在输入框中输入检测脚本即可。建议的三种检测脚本如下。

1) ‘”></script><script>alert(1)</script><”
2) ‘”;alert(1);x=”‘
3) ‘”><img src=x onerror=alert(1)>

我们一般选择第三种就好。如果进入页面发现弹出alert(1),说明漏洞存在。

本文原创于赵伊凡BLOG转载请注明出处。

到这里我们就介绍完两种简单的XSS攻击方式了,大家可以去其他网站试试(别再我这试,肯定没有)。另外的,还有DOM型的XSS,以及flash的XSS。大家有兴趣可以自己研究下。

秒杀系统实现分析

秒杀的特点

再讲怎么实现之前先说说秒杀有什么特点。

秒杀的场景比较特别,一般都会在一些集中的时间点对某些商品进行抢购。

我们先来考虑下常规的购买流程,浏览商品——加入购物车——下单——减库存——支付——支付完成。而多数人的操作其实都是浏览商品,加入购物车,下单购买的占少数。而秒杀的场景,其实大家已经省略掉了前面的操作,直接选择好了商品,就要直接下单、支付了。而且买的还都是同一个商品。这块问题就来了,非常多的人全都来操作这一部分集中的业务数据,对系统的冲击之大可想而知。

比如一般我们来处理库存的方式,需要对数据库加行级锁,然后减库存(同时需要确认库存数量,不能超售),然后释放。一般情况还好,因为大家都在购买不同的商品,所以锁加在不同的记录上面。但是在秒杀场景中,锁需要加载同一个商品上面,当大量请求过来,所有的请求都在等待给这个记录加锁,结果会多惨可想而知。

秒杀的优化

请求尽量拦截在系统上游

从客户端到负载服务,再到业务服务,再到数据库,我们要尽量能把请求拦截到前面就不要往后放。

总体来说的思路有限流、消峰、排队等。

客户端层

记得之前红包也发了个新年版的微信,就是把很多静态资源提前缓存到了客户端,到时候没有的请求,有的就不用请求了。优化了高峰秒杀的服务压力。另外对于商品秒杀,也可以把页面缓存,一些不关键业务静态化,比如商品评价、相关推荐等,减少服务器压力。

记得去年前年的春晚微信红包,摇一摇有机会抽到红包。但是大家都在摇,每个人摇都给你去系统抽一下,系统压力好大,如果你摇三次给你发一次请求呢,是不是系统的压力下降到了1/3?

再举个例子,12306,大家刷票,为什么平时使用的时候一点事没有,而春节、国庆抢票就很难。其实人家已经优化的很好了,但是还是会有很大压力,为什么,就是大家不停的在刷新。想想是不是春节的时候一直在刷票,不管是手动还是软件刷,人家一直查压力很大啊。于是页面上显示几秒才能重新查询一次(但是这样也限制不了外挂党),这样有效降低了服务器压力。

其实很多地方的查询功能也是类似,点了查询,会有个倒计时,几秒之后才能查,按钮置灰。这样可以防止不停的发送请求。尤其是12306这种,查询结果出的稍微一慢,用户还会觉得没查出来,就会不停的点击增加服务器负担。

上面举的两个例子,都是拦截到了客户端(应用、浏览器)层面,但是如果有人用外挂,或者直接写脚本发请求呢(想起月饼时事件)?正常用户也会有很多穿透客户端的,下面就需要在nginx这类服务器层面去做拦截了。(也可能lvs)

负载服务层

对于恶意用户,假如我们客户端限制的是3秒能发一次请求,我们在负载服务一层,限制超过2秒一次的请求,把这个uid给他封锁一定时间,对于短期秒杀场景直接全站封禁也可以。做的松一点就是3秒只放过1个请求,而不封锁帐号。

(这里有个小tip给大家,出现这种异常的情况,我们可以认为就是非法用户了,直接封了也无所谓,但是文案的提示尽量不要说你的帐号被封了什么的,给他一个和一般用户一样的没抢到什么的提示最好。不然写脚本的人会一点点摸索你的频率,伪装成正常用户。)

如果不考虑封锁帐号,也可以增加负载层面的缓存,对于一定时间内的请求,都返回第一次请求的结果,而不去请求后端服务数据。

在大量请求时为了让缓存的结果或者计数的结果尽量一致,可以按UID来映射到具体服务,保证请求得到的结果一致。(对于内存计数,希望同一UID落到一个服务上,缓存结果也是如此)

这里另说一句,千万不要觉得,我们一个nginx负载多少,到时候真出现了大量秒杀的情况,预估多少量,除以目前单nginx负载,就是我们需要的nginx数量。对于单机部署多个nginx或者多nginx协调的情况,都是可能影响性能的,平均响应时间也会变长,需要实际测试出拐点才是正确的做法。

业务服务层

对于秒杀,我举个我们这里实际遇到的例子。我们有红包的业务,对于抢红包的用户来说,就是个秒杀场景。比如发一次红包,可以20个人抢,那么透过数据库的就没有必要太多,一般会做多几个的冗余量(比如5个),这样其他的请求就没必要去与数据库交互了,直接快速返回没抢到就好了。透过去的这25个再进行数据库的行级锁进行减少库存等相关操作。对于上百万千万的请求来说,这25个请求就并不是很多了,数据库也可以轻松抗住。这里还要注意,要使用乐观锁减库存,进一步减少超卖可能。

update xxx set num = num -1 where where id = 1 and num > 0;

加锁的时候检查其实会更好,多出来的5个就不会处理了。

为什么要多放一些呢,假如在进行减库存等相关操作出错了,不要重放,直接抛弃让后面的补上就好了。重放还是复杂了些,同时也符合fail fast规则。

这里具体的实现技术,使用缓存、队列都可以完成,后面说缓存,队列的话不管是用哪种中间件,比如mq、redis队列,都可以轻松搞定。当然对于关键大型的抢购业务,也可以放很多,比如1w商品,放2w入队列。不可能一半都失败吧。

业务上其实也可以配合一些优化,比如很多东西并不需要精细化的显示,就可以粗劣的显示一下,比如红包的剩余个数,可以只显示还有没有,而没必要显示还剩几个(当然也可以显示,但是业务上接受具体数值显示不准的情况)。

数据库

到数据库这一次的压力其实已经很小了,只需要保证数据的准确性就可以了。

对于大量商品同时秒杀的情况,可以按照商品id进行分表或者分库,提升数据库的性能。

多用缓存

在秒杀优化中,一定要充分的利用缓存这一工具。推荐的缓存工具使用redis。

比如在负载服务的时候,可以使用redis作为通用计数器。业务服务的地方,使用redis的队列,或者配合队列做计数器,把超过25个的请求全部快速返回没有抢到。

另外对于读的业务,尽量多的使用缓存,上面提到过,如果是商品页的话,完全可以把整个页面的内容都缓存起来,这里推荐页面的缓存可以在nginx上做。

对于缓存服务挂了的情况,重启一定要记得预热,不过在高并发的秒杀业务下,我们基本上是不允许服务挂了的情况,所以一定要做好服务保护,当过载过高的时候可以抛弃请求,不要让服务挂了。

异步处理

对于订单生成、物流状态等信息,完全可以交给队列后面的服务去处理,并不需要实时处理。把一些不着急的业务逻辑放到异步队列后面处理也是优化的核心。

尽量让http请求能够快速返回。我们的抢红包业务,由于服务与客户端维持了长连接,所以都快速返回了,然后抢到的和一小部分多放过去的量,是通过异步返回的结果,其他的请求都是http快速返回没抢到的结果。

用户体验

秒杀优化的过程中,不能丢失了正常用户的体验。

可以异步化处理一些业务,比如我们上面提到的抢红包业务,虽然抢到的结果是异步发送的,但是速度也不会太久,用户体验就不会太差。

对于商品的抢购,如果具体结果异步处理,可以先来个中间页面,提示用户的抢购结果,或者提示个抢购中。这块最早小米就做了,但是总是抢购中,然后没抢到,大家心里也不是很开心。但是总比啥都没有卡在那好。

最后说点别的

对于一般的企业,如果预估秒杀会比较激烈的话,一定要提到带宽,如果是云服务的话,建议新弄一组机器来做这块的业务,降低对正常业务的影响。

多做压测总是好的。

可以针对秒杀场景做些简化需求,没必要让他和一般商品销售需求一致,尽可能的砍掉更多的不必要功能,保证服务正常运行。

特殊情况可以增加验证机制,比如苹果使用了最烦人的,需要下单用户给苹果发短信,然后获取短信验证码,才能预定店里拿手机。不排除会被刷,但是谁叫人家厉害呢,你不买别人买。但是我们的验证服务尽量还是不要影响到用户的下单流程。

多做提前需求准备,比如建议用户提前把东西加入购物车或者增加一键购这样的功能。建议用户提前选择好收货地址等等。

做倒计时,秒杀一般都是从某一时间点准时开始的,做个倒计时,可以方式用户总是刷新看开枪没,一直重新访问页面也很消耗服务器性能呀。

很多网站初期对于用户的注册还不是很在意,结果出了很多僵尸用户,这些帐号在秒杀的时候被某些工作室用来刷接口。这个建议想办法把这部分用户区别出来。然后只要是这部分用户想要秒杀,需要验证手机号等复杂操作才能进行,防止工作室僵尸用户刷接口秒杀。

本文原创于赵伊凡BLOG转载请注明出处,超过3000字全原创手敲实在不容易。

到此秒杀就说的差不多了,当然秒杀还会涉及到很多东西,这也需要开发人员一步一步的成长,再去提升自己系统的稳定性。数据库扩容,分库、更多的缓存等优化都是需要慢慢进行的。

Java中关于String.format的性能问题

首先需要说明的是本文所说的是java中的String的format方法性能,可能其他语言有所差异。

下面进入正题。一般新入职一家公司的时候,会去看新公司现有的代码。我记得我来的时候用了一段时间把项目的各个业务结合代码实现整个看了个遍,我清楚的记得,我刚来的时候,我们总监的一句话,业务永远是最重要的。

当然有一些Java的用法也是以前没见到过。比如以前字符串拼接,都会用String类型直接加号拼接字符串,顶多心里知道其实有StringBuilder和StringBuffer效率更好。但是效率差的不多就还是用字符串拼接。在这里发现有人在代码中用String的format方法,感觉很方便,也就跟着用了。

其实这个这个用法到现在也用了好久了,现在想来性能并不一定很好,也还是简单介绍一下。下面先看个简单的例子吧。

String b = String.format("id:%d, name:%s", 1, "irfen");

用法就是这样,第一个参数是个字符串,里面有一些替换的字符,同时有对应类型,后面是个变长数组参数。其中%d对应整型数字,%c为char类型,%f为浮点型,%s为字符串,%b为布尔型,学过c语言的可能会比较熟悉。当然还有很多其他用法,这里就不详细介绍了。

附带说下,其实我们经常输出的log日志,也有类似的用法。

logger.info("id:{}, name:{}", 1, "irfen");

只不过不用指定具体类型,更省事了~

这样用真的好吗,对于一般要求不高的系统,其实这样用比字符串拼接看起来还更加清晰一点,但是性能怎么样呢。这里之前写的一篇文章,《Java使用JMH进行简单的基准测试Benchmark》(怎么用?点去看看),来做个测试,测试代码如下。

package me.irfen.jmh;

import org.openjdk.jmh.annotations.*;

import java.util.concurrent.TimeUnit;

@BenchmarkMode(Mode.Throughput)
@Warmup(iterations = 3)
@Measurement(iterations = 10, time = 5, timeUnit = TimeUnit.SECONDS)
@Threads(16)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class StringFormatTest {

    @Benchmark
    public void testStringAdd() {
        String a = "a" + 1 + "b" + 2 + "c";
        print(a);
    }

    @Benchmark
    public void testStringFormat() {
        String a = String.format("a%db%dc", 1, 2);
        print(a);
    }

    private void print(String a) {
    }
}

我们来运行一下,得到的测试结果如下。

# JMH 1.14.1 (released 46 days ago)
# VM version: JDK 1.8.0_71, VM 25.71-b15
# VM invoker: C:\Program Files\Java\jdk1.8.0_71\jre\bin\java.exe
# VM options: -Didea.launcher.port=7532 -Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.2.4\bin -Dfile.encoding=UTF-8
# Warmup: 3 iterations, 1 s each
# Measurement: 10 iterations, 5 s each
# Timeout: 10 min per iteration
# Threads: 16 threads, will synchronize iterations
# Benchmark mode: Throughput, ops/time
# Benchmark: me.irfen.jmh.StringFormatTest.testStringAdd

# Run progress: 0.00% complete, ETA 00:03:32
# Fork: 1 of 2
# Warmup Iteration   1: 1765160.048 ops/ms
# Warmup Iteration   2: 1963889.973 ops/ms
# Warmup Iteration   3: 2072082.071 ops/ms
Iteration   1: 2073452.461 ops/ms
Iteration   2: 2098403.917 ops/ms
Iteration   3: 2071669.851 ops/ms
Iteration   4: 2057731.528 ops/ms
Iteration   5: 2057762.250 ops/ms
Iteration   6: 2076944.228 ops/ms
Iteration   7: 2100384.457 ops/ms
Iteration   8: 2103323.948 ops/ms
Iteration   9: 2107015.190 ops/ms
Iteration  10: 2092262.668 ops/ms

# Run progress: 25.00% complete, ETA 00:02:59
# Fork: 2 of 2
# Warmup Iteration   1: 1989580.834 ops/ms
# Warmup Iteration   2: 1949143.086 ops/ms
# Warmup Iteration   3: 2011865.640 ops/ms
Iteration   1: 2052582.566 ops/ms
Iteration   2: 2054651.084 ops/ms
Iteration   3: 2049439.875 ops/ms
Iteration   4: 2041924.938 ops/ms
Iteration   5: 2034063.807 ops/ms
Iteration   6: 2037295.266 ops/ms
Iteration   7: 2024204.430 ops/ms
Iteration   8: 2081162.560 ops/ms
Iteration   9: 2090790.434 ops/ms
Iteration  10: 2094408.422 ops/ms


Result "testStringAdd":
  2069973.694 ±(99.9%) 22210.562 ops/ms [Average]
  (min, avg, max) = (2024204.430, 2069973.694, 2107015.190), stdev = 25577.716
  CI (99.9%): [2047763.132, 2092184.256] (assumes normal distribution)


# JMH 1.14.1 (released 46 days ago)
# VM version: JDK 1.8.0_71, VM 25.71-b15
# VM invoker: C:\Program Files\Java\jdk1.8.0_71\jre\bin\java.exe
# VM options: -Didea.launcher.port=7532 -Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.2.4\bin -Dfile.encoding=UTF-8
# Warmup: 3 iterations, 1 s each
# Measurement: 10 iterations, 5 s each
# Timeout: 10 min per iteration
# Threads: 16 threads, will synchronize iterations
# Benchmark mode: Throughput, ops/time
# Benchmark: me.irfen.jmh.StringFormatTest.testStringFormat

# Run progress: 50.00% complete, ETA 00:01:59
# Fork: 1 of 2
# Warmup Iteration   1: 2036.947 ops/ms
# Warmup Iteration   2: 4070.937 ops/ms
# Warmup Iteration   3: 4453.920 ops/ms
Iteration   1: 4440.250 ops/ms
Iteration   2: 4593.925 ops/ms
Iteration   3: 4466.877 ops/ms
Iteration   4: 4461.771 ops/ms
Iteration   5: 4421.152 ops/ms
Iteration   6: 4326.495 ops/ms
Iteration   7: 4330.146 ops/ms
Iteration   8: 4448.596 ops/ms
Iteration   9: 4368.319 ops/ms
Iteration  10: 4534.138 ops/ms

# Run progress: 75.00% complete, ETA 00:01:01
# Fork: 2 of 2
# Warmup Iteration   1: 1717.527 ops/ms
# Warmup Iteration   2: 4504.847 ops/ms
# Warmup Iteration   3: 4370.694 ops/ms
Iteration   1: 4527.753 ops/ms
Iteration   2: 4580.512 ops/ms
Iteration   3: 4487.512 ops/ms
Iteration   4: 4541.971 ops/ms
Iteration   5: 4575.898 ops/ms
Iteration   6: 4519.100 ops/ms
Iteration   7: 4574.067 ops/ms
Iteration   8: 4606.887 ops/ms
Iteration   9: 4566.840 ops/ms
Iteration  10: 4682.968 ops/ms


Result "testStringFormat":
  4502.759 ±(99.9%) 82.444 ops/ms [Average]
  (min, avg, max) = (4326.495, 4502.759, 4682.968), stdev = 94.943
  CI (99.9%): [4420.315, 4585.203] (assumes normal distribution)


# Run complete. Total time: 00:04:06

Benchmark                               Mode  Cnt        Score       Error   Units
StringFormatTest.testStringAdd         thrpt   20  2069973.694 ± 22210.562  ops/ms
StringFormatTest.testStringFormat  thrpt   20     4502.759 ±    82.444  ops/ms

直接关注最后一行,性能差好多。用结果说话,String的format性能真的没有字符串拼接性能好,而且是差太多,更别说StringBuilder了。

为什么性能这么差呢?虽然我们得到了结果,也来了解下原因吧。首先可以想到的是,String的format需要去逐个替换占位符,另外由于不同的类型,还需要去匹配类型,这肯定比直接字符串相加性能消耗多了很多。

下面来简单了解下关键部位的源码就知道了。

public Formatter format(Locale l, String format, Object ... args) {
        ensureOpen();

        // index of last argument referenced
        int last = -1;
        // last ordinary index
        int lasto = -1;

        FormatString[] fsa = parse(format);
        for (int i = 0; i < fsa.length; i++) {
            FormatString fs = fsa[i];
            int index = fs.index();
            try {
                switch (index) {
                case -2:  // fixed string, "%n", or "%%"
                    fs.print(null, l);
                    break;
                case -1:  // relative index
                    if (last < 0 || (args != null && last > args.length - 1))
                        throw new MissingFormatArgumentException(fs.toString());
                    fs.print((args == null ? null : args[last]), l);
                    break;
                case 0:  // ordinary index
                    lasto++;
                    last = lasto;
                    if (args != null && lasto > args.length - 1)
                        throw new MissingFormatArgumentException(fs.toString());
                    fs.print((args == null ? null : args[lasto]), l);
                    break;
                default:  // explicit index
                    last = index - 1;
                    if (args != null && last > args.length - 1)
                        throw new MissingFormatArgumentException(fs.toString());
                    fs.print((args == null ? null : args[last]), l);
                    break;
                }
            } catch (IOException x) {
                lastException = x;
            }
        }
        return this;
    }

这里就不粘这里面的parse方法了,也是个循环。

到此我们应该知道他有多慢,而且为什么这么慢了。以后什么时候该用哪个还是要根据具体情况来选择。

本文原创于赵伊凡BLOG转载请注明出处。

Java使用JMH进行简单的基准测试Benchmark

这里说道的基准测试Benchmark其实是微基准测试Micro-Benchmark。这里面的概念就不详细介绍了,反正就是JMH可以非常方便的帮助我们进行java代码的简单基准测试。

有什么用

可以对多组代码进行基准测试比较。

很多人总说,这样用速度快,性能好,别听他们的,自己试过才知道。

Java的基准测试需要注意的几个点

测试前需要预热。
防止无用代码进入测试方法中。
并发测试。
测试结果呈现。

简单的代码例子

我们来看一个简单的示例,大家就知道JMH的强大了。

测试代码如下。

package me.irfen.jmh;

import org.openjdk.jmh.annotations.*;

import java.util.concurrent.TimeUnit;

/**
 * author: zhaoye
 * date: 2016/11/4 14:36
 */
@BenchmarkMode(Mode.Throughput)
@Warmup(iterations = 3)
@Measurement(iterations = 10, time = 5, timeUnit = TimeUnit.SECONDS)
@Threads(16)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class StringBuilderTest {

    @Benchmark
    public void testStringAdd() {
        String a = "";
        for (int i = 0; i < 10; i++) {
            a += i;
        }
        print(a);
    }

    @Benchmark
    public void testStringBuilderAdd() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            sb.append(i);
        }
        print(sb.toString());
    }

    private void print(String a) {
    }
}

代码中有好多注解,我们一会再说,先说我们要干什么。这里应该很好看出来,大家都说String进行字符相加的时候没有StringBuilder快,怎么证明,则就是我们要做的事情。

现在来解释注解

@Setup

这次我们没用到,简单说,这个注解的作用就是我们需要在测试之前进行一些准备工作,比如对一些数据的初始化之类的。。

@BenchmarkMode

基准测试类型。这里选择的是Throughput也就是吞吐量。根据源码点进去,每种类型后面都有对应的解释,比较好理解,吞吐量会得到单位时间内可以进行的操作数。

下面看下这里的源码。

Throughput("thrpt", "Throughput, ops/time"),
AverageTime("avgt", "Average time, time/op"),
SampleTime("sample", "Sampling time"),
SingleShotTime("ss", "Single shot invocation time"),
All("all", "All benchmark modes");

@Warmup

上面我们提到了,进行基准测试前需要进行预热。一般我们前几次进行程序测试的时候都会比较慢,所以要让程序进行几轮预热,保证测试的准确性。其中的参数iterations也就非常好理解了,就是预热轮数。

@Measurement

度量,其实就是一些基本的测试参数。iterations进行测试的轮次,time每轮进行的时长,timeUnit时长单位。都是一些基本的参数,可以根据具体情况调整。一般比较重的东西可以进行大量的测试,放到服务器上运行。

@Threads

测试线程,这个非常好理解,根据具体情况选择,一般为cpu乘以2。

@OutputTimeUnit

这个比较简单了,基准测试结果的时间类型。一般选择秒或者毫秒。

@State

当使用@Setup参数的时候,必须在类上加这个参数,不然会提示无法运行。

执行方式

生成jar执行

一般对于大型的测试,需要测试时间比较久,线程比较多的话,就需要去写好了丢到linux程序里执行,不然本机执行很久时间什么都干不了了。

$ mvn clean install
$ java -jar target/benchmarks.jar

首先编译,然后执行就可以了。当然在执行的时候可以输入-h参数来看帮助。

在IDE中执行

对于一些我们自己的一些小测试,就可以直接在IDE中执行了,还丢到linux上去太麻烦了。怎么搞呢,看下面。

package me.irfen.jmh;

import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

public class Test {

    public static void main(String[] args) throws RunnerException {
        Options options = new OptionsBuilder().include(StringBuilderTest.class.getSimpleName())
                .output("E:/Benchmark.log").forks(2).build();
        new Runner(options).run();
    }
}

执行的方法当然还是个main方法,当然你用junit也是可以的。这里其实也比较简单,new个Options,然后传入要运行哪个测试,选择基准测试报告输出文件地址,设置fork出的线程数,然后通过Runner的run方法就可以跑起来了。

报告结果

下面我们来看下报告结果。

# JMH 1.14.1 (released 45 days ago)
# VM version: JDK 1.8.0_71, VM 25.71-b15
# VM invoker: C:\Program Files\Java\jdk1.8.0_71\jre\bin\java.exe
# VM options: -Didea.launcher.port=7532 -Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.2.4\bin -Dfile.encoding=UTF-8
# Warmup: 3 iterations, 1 s each
# Measurement: 10 iterations, 5 s each
# Timeout: 10 min per iteration
# Threads: 16 threads, will synchronize iterations
# Benchmark mode: Throughput, ops/time
# Benchmark: me.irfen.jmh.StringBuilderTest.testStringAdd

# Run progress: 0.00% complete, ETA 00:03:32
# Fork: 1 of 2
# Warmup Iteration   1: 14690.103 ops/ms
# Warmup Iteration   2: 18731.179 ops/ms
# Warmup Iteration   3: 19475.241 ops/ms
Iteration   1: 18787.224 ops/ms
Iteration   2: 18949.244 ops/ms
Iteration   3: 18715.979 ops/ms
Iteration   4: 18770.003 ops/ms
Iteration   5: 18912.926 ops/ms
Iteration   6: 19252.784 ops/ms
Iteration   7: 18975.545 ops/ms
Iteration   8: 18767.721 ops/ms
Iteration   9: 18976.551 ops/ms
Iteration  10: 18830.076 ops/ms

# Run progress: 25.00% complete, ETA 00:03:05
# Fork: 2 of 2
# Warmup Iteration   1: 15871.759 ops/ms
# Warmup Iteration   2: 19330.148 ops/ms
# Warmup Iteration   3: 18851.970 ops/ms
Iteration   1: 19058.934 ops/ms
Iteration   2: 18851.454 ops/ms
Iteration   3: 18511.584 ops/ms
Iteration   4: 18951.476 ops/ms
Iteration   5: 18721.372 ops/ms
Iteration   6: 18891.480 ops/ms
Iteration   7: 18651.455 ops/ms
Iteration   8: 18854.140 ops/ms
Iteration   9: 19198.246 ops/ms
Iteration  10: 19148.773 ops/ms


Result "testStringAdd":
  18888.848 ±(99.9%) 160.591 ops/ms [Average]
  (min, avg, max) = (18511.584, 18888.848, 19252.784), stdev = 184.936
  CI (99.9%): [18728.258, 19049.439] (assumes normal distribution)


# JMH 1.14.1 (released 45 days ago)
# VM version: JDK 1.8.0_71, VM 25.71-b15
# VM invoker: C:\Program Files\Java\jdk1.8.0_71\jre\bin\java.exe
# VM options: -Didea.launcher.port=7532 -Didea.launcher.bin.path=C:\Program Files (x86)\JetBrains\IntelliJ IDEA 2016.2.4\bin -Dfile.encoding=UTF-8
# Warmup: 3 iterations, 1 s each
# Measurement: 10 iterations, 5 s each
# Timeout: 10 min per iteration
# Threads: 16 threads, will synchronize iterations
# Benchmark mode: Throughput, ops/time
# Benchmark: me.irfen.jmh.StringBuilderTest.testStringBuilderAdd

# Run progress: 50.00% complete, ETA 00:02:04
# Fork: 1 of 2
# Warmup Iteration   1: 84345.885 ops/ms
# Warmup Iteration   2: 118411.934 ops/ms
# Warmup Iteration   3: 69339.009 ops/ms
Iteration   1: 74770.077 ops/ms
Iteration   2: 76996.804 ops/ms
Iteration   3: 77855.877 ops/ms
Iteration   4: 76883.502 ops/ms
Iteration   5: 75685.537 ops/ms
Iteration   6: 76299.372 ops/ms
Iteration   7: 77065.766 ops/ms
Iteration   8: 76537.937 ops/ms
Iteration   9: 77216.754 ops/ms
Iteration  10: 75410.698 ops/ms

# Run progress: 75.00% complete, ETA 00:01:02
# Fork: 2 of 2
# Warmup Iteration   1: 78998.331 ops/ms
# Warmup Iteration   2: 61750.531 ops/ms
# Warmup Iteration   3: 69513.539 ops/ms
Iteration   1: 64862.481 ops/ms
Iteration   2: 65963.130 ops/ms
Iteration   3: 66719.366 ops/ms
Iteration   4: 66315.918 ops/ms
Iteration   5: 67172.960 ops/ms
Iteration   6: 66156.558 ops/ms
Iteration   7: 67372.587 ops/ms
Iteration   8: 67607.029 ops/ms
Iteration   9: 67339.769 ops/ms
Iteration  10: 65845.035 ops/ms


Result "testStringBuilderAdd":
  71503.858 ±(99.9%) 4491.696 ops/ms [Average]
  (min, avg, max) = (64862.481, 71503.858, 77855.877), stdev = 5172.644
  CI (99.9%): [67012.162, 75995.554] (assumes normal distribution)


# Run complete. Total time: 00:04:11

Benchmark                                Mode  Cnt      Score      Error   Units
StringBuilderTest.testStringAdd         thrpt   20  18888.848 ±  160.591  ops/ms
StringBuilderTest.testStringBuilderAdd  thrpt   20  71503.858 ± 4491.696  ops/ms

内容有点多,仔细看,三大部分,第一部分是有序的结果,第二部分是无序的结果,第三部分就是两个的简单结果比较。这里注意我们forks传的2,所以每个测试有两个fork结果。

前两部分是一样的,简单说下。首先会写出每部分的一些参数设置,然后是预热迭代执行(Warmup Iteration),然后是正常的迭代执行(Iteration),最后是结果(Result)。这些看看就好,我们最关注的就是第三部分,其实也就是最终的结论。千万别看歪了,他输出的也确实很不爽,error那列其实没有内容,score的结果是xxx ± xxx,单位是没毫秒多少个操作。可以看到,StringBuilder的速度还确实是要比String进行文字叠加的效率好太多。

最后

到此我们介绍了JMH的一些简单用法。对于别人说的东西,现在jvm优化了很多,哪些还是真的,哪些是已经过时的?只有自己试过了才知道。

官网在这,http://openjdk.java.net/projects/code-tools/jmh/
其他还有很多有趣的例子,http://hg.openjdk.java.net/code-tools/jmh/file/tip/jmh-samples/src/main/java/org/openjdk/jmh/samples/

本文原创于赵伊凡BLOG转载请注明出处。

好好用Java的HashMap及1.8的变化

HashMap有什么好说的?从最开始接触java语言,可能就开始使用了。对于一个稍微钻研过的Java开发来说,心里都非常的明白HashMap内部的实现结构。他就是数组+链表实现的。

最近越来越多的团队都把Java升级到1.8了,但是绝大多数人对Java的理解还都停留在1.6版本。而对于1.7、1.8的理解,也仅仅只是局限于语法这个层面。

本篇我们就来聊聊HashMap在1.6到1.8到底发生了什么变化(1.6和1.7大致相近),以及怎么样更高效的使用HashMap。

先说下1.6时代HashMap的实现

可能很多人如果没有对Java源码深究过的话,不会太知道HashMap到底内部是怎么实现的。或者看过数据结构的书的话,可能也知道HashMap会有哪些种实现方式。这里安利一下我写的算法书——轻松学算法(东强那边好像没货了,去这里看看),里面有介绍到这一数据结构,但是没有介绍1.8中的变化,最近打算面试的可以买来参考下。

在1.6时代,HashMap是由数组+链表的形式存储的,通过key进行hash算法得到一个值,映射到数组中,如果数组上已经有值,那么会建立一个链表来存储。如果链表已经存在,那么会在链表的首位插入这个新增的元素(想想为什么要在首位?)。

所以HashMap在1.6时代,大致的实现方式是下面这张图的样子。

HashMap1.6版本结构
HashMap1.6版本结构

所以如果key经过hash算法映射之后,整个HashMap的key都映射到一个格子上的话,那么这个HashMap就会退化成一个链表。性能就很差了。

这里顺便说下1.6时代,hash算法对key的hashCode进行了两次异或(假设key的hashCode值为h),那么1.6版本的hash算法是下面这样的。

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

1.8下HashMap产生的变化

1.8的HashMap到底怎么了?他的性能更好了,在这个版本HashMap的存储结构发生了细微的变化,而这个变化,也直接导致了HashMap的性能比以前好了一些。

首先的一个重要的变化,那就是存储结构由以前单纯的数组+链表,变成了数组+链表/红黑树。什么意思呢,就是这个数组上跟着的可能是一个链表,也可能是个红黑树。当冲突节点(也就是链表上的节点)个数达到7个或者7个以上的时候,将会把链表转换为红黑树,然后继续进行存储。这里需要说明一点,就是HashMap中就可能存在有个数组节点后面是链表,有的是红黑树的情况。

有个什么好处呢,在最坏的情况下,冲突节点个数假设为N,那么1.6版本的时间复杂度为O(N),但是在1.8版本中时间复杂度会是O(logN),性能有了提升。

下面看一下1.8版本的HashMap存储结构图(偷个懒省略null了)。

hashmap1.8版本结构
hashmap1.8版本结构

当冲突比较明显的时候,红黑树是要比链表好点。接下来再看看1.8的hash算法是什么样的,同样设h为key的hashCode。

return h >>> 16;

比1.6的简单了好多啊,由于HashMap的key进行hash如果冲突之后,使用红黑树比链表性能更好,所以作者觉得就算冲突了也还好,所以简化了hash算法,只是把高16位异或下来了而已。

再聊下加载因子Load Factor

HashMap中用到了一个扩容因子,他的作用很简单,就是为了防止数组都有元素的时候才扩容,默认扩容因子为0.75,也就是说,默认16个长度的数组,在有13分元素占满数组的时候,就会开始扩容了。如果没有扩容因子,那么到16个数字格子都占满了才扩容,那肯定这时候肯定很多数组元素里面后面有很长的冲突了(链表很长或者红黑树很高)。而且HashMap的扩容,其实要比ArrayList扩容复杂的多,性能也差很多。

假设声明一个HashMap,大概知道数组可能的长度,或者要copy一个HashMap,不能简单的像下面这样写。

HashMap map = new HashMap(n); // n为知道的可能长度

因为加载因子的作用,在填充内容的时候很容易还是需要一次扩容的。HashMap里面有一个可以把一个HashMap复制过来的方法,是putAll方法,接收一个Map参数,看下里面的实现,其实他会初始化一个长度,((float)s / loadFactor) + 1.0F,然后转换为int类型,其中s为原Map的size。

最后拓展个IntObjectHashMap

先写个测试代码。

IntObjectHashMap<String> map = new IntObjectHashMap<String>();
map.put(1, "c");
map.put(2, "b");
map.put(3, "a");
MutableIntSet mutableIntSet = map.keySet();
for (IntIterator iter = mutableIntSet.intIterator(); iter.hasNext();) {
    int key = iter.next();
    System.out.println(map.get(key));
}
System.out.println(map.getFirst()); // c
System.out.println(map.max()); // c

很多时候我们想要用key类型为int的Map,但是常规情况HashMap的key只能是Integer,虽说空间浪费了一点我们也不是很在意,但是这个IntObjectHashMap确实有更多厉害的地方。

通过上面示例代码我们可以看到他可以取第一个元素,可以拿到最大值的元素。其实他的Set也可以获取min()和max(),还可以转换为数组和有序数组。

最后有个内容差点忘了,IntObjectHashMap并不是JDK自带的,但是如果你的项目比较大的话,很容易就已经引用到了这个模块,pom文件看下面,版本号并不重要。

<dependency>
  <groupId>com.goldmansachs</groupId>
  <artifactId>gs-collections</artifactId>
  <version>7.0.0</version>
</dependency>

两个内容混起来写总觉得不太好,我又懒了。

本文原创于赵伊凡BLOG转载请注明出处。

Java中生成随机数Random、ThreadLocalRandom、SecureRandom

使用java生成随机数,其实有很多种方式,我们一点点来说。

我们最常用的方法就是下面这样直接用Random。

Random

Random random = new Random();
int a = random.nextInt(5);

这样a的值可能是0~4之间的数字。

我们再细究一下,其实Random是有构造函数的,他的参数可以传一个long类型的值,当使用空的构造的时候,使用的实际上是System.currentTimeMillis()也就是当前时间毫秒数的值,我们把这个叫做种子

种子是干什么的呢,实际上我们生成的随机数都是伪随机数,而想要使我们生成的随机数强度更高,就需要更好的算法和种子。一般情况下,要使用Random去生成随机数,直接用空构造函数就可以了。那么这个种子到底有什么用呢,实际上读者去试验一下就知道了,我们使用固定随机数,比如1,然后我们连续次去new这个Random,然后去生成一个随机数,像下面这样,你会发现,三个数的结果是一样的。

Random random = new Random(1);
int a = random.nextInt(5);
random = new Random(1);
int b = random.nextInt(5);
random = new Random(1);
int c = random.nextInt(5);

所以我们一定不能把这个种子写死,用当前时间毫秒数,还是比较好些。另外,使用Random尽量不要重复new对象,其实也没什么意义的。

最后说一点,Random是线程安全的,去这里的官方文档可以看到,“Instances of java.util.Random are threadsafe.”。但是在多线程的表现中,他的性能很差。

ThreadLocalRandom

这个类是Java7新增的类,给多线程并发生成随机数使用的。为什么ThreadLocalRandom要比Random快呢,这是因为Random在生成随机数的时候使用了CAS,但是ThreadLocalRandom却没有使用。

另外ThreadLocalRandom的实例化比较特别,下面简单举例一下。

ThreadLocalRandom threadLocalRandom = ThreadLocalRandom.current();
int a =threadLocalRandom.nextInt(5);

由于是和线程绑定的,所以他也是从当前线程获取的。

SecureRandom

在需要频繁生成随机数,或者安全要求较高的时候,不要使用Random,这个很好理解吧,从我们最开始的介绍中可以知道,Random生成的值其实是可以预测的。

内置两种随机数算法,NativePRNG和SHA1PRNG,看实例化的方法了。通过new来初始化,默认来说会使用NativePRNG算法生成随机数,但是也可以配置-Djava.security参数来修改调用的算法。如果是/dev/[u]random两者之一就是NativePRNG,否则就是SHA1PRNG。

jvm启动参数这样加就好了,-Djava.security=file:/dev/urandom。

当然还可以通过getInstance来初始化对象,有一个参数的,直接传一个算法名就行,如果不存在算法抛异常;另外有两个参数的,第二个参数还可以指定算法程序包。下面来看下实现代码。

SecureRandom secureRandom = new SecureRandom();
SecureRandom secureRandom3 = SecureRandom.getInstance("SHA1PRNG");
SecureRandom secureRandom2 = SecureRandom.getInstance("SHA1PRNG", "SUN");

当然我们使用这个类去生成随机数的时候,一样只需要生成一个实例每次去生成随机数就好了,也没必要每次都重新生成对象。另外,这个类生成随机数,首次调用性能比较差,如果条件允许最好服务启动后先调用一下nextInt()。

另外,实际上SHA1PRNG的性能将近要比NativePRNG的性能好一倍,synchronized的代码少了一半,所以没有特别重的安全需要,尽量使用SHA1PRNG算法生成随机数。

正则表达式的断言

最近想从一段文本文件中找出符合一段指定要求条件的内容,于是想到了使用正则,虽然以前也用过,但是想到断言的类型还是比较多,所以把它整理下来,以后忘了就不用来回找了。

断言分为先行断言和后行断言,而每个又细分为正向和负向的,所以总共正则的断言有以下四种:
(?=pattern):零宽正向先行断言(zero-width positive lookahead assertion)
(?!pattern):零宽负向先行断言(zero-width negative lookahead assertion)
(?<=pattern):零宽正向后行断言(zero-width positive lookbehind assertion)
(?<!pattern):零宽负向后行断言(zero-width negative lookbehind assertion)

这里面的pattern是个正则表达式。断言就和^代表开始,$代表结束,\b代表单词边界一样,断言也有这样的功能。他们只匹配位置,但是在匹配的时候不占用字符,所以叫“零宽”。顺便说一句,使用断言,需要把断言的部分用括号括起来。下面分别介绍每种断言。

(?=pattern) 正向先行断言

首先他是一个位置,紧接着这个位置之后的字符序列需要匹配pattern。下面举个例子就很好理解了。
”a regular expression”这个字符串,要想匹配regular中的re,但不能匹配expression中的re,可以用”re(?=gular)”,该表达式限定了re右边的位置,这个位置之后是gular,但并不消耗gular这些字符,将表达式改为”re(?=gular).”,将会匹配reg,元字符.匹配了g(.匹配任意字符),括号这一部分匹配了e和g之间的位置。

(?!pattern) 负向先行断言

首先他是一个位置,紧接该位置之后的字符序列不能匹配pattern。
对”regex represents regular expression”这个字符串,要想匹配除regex和regular之外的re,可以用”re(?!g)”,该表达式限定了re右边的位置,这个位置后面不是字符g。负向和正向的区别,就在于该位置之后的字符能否匹配括号中的表达式。

(?<=pattern) 正向后行断言

首先他是一个位置,紧接该位置之前的字符序列能够匹配pattern。
例如对”regex represents regular expression”这个字符串,有4个单词,要想匹配单词内部的re,但不匹配单词开头的re,可以用”(?<=\w)re”,单词内部的re,在re前面应该是一个单词字符。之所以叫后行断言,是因为正则表达式引擎在匹配字符串和表达式时,是从前向后逐个扫描字符串中的字符,并判断是否与表达式符合,当在表达式中遇到该断言时,正则表达式引擎需要往字符串前端检测已扫描过的字符,相对于扫描方向是向后的。

(?<!pattern) 负向后行断言

首先他是一个位置,紧接该位置之前的字符序列不能匹配pattern。
例如对”regex represents regular expression”这个字符串,要想匹配单词开头的re,可以用”(?<!\w)re”。单词开头的re,在本例中,也就是指不在单词内部的re,即re前面不是单词字符。当然也可以用”\bre”来匹配。

对于这4个断言的理解,可以从两部分入手:
1.关于先行(lookahead)和后行(lookbehind):正则表达式引擎在执行字符串和表达式匹配时,会从头到尾(从前到后)连续扫描字符串中的字符,设想有一个扫描指针指向字符边界处并随匹配过程移动。先行断言,是当扫描指针位于某处时,引擎会尝试匹配指针还未扫过的字符,先于指针到达该字符,故称为先行。后行断言,引擎会尝试匹配指针已扫过的字符,后于指针到达该字符,故称为后行。
2.关于正向(positive)和负向(negative):正向就表示匹配括号中的表达式,负向表示不匹配。

我们经常用正则表达式来检测一个字符串中包含某个子串,要表示一个字符串中不包含某个字符或某些字符也很容易,用[^…]形式就可以了。要表示一个字符串中不包含某个子串(由字符序列构成)呢?
用[^…]这种形式就不行了,这时就要用到(负向)先行断言或后行断言、或同时使用。
例如判断一句话中包含this,但不包含that。
包含this比较好办,一句话中不包含that,可以认为这句话中每个字符的前面都不是that或每个字符的后面都不是that。正则表达式如下:
^((?<!that).)*this((?<!that).)*$ 或 ^(.(?!that))*this(.(?!that))*$
对于”this is the case”这句话,两个表达式都能够匹配成功,而”note that this is the case”都匹配失败。
在一般情况下,这两个表达式基本上都能够满足要求了。考虑极端情况,如一句话以that开头、以that结尾、that和this连在一起时,上述表达式就可能不胜任了。
如”note thatthis is the case”或者”this is the case, not that”等。
只要灵活运用这几个断言,就很容易解决:
^(.(?<!that))*this(.(?<!that))*$
^(.(?<!that))*this((?!that).)*$
^((?!that).)*this(.(?<!that))*$
^((?!that).)*this((?!that).)*$
这4个正则表达式测试上述的几句话,结果都能够满足要求。

上述4种断言,括号里的pattern本身是一个正则表达式。但对2种后行断言有所限制,在Perl和Python中,这个表达式必须是定长(fixed length)的,即不能使用*、+、?等元字符,如(?<=abc)没有问题,但(?<=a*bc)是不被支持的,特别是当表达式中含有|连接的分支时,各个分支的长度必须相同。之所以不支持变长表达式,是因为当引擎检查后行断言时,无法确定要回溯多少步。java支持?、{m}、{n,m}等符号,但同样不支持*、+字符。Javascript不支持后行断言。

spring-data-redis的一个缺陷导致redis报错(精简版)

原文在这里

为什么要再写个精简版呢,一个是原来的文章偷懒排版太差,另一个是原来的文章代码贴得太多怕大家看的头疼。有同事也遇到这个问题了,搜到了我的文章,表示太长,不想看,好吧,下面是精简版。

本篇只简述问题、原理、解决方案,要看详细心路历程就去看原来的那篇文章吧。

问题

之前用spring-data-redis,调用redis的expire方法的时候,出现了很奇怪的错误。

jedis.exceptions.JedisConnectionException: Unknown reply: 3
org.springframework.data.redis.RedisConnectionFailureException: Unknown reply: 3; nested exception is redis.clients.jedis.exceptions.JedisConnectionException: Unknown reply: 3

就类似的可能这个3是别的什么奇怪的字符都有可能。

原理

spring在做expire处理的时候,不管你用的单位是什么,他最后都会处理成毫秒传给redis,但是这里用的类型是int,是不是很烦,int最大值是2147483647,算一下支持多少天,24.8天。这里就知道原因了,只需要把失效时间设置为小于24.8天就OK了。另一种方案就是别用spring-data-redis去处理。

本文原创于赵伊凡BLOG

JavaCPU的分支预测(Branch Prediction)模型

本文以stackoverflow上Why is it faster to process a sorted array than an unsorted array?为原型,翻译了问题和投票高的回答,并加入了大量补充说明,方便读者理解。

背景
先来看段c++代码,我们用256的模数随机填充一个固定大小的大数组,然后对数组的一半元素求和:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // 随机产生整数,用分区函数填充,以避免出现分桶不均
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data = std::rand() % 256;

    // !!! 排序后下面的Loop运行将更快
    std::sort(data, data + arraySize);

    // 测试部分
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // 主要计算部分,选一半元素参与计算
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data >= 128)
                sum += data;
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

编译并运行:
g++ branch_prediction.cpp
./a.out

在我的macbook上运行结果:
# 1. 取消std::sort(data, data + arraySize);的注释,即先排序后计算
10.218
sum = 312426300000
# 2. 注释掉std::sort(data, data + arraySize);即不排序,直接计算
29.6809
sum = 312426300000

由此可见,先排序后计算,运行效率有进3倍的提高。

为保证结论的可靠性, 我们再用java来测一遍:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data >= 128)
                    sum += data;
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

在intellij idea中运行结果:
# 1. 先排序后计算
5.549553
sum = 155184200000
# 2. 不排序直接结算
15.527867
sum = 155184200000

也有三倍左右的差距。且java版要比c++版整体快近乎1倍?这应该是编译时用了默认选项,gcc优化不够的原因,后续再调查这个问题。

问题的提出
以上代码在数组填充时已经加入了分区函数,充分保证填充值的随机性,计算时也是按一半的元素来求和,所以不存在特例情况。而且,计算也完全不涉及到数据的有序性,即数组是否有序理论上对计算不会产生任何作用。在这样的前提下,为什么排序后的数组要比未排序数组运行快3倍以上?

分析
想象一个铁路分叉道口。

为了论证此问题,让我们回到19世纪,那个远距离无线通信还未普及的年代。你是铁路交叉口的扳道工。当听到火车快来了的时候,你无法猜测它应该朝哪个方向走。于是你叫停了火车,上前去问火车司机该朝哪个方向走,以便你能正确地切换铁轨。

要知道,火车是非常庞大的,切急速行驶时有巨大的惯性。为了完成上述停车-问询-切轨的一系列动作,火车需耗费大量时间减速,停车,重新开启。

既然上述过车非常耗时,那是否有更好的方法?当然有!当火车即将行驶过来前,你可以猜测火车该朝哪个方向走。

如果猜对了,它直接通过,继续前行。
如果猜错了,车头将停止,倒回去,你将铁轨扳至反方向,火车重新启动,驶过道口。
如果你不幸每次都猜错了,那么火车将耗费大量时间停车-倒回-重启。如果你很幸运,每次都猜对了呢?火车将从不停车,持续前行!

上述比喻可应用于处理器级别的分支跳转指令里:

原程序:
if (data >= 128)
sum += data;

汇编码:
cmp edx, 128
jl SHORT $LN3@main
add rbx, rdx
$LN3@main:

让我们回到文章开头的问题。现在假设你是处理器,当看到上述分支时,当你并不能决定该如何往下走,该如何做?只能暂停运行,等待之前的指令运行结束。然后才能继续沿着正确地路径往下走。

要知道,现代编译器是非常复杂的,运行时有着非常长的pipelines, 减速和热启动将耗费巨量的时间。

那么,有没有好的办法可以节省这些状态切换的时间呢?你可以猜测分支的下一步走向!

如果猜错了,处理器要flush掉pipelines, 回滚到之前的分支,然后重新热启动,选择另一条路径。
如果猜对了,处理器不需要暂停,继续往下执行。
如果每次都猜错了,处理器将耗费大量时间在停止-回滚-热启动这一周期性过程里。如果侥幸每次都猜对了,那么处理器将从不暂停,一直运行至结束。

上述过程就是分支预测(branch prediction)。虽然在现实的道口铁轨切换中,可以通过一个小旗子作为信号来判断火车的走向,但是处理器却无法像火车那样去预知分支的走向–除非最后一次指令运行完毕。

那么处理器该采用怎样的策略来用最小的次数来尽量猜对指令分支的下一步走向呢?答案就是分析历史运行记录: 如果火车过去90%的时间都是走左边的铁轨,本次轨道切换,你就可以猜测方向为左,反之,则为右。如果在某个方向上走过了3次,接下来你也可以猜测火车将继续在这个方向上运行…

换句话说,你试图通过历史记录,识别出一种隐含的模式并尝试在后续铁道切换的抉择中继续应用它。这和处理器的分支预测原理或多或少有点相似。

大多数应用都具有状态良好的(well-behaved)分支,所以现代化的分支预测器一般具有超过90%的命中率。但是面对无法预测的分支,且没有识别出可应用的的模式时,分支预测器就无用武之地了。

关于分支预测期,可参考维基百科相关词条“Branch predictor” article on Wikipedia..

文首导致非排序数组相加耗时显著增加的罪魁祸首便是if逻辑:
if (data >= 128)
sum += data;

注意到data数组里的元素是按照0-255的值被均匀存储的(类似均匀的分桶)。数组data有序时,前面一半元素的迭代将不会进入if-statement, 超过一半时,元素迭代将全部进入if-statement.

这样的持续朝同一个方向切换的迭代对分支预测器来说是非常友好的,前半部分元素迭代完之后,后续迭代分支预测器对分支方向的切换预测将全部正确。

简单地分析一下:有序数组的分支预测流程:
T = 分支命中
N = 分支没有命中

data[] = 0, 1, 2, 3, 4, … 126, 127, 128, 129, 130, … 250, 251, 252, …
branch = N N N N N … N N T T T … T T T …

= NNNNNNNNNNNN … NNNNNNNTTTTTTTTT … TTTTTTTTTT (非常容易预测)

无序数组的分支预测流程:

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, …
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N …

= TTNTTTTNTNNTTTN … (完全随机–无法预测)

在本例中,由于data数组元素填充的特殊性,决定了分支预测器在未排序数组迭代过程中将有50%的错误命中率,因而执行完整个sum操作将会耗时更多。

优化
利用位运算取消分支跳转。基本知识:

|x| >> 31 = 0 # 非负数右移31为一定为0
~(|x| >> 31) = -1 # 0取反为-1

-|x| >> 31 = -1 # 负数右移31为一定为0xffff = -1
~(-|x| >> 31) = 0 # -1取反为0

-1 = 0xffff
-1 & x = x # 以-1为mask和任何数求与,值不变

故分支判断可优化为:
int t = (data – 128) >> 31; # statement 1
sum += ~t & data; # statement 2

分析:
data < 128, 则statement 1值为: 0xffff = -1, statement 2等号右侧值为: 0 & data == 0;
data >= 128, 则statement 1值为: 0, statement 2等号右侧值为: ~0 & data == -1 & data == 0xffff & data == data;

故上述位运算实现的sum逻辑完全等价于if-statement, 更多的位运算hack操作请参见bithacks.

若想避免移位操作,可以使用如下方式:
int t=-((data>=128)); # generate the mask
sum += ~t & data; # bitwise AND

结论

使用分支预测: 是否排序严重影响performance
使用bithack: 是否排序对performance无显著影响
这个例子告诉给我们启示: 在大规模循环逻辑中要尽量避免数据强依赖的分支(data-dependent branching).

补充知识

Pipeline

先简单说明一下CPU的instruction pipeline(指令流水线),以下简称pipeline。 Pipieline假设程序运行时有一连串指令要被运行,将程序运行划分成几个阶段,按照一定的顺序并行处理之,这样便能够加速指令的通过速度。

绝大多数pipeline都由时钟频率(clock)控制,在数字电路中,clock控制逻辑门电路(logical cicuit)和触发器(trigger), 当受到时钟频率触发时,触发器得到新的数值,并且逻辑门需要一段时间来解析出新的数值,而当受到下一个时钟频率触发时触发器又得到新的数值,以此类推。

而借由逻辑门分散成很多小区块,再让触发器链接这些小区块组,使逻辑门输出正确数值的时间延迟得以减少,这样一来就可以减少指令运行所需要的周期。 这对应Pipeline中的各个stages。

一般的pipeline有四个执行阶段(execuate stage): 读取指令(Fetch) -> 指令解码(Decode) -> 运行指令(Execute) -> 写回运行结果(Write-back).

分支预测器

分支预测器是一种数字电路,在分支指令执行前,猜测哪一个分支会被执行,能显著提高pipelines的性能。

条件分支通常有两路后续执行分支,not token时,跳过接下来的JMP指令,继续执行, token时,执行JMP指令,跳转到另一块程序内存去执行。

为了说明这个问题,我们先考虑如下问题。

没有分支预测器会怎样?

加入没有分支预测器,处理器会等待分支指令通过了pipeline的执行阶段(execuate stage)才能把下一条指令送入pipeline的fetch stage。

这会造成流水线停顿(stalled)或流水线冒泡(bubbling)或流水线打嗝(hiccup),即在流水线中生成一个没有实效的气泡。

Stream hiccup现象在早期的RISC体系结构处理器中常见。

有分支预测期的pipeline

我们来看分支预测器在条件分支跳转中的应用。条件分支通常有两路后续执行分支,not token时,跳过接下来的JMP指令,继续执行, token时,执行JMP指令,跳转到另一块程序内存去执行。

加入分支预测器后,为避免pipeline停顿(stream stalled),其会猜测两路分支哪一路最有可能执行,然后投机执行,如果猜错,则流水线中投机执行中间结果全部抛弃,重新获取正确分支路线上的指令执行。可见,错误的预测会导致程序执行的延迟。

由前面可知,Pipeline执行主要涉及Fetch, Decode, Execute, Write-back几个stages, 分支预测失败会浪费Write-back之前的流水线级数。现代CPU流水线级数非常长,分支预测失败可能会损失20个左右的时钟周期,因此对于复杂的流水线,好的分支预测器非常重要。

常见的分支预测器

  • 静态分支预测器

静态分支预测器有两个解码周期,分别评价分支,解码。即在分支指令执行前共经历三个时钟周期。

  • 双模态预测器(bimodal predictor)
    也叫饱和计数器,是一个四状态状态机. 四个状态对应两个选择: token, not token, 每个选择有两个状态区分强弱:strongly,weakly。分别是Strongly not takenWeakly not taken,Weakly taken, Strongly taken

状态机工作原理图如下:

4166840329-57da67c5b5303_articlex

图左边两个状态为不采纳(not token),右边两个为采纳(token)。由not token到token中间有两个渐变状态。由红色到绿色翻转需要连续两次分支选择。

技术实现上可用两个二进制位来表示,00, 01, 10, 11分别对应strongly not token, weakly not token, weakly token, strongly token。 一个判断两个分支预测规则是否改变的简单方法便是判断这个二级制状态高位是否跳变。高位从0变为1, 强状态发生翻转,则下一个分支指令预测从not token变为token,反之亦然。

据评测,双模态预测器的正确率可达到93.5%。预测期一般在分支指令解码前起作用。

其它常见分支预测器如两级自适应预测器,局部/全局分支预测器,融合分支预测器,Agree预测期,神经分支预测器等。

本文发表自赵伊凡BLOG

转载并发编程网 – ifeve.com

使用七牛云为wordpress站点免费加速

如果你比较关注本站的话,可以发现本站的速度相比以前有了一些提升,其实还是挺慢,主要wordpress里面有一些统计的东西需要访问美国的网站,导致加速速度没有办法特别快。但是相比以前好了很多。

这里的一个原因就是由于本站现在所有的静态都放到了七牛云上。

前端的同学可以谷歌浏览器F12看到,我这里加载的很多图片地址的域名,是ocv8什么什么开头的的一串域名,这个就是七牛提供的一个域名。

先说说为什么选择七牛,这里也不是打广告,我也没收钱,就是因为七牛提供长期的免费额度。10GB的免费存储空间,每月国内10GB的免费下载流量,10GB的免费海外下载流量,100万次免费GET请求(调用七牛API),10万次免费PUT请求(调用七牛API)。这免费额度已经算是相当高了,对于我们普通个人站来说,绝对够用。

这里我们只是为wordpress加速的话,主要需要关注国内下载流量、PUT次数,如果站外多的话,还可以关心下海外的下载流量。如果流量不够的话,可以付费购买,用多少扣多少,如果流量真能用到那么多,应该也不会在意这点小钱了吧,其实很便宜。

接下来说下怎么用。很简单,跟着下面步骤走,都能会。

①首先去七牛注册一个帐号,然后登录上去。进入开发中平台。
②选择添加资源(七牛可能会改版,但是内容应该还是一样的),找到七牛官方资源的,“对象存储”,然后点击立即添加按钮。
③进去新的页面之后,有个资源名要填,随便按要求填你的资源名就好,存储地区按照喜好选个吧,我在北京所以选了个华北的。访问控制选择公开。接下来确认创建即可。
④这时候在资源列表里就能看到你的资源了。在测试域名一栏能看到你的域名,把这个记下来。包括空间容量、API调用次数等。要看具体统计可以点击“数据统计”按钮。
⑤内容管理里面是你所有的文件,目前肯定还没有。然后点返回之后一个“镜像存储”的tab,点击进入。这里有个镜像源,填写你站点的域名,需要加http,然后下面勾选使用默认robots.txt文件(这个是为了不让搜索引擎收录图片,对你的站点SEO有帮助),点击保存设置即可。剩下的就不用管了,接下来我们去wordpress后台操作。
⑥在wordpress插件里搜索WP Super Cache,这里推荐这个插件而不是七牛推荐的插件,这个会比较简单些。搜索出来后安装、启用。
⑦接下来去WP Super Cache的设置页面进行配置。在设置页面点击CDN标签,勾选开启CDN支持,并在Off-site URL一栏填写刚刚七牛给我们的测试域名,然后包含目录填写“wp-content,wp-includes”,应该默认就是填好的。后面的不用管,我们最后再说。填完直接点击保存修改就好。这时候我们的CDN就已经弄好啦。
⑧第一次打开页面会感觉有点慢,这是因为第一次七牛需要去你网站同步静态数据,在第二次再访问这些页面的时候就好了。

到这里,我们就已经完成七牛CDN的免费配置了。可能过两天七牛会给你打电话,你就说个人站,用不了多少流量什么的,就完事了,他就是个回访,很友好。

最后我们再说说,怎么把这个该死的超长域名替换掉。想要替换必须得是在中国备案了的域名,如果没有备案,不好意思,替换不来,所以我的也就没有替换。其实没啥关系。

想要使用自己的域名,也很简单,在七牛添加一个“融合 CDN 加速”的资源,直接填写你的加速的普通域名就可以了。接下来,你需要把你的这个静态域名的CNAME记录指向七牛给你的域名下,这个七牛都有详细的引导。最后再去你wordpress里的插件设置那,CDN一栏,附加 CNAME 记录填写你自己的域名就可以了。这个会覆盖上面的域名配置。

到此我们就可以成功使用七牛CDN为我们的站点加速了。看了下速度,都在个位毫秒以内,速度很快。另外需要提醒一下大家的是,有时候由于修改了哪里的配置,或者安装了什么插件、升级什么的情况,可能导致域名又用回我们自己的站点了,这时候也可以到插件的设置页面,通用一栏,缓存功能还是启用,重新点击一下更新按钮就可以了。

本文原创于赵伊凡BLOG转载请注明出处。

现在我们就可以愉快的使用七牛CDN啦。不紧加速,还能省流量,多好~