Opened 12 years ago

Closed 12 years ago

Last modified 17 months ago

#8912 closed patch

KYRA: ResFileEntry parent cache optimization

Reported by: tramboi Owned by: lordhoto
Priority: normal Component: Engine: Kyra
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)

kyra_resource_parent_cache_v3.diff (5.8 KB ) - added by tramboi 12 years ago.
kyra_resource_parent_cache_v5.diff (7.9 KB ) - added by tramboi 12 years ago.
kyra_resource_parent_cache_v6.diff (8.8 KB ) - added by tramboi 12 years ago.
kyra_resource_parent_cache_v7.diff (10.4 KB ) - added by tramboi 12 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 by tramboi, 12 years ago

File Added: kyra_resource_parent_cache.diff

by tramboi, 12 years ago

comment:2 by tramboi, 12 years ago

File Added: kyra_resource_parent_cache_v3.diff

by tramboi, 12 years ago

comment:3 by tramboi, 12 years ago

File Added: kyra_resource_parent_cache_v5.diff

by tramboi, 12 years ago

comment:4 by tramboi, 12 years ago

Always less map lookups File Added: kyra_resource_parent_cache_v6.diff

comment:5 by fingolfin, 12 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 tramboi, 12 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 lordhoto, 12 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 fingolfin, 12 years ago

Summary: [KYRA] ResFileEntry parent cache optimizationKYRA: ResFileEntry parent cache optimization

comment:9 by fingolfin, 12 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 tramboi, 12 years ago

comment:10 by tramboi, 12 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 fingolfin, 12 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 lordhoto, 12 years ago

Status: newclosed

comment:13 by lordhoto, 12 years ago

Committed (to both trunk and branch) with a slight formatting fix. Thanks for the patch.

comment:14 by digitall, 17 months ago

Component: Engine: Kyra
Note: See TracTickets for help on using tickets.