C++ Чтение первых нескольких байтов из каждого X байта эффективно

Question

Я хочу прочитать первые 16 байтов из каждого файла размером * * 16 байтов. Код, который я написал, работает, но довольно медленный из-за многих вызовов функций.

std::vector<Vertex> readFile(int maxVertexCount) { 
    std::ifstream in = std::ifstream(fileName, std::ios::binary); 
    in.seekg(0, in.end); 
    int fileLength = in.tellg(); 
    int vertexCount = fileLength/16; 

    int stepSize = std::max(1, vertexCount/maxVertexCount); 

    std::vector<Vertex> vertices; 
    vertices.reserve(vertexCount/stepSize); 
    for (int i = 0; i < vertexCount; i += stepSize) { 
     in.seekg(i * 16, in.beg); 
     char bytes[16]; 
     in.read(bytes, 16); 
     vertices.push_back(Vertex(bytes)); 
    } 
    in.close(); 
} 

Может кто-нибудь дать мне несколько предложений по повышению эффективности этого кода?

Answer 1

Вероятно, функция не вызывает себя, а не последовательный шаблон доступа, выделяя небольшие сегменты из большого файла. Несмотря на то, что вы читаете только 16 байт, подсистема хранения, скорее всего, считывает (и кэширует) большие блоки. Ваш шаблон доступа смертелен для типичных операций ввода-вывода.

(профилирование должен показать доступ к диску, является ли горлышко бутылки. Если бы это было «много вызовов функций», CPU будет.)

Итак, в первую очередь, вы можете изменить это требование?
Это самый простой выход из всех сценариев.

Не могли бы вы рассеять меньше? Например. вместо чтения вершин 0, 20, 40, ..., 1000, считанных вершин 0,1,2,3,4, 100, 101, 102, 103, 104, 200, 201, 202, 203, 204, .. . - то же количество вершин, из «всех частей» файла.

Во-вторых, Особые оптимизации ОС.
Нет никакого портативного способа управления кэшированием уровня ОС.

Одним из решений является сопоставление памяти файла (CreaterFileMapping на Windows, mmap на системах Linux), как было предложено @Nim. Это может опустить одну копию памяти, но все же будет прочитан весь файл.

не может помочь много с Linux, но на Windows, у вас есть в качестве параметров CreateFile:

• FILE_FLAG_NO_BUFFERING, которые в основном означает, что вы сделать буферизацию, что дает вам больше контроля над кэшированием, что происходит, но вы не можете искать + читать волей-неволей.

• FILE_FLAG_SEQUENTIAL_SCAN который только telsl кэш не хранить старые данные

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

В-третьих, Снимок.
Лучшим вариантом может быть сохранение перемеженного моментального снимка либо в связанном файле.

Снимок может быть просто результатом вашей операции, для конкретного maxVertexCount. Или несколько снимков, например mipmapping. Идея состоит в том, чтобы заменить рассеянное чтение последовательным чтением.

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

64, 32, 96, 16, 48, 80, 112 8, 24, 40, 56, 72, 88, 104, 120 ...

ли вы прочитайте первые 3 или первые 7 или первые 15 или первые 31 ... значения, образцы равномерно распределены по файлу, как в исходном коде. Переупорядочение их в памяти будет намного быстрее - особенно если это всего лишь небольшое подмножество.

Примечание: вам нужен надежный алгоритм для обнаружения того, что ваш снимок устарел, независимо от многих забавных вещей, которые происходят с «последней датой записи» в разных файловых системах. «Счетчик изменений» в главном файле был бы самым безопасным (хотя это уменьшило бы стоимость изменений).

В-четвертых, Изменить формат файла

(В случае, если вы можете контролировать, что) Перемеженный хранения предложено выше, может быть использован для всего файла. Однако это имеет большое значение для обработки - особенно если вам нужно восстановить «оригинальный» порядок в какой-то момент.

Элегантный вариант будет иметь такое перемеженное подмножество как часть файла, и полный список вершин в исходном порядке.Существует обрезание stepSize, где это больше не помогает, возможно, около 2 * сектора/размера блока на диске. Таким образом, размер файла увеличился бы всего на несколько процентов. Тем не менее, записи станут немного более дорогостоящими, значительно изменится количество вершин.

---

предупреждение Aliasing

Если это предназначено, чтобы получить «статистический» или «визуально достаточный» выборки, фиксированный stepSize может быть проблематичным, так как это может создать эффект наложения спектров (думаю Муаровые) с любыми шаблонами, присутствующими в данных.

В этом случае предпочтительным будет случайный выборка. Это может показаться страшным и делает некоторые из решений выше немного сложнее, но часто это самый простой способ избежать многих субоптимальных случаев.

Answer 2

Не используйте seek, я бы mmap весь этот файл, а затем просто прочитал байты в нужном месте.

Я не собираюсь писать код для вас, но это должно быть вдоль линий:

1. Откройте файл, вычислить размер файла
2. mmap весь файл
3. итерацию через ваши размеры шага, вычисляющие адрес каждого блока
4. Постройте каждый Vertex на основе блока и нажмите на вектор
5. вернуть вектор.

Answer 3

... и если по каким-то причинам вы не можете использовать map прочитать файл в буфер в «больших больших глотков» ... буферным размера, который некоторые кратно X байт. Продолжайте чтение в этот буфер (обратите внимание, сколько байтов было). пока не дойдете до конца файла.

Что вы конкретно пытаетесь избежать целая куча физической операций ввода/вывода: движение механизма чтения/записи диска. По этой причине операционная система любит буферизовать вещи, но может только угадать при чем ваше приложение пытается сделать, и оно может догадаться неправильно. Как только диск позиционирует головку чтения/записи на нужную дорожку («время поиска»), он может извлекать данные целиком за один оборот. Но «искать время» сравнительно медленно.

Отображение файла, а затем читает данные в файле отображенной неслучайным, несомненно, является наиболее благоприятной стратегией, потому что теперь операционная система знает точно, что происходит.

Answer 4

Во-первых, я согласен, что вы возвращаете вектор по значению из определения, хотя в вашем опубликованном коде отсутствует оператор return, поэтому вектор должен быть скопирован. Передайте его по ссылке в свой метод, поэтому копирование не требуется.

И вы можете использовать низкоуровневые pread() читать без необходимости искать:

void readFile(size_t maxVertexCount, std::vector<Vertex> &vertices) 
{ 
    struct stat sb; 
    int fd = std::open(fileName, O_RDONLY); 
    std::fstat(fd, &sb); 

    size_t vertexCount = sb.st_size/16; 

    size_t stepSize = std::max(1, vertexCount/maxVertexCount); 

    vertices.reserve(vertexCount/stepSize); 

    for (off_t i = 0; i < vertexCount; i += stepSize) 
    { 
     char bytes[ 16 ]; 
     std::pread(fd, bytes, 16, 16 * i); 
     vertices.push_back(Vertex(bytes)); 
    } 

    std::close(fd); 
} 

Вы должны быть в состоянии выяснить необходимые обработки ошибок и файлы заголовков.

Это позволяет использовать кеш страницы и, вероятно, читать дальше. В зависимости от вашей ОС и конфигурации другие методы, такие как mmap() или чтение всего файла, могут быть или не быть быстрее.