#8912 closed patch
KYRA: ResFileEntry parent cache optimization
| Reported by: | tramboi | Owned by: | lordhoto |
|---|---|---|---|
| Priority: | normal | Component: | Engine: Kyra |
| Version: | Keywords: | ||
| Cc: | Game: |
Description
This patch minimizes string creations/destructions and hash map lookups in the Kyra resource management system.
Ticket imported from: #2055831. Ticket imported from: patches/1017.
Attachments (4)
Change History (18)
comment:1 by , 16 years ago
by , 16 years ago
| Attachment: | kyra_resource_parent_cache_v3.diff added |
|---|
by , 16 years ago
| Attachment: | kyra_resource_parent_cache_v5.diff added |
|---|
by , 16 years ago
| Attachment: | kyra_resource_parent_cache_v6.diff added |
|---|
comment:5 by , 16 years ago
Bertrand, please provide some motivation for the patch: I.e. don't just state what it does, but also *why* it does it. Like: "Without this patch, Kyra is unusable on system X, with it, performance increases by Y" or "memory usage drops by Z which allows using Kyra on device ABC, on which it previously did not run".
After all, code optimizations like this are always a tread-off: Simple code which does not care much about memory/CPU resource preservation; vs. complex code with better resource management. So, it is not automatically evident (at least to me), that your patch has any merits. Hence the wish to get an explanation as to what the supposed merits *are* :).
comment:6 by , 16 years ago
Max, Johannes, dear unknown reader :)
without this patch launching Kyrandia 3 does 1.750.000 hashmap lookups (launcher GUI and other stuff included). Each of these need hashing a string, calculating a modulo, and pointer-walking the bucket while comparing the strings. It is expensive per se, but on top of that division is software emulated on the NDS (and probably GP2X) and is very expensive (think one or two hundred cycles).
This patch is to cache some results and replace total iterations (for file type detection) on the resource map by cherry picking the right stuff to do. Once applied, it gets down to 45.000 lookups, much more reasonable, and it alleviates a very big part of the CPU cost of launching the Kyrandia games.
(Btw you're totally right to ask for precisions, and I wish I'd see the same kind of metrics for the blitting optimizations, for instance, instead of blindly optimizing the code in case it becomes faster).
Hope what I want to achieve here is clearer :) Bertrand
comment:7 by , 16 years ago
Apart from some formatting glitches (also usage of NULL instead of 0) and that global 'debug' vars, it looks fine to me actually.
comment:8 by , 16 years ago
| Summary: | [KYRA] ResFileEntry parent cache optimization → KYRA: ResFileEntry parent cache optimization |
|---|
comment:9 by , 16 years ago
Bertrand, Johannes, thanks for the reply:
* Reducing from 1.7 mio lookups to some ten thousands certainly sounds like a great improvement. As LordHoto approves of the change, it's fine by me.
* If you have ideas on how to improve the HashMap code, feel free to submit them to scummvm-devel, that would be much appreciated. One clear optimization would be to use powers of 2 for the hashtable sizes. That requires some changes to the rest of the code, of course. Maybe a good idea would be to rewrite the code based on the python dictionary implementation. Anyway, the mailing list is a better place to discuss this :)
* If you have issues with the SCUMM GFX changes, then say so on scummvm-devel; this patch tracker item is the wrong place for it.
* As LordHoto already pointed, please adjust the code formatting to match our guidelines. In particular, don't write } else { but rather } else {
* While I am at it: Please change isAccessable to isAccessible (i.e. proper english); of course this is not an issue of this patch, but of the code it patches ;)
* All in all: Great work, now that I know, what it is about :)
by , 16 years ago
| Attachment: | kyra_resource_parent_cache_v7.diff added |
|---|
comment:10 by , 16 years ago
Here we go! I fixed the coding conventions issues that were left (I think), removed the debug code that exhibited the cache hit/miss rate and renamed isAccessable to a proper isAccessible. Good day to you sirs, hear you on the mailing list Tramb
File Added: kyra_resource_parent_cache_v7.diff
comment:11 by , 16 years ago
See here for an experimental HashMap rewrite: <https://sourceforge.net/tracker/index.php?func=detail&aid=2062263&group_id=37116&atid=418822>
comment:12 by , 16 years ago
| Status: | new → closed |
|---|
comment:13 by , 16 years ago
Committed (to both trunk and branch) with a slight formatting fix. Thanks for the patch.
comment:14 by , 6 years ago
| Component: | → Engine: Kyra |
|---|
File Added: kyra_resource_parent_cache.diff