I just thought about another possible way to reduce the look up time of textboxes (or other arbitrarily numbered homogeneous items) to O(1): just add a hash table to nodes with children. That way, one can use GetChildByName, and pull the box directly. Of course, hilarity would ensue with duplicate names... Hmm...
(The original idea posited here was a sorta complex tree sorted by digits counting from the low digit -- this is a lot easier!) -- Mike Caron -----Original Message----- From: Seth Hetu <[email protected]> Date: Fri, 9 Apr 2010 15:07:44 To: <[email protected]> Cc: <[email protected]> Subject: Re: [Ohrrpgce] RELOAD Delay Loading > Seems to me that the only way we could match that level of performance > is if every single reload node in the on-disk format kept an index of > the offets of all its children, so you could jump to node 21340 without > 21339 NextSibling calls Regarding this, and regarding Mike's plan in general, I have two completely unrelated points to make: 1) If you ALWAYS load in segments, then you'll face a huge penalty when initially loading the RPG, or when loading lots of data in general. (This is because disk access usually causes the calling process to be put into the waiting queue.) So, I propose modifying your idea slightly: A) Do everything you said earlier. B) On top of that, have a cache of files that you've read. Eject items from the cache using a queue-based modus, and have the eject policy be such that the the cache only ever contains a certain amount of data (say, 1mb). C) This way, if someone calls loadTextBox(1), then loadTextBox(2), ... loadTextBox(N), we only get the read penalty once. At the same time, we don't fill up too much extra memory. And, if the cache limit is big enough, then there will be no need to reload files when loading a lot of data at once (say, an entire map). 2) Regarding James's comment, above, I see two possible alternatives: A) For structures that we "know" are going to be big (like text boxes), the first time the file (lump?) is loaded, we save the indices of each message into a lookup table. If you think about it, it's unlikely that more than a handful of entries will ever rise above that "obnoxious" limit ---text boxes, npcs, maps, tilesets, and sounds are some that come to mind. B) Alternatively, you could try to automate the process. Create a second cache, similar to the one above, and every time a RELOAD file is loaded, save some kind of "lookup". Then, when the cache is full, eject the SMALLEST lookup entry (since the big ones are likely the ones we wanted to cache anyway). Sorry, Mike, I don't know the official name of a "smallest item" eject modus. -------The benefit to (B) is that it's relatively automatic. The problem is choosing how to store a "lookup" automatically. Perhaps if the ROOT reload node is of "array" type, then an index could be trivially created. But this is where I'll have to ask the experts. -->Seth _______________________________________________ Ohrrpgce mailing list [email protected] http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
