QFile seek performance

Question

It appears that QFile when working with a regular file (not a special Linux I/O device file) is random access, meaning that a seek operation has constant-time complexity O(1).

However, I haven't been able to confirm this. In general, when jumping to a specific position in a file (for writing or reading), does std::fstream and QFile provide constant-time running time complexity?

Answer 1

The short answer is "yes, for practical purposes". The long answer is... It's complicated.

Seeking on a file stream ultimately calls lseek() on the underlying file descriptor, whose performance depends on the kernel.

The running time will depend on what file system you are using and how large the files are. As the files get larger, random seeks require chasing more levels of "indirect" indexing blocks. But even for files up to 2^64 bytes, the number of levels is just a handful.

So in theory, seeking is probably O(log n); but in practice, it is essentially constant for a modern file system.