External Texture Load Speed

[ceriux]

baker, couldnt you just do a check or something the first time your texture search is ran? after its ran make a list and location of all files being replaced save it that way the engine knows what it has to do exactly the next time it loads? (maybe add in a cvar or something to refresh the search for replacements?) i have no idea what goes into engine coding im a noob to all that. but something like this might be a easier fix?

[mh]

baker, couldnt you just do a check or something the first time your texture search is ran? after its ran make a list and location of all files being replaced save it that way the engine knows what it has to do exactly the next time it loads? (maybe add in a cvar or something to refresh the search for replacements?) i have no idea what goes into engine coding im a noob to all that. but something like this might be a easier fix?

I had implemented this in earlier versions of DirectQ; it was faster to load files but slower on initial startup and game changes. In the end I felt that I would be happier with a more balanced solution.

I've just done the binary search idea on Quake 2 and it is significantly faster for loading maps. This is especially relevant here as Quake 2 stores textures externally in PAK files.

Some neat hacks are:

• If you use the CRT qsort and bsearch functions you can pass them the same comparison function.
• The comparison function just needs to return the result of a strcmp between the file names.
• It may be necessary to strlwr the PAK file names and the file name to search for so that typing "map e1m1" at the console would work if the map name was actually stored as "E1M1" in the PAK.
• Because the file name is the first item in the packfile_t struct you can just pass the char * arg to COM_FOpenFile as your search key to bsearch and it will work.

[Baker]

baker, couldnt you just do a check or something the first time your texture search is ran? after its ran make a list and location of all files being replaced save it that way the engine knows what it has to do exactly the next time it loads? (maybe add in a cvar or something to refresh the search for replacements?) i have no idea what goes into engine coding im a noob to all that. but something like this might be a easier fix?

I could have done any of the ideas in this thread. But the way I implemented loads them virtually instantly (mark what kind of files are in a pak, an index of the first occurence and last occurence of each file type).

So I started this thread not to look for solutions (there are many), but to bring the topic to light and share the experience of discovering this bottleneck firsthand.

[Spike]

This is especially relevant here as Quake 2 stores textures externally in PAK files.

Q2 also has '../' in some filenames within the pak.

[Knightmare]

Based on Baker's approach, I whipped up some quick code that returns a bit flag based on file extension. This can be easily customized based on what file types an engine uses. More than 32 extensions will require a 64-bit integer type.

Code: Select all

char *type_extensions[] =
{
	"bsp",
	"md2",
	"md3",
	"sp2",
	"dm2",
	"cin",
	"roq",
	"wav",
	"ogg",
	"pcx",
	"wal",
	"tga",
	"jpg",
	"png",
	"cfg",
	"txt",
	"def",
	"alias",
	"arena",
	"script",
	0
};

unsigned int FS_TypeFlagForPakItem (char *itemName)
{
	int		i;	
	char	extension[8];

	Com_FileExtension (itemName, extension, sizeof(extension));
	for (i=0; type_extensions[i]; i++) {
		if ( !Q_stricmp(extension, type_extensions[i]) )
			return (1<<i);
	}
	return 0;
}

EDIT: I just implemented this, and there is a noticeable speed up beyond what I got from checking hashes for pak items, especially for models and sounds.

[Baker]

Based on Baker's approach ...
EDIT: I just implemented this, and there is a noticeable speed up beyond what I got from checking hashes for pak items, especially for models and sounds.

When I produced Engine X prelease info (not here, but that's academic), I didn't say external texture load speed was fast. I said it was the fastest of any engine. And It is. As you noticed, it wasn't just external textures that benefited from the performance boost ... everything loads accelerated.

[mh]

Correct me if I'm wrong here, but I believe a binary search would be faster. In the case where you have say, 500 TGAs in a PAK file, if I understand this right you still need to do a linear search through all 500 in order to find the one you want. You can sort the PAK file directory by content type so that there are no other file types scattered in the midst of those 500, but best case is still a linear search of 500 items, meaning that for any given TGA - and assuming an even distribution of file names - you've an average of 250 checks before you find it. If it's not in the PAK you need to search all 500 before you can confirm that.

For a PAK file containing nothing but TGAs there is no gain - it's still a linear search through all of the PAK file contents.
Flagging the content types that a PAK file contains so that you can skip over searching through some PAKs sounds useful though. Binary search could also get this optimization.

That's assuming that I've understood this correctly.

With a binary search you get a worst case of ~9 searches for a PAK file containing 500 items, and that's for the case where a file is not present. You still need to sort the PAK directory on load, but that's a one-time-only operation.

Where linear search is better is that it's more cache-friendly for sure, but on balance I still believe that binary search is preferred.

Example: using binary search, I can load EngineX's Yellow No5 PAK for e1m3 in 0.101197 seconds; that's including time taken in disk access for reading files, the texture loader and animation sequencing, of course, but it seems nippy enough, and it's further optimizable by building a table of ranges for each letter that a file name can start with, and restricting the search to that range (which would also benefit linear if you sort the PAK directory beforehand). Some kind of comparable benchmark built into EngineX would be useful so that we could do a side-by-side on this.

As a total aside, this will crash:

Code: Select all

	if (!myImageWork.currentWork)
		Sys_Error ("Not in imagework, last was %s", myImageWork.currentWork);

[Baker]

Correct me if I'm wrong here, but I believe a binary search would be faster. In the case where you have say, 500 TGAs in a PAK file, if I understand this right you still need to do a linear search through all 500 in order to find the one you want. You can sort the PAK file directory by content type so that there are no other file types scattered in the midst of those 500, but best case is still a linear search of 500 items, meaning that for any given TGA - and assuming an even distribution of file names - you've an average of 250 checks before you find it. If it's not in the PAK you need to search all 500 before you can confirm that.

I'm sure the speeds could be improved even a bit further with your method, but I have it so fast I'd prefer to work on the all the rest of the stuff in my long queue of things I'd like to do.

But here is a dirty little secret to think about:

I added a few flags to indicate the contents of a PAK and a couple of fields to mark the first (start search at this index) and last index (end search at this index) per file type per pak.

All the .mdl tend to be in "progs". All the .wav tend to be in "sound". All the ".lmp" in gfx, etc.

So those files tend to be sequentially grouped together in a pak file. So by storing the first and last index, if there are 50 models total it only has to look through about 50 entries. Not because it knows what entries are "mdl" but because they happen to be in the same folder and sequential in pak file. Same with wav, etc. etc.

As a total aside, this will crash:

Code: Select all

	if (!myImageWork.currentWork)
		Sys_Error ("Not in imagework, last was %s", myImageWork.currentWork);

Oops Thanks for heads up on that. Yeah it should "printf" the description not that. I hate printf and the variable typing vulnerabilities that come with it.