文档章节

Java 正则表达式 StackOverflowError 问题及其优化

大数据之路
 大数据之路
发布于 2015/08/02 05:05
字数 2697
阅读 1758
收藏 18

正则可以看做一门 DSL,但它却应用极其广泛,可以轻松解决很多场景下的字符串匹配、筛选问题。同时呢有句老话:

“ 如果你有一个问题,用正则表达式解决,那么你现在就有两个问题了。”

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

今天我们就来聊聊 Java 正则表达式 StackOverflowError 的问题及其一些优化点。

1、问题

最近,有同事发现一段正则在本地怎么跑都没问题,但是放到 Hadoop 集群上总会时不时的抛 StackOverflowError 。

代码我先简化下:

package java8test;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Test {

	public static void main(String[] args) {

		final String TEST_REGEX = "([=+]|[\\s]|[\\p{P}]|[A-Za-z0-9]|[\u4E00-\u9FA5])+";
		StringBuilder line = new StringBuilder();
		System.out.println("++++++++++++++++++++++++++++++");
		for (int i = 0; i < 10; i++) {
			line.append(
					"http://hh.ooxx.com/ershoufang/?PGTID=14366988648680=+.7342327926307917&ClickID=1&key=%2525u7261%2525u4E39%2525u5BCC%2525u8D35%2525u82B1%2525u56ED&sourcetype=1_5");
			line.append(
					"http://wiki.corp.com/index.php?title=Track%E6%A0%87%E5%87%86%E6%97%A5%E5%BF%97Hive%E8%A1%A8-%E5%8D%B3%E6%B8%85%E6%B4%97%E5%90%8E%E7%9A%84%E6%97%A5%E5%BF%97");
			line.append(
					"http://www.baidu.com/s?ie=UTF-8&wd=58%cd%ac%b3%c7%b6%fe%ca%d6%b3%b5%b2%e2%ca%d4%ca%fd%be%dd&tn=11000003_hao_dg");
			line.append("http://cs.ooxx.com/yewu/?key=城&cmcskey=的设计费开始低&final=1&jump=1&specialtype=gls");
			line.append(
					"http%3A%2F%2Fcq.ooxx.com%2Fjob%2F%3Fkey%3D%25E7%25BD%2591%25E4%25B8%258A%25E5%2585%25BC%25E8%2581%258C%26cmcskey%3D%25E7%25BD%2591%25E4%25B8%258A%25E5%2585%25BC%25E8%2581%258C%26final%3D1%26jump%3D2%26specialtype%3Dgls%26canclequery%3Disbiz%253D0%26sourcetype%3D4");
		}
		line.append(" \001 11111111111111111111111111");
		Pattern p_a = null;
		try {
			p_a = Pattern.compile(TEST_REGEX);
			Matcher m_a = p_a.matcher(line);
			while (m_a.find()) {
				String a = m_a.group();
				System.out.println(a);
			}
		} catch (Exception e) {
			// TODO: handle exception
		}

		System.out.println("line size: " + line.length());
	}
}

执行之后的结果是:

++++++++++++++++++++++++++++++
Exception in thread "main" java.lang.StackOverflowError
	at java.util.regex.Pattern$Loop.match(Unknown Source)
	at java.util.regex.Pattern$GroupTail.match(Unknown Source)
	at java.util.regex.Pattern$BranchConn.match(Unknown Source)
	at java.util.regex.Pattern$CharProperty.match(Unknown Source)
......

起初这个问题是从集群上抛出来的,大家可以看到这个异常有两个特点:

(1)不可用 Exception 捕获,因为 Error 直接继承自 Throwable 而非 Exception,所以即使你要捕获也应当捕获 Error。

(2)另外一点是大家可以看到抛出的错误并没有指明行号,当这段代码混在一个数百行的工具类,有数十条类似的正则的时候,无疑给定位问题带来了难度,这就需要我们能有一定的单元测试能力。

注:

(1)如果你的环境没有抛出上述错误,尝试调大 for 循环的次数或者指定 jvm 参数:-Xss1k

(2)如果你还不明白 StackOverflowError 是什么含义,可以参考上一篇文章:JVM 运行时数据区简介

2、问题分析

正则表达式引擎分成两类,一类称为DFA(确定性有穷自动机),另一类称为NFA(非确定性有穷自动机)。两类引擎要顺利工作,都必须有一个正则式和一个文本串。DFA捏着文本串去比较正则式,看到一个子正则式,就把可能的匹配串全标注出来,然后再看正则式的下一个部分,根据新的匹配结果更新标注。而NFA是捏着正则式去比文本,吃掉一个字符,就把它跟正则式比较,匹配就记下来,然后接着往下干。一旦不匹配,就把刚吃的这个字符吐出来,一个个的吐,直到回到上一次匹配的地方。 

     DFA与NFA机制上的不同带来5个影响: 

     1. DFA 对于文本串里的每一个字符只需扫描一次,比较快,但特性较少;NFA要翻来覆去吃字符、吐字符,速度慢,但是特性丰富,所以反而应用广泛,当今主要的正则表达式引擎,如Perl、Ruby、Python的re模块、Java和.NET的regex库,都是NFA的。 

     2. 只有NFA才支持lazy和backreference等特性; 

     3. NFA急于邀功请赏,所以最左子正则式优先匹配成功,因此偶尔会错过最佳匹配结果;DFA则是“最长的左子正则式优先匹配成功”。 

     4. NFA缺省采用greedy量词; 

     5. NFA可能会陷入递归调用的陷阱而表现得性能极差。 

在使用正则表达式的时候,底层是通过递归方式调用执行的,每一层的递归都会在栈线程的大小中占一定内存,如果递归的层次很多,就会报出stackOverFlowError异常。所以在使用正则的时候其实是有利有弊的。

Java程序中,每个线程都有自己的Stack Space。这个Stack Space不是来自Heap的分配。所以Stack Space的大小不会受到-Xmx和-Xms的影响,这2个JVM参数仅仅是影响Heap的大小。Stack Space用来做方法的递归调用时压入Stack Frame。所以当递归调用太深的时候,就有可能耗尽Stack Space,爆出StackOverflow的错误。Stack Space的大小随着OS,JVM以及环境变量的大小而发生变化。一般说来默认的大小是512K。在64位的系统中,这个Stack Space值会更大。一般说来,Stack Space为128K是够用的。这时你说需要做的就是观察。如果你的程序没有爆出StackOverflow的错误,可以使用-Xss来调整Stack Space的大小为128K。(eg:-Xss128K)

文章开头的问题可以简单理解为方法的嵌套调用层次太深,上层的方法栈一直得不到释放,导致栈空间不足。

下面我们要做的就是了解一些正则性能的优化点,规避这种深层次的递归调用。

3、Java 正则的一些优化点

3.1 Pattern.compile() 预编译表达式

如果在程序中多次使用同一个正则表达式,一定要用Pattern.compile()编译,代替直接使用Pattern.matches()。如果一次次对同一个正则表达式使用Pattern.matches(),例如在循环中,没有编译的正则表达式消耗比较大。因为matches()方法每次都会预编译使用的表达式。另外,记住你可以通过调用reset()方法对不同的输入字符串重复使用Matcher对象。

3.2 留意选择(Beware of alternation)

类似“(X|Y|Z)”的正则表达式有降低速度的坏名声,所以要多留心。首先,考虑选择的顺序,那么要将比较常用的选择项放在前面,因此它们可以较快被匹配。另外,尝试提取共用模式;例如将“(abcd|abef)”替换为“ab(cd|ef)”。后者匹配速度较快,因为NFA会尝试匹配ab,如果没有找到就不再尝试任何选择项。(在当前情况下,只有两个选择项。如果有很多选择项,速度将会有显著的提升。)选择的确会降低程序的速度。在我的测试中,表达式“.*(abcd|efgh|ijkl).*”要比调用String.indexOf()三次——每次针对表达式中的一个选项——慢三倍。

3.3 减少分组与嵌套

如果你实际并不需要获取一个分组内的文本,那么就使用非捕获分组。例如使用“(?:X)”代替“(X)”。

总结下来就是:减少分支选择、减少捕获嵌套、减少贪婪匹配

4、解决方案

4.1 临时工方案

try...catch.../增加-Xss,治标不治本,不推荐。

4.2 优化正则才是王道

4.2.1 语法层面优化

根据 3.2 提到的,我们这样优化下:

final String TEST_REGEX = "([=+\\s\\p{P}A-Za-z0-9\u4E00-\u9FA5])+";

经测试,JVM 参数不变的情况下,for 循环 100w 次直到 OOM 了都不会再发生文章开头的栈溢出的问题了。

4.2.2 业务逻辑层面优化

由于我不清楚作者的业务场景,不好做业务优化,总的原则是当你的正则太复杂的时候,可以考虑逻辑拆分,或者部分不走正则,如果把正则当做万能工具可能会得不偿失。

总结:在字符串查找与匹配领域,正则可以说几乎是“万能”的,但是许多场景下,它的代价不容小觑,如何写出高效率、可维护的正则或者怎么能避开正则都是值得咱们思考的问题。

5、NFA引擎正则性能优化Tips

  • 1. 优先选择最左端的匹配结果

  • 2.标准量词优先匹配

比如'.*[0-9][0-9]' 来匹配字符串"abcd12efghijklmnopqrstuvw",这时候的匹配方式是‘.*’先匹配了整行,但是不能满足之后的两个数字的匹配,所以‘.*’就退还一个字符‘w’,还是无法匹配,继续退还一个‘v’,循环退还字符到‘2’发现匹配了一个,但是还是无法匹配两个数字,所以继续退还‘1’

  • 3.谨慎使用捕获性括号(),选择使用非捕获性括号(?:expression)

捕获性括号需要消耗一部分内存

  • 4.使用字符组代替分支(替换)条件

例如用[a-d] 代替 a|b|c|d避免不必要的回溯

  • 5.不要滥用字符组(单个字符时不要用字符组)

\. 代替 [.]

  • 6.使用锚点^ $ \b 加速定位

  • 7.从两次中提取必须元素

a{2,4} 写成 aa{0,2}

  • 8.提取多选结构开头的相同字符

the|this 改成th(?:e|is)

  • 9.选择字符串中最常出现的字符串放到分支最前面

  • 10.能懒则懒,不要贪婪

在 * + {m,n}后面加上问好?就会变成非贪婪模式

总结:引用CFC4N大牛的一句话 滥用. 点号  * 星号  +加号  ()括号 是不环保,不负责任的做法 !

  • 11.简单字符串处理应避免使用正则表达式

Refer:

[1] 关于Java正则引起的StackOverFlowError问题以及解决方案

http://blog.csdn.net/qq522935502/article/details/8161273

[2] Java正则与栈溢出

http://daimojingdeyu.iteye.com/blog/385304

[3] 优化Java中的正则表达式

http://blog.csdn.net/mydeman/article/details/1800636

[4] 从一个正则表达式造成的StackOverflowError说起

http://ren.iteye.com/blog/1828562

[5] 正则表达式(三):Unicode诸问题(下)

http://www.infoq.com/cn/news/2011/03/regular-expressions-unicode-2

http://www.infoq.com/cn/author/%E4%BD%99%E6%99%9F

[6] StackOverflowError when matching large input using RegEx

http://stackoverflow.com/questions/15082010/stackoverflowerror-when-matching-large-input-using-regex

[7] try/catch on stack overflows in java?

http://stackoverflow.com/questions/2535723/try-catch-on-stack-overflows-in-java

[8] Java正则达式引起死循环问题解决办法

http://blog.csdn.net/shixing_11/article/details/5997567

[9] JAVA 正则表达式的溢出问题 及不完全解决方案

http://www.blogjava.net/roymoro/archive/2011/04/28/349163.html

[10] NFA引擎正则优化TIPS、Perl正则技巧及正则性能评测方法  

http://danqingdani.blog.163.com/blog/static/18609419520144523853586/

[11] Java正则引发的思考

http://blogread.cn/it/article/5982?f=wb

[12] 进阶正则表达式

http://www.barretlee.com/blog/2014/01/18/cb-how-regular-expressions-work/

[13] 一个由正则表达式引发的血案

http://bit.ly/2vlKfIf

© 著作权归作者所有

共有 人打赏支持
大数据之路
粉丝 1543
博文 516
码字总数 343694
作品 0
武汉
架构师
私信 提问
编写高性能 Java 代码的最佳实践

摘要:本文首先介绍了负载测试、基于APM工具的应用程序和服务器监控,随后介绍了编写高性能Java代码的一些最佳实践。最后研究了JVM特定的调优技巧、数据库端的优化和架构方面的调整。以下是译...

这篇文章
06/20
0
0
怎样写出高性能的 Java 代码?

在这篇文章中,我们将讨论几个有助于提升Java应用程序性能的方法。我们首先将介绍如何定义可度量的性能指标,然后看看有哪些工具可以用来度量和监控应用程序性能,以及确定性能瓶颈。 我们还...

程序员之家_
08/24
0
0
java正则表达式对字符串的操作

学习java正则表达式的都知道,它的重要性;但同时也了解它的难度和复杂性。所以为了加深我们对它的了解。我举了几个例子: 例子1、 查找以Java开头,任意结尾的字符串 Pattern pattern = Patt...

goqin
2012/06/29
0
0
关于java中split的使用

之前在http://shukuiyan.iteye.com/blog/507915文中已经叙述过这个问题,但是最近一次笔试中居然有碰到了这个知识点,而且还做错了,囧!学艺不精啊。题目大概是这样的: Java代码 String s...

墨梅
2014/04/28
0
0
java.util.regex Pattern 正则

/**String 中 replaceAll(),matches(),split() 等方法,都是调用Pattern中的方法。学习了,瞬间觉得Pattern强大了 public String replaceAll(String regex, String replacement) {return Pat......

happycode
2014/04/02
0
1

没有更多内容

加载失败,请刷新页面

加载更多

Java程序员可知为何公司宁花25K重新招人,也不花20K留住老员工?

身在职场,经常会暗自打听同事工资,尤其是得知身边新入职同事的工资居然比自己高,还高出一大截时,心里自然很不平衡,一心想要离职。 那么,为什么公司宁愿花高价招聘新员工也不愿意给老员...

Java填坑路
9分钟前
2
0
如何通俗地解释什么是网桥?

吴伟祥
12分钟前
1
0
阿里云文件存储(NAS)助力业务系统承载双十一尖峰流量

2018天猫双11全球狂欢节,全天成交额再次刷新纪录达到2135亿元,其中总成交额在开场后仅仅用了2分05秒即突破100亿元,峰值的交易量达到惊人的高度,背后离不开阿里云大数据计算和存储能力的支...

阿里云云栖社区
13分钟前
0
0
【windows 找不到“\\192.168.X.X”,请检查拼写是否正确】错误&139端口和445端口区别

今天像往常一样,通过共享盘访问其他主机时,却出现如题的错误,百思不得其解,毕竟没有改动什么配置啊,地址也没输错啊。 然后就在网上看到了一篇博客,才想起来上周末因为考虑到安全问题,...

fang_faye
14分钟前
0
0
示例Express中路由规则及获取请求参数

本次给大家分享一篇基于express中路由规则及获取请求参数的方法,写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 express中常见的...

前端攻城小牛
17分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部