一次快速排序引发的jvm调优

闲来无事，顺便写一个快排的代码。结果却引发了java.OutOfMemoryError:Java heap space。

首先谈谈快速排序，这是一种在统计上很快的排序，他的核心思想是，在一个数组中随便取一个数作为基准(通常取最后一个)，然后把整个数组划分，把比基准小或等于的数放在基准之前，把大于基准的数放在基准之后。然后再分别对基准之前的数组和基准之后的数组进行快速排序。

java 代码：

void quicksort(int[] nums,int begin,int end)
    {
        if(end <= begin)return;
        int p = begin-1;
        for(int i = begin;i <= end;i++)
            if(nums[i] <= nums[end])
            {
                p++;
                int temp = nums[i];
                nums[i] = nums[p];
                nums[p] = temp;
            }
        quicksort(nums,begin,p-1);
        quicksort(nums,p+1,end);
    }

这里唯一难理解的就是这个p，这里的思想是，p及其左侧都是小于等于基准的数，而p的右侧都是大于基准的数。因此，遍历这个数组的时候，若数大于基准，则访问下一个，否则把p+1，然后交换p和这个位置上的数，这样就能成功划分。

因为它是快速排序，所以我想小数据量并不能体现它的快速。因此，我使用了一个很大的数组，并且使用随机数填充它。

Random random = new Random();
int[] nums = new int[ (1024*1024*1024) ];
for(int i = 0;i < nums.length;i++)
    nums[i] = random.nextInt(500000);

这个数组的大小是4个GB，因为一个int是4B，而1024*1024是1M，而1024M是1G。

正当我要运行程序并且统计其运行时间时，悲剧发生了！！！

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

这是一个堆内存溢出错误。

于是我立马想到一个解决方法，那就是 扩大堆内存 ！

数组大小只有4GB，我现在给JVM进程5000MB大小的堆内存，也就是大约4.8GB的内存，程序一定是没问题的了。于是我添加了参数-Xms5000m。 这个参数的意义是，最小堆内存为5000MB。

然鹅，结果是

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

why???

要说明这个必须先知道 java内存结构 。

理解了 java 内存结构之后，才能明白。堆内存又分为，新生代(Young)和老年代(Old)，而数组这种大对象一般是直接分配在老年代中。虽然我设置了5000MB的堆内存，但是这5000MB的内存并不都是给老年代的，老年代和新生代内存的默认比例是2，也就是说5000MB里只有2/3是老年代的，也就是3333MB≈3.25GB，这个大小仍然小于数组的4GB，因此现在我设置老-新比例为9，也就是老年代拥有5000MB*0.9=4500MB≈4.39GB，此时已经大于数组所需要的内存大小！

添加完参数-Xms5000m -XX:NewRatio=9后，我再次运行程序，运行成功！！！经过漫长的等待，输出了 排序 的时间为1443.11s，也就是大约 24分钟 ！！！

最后，java 核心代码:

public static void main(String[] args) {
        Random random = new Random();

        int[] nums = new int[ (1024*1024*1024) ];
        for(int i = 0;i < nums.length;i++)
            nums[i] = random.nextInt(500000);
        long being = System.currentTimeMillis();
        quicksort(nums,0,nums.length-1);

        long end = System.currentTimeMillis();
        System.out.println(((double) (end-being))/1000+"s");



    }


   static void quicksort(int[] nums,int begin,int end)
    {
        if(end <= begin)return;
        int p = begin-1;
        for(int i = begin;i <= end;i++)
            if(nums[i] <= nums[end])
            {
                p++;
                int temp = nums[i];
                nums[i] = nums[p];
                nums[p] = temp;
            }
        quicksort(nums,begin,p-1);
        quicksort(nums,p+1,end);
    }