Difference between revisions of "Talk:VFS"
Jump to navigation
Jump to search
Line 61: | Line 61: | ||
== VFS index: std::map (low hanging fruit) == | == VFS index: std::map (low hanging fruit) == | ||
I've been reading through the STL source and documentation. std::map by itself is the wrong solution for the index. | I've been reading through the STL source and documentation. std::map by itself is the wrong solution for the index. [[User:Strife Onizuka|Strife Onizuka]] 11:29, 27 March 2007 (PDT) | ||
#It is only sorted explicitly (std::sort) | #It is only sorted explicitly (std::sort) | ||
#map.find has a n-based time frame. | #map.find has a n-based time frame. |
Revision as of 11:29, 27 March 2007
This is a talk page associated with the Open Source Portal. Changes to all pages like this one can be tracked by watching the "Related Changes" for "Category:Open Source Talk Page"
Please sign comments you leave here by putting four tildes (~~~~) at the end of your comment. For more guidelines, see Talk Page Guidelines
Please sign comments you leave here by putting four tildes (~~~~) at the end of your comment. For more guidelines, see Talk Page Guidelines
Related discussions:
Alternative implementation
Only desk-checked:
// N_LEVELS * N_CHARS should probably not be greater than 8, since there's a // separator in the UUID there. #define N_LEVELS 2 // UUID is hex, so 2 chars means maximum of 256 directories per level #define N_CHARS 2 #ifdef I_KNOW_THIS_ITS_A_UNIX_SYSTEM # define DIR_SEP '/' #else # define DIR_SEP '\\' #endif extern char *cache_dir; extern int safe_make_directory_path(char *path); FILE *fopen_texture(char *filename, char *mode) { int l = strlen(cache_dir); int m = strlen(filename); char *new_filename = calloc(l + 1 + m + N_LEVELS * (N_CHARS + 1) + 1); char *s, *t; int i, j; FILE *fp; if (!new_filename) return NULL; s = filename; t = new_filename; strcpy(t, cache_dir); t += l; for (i = 0; *s && i < N_LEVELS; i++) { *t++ = DIR_SEP; for (j = 0; *s && j < N_CHARS; j++) *t++ = *s++; } *t = '\0'; if (!safe_make_directory_path(new_filename)) return free(new_filename), NULL; *t++ = DIR_SEP; strcpy(t, filename); fp = fopen(new_filename, mode); free(new_filename); return fp; }
VFS index: std::map (low hanging fruit)
I've been reading through the STL source and documentation. std::map by itself is the wrong solution for the index. Strife Onizuka 11:29, 27 March 2007 (PDT)
- It is only sorted explicitly (std::sort)
- map.find has a n-based time frame.
- A cache with 20,000 assets has to do 20,000 comparisons when it wants to find out about the most recently added asset.
Solutions:
-
Sort the map:
- Keep the map sorted by doing a binary search to determine where an asset should be inserted.
- A cache with 20,000 assets would only have to do about 16 comparisons to add an asset
- Use std::lower_bound instead of map.find (map.lower_bound suffers from the same problem as map.find)
- The bulk of the index needs to be written to disk when a single asset is added. mIndexHoles & LLVFS::sync can't be used.
- Keep the map sorted by doing a binary search to determine where an asset should be inserted.
-
Keep a duplicated sorted map (without the holes):
- All requests into the cache would go through the new map, the old map is used to handle positions and allow for the use of mIndexHoles.
- Extra resources required for maintaining two maps.