Побайтовая работа с файлами

Special for Коротко о сути. Если читать файл по одному байту через FileInputStream.read(), гигабайтный файл обрабатывается часами. Если тот же файл читать кусками по 64 000 байт в массив byte[], а результаты складывать в обычный long[256] вместо коллекции, время падает до долей секунды. Ниже пять вариантов одной и той же программы, от самого наивного до быстрого, с реальными замерами на файлах в 46 Мб, 1 Гб и 32 Гб.

Кратко

• Задача такая: посчитать, какие байты встречаются в файле, и вывести их коды по убыванию без повторов.
• ArrayList<Integer> на миллиард элементов не переживет ни один компьютер: каждое число превращается в объект и тянет за собой заголовок и ссылку.
• TreeSet снимает проблему памяти (в множестве не больше 256 элементов) и сортирует сам, но само чтение остается медленным.
• Обычный long[256] со счетчиками быстрее любой коллекции и не требует сортировки вовсе: индекс массива это и есть байт-код.
• Главный тормоз не в структуре данных, а в том, что байты читаются по одному: каждое обращение к диску стоит дорого.
• Чтение блоками по 64 000 байт ускоряет обработку гигабайтного файла с трех часов до долей секунды.

Начнем-с

В 18 уровне начались первые задачи побайтного чтения файлов: прочитать файл, далее найти минимальные/максимальные байты или вывести в упорядоченном виде и т.п. Народ тут весьма ушлый. Знают про коллекции и про то, что они могут сортировать, вставлять. Коллекции это мощный механизм. И многие не применяли их вообще до JavaRush-а. Оно, конечно, похвально изучать их и пытаться приткнуть куда не попадя. И так. Возьмем задачу, которой нет в заданиях (чтобы не было спойлеров при решении), но есть сильно похожие:

• Ввести с консоли имя файла
• Считать все байты из файла.
• Не учитывая повторений - отсортировать их по байт-коду в убывающем порядке.
• Вывести на экран
• Закрыть поток ввода-вывода

Пример байт входного файла 44 83 44 Пример вывода 83 44 Мы дополнительно завели переменные startTime и finishTime, чтобы засечь время выполнения программы. Для вычисления использовал i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64 (примеры программ в вариантах 1-2 взяты из форума info.javarush, они чуть модифицированы только для сортировки в возрастающем порядке - то есть они РЕАЛЬНЫЕ!!)

Решаем в лоб:

// Вариант 1. Загоняем в коллекцию и сортируем используя ее метод Collections.sort 
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());
        long startTime = System.currentTimeMillis();
        
        ArrayList<Integer> listData = new ArrayList<Integer>();
        while (inputStream.available() > 0) listData.add(inputStream.read());
        inputStream.close();
        ArrayList<Integer> result = new ArrayList<Integer>(new HashSet<Integer>(listData));
        Collections.sort(result);

        while (!result.isEmpty()) {
            System.out.print(result.get(result.size()-1) + " ");
            result.remove(result.get(result.size()-1));
        }

        long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

Решает все замечательно! Тест (если бы был, прошелся бы на ура). Но в жизни мало файлов содержащих только строчку "Мама мыла раму". Давайте скормим нашей программе файл в 46Мб (по нынешним меркам вроде и не особо много). Что такое, программа выполняется 220 секунд. Попытка скормить с вечера 1Gb файл (размер MPEG4 фильма не в самом лучшем качестве) не увенчалась успехом. Программа утром все еще читала - а мне идти на работу уже. В чем проблема? Наверное, в использовании ArrayList<Integer>, у которого внутри 1 миллиард элементов. Каждый элемент занимает минимум 16 байт (заголовок объекта 12 байт плюс само поле int 4 байта), и это не считая ссылки на объект в массиве внутри списка, а она добавляет еще 4 байта. Часть значений, от -128 до 127, Java берет из кэша Integer и заново не создает, но даже с этой поправкой на миллиарде элементов в память уезжает больше десяти гигабайт при размере оперативы в 8. Будем делать лучше. Нырнем в коллекции глубже. И ура, нашлось то, что нам нужно.

Встречаем TreeSet

Это множество:

• не допускает хранение двух одинаковых элементов (а значит мы будем хранить в памяти все 255 элементов, вместо миллиарда!)
• при манипуляциях со своими элементами автоматом упорядочивает (само сортирует - вот он, верх совершенства!)

Получаем:

// Вариант 2. Загоняем в ТreeSet который сам сортирует (лютый win!)
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());

        byte[] arrBytes = new byte[256];
        long startTime = System.currentTimeMillis();

        SortedSet<Integer> list = new TreeSet<Integer>();
        while(inputStream.available()>0) list.add(inputStream.read());
        inputStream.close();

        while (!list.isEmpty())        {
            System.out.print(list.last() + " ");
            list.remove(list.last());
        }

		long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

Имеем на выходе: 46Мб файл 176 секунд. 1Gb файл - 3 часа 5 минут. Прогресс налицо. Мы смогли "дождаться" результатов, да и 46Мб файл заметно быстрее обрабатывается. Идем дальше. Давайте попытаемся отказаться от коллекций (это будет для некоторых мучительно больно). Будем использовать простые массивы (это так примитивно). Заметим одну важную вещь. Кол-во встречающихся байт можно загнать в массив длиной 256. Так просто будем увеличивать на единицу соответствующий считанному байту элемент массива.

Массив: побайтно

// Вариант 3. Считываем массив побайтно.
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());

        long[] arrBytes = new long[256];
        long startTime = System.currentTimeMillis();
        
        while (inputStream.available() > 0) arrBytes[inputStream.read()]++;

		inputStream.close();
        // Выводим отсортированный по байт-коду в обратном порядке
        for (long i = 255; i >= 0 ; i--)
            if (arrBytes[(int) i] > 0) System.out.print(i + " ");

			long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

Имеем на выходе: 46Мб файл 158 секунд. 1Gb файл - 2 часа 55 минут. Опять улучшение, но небольшое. И мы сделали все простыми инструментами. Не использовали микроскоп для забивания гвоздей. Теперь лирическое отступление. Вспомним устройство компьютера. Память ОЗУ (DRAM) где обычно выполняется программа и хранятся переменные имеет высокую скорость доступа, но небольшой размер. Память на жестком/flash диске (HDD или Flash-накопители) где обычно хранятся файлы, наоборот имеет низкую скорость доступа, но большой размер. Так что когда мы побайтно читаем 1Gb файл (то есть миллиард раз обращаемся к HDD) - мы тратим много времени на работу с низкоскоростным устройством (по песчинке перекладываем песок с кузова КамАЗа в песочницу). Попробуем еще улучшить.

Вывалим сразу ВЕСЬ КамАЗ с песком за один раз!

// Вариант 4. Считываем массив сразу целиком за раз в память.
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());

        long[] arrBytes = new long[256];
        long startTime = System.currentTimeMillis();
        
        byte fileImage[]=new byte[inputStream.available()];
        long fileSize=fileImage.length;
        inputStream.read(fileImage);
        for (int i = 0; i = 0 ; i--)
            if (arrBytes[(int) i] > 0) System.out.print(i + " ");

		long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

небольшое, но опять таки важное отступление Заметим:

1. индекс у arrBytes определен в пределах 0..255,
2. fileImage - массив байт, элементы которого имеют значение -128..127

Поэтому для подсчета байт будем использовать конструкцию arrBytes[fileImage[i] & 0b11111111]++; которая банально сбросит бит знака и вернет нам значение в диапазоне 0..255 И так, результаты: 46Мб файл 0.13 секунды (меньше секунды). 1Gb файл - 9 секунд. Мы сделали это! Мы невероятно круты! Ускорились с 3 часов до 9 секунд. Все, можно откинуться в кресле и попить чайку. А теперь еще один эксперимент - попробуем файл в 32 Gb (например, HD фильм). Получим в результате треск работающего HDD с вываливанием программы в Windows. КамАЗ вывалив кузов с песком сломал песочницу! Что будем делать? Вспомним еще один факт. Файлы в ОС хранятся обычно порциями (кластерами) по 2-64Кб (зависит от типа файловой системы, настроек и т.п.). Будем считывать порциями, для примера в 64000 байт. Попытаемся разгрузить КамАЗ экскаватором достаточно большими порциями:

Используем буфер

// Вариант 5. Считываем массив кусками.
public class Solution {
    public static void main(String[] args) throws Exception {
        FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());

        long[] arrBytes = new long[256];
        long startTime = System.currentTimeMillis();
        
        int  bufferSize = 64000;
        byte buffer[]   = new byte[64000];

        while (inputStream.available() > 0) {
            if (inputStream.available() < 64000) bufferSize = inputStream.available();
            inputStream.read(buffer, 0, bufferSize );
            for (int i = 0; i = 0 ; i--)
            if (arrBytes[(int) i] > 0) System.out.print(i + " ");

		long finishTime = System.currentTimeMillis();
        System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
    }
}

В итоге получили: 46Мб файл 0.08 секунды (меньше секунды). 1Gb файл - 0.9 секунд(меньше секунды). 32Gb файл - 31 секунда. Заметим для 1 Gb файла мы улучшили производительность с нескольких часов до долей секунд!!!

Сравним все пять вариантов

Чтобы цифры не были разбросаны по всей статье, сведем их в одну таблицу. Замеры сделаны на одной и той же машине, ее конфигурация указана в начале: На этом скромном факте закончим эксперимент и улучшение начального кода. Мы достигли прогресса во многом - нас радуют новые показатели расхода памяти и времени работы. Также мы не подтягиваем в данном случае бесполезные коллекции из стандартной библиотеки.

Что здесь не так с точки зрения продакшена

Все пять вариантов выше решают учебную задачу и решают ее верно. Но если такой код поедет в реальный проект, у него найдутся два слабых места. Первое. В варианте 4 размер файла определяется как new byte[inputStream.available()]. Документация Oracle предупреждает об этом дословно: возвращаемое значение available() никогда не следует использовать для выделения буфера под весь поток. С FileInputStream на локальном файле это случайно работает, но для потока из сети или из конвейера метод вернет лишь то, что успело прийти в буфер прямо сейчас. Второе. Конструкция while (inputStream.available() > 0) ненадежна по той же причине: у сетевого потока данные могут просто задержаться в пути, метод вернет ноль, и цикл завершится на середине файла. Плюс во всех вариантах игнорируется то, что возвращает read(), а он имеет полное право прочитать меньше байт, чем у него попросили. Канонический цикл чтения обеих проблем не имеет и выглядит так:

int count;
while ((count = inputStream.read(buffer)) != -1) {
    for (int i = 0; i < count; i++) arrBytes[buffer[i] & 0b11111111]++;
}

Признаком конца файла тут служит -1, который возвращает сам read(), а переменная count говорит, сколько байт реально прочитано за этот заход.

Как это пишут сегодня

Статье почти десять лет, и с тех пор часть работы взял на себя стандартный пакет. Во-первых, ручной буфер из варианта 5 давно реализован в классе BufferedInputStream: он делает ровно то же самое, читает с диска большими кусками и отдает вам хоть по одному байту. Во-вторых, поток стоит открывать в try-with-resources: тогда он закроется сам даже при исключении, а не только при удачном завершении, как сейчас. Тот же подсчет байт на современных средствах:

public class Solution {
    public static void main(String[] args) throws Exception {
        Path path = Paths.get(new BufferedReader(new InputStreamReader(System.in)).readLine());
        long[] arrBytes = new long[256];

        try (InputStream in = new BufferedInputStream(Files.newInputStream(path))) {
            byte[] buffer = new byte[64000];
            int count;
            while ((count = in.read(buffer)) != -1) {
                for (int i = 0; i < count; i++) arrBytes[buffer[i] & 0b11111111]++;
            }
        }

        // Выводим отсортированный по байт-коду в обратном порядке
        for (int i = 255; i >= 0; i--)
            if (arrBytes[i] > 0) System.out.print(i + " ");
    }
}

Для файлов, которые заведомо помещаются в память, есть путь еще короче: Files.readAllBytes(path) вернет сразу весь массив байт. Но разбираться, что происходит под капотом, все равно полезнее, чем сразу звать готовый метод, ради этого статья и написана. P.S. Кто-то скажет пример надуманный и т.п. Но полно похожих задач: проанализировать огромный объем элементов, имеющих конечное число состояний. Например изображения (RGB обычно хранится в 24 битах, в нашем случае long[] arrRGB = new long[256*256*256] занял бы в памяти 128Мб), музыка (амплитуда обычно оцифровывается в 16 или 24 бита) или дискретные показатели датчиков и т.п.

Вопросы и ответы

Почему побайтное чтение файла работает так медленно?

Потому что каждый вызов read() без буфера доходит до операционной системы, а обращение к диску стоит на порядки дороже операции в памяти. Миллиард байт это миллиард таких обращений. В примерах выше картину усугубляет и available(), который тоже вызывается на каждой итерации цикла. Лечится это чтением блоками: один вызов забирает сразу десятки тысяч байт.

Зачем в коде побитовая маска 0b11111111?

Потому что byte в Java знаковый и хранит значения от -128 до 127, а индекс массива счетчиков нужен в диапазоне от 0 до 255. Маска & 0b11111111 (то же самое, что & 0xFF) обнуляет разряды выше восьмого, которые появляются при расширении byte до int, и превращает -1 в 255. Без нее на первом же байте со старшим битом программа упала бы с ArrayIndexOutOfBoundsException.

Можно ли просто прочитать файл целиком в массив?

Для небольших файлов да, но ограничений два. Первое: массив в Java адресуется int, поэтому больше примерно двух гигабайт в него физически не поместится. Второе: файл целиком должен влезть в оперативную память, и вариант 4 выше именно поэтому падает на 32 Гб. Отдельно стоит знать, что определять размер файла через available() неправильно: документация Oracle прямо предупреждает, что возвращаемое значение этого метода нельзя использовать для выделения буфера под весь поток.

Какой размер буфера выбрать?

Разумный диапазон это от 8 до 64 килобайт. Смысл в том, чтобы за одно обращение к диску забирать сразу несколько кластеров файловой системы: дальнейшее увеличение почти не дает выигрыша, зато расходует память. Для ориентира у BufferedInputStream размер буфера по умолчанию 8192 байта. В примере выше взято 64 000 байт, и этого хватает с запасом.

Можно ли обойтись без ручного буфера?

Да. Обернув поток в BufferedInputStream, вы получите буферизацию бесплатно и с тем же эффектом, а читать сможете хоть по одному байту. Есть и более короткие пути из пакета java.nio.file: Files.newInputStream() вместо new FileInputStream() и Files.readAllBytes(), если файл заведомо небольшой. Ручной буфер в статье полезен тем, что показывает, что именно происходит внутри.

Почему ArrayList из Integer занимает так много памяти?

Потому что в коллекцию нельзя положить примитив: каждое число превращается в объект Integer. А объект это не только четыре байта самого значения, но и служебный заголовок, выравнивание до кратности восьми и ссылка на него в массиве внутри списка. В сумме выходит около двадцати байт на одно число вместо одного байта, который вы прочитали из файла. На миллиарде элементов эта разница и становится решающей.

Читайте также

• Классы FileInputStream, FileOutputStream, BufferedInputStream в Java
• BufferedReader и InputStreamReader: считывание с клавиатуры
• Java.io: операции ввода-вывода в Java
• TreeSet в Java