标签归档:文件I/O

Java IO Stream句柄泄露分析

Java io包封装了常用的I/O操作,流式操作被统一为InputStream、OutputStream、Reader、Writer四个抽象类,其中InputStream和OutputStream为字节流,Reader和Writer为字符流。流式抽象的好处在于程序员无需关心数据如何传输,只需按字节或字符依次操作即可。

在使用流式对象进行操作时,特别是文件操作,使用完毕后千万不能忘记调用流对象的close()方法,这也是老生常谈的话题,但是偏偏很容易忘记,或者没忘记但是使用不当导致close()方法没调用到。正确的做法是把close()方法放在finally块中调用,比如这样:

InputStream in = ...;
OutputStream out = ...;
try {
    doSth(in, out);
} catch (Exception e) {
    handleException();
} finally {
    try {
        in.close();
    } catch (Exception e1){
    }
    try {
        out.close();
    } catch (Exception e2){
    }
}

Java流式操作在便捷了I/O操作的同时,也带来了错误处理上复杂性,这也是Java被人诟病的理由之一。Golang在这块的处理就非常优雅,它提供了defer关键字来简化流程。

当文件流未被显式关闭时,会产生怎样的后果?结果就是会引起文件描述符(fd)耗尽。以下代码会打开一个文件10次,向系统申请了10个fd。

public static void main(String[] args) throws Exception {
    for (int i = 0; i < 10; i++) {
        InputStream is = new FileInputStream(new File("file"));
    }
    System.in.read(b); // pause
}

到/proc/{pid}/fd目录下确定已打开的文件描述符:

root@classa:/proc/16333/fd# ls -l
total 0
lrwx------ 1 root root 64 Aug  2 20:43 0 -> /dev/pts/3
lrwx------ 1 root root 64 Aug  2 20:43 1 -> /dev/pts/3
lr-x------ 1 root root 64 Aug  2 20:43 10 -> /usr/lib/jvm/java-7-openjdk-amd64/jre/lib/ext/sunjce_provider.jar
lr-x------ 1 root root 64 Aug  2 20:43 11 -> /root/file
lr-x------ 1 root root 64 Aug  2 20:43 12 -> /root/file
lr-x------ 1 root root 64 Aug  2 20:43 13 -> /root/file
lr-x------ 1 root root 64 Aug  2 20:43 14 -> /root/file
lr-x------ 1 root root 64 Aug  2 20:43 15 -> /root/file
lr-x------ 1 root root 64 Aug  2 20:43 16 -> /root/file
lr-x------ 1 root root 64 Aug  2 20:43 17 -> /root/file
lr-x------ 1 root root 64 Aug  2 20:43 18 -> /root/file
lr-x------ 1 root root 64 Aug  2 20:43 19 -> /root/file
lrwx------ 1 root root 64 Aug  2 20:43 2 -> /dev/pts/3
lr-x------ 1 root root 64 Aug  2 20:43 20 -> /root/file
lr-x------ 1 root root 64 Aug  2 20:43 3 -> /usr/lib/jvm/java-7-openjdk-amd64/jre/lib/rt.jar

但是根据以往经验,即使流未显式关闭,也没见过文件描述符耗尽的情况。这是因为Java文件流式类做了保护措施,FileInputStream和FileOutputStream类利用Java的finalizer机制向GC注册了资源回收的回调函数,当GC回收对象时,实例对象的finalize()方法被调用。以FileInputStream为例,看看它是怎么处理的:

/**
 * Ensures that the close method of this file input stream is
 * called when there are no more references to it.
 *
 * @exception  IOException  if an I/O error occurs.
 * @see        java.io.FileInputStream#close()
 */
protected void finalize() throws IOException {
    if ((fd != null) &&  (fd != FileDescriptor.in)) {

        /*
         * Finalizer should not release the FileDescriptor if another
         * stream is still using it. If the user directly invokes
         * close() then the FileDescriptor is also released.
         */
        runningFinalize.set(Boolean.TRUE);
        try {
            close();
        } finally {
            runningFinalize.set(Boolean.FALSE);
        }
    }
}

当fd未释放时,finalize()方法会调用close()方法关闭文件描述符。有了这一层保障后,即使程序员粗心忘了关闭流,也能保证流最终会被正常关闭了。以下程序可以验证:

public static void main(String[] args) throws Exception {
    for (int i = 0; i < 10; i++) {
        InputStream is = new FileInputStream(new File("file"));
    }
    byte[] b = new byte[2];
    System.in.read(b); // pause1
    System.gc();
    System.in.read(b); // pause2
}

Java运行参数加上GC信息便于观察:

# java -verbose:gc -XX:+PrintGCDetails -Xloggc:gc.log -XX:+PrintGCTimeStamps StreamTest

程序在pause1处打开了10个fd,接着强制通过System.gc()触发一次GC,等gc.log中GC日志输出后再观察/proc/{pid}/fd目录,发现已打开的文件描述符均已经关闭。

但是即便如此,依然存在资源泄漏导致程序无法正常工作的情况,因为JVM规范并未对GC何时被唤起作要求,而对象的finalize()只有在其被回收时才触发一次,因此完全存在以下情况:在两次GC周期之间,文件描述符被耗尽!这个问题曾经在生产环境中出现过的,起因是某同事在原本只需加载一次的文件读取操作写成了每次用户请求加载一次,在一定的并发数下就导致too many open file的异常:

Exception in thread "main" java.io.FileNotFoundException: file (Too many open files)
        at java.io.FileInputStream.open(Native Method)
        at java.io.FileInputStream.(FileInputStream.java:146)
        ......

--EOF--

Erlang文件I/O小结

Erlang中用来进行文件操作的函数封装在4个库里,分别为file,filename,filelib和io模块:
1. file模块:包括文件打开/关闭,读取/写入,文件/目录操作等。
2. filename模块:提供了一组文件名相关操作的函数,这些函数平台独立,方便写跨平台的程序。
3. filelib模块:file模块的扩展,大部分函数基于file模块的导出函数实现。
4. io模块:提供一组对已打开文件进行操作的函数。

下面分场景总结下文件I/O函数的使用:

0. 准备
数据文件data.dat内容:

1
2
3
4
{person, "kaka",
  [{occupation, programmer},{favorite, erlang}]}.
 
{cat, {name, "tom"},{owner, "kaka"}}.

1. 按Erlang项式读写
按Erlang项式读写是指每次I/O的对象是Erlang项式。

从文件中一次读取所有项式:

1
2
3
4
1> file:consult('data.dat').
{ok,[{person,"kaka",
             [{occupation,programmer},{favorite,erlang}]},
     {cat,{name,"tom"},{owner,"kaka"}}]}

一次读取一个项式需要多个函数组合首先,先用file:open/2打开文件,再用io:read/2函数读取一项,直到文件结束,返回eof。

1
2
3
4
5
6
7
8
9
10
11
1> {ok, File} = file:open('data.dat', [read]). %File是一个用于访问文件的设备。
{ok,<0.37.0>}
2> io:read(File, '').
{ok,{person,"kaka",
            [{occupation,programmer},{favorite,erlang}]}}
3> io:read(File, '').
{ok,{cat,{name,"tom"},{owner,"kaka"}}}
4> io:read(File, '').
eof
5> file:close(File). %关闭设备。
ok

如果文件内容包含非法Erlang项式,file:consult/1和io:read/2都会抛出erl_parse异常。

向文件中写入项式可用io:format/3函数实现:

1
2
3
4
5
6
7
8
1> {ok, File} = file:open('data.dat', [write]).
{ok,<0.33.0>}
2> Person = {person, "kaka", [{occupation, programmer},{favorite, erlang}]}.
{person,"kaka",[{occupation,programmer},{favorite,erlang}]}
3> io:format(File, "~p.~n", [Person]).
ok
5> file:consult('data.dat').
{ok,[{person,"kaka", [{occupation,programmer},{favorite,erlang}]}]}

io:format/3可以对输出进行格式化,格式化参数较多,可参考io模块手册

2. 按行读写
io:get_line/2函数可以一次从文件中读取一行,文件结束时返回eof:

1
2
3
4
5
6
7
8
9
10
11
12
1> {ok, File} = file:open('data.dat', [read]).
{ok,<0.33.0>}
2> io:get_line(File, '').
"{person, \"kaka\",\n"
3> io:get_line(File, '').
"  [{occupation, programmer},{favorite, erlang}]}.\n"
4> io:get_line(File, '').
"\n"
5> io:get_line(File, '').
"{cat, {name, \"tom\"},{owner, \"kaka\"}}."
6> io:get_line(File, '').
eof

向文件中写入一行也是用到io:format/3。同前文。

3. 随机读写。
从文件随机位置读取数据用到file:pread/3函数,它的3个参数分别表示文件设备IoDevice,起始位置Start,读取长度Len。如下:

1
2
3
4
1> {ok, File} = file:open('data.dat', [read, binary, raw]).
{ok,{file_descriptor,prim_file,{#Port<0.587>,11}}}
2> file:pread(File, 5, 10).
{ok,<<"on, \"kaka\"">>}

它表示从第5个字节开始,读取10个字节长度的二进制数据。如果当前位置离文件末尾不足Len个字节,则返回能读取到的字节数的内容。

与随机读对应的随机写函数为file:pwrite/3,它的3个参数分别表示文件设备IoDevice,起始位置Start,待写二进制内容Bin。如下:

1
2
3
4
1> {ok, File} = file:open('data.dat', [write, binary, raw]).
{ok,{file_descriptor,prim_file,{#Port<0.587>,11}}}
2> file:pwrite(File, 5, <<"test">>).
ok

此外,file:position/2可以任意指定当前文件的指针位置,它的2个参数分别表示文件设备IoDevice,目标位置Location。如下:

1
2
3
4
5
6
1> {ok, File} = file:open('data.dat', [write, binary, read,raw]). 
{ok,{file_descriptor,prim_file,{#Port<0.587>,11}}}
2> file:position(File, 0). %指针移到文首。
{ok,0}
3> file:position(File, eof). %指针移到文末
{ok,105}

4. 以二进制方式读取整个文件内容

1
2
3
1> file:read_file('data.dat').
{ok,<<"{person, \"kaka\",\n  [{occupation, programmer},{favorite, erlang}]}.\n\n
{cat, {name, \"tom\"},{owner, \"kaka\"}}.">>}

摘自Joe Armstrong - 『Programming Erlang』。

--EOF--

六种基本内部排序算法效率分析

本文所谓的效率分析,是建立在『六种基本内部排序算法的C++实现』的代码之上,并根据书中资料总结而来的。大致就是对这几种排序效率的理论值通过实验验证一下。

对于排序算法的分析无非是从时间复杂度、空间复杂度、适用范围以及稳定性等几个方面考察。这次实验主要验证的是时间复杂度,测试方法为随机生成100000个整数,存成文本文件(源代码),测试时将文件中数据读到内存,然后排序,最后将排序后的数据存回文本文件,时间复杂度的计算方法为在排序前后分别调用C语言库函数clock(),排序消耗的时间就是两次函数返回值的差,这样就能略去因文件I/O带来的CPU开销。

1、直接插入排序(源代码)
直接插入排序在序列基本有序的情况下的时间复杂度为O(n),最坏情况是当序列为逆序排列,这时的时间复杂度为O(n2),平均时间复杂度为O(n2)。它只需要一个变量用于临时存储,因此它的空间复杂度为O(1)。当序列基本有序,或者待排记录个数较小时可以选择直接插入排序。此外,直接插入排序是稳定的。

实验中,当待排序列为100000个随机数时,其排序时间为12.24秒。

1
2
3
me@ubuntu:~/sort$ gcc straightinsertionsort.c -o straightinsertionsort
me@ubuntu:~/sort$ ./straightinsertionsort 
Duration: 12.240000 Secs.

2、冒泡排序(源代码)
冒泡排序同直接插入排序类似,在序列基本有序的情况下时间复杂度为O(n),最坏情况下当序列为逆序是时间复杂度为O(n2),平均时间复杂度为O(n2)。冒泡排序需要的额外空间仅为一个用于数据交换的临时变量,因此它的空间复杂度也为O(1)。当序列基本有序,或者待排记录个数较小时可以选择冒泡排序。冒泡排序也是稳定的。

实验中,当待排序列为100000个随机数时,其排序时间为43.68秒。可见,当待排记录个数稍微一大,冒泡排序就是个悲剧。

1
2
3
me@ubuntu:~/sort$ gcc bubblesort.c -o bubblesort
me@ubuntu:~/sort$ ./bubblesort 
Duration: 43.680000 Secs.

3、选择排序(源代码)
选择排序最好情况下、最差情况下、平均情况下的时间复杂度均为O(n2)。它所需要的额外空间为一个用于交换数据的临时变量,因此空间复杂度为O(1)。选择排序适用于待排记录个数较小的情况下,相对于直接插入排序,选择排序移动记录的次数少。另外,选择排序算法比较直观,而且它是不稳定的。

实验中,当待排序列为100000个随机数时,其排序时间为41.34秒。可见,当待排记录个数较大时,选择排序效果很不理想。

1
2
3
me@ubuntu:~/sort$ gcc selectsort.c -o selectsort
me@ubuntu:~/sort$ ./selectsort 
Duration: 41.340000 Secs.

4、快速排序(源代码)
快速排序的最好情况下的时间复杂度为O(nlog2n),出现在当待排序列元素分布非常随机时。最坏情况的时间复杂度为O(n2),出现在当待排序列的元素基本有序(无论正序或逆序)时。平均时间复杂度为O(nlog2n)。由于快排要进行递归划分操作,而每一次划分都需要消耗一个变量用于临时存储,因此,随着递归的深入,当处在最好情况下,每次划分后枢轴元素都在中间,此时它的空间复杂度为O(log2n),最坏情况下,当每次划分枢轴元素都靠近序列的端点,则空间复杂度为O(n)。当待排序列记录个数较多,并且记录随机分布时,可以选择快速排序。快速排序是不稳定的。

实验中,当待排序列为100000个随机数时,其排序时间为0.01秒。可见,当待排记录个数较大时,快速排序秒杀前面三种平均时间复杂度为O(n2)的排序算法。

1
2
3
me@ubuntu:~/sort$ gcc quicksort.c -o quicksort
me@ubuntu:~/sort$ ./quicksort 
Duration: 0.010000 Secs.

5、堆排序(源代码)
堆排序在最好情况下、最差情况下、平均情况下的时间复杂度均为O(nlog2n)。空间复杂度上,堆排序需要在调整大顶堆的筛选过程中需要一个额外临时变量,交换堆顶和堆末元素时需要一个临时变量,因此总的空间复杂度是O(1)。当待排序列记录个数较多时,可以选择堆排序,堆排序也是不稳定的。

实验中,当待排序列为100000个随机数时,其排序时间为0.03秒,跟快速排序相差无几。

1
2
3
me@ubuntu:~/sort$ gcc heapsort.c -o heapsort
me@ubuntu:~/sort$ ./heapsort 
Duration: 0.030000 Secs.

6、归并排序(源代码)
归并排序在最好情况下、最差情况下、平均情况下的时间复杂度均为O(nlog2n)。由于采用了与待排序列相同长度的辅助序列,因此归并排序的空间复杂度始终为O(n),这在线性对数阶的三种排序算法中是最差的,但是归并排序有一个好处就是它是稳定的。当待排序列个数较多,并且需要稳定排序时,可以选择归并排序。

实验中,当待排序列为100000个随机数时,其排序时间为0.03秒,跟快速排序、堆排序相差无几。

1
2
3
me@ubuntu:~/sort$ gcc mergesort.c -o mergesort
me@ubuntu:~/sort$ ./mergesort 
Duration: 0.030000 Secs.

以上六种排序算法的时空复杂度总结如下的表格:

排序算法 最好时间复杂度 最差时间复杂度 平均时间复杂度 空间复杂度 稳定性
直接插入排序 O(n) O(n2) O(n2) O(1) 稳定
冒泡排序 O(n) O(n2) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
快速排序 O(nlog2n) O(n2) O(nlog2n) O(log2n) ~ O(n) 不稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定

以上是六种排序算法在记录个数为10w时的情形,现在剔除前三种O(n2)的算法(直接插入排序、冒泡排序、选择排序),增大待排序列记录个数的数量级,考察一下后三种O(nlog2n)算法(快速排序、堆排序、归并排序)的排序时间问题。

随机生成1亿个整数,存成文本文件,方法同前。以下分别是调整数量级后的快速排序、堆排序和归并排序的算法处理时间:
快速排序:27.89秒!

1
2
3
me@ubuntu:~/sort$ gcc quicksort.c -o quicksort
me@ubuntu:~/sort$ ./quicksort 
Duration: 27.890000 Secs.

堆排序:110.52秒!

1
2
3
me@ubuntu:~/sort$ gcc heapsort.c -o heapsort
me@ubuntu:~/sort$ ./heapsort 
Duration: 110.520000 Secs.

归并排序:!!! Segmentation fault!!! 申请内存太多,虚拟机上跑不了了,囧~

1
2
3
me@ubuntu:~/sort$ gcc mergesort.c -o mergesort
me@ubuntu:~/sort$ ./mergesort 
Segmentation fault

--EOF--