Performance problem when reading binary data from a file in C

Question

I am writing a program that reads signal values from a file. My current problem is that I have a problem with the performance, the data cannot be read out fast enough.

The format of how the signal values (most of the time 32bit floating-point) are stored in the file is as follows:

(The file was loaded into main memory, also this is a binary file).

The basic format is as follows:

1. I have a starting address at which the numbers are stored.
2. There is always more than one block of data, depending on who created it.
3. There is one offset per block, as mentioned in 2.
4. I have given the number of elements I have to read out.

If you had to sketch it, it looks like this:

The blue blocks are the data I have to read out or write into an array, so that they are in a array. The spacing between the blue boxes is always the same, but it can be that the spacing is larger than a cacheline, which (I suspect) causes performance to suffer a lot.

My current code:

void extract_4byte_blocks(
    size_t offset_of_entry,
    size_t offset_between_elements,
    char *arr,
    size_t size_of_array,
    char * start_of_data) {

    char *next_block_start = (char *) start_of_data;

    for (size_t i = 0; i < size_of_array; ++i) {

        char *src = next_block_start + offset_of_entry;
        char *dest = arr + i * 4;
        next_block_start += offset_between_elements;

        memcpy(dest, src, 4);
    }
}

Current profiling data:

Execution time:

Cache:

Does anyone have a tip on what I can do to improve performance?

---

I fired up the profiler again and this time with -O3 and then I remembered why I stopped profiling with -O3. I can't read anything out and the time gain of 2 seconds is not so good that I can say I can live with it.The only thing that has changed is that the compiler has probably inlined everything or something. Which is how the duration gets into the calling function.

As you can see, the main problem is reading. I get the most cache misses, which is what I suspected. I have looked at the offset_between_elements. And as suspected, it can be very large. The offset_between_elements is (for those reads that are the most performance demanding) 2632, 2210, 109 and 366 bytes. Ergo, each read results in a cache miss.

Answer 1

Although I have not activated any optimisation in the profiling, I checked with godbolt and, with the index calculation, it optimises itself away

Then your profiling makes no sense at all. Trust your compiler.

When you do not optimize your function accesses memory 24 times. When you optimize it does only 2 times. 12x more memory accesses. Profiling without optimizations makes no sense at all.

extract_4byte_blocks:                       |   extract_4byte_blocks:
        test    rcx, rcx                    |            push    rbp
        je      .L1                         |            mov     rbp, rsp
        add     r8, rdi                     |           mov     QWORD PTR [rbp-40], rdi     
        lea     rcx, [rdx+rcx*4]            |            mov     QWORD PTR [rbp-48], rsi
.L3:                                        |            mov     QWORD PTR [rbp-56], rdx
        mov     eax, DWORD PTR [r8]         |            mov     QWORD PTR [rbp-64], rcx
        add     rdx, 4                      |            mov     QWORD PTR [rbp-72], r8
        add     r8, rsi                     |            mov     rax, QWORD PTR [rbp-72]
        mov     DWORD PTR [rdx-4], eax      |            mov     QWORD PTR [rbp-8], rax
        cmp     rdx, rcx                    |            mov     QWORD PTR [rbp-16], 0
        jne     .L3                         |            jmp     .L2
.L1:                                        |    .L3:
        ret                                 |            mov     rdx, QWORD PTR [rbp-8]
                                            |            mov     rax, QWORD PTR [rbp-40]
                                            |            add     rax, rdx
                                            |            mov     QWORD PTR [rbp-24], rax
                                            |            mov     rax, QWORD PTR [rbp-16]
                                            |            lea     rdx, [0+rax*4]
                                            |            mov     rax, QWORD PTR [rbp-56]
                                            |            add     rax, rdx
                                            |            mov     QWORD PTR [rbp-32], rax
                                            |            mov     rax, QWORD PTR [rbp-48]
                                            |            add     QWORD PTR [rbp-8], rax
                                            |            mov     rax, QWORD PTR [rbp-24]
                                            |            mov     edx, DWORD PTR [rax]
                                            |            mov     rax, QWORD PTR [rbp-32]
                                            |            mov     DWORD PTR [rax], edx
                                            |            add     QWORD PTR [rbp-16], 1
                                            |    .L2:
                                            |            mov     rax, QWORD PTR [rbp-16]
                                            |            cmp     rax, QWORD PTR [rbp-64]
                                            |            jb      .L3
                                            |            nop
                                            |            nop
                                            |            pop     rbp
                                            |            ret        

https://godbolt.org/z/q4nfE7qoK

You may also try to force gcc to unroll the loops by using pragmas

#pragma GCC unroll 16
    for (size_t i = 0; i < size_of_array; ++i) {

But you neet to profile because unrolling loops may have adverse effect on the performance. Everything depends on the program.

For large files I would suggest having another task/thread loading new data from the file whilst you process the current one.

Answer 2

It may depend on the size of your data to read. You can at least eliminate some computations as offset is always the same as also the length of the copy:

char *src = (char *) start_of_data + offset_of_entry;
char *dest = arr;

for (size_t i = 0; i < size_of_array; ++i) {
    memcpy(dest, src, 4);
    dest += 4;
    src += offset_between_elements;
}

Aside: The file was loaded into main memory. If the file is huge, that may not be a good idea.