Skip to main content

函数式编程介绍

最近在研究JDK8的新特性,一直熟悉面向过程和面向对象的编程模式,突然发现没怎么了解过函数式编程,于是最近乘这个机会,研究了一下函数式编程。

bg2012040601

定义
简单说,”函数式编程”是一种”编程范式”(programming paradigm),也就是如何编写程序的方法论。
它属于”结构化编程”的一种,主要思想是把运算过程尽量写成一系列嵌套的函数调用。函数,大家应该都了解,就是一个功能逻辑单元,它没有特定的属性和归属。
函数式编程(FP)的核心就是一切都是函数,也就是说”活“的不再是对象,而是函数。函数本质是x到f(x)的变换,所以FP的元素就两种,一种是函数(”pure function“的概念,表现为命名句柄或表达式,所以独立性->并发性),一种是状态(immutable,因为只要发生变换,就通过函数表现)。 函数的独立性,导致了我们没法记录函数内部运行的状态,怎么解决呢,把状态放在参数里呗,然后用递归来搞定。

函数式编程的特点

    函数式编程的三大特性:
  • immutable data 不可变数据:像Clojure一样,默认上变量是不可变的,如果你要改变变量,你需要把变量copy出去修改。这样一来,可以让你的程序少很多Bug。因为,程序中的状态不好维护,在并发的时候更不好维护。(你可以试想一下如果你的程序有个复杂的状态,当以后别人改你代码的时候,是很容易出bug的,在并行中这样的问题就更多了)
  • first class functions:这个技术可以让你的函数就像变量一样来使用。也就是说,你的函数可以像变量一样被创建,修改,并当成变量一样传递,返回或是在函数中嵌套函数。这个有点像Javascript的Prototype(参看Javascript的面向对象编程)
  • 尾递归优化:我们知道递归的害处,那就是如果递归很深的话,stack受不了,并会导致性能大幅度下降。所以,我们使用尾递归优化技术——每次递归时都会重用stack,这样一来能够提升性能,当然,这需要语言或编译器的支持。Python就不支持。
    函数式编程的几个技术
  • map & reduce :这个技术不用多说了,函数式编程最常见的技术就是对一个集合做Map和Reduce操作。这比起过程式的语言来说,在代码上要更容易阅读。(传统过程式的语言需要使用for/while循环,然后在各种变量中把数据倒过来倒过去的)这个很像C++中的STL中的foreach,find_if,count_if之流的函数的玩法。
  • pipeline:这个技术的意思是,把函数实例成一个一个的action,然后,把一组action放到一个数组或是列表中,然后把数据传给这个action list,数据就像一个pipeline一样顺序地被各个函数所操作,最终得到我们想要的结果。
  • recursing 递归 :递归最大的好处就简化代码,他可以把一个复杂的问题用很简单的代码描述出来。注意:递归的精髓是描述问题,而这正是函数式编程的精髓。
  • currying:把一个函数的多个参数分解成多个函数, 然后把函数多层封装起来,每层函数都返回一个函数去接收下一个参数这样,可以简化函数的多个参数。在C++中,这个很像STL中的bind_1st或是bind2nd。
  • higher order function 高阶函数:所谓高阶函数就是函数当参数,把传入的函数做一个封装,然后返回这个封装函数。现象上就是函数传进传出,就像面向对象对象满天飞一样。
    函数式编程的优势
  • 代码简洁,开发快速。函数式编程大量使用函数,减少了代码的重复,因此程序比较短,开发速度较快
  • 接近自然语言,易于理解。函数式编程的自由度很高,可以写出很接近自然语言的代码。
    比如表达式(1 + 2) * 3 – 4,如果用函数式编程格式,如下:

    add(1,2).multiply(3).subtract(4)

    它更接近我们人的表达方式,更容易理解。其实好的程序是人更容易理解,而不是让机器更容易。
  • parallelization 并行:所谓并行的意思就是在并行环境下,各个线程之间不需要同步或互斥。
  • determinism 确定性:所谓确定性的意思就是像数学那样 f(x) = y ,这个函数无论在什么场景下,都会得到同样的结果,这个我们称之为函数的确定性。而不是像程序中的很多函数那样,同一个参数,却会在不同的场景下计算出不同的结果。所谓不同的场景的意思就是我们的函数会根据一些运行中的状态信息的不同而发生变化。因此函数式编程不依赖、也不会改变外界的状态,只要给定输入参数,返回的结果必定相同。每一个函数都可以被看做独立单元,很有利于进行单元测试(unit testing)和除错(debugging),以及模块化组合。

参考
https://en.wikipedia.org/wiki/Programming_paradigm
http://coolshell.cn/articles/10822.html
http://www.ruanyifeng.com/blog/2012/04/functional_programming.html

高效的字符串匹配器

使用场景

String html="......<script type="text/javascript.........</script>"";

StringMatcher matcher = new StringMatcher("</script>");


for(int i=0;i<html.length;i++){

    matcher.push(html.charAt(i));

    if(matcher.isTarget()){

        //do something

    }

}
/**
 * StringMathcer是一个利用了循环链表原理的数组型字符串匹配器.
 * 
 * Matcher主要是在字符串处理中匹配字串,原理是把字符push到匹配器中 进行比较,匹配器不提供remove(int index)方法,只能放或者清空。
 * 用单纯的数组进行匹配时,很容易地,数组会满而导致大量的元素移动操作, 代价交代,用循环链表只需修改两次指针位置即可。
 * 为了更多的减少条件判断,在构造方法中就已经让数组处于满的状态。
 * 
 * @author maoanapex88@163.com
 * 
 */
public class StringMatcher {
	char[] cache;
	int start;
	String target;

	public StringMatcher(String s) {
		this.target = s;
		int length = s.length();
		cache = new char[length];
		start = 0;
		for (int i = 0; i < cache.length; i++)
			cache[i] = 128;
	}

	public void push(char c) {
		cache[start++] = c;
		start %= cache.length;
	}

	public boolean isTarget() {
		if (cache[(start + 1) % cache.length] == 128)
			return false;
		int index = 0;
		for (int i = start; i < cache.length; i++, index++)
			if (cache[i] != target.charAt(index))
				return false;
		for (int i = 0; i < start; i++, index++)
			if (cache[i] != target.charAt(index))
				return false;
		return true;
	}

	public boolean isTarget(boolean ignoreCase) {
		if (cache[(start + 1) % cache.length] == 128)
			return false;
		int index = 0;
		for (int i = start; i < cache.length; i++, index++) {
			if (ignoreCase && cache[i] != target.charAt(index)
					&& cache[i] - target.charAt(index) != 32
					&& cache[i] - target.charAt(index) != -32)
				return false;
		}
		for (int i = 0; i < start; i++, index++) {
			if (ignoreCase && cache[i] != target.charAt(index)
					&& cache[i] - target.charAt(index) != 32
					&& cache[i] - target.charAt(index) != -32)
				return false;
		}
		return true;
	}

	/**
	 * clear
	 */
	public void clear() {
		start = 0;
		for (int i = 0; i < cache.length; i++)
			cache[i] = 128;
	}

	/**
	 * @return
	 */
	public int length() {
		return target.length();
	}
}

为Java实现LinkedArray

前面的文章中,我们通过分析java的排序,顺便分析了ArrayList和LinkedList,这两个各有优缺点,那么我们能不能折合两者优点呢?我思考了一个问题-信息率,也就是为了存一个我希望存的对象而额外耗费的空间,

  • 对于ArrayList,每个数组的下标对于的地址单元存量一个对象指针,1:1的存,但是问题是在于增量导致的数组增长和整体数组的copy实在太损耗性能
  • 对于LinkedList,每一个链表节点,要额外增加一个前续来维持链表结构,1:2,事实JDK的LinkedList是prev和next都记录的,是双向链表,为1:3

既然有这个问题,我们可不可以增加信息率来提高些平均性能呢?如下

  • ArrayList: [a0,a1,a2,…,an]
  • LinkedList:  a0<->a1<->a2<->…..an
  • LinkedArray: [a0,a1,a2,….ai]<->[ai+1,….aj]<—>[aj+1,………an]

LinkedArray是用链表为基础,但是链表的节点是一个数组,这样节点的信息率上升为n:n+2,(n是数组的大小),这样可以这种一些两者的性能。

package net.sourceforge.util;

import java.util.AbstractList;
/**
 * 
 * @author maoanapex88@163.com
 * 
 * @param <E>
 */
public class LinkedArray<E> extends AbstractList<E> {
	public static final int DEFAULT_ARRAY_SIZE=10;
	public static final int DEFAULT_CATACITY=10;
	
	private int arraySize=DEFAULT_ARRAY_SIZE;
	private int size;
	
	private transient ListNode<E> head,tail;
	
	public LinkedArray(){
		this(DEFAULT_CATACITY,DEFAULT_ARRAY_SIZE);
	}
	public LinkedArray(int initialCapacity){
		this(initialCapacity,DEFAULT_ARRAY_SIZE);
	}
	public LinkedArray(int initialCapacity, int arrayLengthInNode){
		if(initialCapacity<=0) throw new IllegalArgumentException("initialCapacity < 0");
		if(arrayLengthInNode<=0) throw new IllegalArgumentException("arrayLengthInNode < 0");
		
		arraySize=arrayLengthInNode;
		
		int nodeCount=initialCapacity/arrayLengthInNode;
		if(initialCapacity%arrayLengthInNode!=0) nodeCount++;
		
		ListNode<E> pre=null;
		for(int i=0;i<nodeCount;i++){
			ListNode<E> node=new ListNode<E>(arraySize);
			if(i==0) head=node;
			else{
				pre.next=node;
				node.previous=pre;
			}
			
			if(i==nodeCount-1) tail=node;
			pre=node;
		}
		size=0;
	}
	
	@Override
	public E remove(int index) {
		rangeCheck(index);
		ListNode<E> node=findNodeByIndex(index);// must not be null
		E ret=node.objArray[index-node.globalStartIndex];

		int start = index - node.globalStartIndex + 1;
		for (int i = start; i < node.localSize; i++) {
			node.objArray[i - 1] = node.objArray[i];
		}
		node.objArray[arraySize - 1] = null;
		node.localSize--;
		
		if(node.localSize==0) {// remove the empty node
			ListNode<E> pre=node.previous;
			ListNode<E>  next=node.next;
			
			if(pre==null){// equals node is the head node
				node.previous=null;
				head=node;
				updateNode(head,0);
			}
			else{
				pre.next=next;
				if(next!=null) next.previous=pre;
				
				updateNode(pre.next,pre.globalStartIndex+pre.localSize);
			}
		}
		
		else updateNode(node.next,node.globalStartIndex+node.localSize);
		
		size--;
		return ret;
	}
	@Override
	public E set(int index, E element) {
		rangeCheck(index);
		ListNode<E> node=findNodeByIndex(index);// must not be null
		E ret=node.objArray[index-node.globalStartIndex];
		node.objArray[index-node.globalStartIndex]=element;
		return ret;
	}
	@Override
	public void add(int index, E element) {
		if (index > size || index < 0) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
		ListNode<E> node=findNodeByIndex(index);
		if(node==null){// equals to index==size
			if(tail.localSize==arraySize){//tail node's array is full, append a node
				ListNode<E> newNode=new ListNode<E>(arraySize);
				newNode.globalStartIndex=size;
				tail.next=newNode;
				tail=newNode;
			}
			tail.objArray[tail.localSize]=element;
			tail.localSize++;
			if(size==0) head.globalStartIndex=0;
		}
		else{//insert in the middle of node list
			if(node.localSize==arraySize) {//node's array is full
				ListNode<E> next=node.next;
				ListNode<E> newNode=new ListNode<E>(arraySize);
				node.next=newNode;
				newNode.previous=node;
				
				newNode.next=next;
				if(next!=null) next.previous=newNode;
				
				newNode.objArray[newNode.localSize]=element;
				newNode.localSize++;
				updateNode(newNode,node.globalStartIndex+node.localSize);
			}
			else {//node's array is not full
				node.objArray[node.localSize]=element;
				node.localSize++;
				updateNode(node.next,node.globalStartIndex+node.localSize);//node.next must not be null
			}
		}
		size++;
	}
	private void updateNode(ListNode<E> node, int myGlobalStartIndex) {
		if(node==null) return;
		node.globalStartIndex=myGlobalStartIndex;
		if(node.localSize!=0) updateNode(node.next,node.globalStartIndex+node.localSize);
	}
	
	public E get(int index) {
		rangeCheck(index);
		ListNode<E> cur=findNodeByIndex(index);
		if(cur==null) throw new IllegalStateException("This should be an inner error, findNodeByIndex can not return null when used by get method. index="+index);
		return cur.objArray[index-cur.globalStartIndex];
	}

	public int size() {
		return size;
	}
	private final ListNode<E> findNodeByIndex(final int index){
		ListNode<E> cur=head;
		while(cur!=null) {
			if(cur.globalStartIndex+cur.localSize>index) return cur;
			cur=cur.next;
		}
		return null;
	}
	private final void rangeCheck(int index) {
		if (index<0||index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: "+ size);
	}
	
	public String toString() {
		StringBuilder builder=new StringBuilder();
		ListNode<E> node=head;
		builder.append("{").append(size).append(",");
		while(node!=null) {
			builder.append(node.toString()).append("->");
			node=node.next;
		}
		builder.append("}");
		return builder.toString();
	}
	
	private static class ListNode<E> {
		static final int NULL=-1;
		transient E[] objArray;
		ListNode<E> previous,next;
		int globalStartIndex=NULL, localSize=0;
		@SuppressWarnings("unchecked")
		public ListNode(int arrayLength) {
			super();
			objArray=(E[])new Object[arrayLength];
		}
		@Override
		public String toString() {
			StringBuilder sb=new StringBuilder();
			sb.append("(")
			.append(globalStartIndex).append(",")
			.append(localSize).append(",[");
			for(int i=0;i<localSize;i++) sb.append(objArray[i]).append(",");
			sb.append("])");
			return sb.toString();
		}
	}
}

谈一谈内存排序在JDK中的实现

说起内存排序,我立刻想到了大学和数据结构+算法设计老师的聊天,她推荐我去看《大道至简》,告诉我说,在很多复杂的情况下,先做内排序得到一个有序序列可以排除很多后续难题。我至今受用。

现在的计算机语言越来越高级,门槛越来越低,很多的基础细节再无人问津。万变不离其宗,作为科班出身的程序员,应该时刻温习基础知识。这里和大家一起从源码出发,看看Java中的排序是如何实现的。

还是先温习下内排序:

sort

那么,java中到底是怎么排序的呢?它是使用的哪一种呢?首先,Java中用于给集合排序的API是,你只需要写个排序器或者实现排序接口,然后一句优雅的代码即可搞定排序,

  • Collections.sort用于给List<T> 类型的对象集合排序
  • Arrays.sort用于给T[]对象数组来排序

我们先来看看Collections.sort是怎么工作的,少废话,看源码。

sort-1

Oh!天哪。Java很粗暴的直接用来list.toArray来把对象集合转化为对象数组,直接调用了Arrays.sort方法来sort,sort完成后再赋值回对象集合list中。那么,进一步探究,toArray干了什么?进一步看源代码,java中的list大家常用的是ArrayList和LinkedList,数组实现和链表实现。

  • ArrayList:他非常暴力的直接新建了一个和list一样长度的数组,把ArrayList的data[]都copy了进去

sort-2

  • LinkedList:他也非常暴力的直接新建了一个和list一样长度的数组,然后采用了迭代器(Iteraotr)遍历一遍,把对象都copy了过去。

sort-3

所以,从这里可以得出一个结论,编程过程中,如果能预知目标对象长度,请尽量使用对象数组来来管理多个对象,这里顺便补充些知识点,学过C的人都知道,想操作系统申请内存只能是一段连续的内存单元,编写过C语言的人对malloc和relloc函数很熟悉,一个拥有开辟一片内存,一个是追加内存。LinkedList我们都知道采用链表实现,无所谓浪费空间。ArrayList封装的就是一个数组private transient Object[] elementData; 那么ArrayList是怎么让你可以自由的add(T  t)的呢?我们也来看源代码,它在add方法中每次都要事先调用一句ensureCapacityInternal(size + 1);  // Increments modCount!! 即确保容量的过程,追溯代码如下:

这里是JDK1.7中的源码,JDK1.5之前,ensureCapcity算法有点不一样,但是也是类似,大家自行比较!

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); 这句话等价于 新的数组大小等于当前的大小乘以1.5,也就是增加50%

 

//如果新的大小比要求的最小容量小,则以最小容量为准,换言之,新容量=老容量+1
if (newCapacity – minCapacity < 0)
newCapacity = minCapacity;

 

//处理超大容量,如果对象巨大,达到了最大值(int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;)新数组大小就是 Integer.MAX_VALUE这么大,还不够,代码是OutOfMemoryError!!
if (newCapacity – MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:

 

//最后是让我及其讨厌的内存复制,
elementData = Arrays.copyOf(elementData, newCapacity);
}

 

代码可以看得出,程序员在随意的add的时候,JDK随时在检查给你的对象集合扩容,这个扩展的速度十分可观,可以每次增加50%,如果你使用的构造函数是new ArrayList<YourDomain>,那么初始大小是10,此增长速度就是10*1.5的n次方。所以,这里建议大家:

如果你能预知和估算将要存的对象的数据,请使用new ArrayList<YourDomain>(size); 这会大大减少不断的扩充数组,复制对象….

如果你有频繁的中间插入对象,删除对象等等,请使用LinkedList

我们回到主题,来看排序算法问题,现在我们已经知道不管是Collection还是Array最终都是在Array上进行的排序。

sort-4

我们看一下,jdk7中,进sort首先是一个if – else,说明一下,legacy的英文意思是遗留,这里的意思是,如果你想使用jdk5遗留的老排序算法的话,则使用老的MergeSort,否则使用新的TimSort,注意了,JDK5后排序算法有重大改进!如果你想在jdk5后的jdk中想继续沿用老的排序算法,则可以通过启动参数

-Djava.util.Arrays.useLegacyMergeSort=true

来强制使用遗留的MergeSort。

ok,接下来,我们的按JDK5以前(含5)的归并排序算法和JDK5后的算法分开讨论了。那么JDK5的归并排序算法,请自行看JDK的源码,

void java.util.Arrays.mergeSort(Object[] src, Object[] dest, int low, int high, int off)

对于这个排序,这里无需多言,他是一个实实在在,纯的归并排序算法,只是在size<7,因为数组是在太小了,不需要浪费空间交换时间里,草草一个插入排序解决。

归并算法还记得么,温习一下,“归并排序是将两个或者多个有序序列合并为一个新的有序表”,系统采用的双路归并算法-将一维数组中前后相邻的两个有序序列归并为一个有序序列。

JDK6后的排序算法叫TimSort,一脸懵逼?什么是TimSort,没听过啊,看百科,别百度。 https://en.wikipedia.org/wiki/Timsort

从源码可以看得出,TimSort是一种杂和的排序算法,Java是怎么杂和的呢,上源码如下。

如果你仔细读以下源代码,你会发现其实他很简单,就是把数组分组排序,每组大小如果小于了MIN_MERGE-1=31个,这31个关键字采用binarySort,这个binarySort不做进一步解释,他是简单插入排序的简单改进型。

排序算法如何改进?请记住,尽你所能,

  1. 减少关键字比较次数
  2. 减少记录移动次数

binarySort就是在插入排序的比较关键字过程重不使用for循环,采用折半搜索快速跳跃的方式来比较关键字。就这么简单。

static void sort(Object[] a, int lo, int hi) {

//检查范围,防止数组越界问题
rangeCheck(a.length, lo, hi);
int nRemaining = hi – lo;//还剩下没有排的数组范围

 

//如果仅是1个没有排,显数组已经排好了,一个数他自身是有序的
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted

 

//如果这一段待排序的数组长度<32了,小规模的可以采用简单排序了,上binarySort

// If array is small, do a “mini-TimSort” with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}

 

/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/

//这里是核心算法,他采用了栈模拟递归的方法来做分块排序
ComparableTimSort ts = new ComparableTimSort(a);
int minRun = minRunLength(nRemaining);//计算最小的排序长度
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);//计算下一趟运行的长度

// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;//还有一个强制的最小run的长度force
binarySort(a, lo, lo + force, lo + runLen);//足够小了,开始用小规模快读排序法-基于折半查找的插入排序法
runLen = force;
}

// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);//把排序的块信息压栈
ts.mergeCollapse();

//合并,这个很有意思,把栈元素进行合并,啥意思?很简单 某次排序 得到子序列如下:[2,3,5] [7,9,10],

//第一块的最大值比后一块的最小值小,这俩合并也是有序的。具体的看JDK注释,这是简单粗暴的解释!

// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);

// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();//还强制合并一下下
assert ts.stackSize == 1;//还下个断言,方便是方便,影响性能啊
}

 

 

那么,JDK为什么要摒弃MergerSort,转而改用TimSort呢?也很简单,事关时间和空间转换的法则,我们进入了大数据时代,CPU性能提高很多,MergerSort需要和原来一模一样大小的数据来最归并,这个新的空间复杂度和对象拷贝的过程相当损耗性能。

我们假设一下,一个程序员用了new ArrayList<>();没有指定初始大小,它存了200万个对象,ArrayList的elementData长度是850万,从200万+1到后面都是NULL。

那么MergeSort还没开始,它就要耗费:200万x4bytes = 7812.5K, 合计7.63M。 存对象的数组我理解为一个指针变量,按Int算,不算其他额外对象开销,然后还要花大量时间去Copy200万的对象到新数组,然后排序还没有开始。

TimSort适当的牺牲了时间性能,(我没有仔细测试,实际上不一定有牺牲),但是挽救了大量的内存消耗,性能大大提升。

玩转JVM – 为wrtnode编译一个嵌入式JVM

摩尔定律到达顶峰时期,物联网时代正在袭来,各种智能硬件玲琅满目,这让硬件和软件的的界限越来越模糊,硬件工程师可以不再面对元件一一焊起,软件工程师也可以轻易买到各种开发板,它已经”超乎“了嵌入式的概念,因为它完全是台小电脑。

从软件角度,当前NodeJS和Python等语言由于其轻量级内核(例如Python内核仅仅861Kbytes),因此厂商们为了吸引更多的爱好者和开发者使用产品,很多板子都会搭载NodeJS,例如,MTK的Sed Stadio,wrtnode等等。作为资深Java工程师,我开始着手研究能否在这些板子上跑JVM呢?本人以wrtnode r2 http://www.wrtnode.cc/ 入手,做了一些研究,成功运行起JVM。值得提起的是,我希望是能够支持比较完整的JavaSE API的JVM,我不希望是安卓,或者是JavaME方式,因为那样改变了我的编程方式,我希望我可以从public static void main(String args[]) 开始编写Java程序。

我们来看看wrtnode 2r的硬件参数,这里只关注CPU,RAM和ROM,IO和其他定时器等不需要考察:

  • CPU:MTK MT7688AN mips24k 主频580M,
  • DDR2 256MB RAM,
  • NOR FLASH 32MB ROM
  • Mips架构,el小端存储

可以看见其CPU基本和2000年左右的奔腾II差不多性能,RAM高达256M,运行JVM绰绰有余,只是ROM,在搭载其嵌入式操作系统占用5.6M后,可用的ROM只有约20M,换言之,我们必须把我们的JVM剪裁到20M以内。另外,wrtnode把/tmp/目录做了内存文件映射,如果实在不行,可以考虑把非关键组件放到其中,问题不言而喻,掉电就丢失。

开始着手研究:

第一步,能否把OpenJDK或者OracleJDK对于的架构呢?我很快就否定了他们,因为他们是在太庞大了,很难清理出一个干净的JVM。

第二部,那么既然这些常用的虚拟机,OpenJDK,OracleJDK, JRokit IceTea等等都太大,难以剪裁,那么会不会有开源爱好者,自行按照Java委员会标准编写虚拟机呢?拓拓的开始Google一把,果然大有人在,心中甚喜。这里贴一个非常用Java虚拟机实现,http://www.gnu.org/software/classpath/stories.html#jvm,综合比较后,我选择了JamVM,理由很简单:


 

JamVM is an open-source Java Virtual Machine that aims to support the latest version of the JVM specification, while at the same time being compact and easy to understand.

JamVM “Features”

For those interested in the design of virtual machines, JamVM includes a number of optimisations to improve speed and reduce foot-print. A list, in no particular order, is given below.

  • Execution engine supports many levels of optimisation from basic switched interpreter to inline-threaded interpreter with stack-caching (equivalent performance to a simple JIT).
  • Uses native threading (posix threads). Full thread implementation including Thread.interrupt()
  • Object references are direct pointers (i.e. no handles)
  • Supports class loaders
  • Efficient thin locks for fast locking in uncontended cases (the majority of locking) without using spin-locking
  • Two word object header to minimise heap overhead (lock word and class pointer)
  • Stop-the-world garbage collector, with separate mark/sweep and mark/compact phases to minimise heap fragmentation
  • Thread suspension uses signals to reduce suspend latency and improve performance (no suspension checks during normal execution)
  • Full object finalisation support within the garbage collector (with finaliser thread)
  • Full support for Soft/Weak/Phantom References (with Reference Handler thread)
  • Full support for class and class-loader garbage-collection and unloading (including associated shared libraries)
  • Garbage collector can run synchronously or asynchronously within its own thread
  • String constants within class files are stored in hash table to minimise class data overhead (string constants shared between all classes)
  • Supports JNI and dynamic loading for use with standard libraries
  • Uses its own lightweight native interface for internal native methods without overhead of JNI
  • VM support for invokedynamic (JSR 292)
  • VM support for type annotations (JSR 308)
  • VM support for lambda expressions (JSR 335)
  • VM support for method parameter reflection
  • JamVM is written in C, with a small amount of platform dependent assembler, and is easily portable to other architectures.

 

它竟然可以支持最新的JVM规范,换言之,他是完完整整的JavaSE。再看其特性,简直了….

敲定方案:JamVM + Classpath方案

第三步,那就的寻找wrtnode官方的交叉编译工具了,很快找到官方WIKI:

http://wiki.wrtnode.com/index.php?title=How_to_compile_with_the_openwrt_toolchain/zh-cn

迅速在我的Ubuntu上安装。

第四步,下载JamVM http://jamvm.sourceforge.net/ 开始交叉编译JVM可执行程序

第五步,下载Classpath http://www.gnu.org/software/classpath/ 编译出类目录,可以理解为rt.jar。

第六步,把编译出来的JVM打zip包,此时zip包的文件一共仅仅22M左右,拷贝到本地进行精简,例如删除里面的Sample,不必要的include和.html等文件。最终整个压缩包仅仅15M左右,惊呼!

第七步,把JVM SCP到wrtnode上面,我写了一个简单的测试程序,用一个for循环循环10000次,每次sleep(1, 2, 3, …),最终计算一下线程调度的的延迟,只是偶尔出现1ms的误差,不得不佩服其性能。最小-Xms768k能够启动其JVM ! 我可以用Java  + JNI来编写我的嵌入式程序了,太棒了


 

当然,我这里一二三四五六七写的很简单,但是真正的摸索和交叉编译过程会遇到各种坎,这里写下来和大家分享:

  • 每一步完成后做必要的检查后,再进行下一步,例如,在安装完交叉编译链后,应该自己写一个helloword.c文件,编译出来,然后移植到板子跑一下,至少需要file一下,看看文件是否是目标平台的字节码。
  • 有zlib依赖,先可以用apt-get install zlib1g-dev给ubuntu系统安装,然后再通过源代码交叉编译给工具链,注意用file命令检查,是否为目标平台字节码

这里付上一个翻墙找到的好帖子,我的成功基本按照其流程完成,想动手的小伙伴可以试试。

This project dealt with:

  • Processor: MIPS 24Kc
  • JVM: JamVM 1.5.4
  • Classpath 0.98 (Could have been 0.99)

Here are the adapted steps, assuming the cross-compile tools are built and setup beforehand.

  1. zlib
Download zlib 1.2.8 from http://www.zlib.net/
Build:
CHOST=mips-example-linux-gnu ./configure
Before make, edit the Makefile to add -fPIC to the SFLAGS that’s used to build the static lib. Otherwise will encounter error when building JamVM.
vim Makefile
    SFLAGS=-O3  -fPIC -D_LARGEFILE64_SOURCE=1 -DHAVE_HIDDEN
make
Install the lib and headers to the toolchains directory:
sudo cp libz.a [toolchains_path]/lib
sudo cp zlib.h [toolchains_path]/include
sudo cp zconf.h [toolchains_path]/include
Edit
  1. JamVM
Download from http://jamvm.sourceforge.net/
Edit the configure to support mips-*-linux compiler:
vim configure   
   mips-*-linux*) host_cpu=mips host_os=linux ;;
Configure and build:
./configure --host=mips-example-linux-gnu --with-classpath-install-dir=/usr/local --prefix=/usr/local --enable-shared --enable-int-threading --enable-int-direct --enable-int-caching --enable-int-prefetch --enable-runtime-reloc-checks --enable-tls --enable-dependency-tracking
make
I think the -install-dir and -prefix is whatever will be like at the target system. Here I just follow convention.
This is what will be printed when running “jamvm -version” on target later on.
Boot Library Path: /usr/local/lib/classpath
Boot Class Path: /usr/local/share/jamvm/classes.zip:/usr/local/share/classpath/glibj.zip
Strip down the binary (I think this step can be skipped if the target build will strip it when making the rootfs):
cd src
mips-example-linux-gnu-strip jamvm

Deploy to target at:

  • src/jamvm -> /usr/sbin/jamvm
  • lib/classes.zip -> /usr/local/share/jamvm/
Edit
  1. Classpath
JamVM 1.5.4 requires GNU classpath.
Download 0.98 at http://www.gnu.org/software/classpath/
Configure and build:
./configure --host=mips-example-linux-gnu --without-x --disable-gtk-peer --disable-plugin --disable-dssi --enable-jni --disable-gconf-peer --enable-default-preferences-peer=memory --enable-default-toolkit --disable-examples --disable-tools --disable-Werror --disable-alsa
make
The resulted lib/glibj.zip is ~9MB.
This can be reduced further. Unzip the glibj.zip, remove “unneeded” (for now) class and zip back.
Depends on the apps to run, some cannot be removed.
For example, these classes can be removed:
– gnu/CORBA
– gnu/java/awt
– gnu/javax/imageio
– gnu/javax/sound
– gnu/javax/swing
– java/sql/
– javax/imageio
– javax/sound
– javax/sql
– javax/swing
Zip the reduced classpath. This is reduced to about 6.5MB.
zip glibj.zip -r *

Deploy to target:

  • lib/glibj.zip -> /usr/local/share/classpath/glibj.zip
All the native libraries must also be deployed on target:
find ./native/ -name "*.so" -exec cp {} ${ROOT_PATH}/usr/local/lib/classpath \;

After completed the above step, should be able to just run the java apps by:

jamvm -jar hello.jar