Недостатки фрагментированных массивов для хранения динамических байтов

Question

По умолчанию ByteArrayOutputStream кажется довольно расточительной реализацией, и мне было интересно, есть ли какая-то конкретная причина для этого. Сначала он сохраняет 1 фиксированный массив в бэкэнд. Если он заполнен, он создает новый массив и копирует в него старый массив (больше памяти и больше накладных расходов). Затем, если вы делаете toByteArray(), он на самом деле снова копирует массив.

Байт-буферы хороши, но также фиксированы по размеру, они просто предлагают несколько в одном массиве, не более того.

Мне было интересно, было бы интересно создать класс (или, если он уже существует, укажите мне его), который использует один или несколько массивов поддержки. Вместо дублирования массива каждый раз для расширения он просто добавляет новый массив поддержки. Для чтения вы можете легко создать интерфейс, такой как входной поток, в то время как вы можете открыть интерфейс, такой как выходной поток для записи

Любая обратная связь о том, существует ли такая вещь, а если нет: почему? Есть ли у меня недостаток, который я не вижу?

Answer 1

Это действительно отличная идея, особенно для больших данных.

Вы можете Quicky столкнуться проблемы с памятью при выделении огромных массивов в куче, поскольку они нуждаются в непрерывной свободной памяти будет выделено. Раньше у нас была такая ситуация, когда мы часто выделяли байтовые массивы размером 10-50 Мбайт и попадали в OutOfMemoryException с, а не потому, что было слишком мало доступной памяти (обычно у нас было 90% или 900 МБ бесплатно), а потому, что из-за кучи фрагментация не было ни одного непрерывного блока памяти, который можно было бы использовать для этого массива.

Мы закончили создание класса Blob, который внутренне хранил данные в виде кусков цепочки (списка) меньшего размера массивов. Массивы имели фиксированный размер (необходимый для быстрого поиска, поэтому вы можете быстро рассчитать задействованный массив и смещение для данного индекса), и мы создаем классы InputStream и OutputStream для этого Blob. Позже мы расширили его для замены и с диска.

• Нижняя сторона? Ничего, кроме небольшого простого усилия по программированию.
• Преимущества? Эффективное хранение больших данных в памяти, не более проблем с фрагментацией кучи.

Я могу только поощрять вас отдать это!

Answer 2

Стандартная библиотека C++ имеет как векторный класс (например, Java ArrayList), так и класс deque (другой класс типа List). Последний обеспечивает эффективное добавление и эффективное добавление. Реализация, которую я видел, поддерживала список блоков массивов с фиксированной длиной. Так что, как и случай, который вас интересует. Таким образом, это, безусловно, возможно.

Недостатком является повышенная сложность кода. Я предполагаю, что реализация в JRE может быть изменена, чтобы делать то, что вы предлагаете, с методом toByteArray, собирающим данные из фрагментов. Но делать это было бы очень низким приоритетом, потому что простая реализация была ослепительно быстрой. Любой код, выполняющий IO, должен предполагать, что чтение и запись являются медленными операциями, которые могут блокироваться. ByteArrayOutputStream вместо этого очень быстро, потому что он выполняет операции с памятью вместо истинного внешнего ввода-вывода. Копирование этих байтовых массивов вокруг, вероятно, будет намного быстрее, чем внешний IO. Недостатком текущей реализации является создание больших массивов мусора при использовании для больших потоков вывода.Но варианты использования для класса - для небольших потоков; если вы хотите временно сохранить байты большого выходного потока, вы должны использовать временный файл. Таким образом, сложность вашего предложения, вероятно, мало поможет на практике

Answer 3

Похоже, вы уже знаете преимущества. Недостатки списка буферов по сравнению с одного буфера включают:

• если буферы имеют фиксированный размер, вам нужно O (N) распределения памяти для записи п байт, ByteArrayOutputStream делает O (журнал N), поскольку буфер растет экспоненциально
• реализации сложнее: нужно следить за активный буфер, может понадобиться для переключения буферов в середине записи (в зависимости от конструкции)
• переключения буферов является промах кэша при чтении

Вы можете написать такую ​​структуру данных если это имеет смысл для вашего приложения

Answer 4

Так, кажется, нет никакой реальной реализации я быстро написал первоначальная реализация для проверки скорости:

public class Buffer { 

    private int size; 

    private int writeIndex, writeOffset, 
     readIndex, readOffset; 

    private List<byte[]> backingArrays = new ArrayList<byte[]>(); 

    public Buffer() { 
     this(10240); 
    } 

    public Buffer(int size) { 
     this.size = size; 
    } 

    public int read(byte [] bytes) { 
     return read(bytes, 0, bytes.length); 
    } 

    public int read(byte [] bytes, int offset, int length) { 
     int read = 0; 
     while(length > 0) { 
      byte [] input = getInput(); 
      // no more data 
      if (input == null) { 
       if (read == 0) 
        return -1; 
       else 
        return read; 
      } 
      int readLength = Math.min(length, (readIndex == writeIndex ? writeOffset : size) - readOffset); 
      System.arraycopy(input, readOffset, bytes, offset, readLength); 
      length -= readLength; 
      offset += readLength; 
      readOffset += readLength; 
      read += readLength; 
     } 
     return read; 
    } 

    public void write(byte [] bytes) { 
     write(bytes, 0, bytes.length); 
    } 

    public void write(byte [] bytes, int offset, int length) { 
     while (length > 0) { 
      byte [] output = getOutput(); 
      int writeLength = Math.min(length, output.length - writeOffset); 
      System.arraycopy(bytes, offset, output, writeOffset, writeLength); 
      length -= writeLength; 
      offset += writeLength; 
      writeOffset += writeLength; 
     } 
    } 

    private byte[] getOutput() { 
     // if we have filled an array, move to the next one 
     if (writeOffset >= size) { 
      writeIndex++; 
      writeOffset = 0; 
     } 
     // create it if it doesn't exist yet 
     if (backingArrays.size() <= writeIndex) 
      backingArrays.add(new byte[size]); 

     return backingArrays.get(writeIndex); 
    } 

    private byte [] getInput() { 
     // nothing written yet 
     if (backingArrays.size() == 0) 
      return null; 

     if (readOffset >= size) { 
      readIndex++; 
      readOffset = 0; 
     } 
     // can not read past where it is written 
     if (readIndex > writeIndex || (readIndex == writeIndex && readOffset >= writeOffset)) 
      return null; 
     else 
      return backingArrays.get(readIndex); 
    } 

    public long size() { 
     return (long) size * (long) writeIndex + writeOffset; 
    } 
} 

Я тестирую путем копирования файла в 36 мегабайт. Многое зависит от взаимодействия с файлами, но в целом на 40% быстрее читать быстрее, чем bytearrayinputstream (колеблется примерно на 5-20%).

Я быстро собрал это, чтобы поймать любые ошибки, дай мне знать.

EDIT:

Добавлена ​​функция, которая по умолчанию массивы, которые были считаны выпущены для дс