gdal becomes painfully slow when used in directories with large number of files

[sroberts]

Starting with gdal-1.5.0 gdal operations done in directories with large number of files have become very slow. I'm working in a directory that has around 54,000 files with a mix of GeoTIFF's and other auxiliary files. So as an example, running gdaltindex on 500 GeoTIFF's that are in this directory using the command "gdaltindex foo.shp stere-2*tiff" will take only 3 seconds using version 1.4.2 but over 13 minutes using 1.5.0! Using gdalinfo on a single GeoTIFF on this director jumped from 00.05 to 01.35 seconds when using 1.5.0. And viewing these GeoTIFFs using mapserver linked to gdal 1.5.0 increased from around a second to over 1/2 minutes! Running strace on gdaltindex shows for every GeoTIFF open there is a corresponding:

open(".", O_RDONLY|O_NONBLOCK|O_LARGEFILE|O_DIRECTORY) = 7

It now appears that every time gdal opens a file it also generates a directory listing! I assume this is the source of the slowdown. And I assume this directory open is related to the 1.5.0 change "Added Identify() method on drivers (per RFC 11: Fast Format Identify)"? I should mention this is being done on RedHat? Linux.

-Steve

[warmerdam]

Steve,

Your analysis is correct. I shall incorporate a configuration option to supress the directory scanning operation in a normal open. This was an attempt to *reduce* directory accesses but it appears that scanning a directory for filenames is more expensive than I anticipated. I would add that 54000 is an unusually large number of files to have in one directory and I'm surprised you don't find the need to break this down into subdirectories more often!

Would this directory happen to be on a network disk or using an unusual filesystem?

[sroberts]

This is a slowly growing database with currently around a total of 9000 GeoTIFF's. Each GeoTIFF has several associated data and metadata files. Up until now I've noticed no performance issues with keeping all these files together so I've had no compelling need to complicate things and split these up. Unix doesn't seem to have a problem with this unless I try to do something like "ls".

I'm doing this on a locally mounted file system. I can also easily recreate the problem on my laptop which is an ext2 filesystem. Looking at the output of "strace gdaltindex ..." every 'open(".", ...' is followed by several hundred of these:

getdents64(7, /* 170 entries */, 4096) = 4096

which is then followed by ~20,0000 lines of:

mremap(0x40d2f000, 143360, 143360, MREMAP_MAYMOVE) = 0x40d2f000

And this is repeated for every GeoTIFF! So all the time seems to be spent on these "mremap" system calls. These calls only show up when the number of files in the directory exceed ~36000. I suspect this is due to exceeding a "soft" limit on the directory linked-list implementation.

[rouault]

In fact, the slow down is not due to I/O but to a performance problem in CSLAddString. This function does a CSLCount which must scan the whole list. Hence a O(n^{2) performance when building a list. I've fixed that in r13600 in trunk, and in r13601 in branches/1.5 by building the list without using CSLAddString.}

Note: I've only fixed VSIUnixStdioFilesystemHandler::ReadDir?. This should also probably done in VSIWin32FilesystemHandler::ReadDir?.

[rouault]

Message from Daniel Bäck posted on gdal-dev on 2008/01/29.

Hello,

We have identfied a serious performance problem with the reading of sibling
files performed in the GDALOpenInfo constructor.

When we commented out lines 123-127 in gdalopeninfo.cpp (the VSIReadDir
call), the runtime of our application went down from 150 days to 15! The
application is 100% i/O-bound (uses no cpu time according to the task
manager)

This is our setup:

7.5 million small (~20 KB) jpeg files with corresponding world files for a
total of 15 million files, distributed in 50000 directories (approximately
300 files per directory).

The files reside on a fast 15K SAS disk running in a Windows 2003 server
with 8 cores and 4 GB RAM. The filesystem is NTFS (no compression /
indexing).

Due to the way the files are organized, neighboring jpeg files are located
in different directories. This means that we always have to read the entire
directory in order to open just one file.

Our app needs to go read the entire dataset ordered geographically.
Unfortunately, changing the directory layout is not an option.

Reading one complete directory means reading ~1.5 MB data from disk. The
data is read non-sequentially, since the NTFS directory structure is a
B-Tree and FindNextFile returns the contents sorted alphabetically.
The disk cache gets exhausted after reading 2700 directories. This means
that we neve re-use the previously read directory data.

I realise that this might be a quite unusual case but it would be very nice
if the sibling reading in GDALOpenInfo was optional.

I don't think that the changes made in ticket #2158 (
http://trac.osgeo.org/gdal/ticket/2158) would help in this case since there
was almost no CPU utilization.

Regards,
  Daniel Bäck

[rouault]

In Daniel Bäck's case, effectively, the insertion of 300 files in a list is something cheap even if the insertion algorithm is O(n^{2). So, the hypothesis that file listing may be slow on NTFS sound reasonable.}

I finally reviewed GDAL code base and found that only few changes were required to make it work even with papszSiblingFiles == NULL. There are in fact only two drivers that needed changes : EHDR and GENBIN. The attached patch also introduces a new CPL configuration option, GDAL_LIST_SIBLING_FILES, set to TRUE by default. When set to NO, the VSIReadDir call is skipped and papszSiblingFiles set to NULL.

FrankW, what do you think of that ? It would also require to change a bit RFC-11 and state clearly that drivers must handle correctly the case where papszSiblingFiles == NULL, that is to say the behaviour before RFC-11 adoption.

[warmerdam]

As a preliminary step, I have modified GDALOpenInfo so that it won't read the directory file list if the GDAL_DISABLE_READDIR_ON_OPEN configuration variable is TRUE (r13627) and also fixed up a couple drivers that depending on the sibling list being read (r13626). These changes were made in trunk and jointly merged back into 1.5 branch as r13628.

Long term though this is not a great solution. Ideally we would identify a better (cheaper from an OS point of view) way of getting directory listings, or we would discard the whole sibling files mechanism if it turns out to be more of a hindrance than a help.

[warmerdam]

Seizing responsibility back from Even. :-)

[rouault]

I've commited the O(n^{2) -> O(n) optimization for WIN32 and MEM virtual file systems in trunk in r13643 and in branches/1.5 in r13644}

[rouault]

Some ideas and experiments :

I'm attaching a patch, gdal_svn_trunk_ that implements an idea I've discussed with a few others on IRC, that is to say a new function, VSIInstallCustomReadDirCallback, that enables the user to provide a callback that can short-circuit VSIReadDir with a custom implementation. I'm also attaching a simple test file that use this API and lists all the files in a directory and displays the raster dimensions.

Another possibility would be to add a GDALOpenExt that would accept papszSiblingFiles as an extra argument, like GDALIdentifyDriver.

I have also noticed that GDALDefaultOverviews::Initialize can take a papszSiblingFiles argument, but no GDAL driver currently passes its poOpenInfo->papszSiblingFiles to GDALDefaultOverviews::Initialize. This would reduce the number of stats/opens done when opening a dataset. Drivers relying on GDALReadWorldFile (PNG, JPEG, GTiff, NITF, MRSID, ECW, BMP, etc..) could also use a new function GDALReadWorldFileExt that would take papszSiblingFiles as an extra argument.

[rouault]

There was a missing variable initialization and missing osPath arguments. Fixed in trunk in r13846 and in branches/1.5 in r13847

[mloskot]

For records, here is related discussion thread on  VSIReadDir() and GDALOpenInfo archived in Jan 2008.

New milestone needed?