WagicProject
Deck menu i/o while building the vector is not optimal.
From [email protected] on November 22, 2010 18:02:32
ive been trying to track down what is causing these 45 sec deckmenu load times on psp, which on pc appears only as a 5 sec stall on huge deck list.
it appears that its root is this function
bool sortByName(DeckMetaData * d1, DeckMetaData * d2) { return strcmp(d1->getName().c_str(), d2->getName().c_str()) < 0;
}
it is being done everything single time the menu is openned which by all means should be fine, however. on longer list this produces groutasque loading times for the menu.
possible to limit alphabetize to compare the first 3 letters and nothing more?
any possiblity of using maybe a quicker sorting mechanic?
Original issue: http://code.google.com/p/wagic/issues/detail?id=528
From [email protected] on November 22, 2010 09:03:44
maybe a possiblity of making this ONLY sort if changes were actually made to the menu list? or once on load up then again anytime you enter the deck editor?
From [email protected] on November 22, 2010 14:13:29
the idea here is to allow sorting on alternate levels, so it hasn't been implemented yet I know. I've been sidetracked by other features. I can move the sorting routine earlier up before the render. I'll try that.
The actual sorting algorithm is the default one used by vectors. The "sortByName" function is what that algorithm uses to determine order. part of the perf may be due to the conversion of a string to a c-style string. That can't be helped unless the class moves away from strings. It would be prudent to run a profile on the algorithm before any changes though, in case a change elsewhere would improve things more dramatically.
Wil? :)
From [email protected] on November 22, 2010 18:06:12
two things on top of my head:
-
CACHE. This is basic, this is simple, we use it everywhere. As long as no new AI decks are created, maintain a cache of their number in alphabetical order. First time you load will be a bit long, next time will have no problem. Invalidate the cache when a player creates a new deck for the AI. The same can go for the player's deck, it can probably be made generic with a hash of vectors/list For Ram reasons, store the id of the decks, not the name themselves. I assume the names themselves are also cached in the meta data cache anyways.
-
don't convert the strings to c_str, compare directly using the strings functions, you avoid extra conversions.
Another idea would be to have the meta deck cache be a hash (what is it now?) which is alphabetically sorted by default. insertion time takes a bit longer than expected, but display should be fast. We use that for cards in the deck editor, I think it's reasonably fast?
From [email protected] on November 24, 2010 09:12:10
i ran the profiler and its not the sorting that takes long. It's the I/O I think. I'm pretty sure it uses a cache as the information is from the DeckManager which is a singleton. If it ends up wiping out the singleton on every display, that's a different story. I'll check it out.
From [email protected] on November 24, 2010 10:07:30
keep in mind, if its taking 2 secs on the profiler on a pc, most likely thats a 30 sec+ timer on psp.
just something to keep in mind.
From [email protected] on November 24, 2010 15:25:59
The meta data cache is wiped every time you change the player's deck, in order to recompute the victories and stuff. maybe the cache for this should be a bit more clever. have a generic cache that doesn't change much (names,...), and then one that depends on the player's deck (victories, etc...)
From [email protected] on December 09, 2010 16:43:04
updated name to better match the situation.
Summary: Deck menu i/o while building the vector is not optimal.
From [email protected] on December 09, 2010 16:52:19
So, here is my suggested solution:
-
Improve the caching of the meta data to make "2nd time loading" almost instant. This is done by: -- storing meta data for all players decks (with a limit?) instead of only one deck. This way when the player switched decks, we stil have the valid information -- Sorting the decks alphabetically in the cache to avoid the extra sorting everytime. This is done by setting a sorting rule in the cache, and removing the sorting rule from the menu construction
-
Store the AI decks in a common zip file to avoid unnecessary I/O accesses. This needs to be a bit clever because we ALSO have decks generated by the game which most likely won't go in the zip file (same for playet's decks). I am assuming here that only AI decks need that, and that players have way less than 100 decks and therefoe don't need that zip technique, let me know if you think this is not a valid assumption
From [email protected] on December 09, 2010 18:12:13
if(wololo && assuming->phrase(that players have way less than 100 decks) return false; //this function tells wololo that hes incorrect.
actually i have 124 decks...i recently removed KF1s decks to see if load times would improve...and they didnt :/ but ive not bothered to readd them as im happy with current decks...
124 is not way less then 100 lol.
From [email protected] on December 09, 2010 20:10:25
Ok... well, the best I can think about for now would be to ask players who have 100's of decks to manually put them in a zip file once we suport it. Then, if we have the time to do that, add compression support for the zip format in wagic (we only support decompression for now). It doesn't have to actually compress anything (just store), the goal is to reduce the number of files, not their size.
From [email protected] on January 31, 2011 02:33:31
the recent set of changes will hopefully make the load time less painful. The next step is to either zip them up or implement a more lazily loaded menu.
From [email protected] on March 23, 2012 15:04:52
i dont think it is too bad anymore, infact it is barely noticable on android devices, i imagine it can be seen on psps but is the issue really worth keeping open when there is no way to make the psp format load it any faster?