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

一支菜鸟 2019-07-01

闲来无事,顺便写一个快排的代码。结果却引发了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);
    }

相关推荐