Java读取超时
读文件的时间复杂度？
问大家一个问题，调用Java的FileInputStream的read(byte[] buf, int offset, int len)的时间复杂度是多少？应该很多人会回答$O(n)$，$n$是实际读到的字节数目。
我以前也naive的这样认为，于是当时我为了减少读取的时间，每次都会把缓冲区设置为$1M$，这样一般读取次数会非常少，从而大幅提高性能。
直到某天参加某次Codeforces比赛后，遇到了一道交互题，这种题要求频繁的读取，一次样例可能需要读取10W次。我当场扑街，TLE到不行。
之后每次遇到类似的多次读取的交互题，我TLE后果断切C++，才苟了过去。
最近一次交互题，2s的时限，我T了，但是我切了C++后，100ms就过了。怎么可能差距这么大。但是过了心里还是不服，凭什么java这么慢。我看了下也有不少人用java过的，时间在500ms上下。打开他们的代码，看到他们用的是标准库里的读写类。
于是我就把我的写出类替换成了标准库的类（我以前一直以为是java的写出后的flush太慢了，傻傻的），但是还是T了。这时候我才终于发现是我的读入类太慢了，我替换成通过的人用的基于StringTokenizer写的读入类后，果然过了，500ms。
接下来开始排查我自己写的读入类和他们的读入类的区别。在内存操作的时间几乎可以忽略，但是看了下他们的方法，他们用的是BufferedWriter，但是似乎也没什么黑魔法，最后调用的也是java底层FileInputStream中的原生readBytes(byte[] buf, int offset, int len)接口，重点是我和他的版本对这个底层接口的调用次数是相同的。
既然相同的调用次数，为啥时间花费差这么大呢，那肯定是参数有区别。看了一下二者，BufferedWriter设置的缓冲区大小为$2^{13}$，而我的缓冲区大小为$2^{20}$。然后我就得到了一个猜想，readBytes(byte[] buf, int offset, int len)接口的时间复杂度不是$O(n)$，而是$O(len)$，即不管读多少个字符，时间都已经花费了，当然这个时间复杂度的原因可能有多个：
- C++源码中扫描了整个数组
- C++源码中分配了等同大小的一个数组
当然上面这两个原因还只是猜想，剩下就是真正的去看一下源码了，打开OpenJDK的源码，在src\java.base\share\native\libjava\FileInputStream.c这个文件中可以找到如下代码：
JNIEXPORT jint JNICALL
Java_java_io_FileInputStream_readBytes(JNIEnv *env, jobject this,
jbyteArray bytes, jint off, jint len) {
return readBytes(env, this, bytes, off, len, fis_fd);
}
之后点击跳转，来到src\java.base\share\native\libjava\io_util.c文件中：
/* The maximum size of a stack-allocated buffer.
*/
#define BUF_SIZE 8192
//这个方法的时间复杂度是O(len)吗？
jint
readBytes(JNIEnv *env, jobject this, jbyteArray bytes,
jint off, jint len, jfieldID fid)
{
jint nread;
//这里使用在栈上分配一个BUF_SIZE大小的数组
//但是大家应该知道，C++、C等编译型语言在栈上分配空间实际上只是汇编语言中改变栈指针而已，所以是O(1)
char stackBuf[BUF_SIZE];
char *buf = NULL;
FD fd;
if (IS_NULL(bytes)) {
JNU_ThrowNullPointerException(env, NULL);
return -1;
}
if (outOfBounds(env, off, len, bytes)) {
JNU_ThrowByName(env, "java/lang/IndexOutOfBoundsException", NULL);
return -1;
}
if (len == 0) {
return 0;
} else if (len > BUF_SIZE) {
//看这里，由于我的len始终是1M，因此总是会进入这个分支
//这里会在内存中分配一个len大小的数组
buf = malloc(len);
if (buf == NULL) {
JNU_ThrowOutOfMemoryError(env, NULL);
return 0;
}
} else {
//假如len不够大，会直接使用栈空间
buf = stackBuf;
}
fd = GET_FD(this, fid);
if (fd == -1) {
JNU_ThrowIOException(env, "Stream Closed");
nread = -1;
} else {
nread = IO_Read(fd, buf, len);
if (nread > 0) {
(*env)->SetByteArrayRegion(env, bytes, off, nread, (jbyte *)buf);
} else if (nread == -1) {
JNU_ThrowIOExceptionWithLastError(env, "Read error");
} else { /* EOF */
nread = -1;
}
}
if (buf != stackBuf) {
//最后这里会把数组回收掉
free(buf);
}
return nread;
}
但是这并不能说明这个方法的时间复杂度是$O(len)$，因为malloc和free的时间复杂度还不知道。之前读过《深入理解计算机系统》这本书，上面介绍了不少的内存分配和回收算法，印象中是存在$O(\log_2len)$时间复杂度的算法的，因此这也不应该导致我的代码超时啊（毕竟$\log_22^{20}=20$而已）。同时在StackOverflow上搜了一下，里面也确实提到了一种$o(1)$时间复杂度的实时内存分配算法Two-Level Segregate Fit，但是这里就不继续深入了。
这里在知乎上翻出一篇回答，说是32位Linux系统的特性，在malloc的时候发现分配的内存超过512KB的时候，会直接使用mmap来进行内存映射，同时操作系统会处于安全原因会将这块内存全部清零。因此这样就真的是$O(len)$了。之后我在codeforces上用类似的方式分以500KB和520KB的读取缓冲区大小提交答案，前者只需要600ms，后者却需要1800ms。这就是答案了。
总结一下：尽量只是用大小为8KB大小的缓冲区，即使要使用很大的缓冲区，也不要超过512KB。