Why stat64() in linux becomes slower as the number of files in a directory increases?

Question

I run stat64() for 1000 files in a folder and took less than 1s but when there were 5000 in the same directory, the time increased to 15s.

Why stat64 () is getting slow non -linearly ? I was expecting the time to be 5s

EDIT I am reading data from a USB with FAT file system.

Answer 1

When you are calling stat64 for a file in a directory which contains N entries, then the complexity is O(N) because with FAT file system the system has to walk through all directory entries and compare each to the one you are looking for.

When you are calling stat64 M times in a folder which contains N entries, then the complexity is O(M*N) and in the case there M=N you end up with O(N*N).

Looking at your example: when you have and stat64 factor 5 files, then you need factor 25 time. If your 1s time in fact was 0.6 seconds, then the results are as expected.