Data Structure Efficiency

[alusch]

Hello everyone,

I've been a big fan of LucasArts adventures and SCUMMVM for a long time. For my data structures class this semester, we have an assignment to pick an open source project and modify one of its data structures to increase efficiency. I'd like to work on SCUMMVM, and I was wondering if anyone had any suggestions. I was considering your HashMap, but would be open to other possibilities. If this is the wrong place for this question, I apologize, and I would love to know where I should look. Thanks for all your help.

Adam

[clem]

not all devs read the forum - you might get more immediate feedback on IRC:
#scummvm on Freenode (irc.freenode.net)

[eriktorbjorn]

I was considering your HashMap, but would be open to other possibilities.

I guess you could try using a profile to find out where ScummVM is spending most of the time. That should give an indication on whether or not optimising HashMap will make any noticeable difference.

[sev]

I was considering your HashMap, but would be open to other possibilities.

I guess you could try using a profile to find out where ScummVM is spending most of the time. That should give an indication on whether or not optimising HashMap will make any noticeable difference.

That will be extremely engine-dependent, and I suppose, most time is used for rendering anyway.

HashMap is not bad candidate, but not just that, but how it is used in our GUI code. Even today, after optimizations, it takes noticeable time to load GUI theme. So if you would look into that, that will be helpful.


Eugene

[fingolfin]

However, I don't think that the Hashmap is the best candidate if you are looking for bottlenecks in the GUI loading code... but maybe I am wrong. It certainly wouldn't hurt for somebody to investigate that. At least as long as it means you are using profiling tools etc. instead of just making blind "optimizations", of course. But I'll assume that is what is meant

[alusch]

Thanks for the replies. Does anyone know of any good profiling tools for Linux? Also, are there any suggestions for a different data structure that might be more problematic? Thanks again.

[eriktorbjorn]

Thanks for the replies. Does anyone know of any good profiling tools for Linux? Also, are there any suggestions for a different data structure that might be more problematic? Thanks again.

I don't have much experience with profiling, really, so I can't judge which are good tools and which aren't. The GCC manual mentions gprof (which I have used a little) and gcov (which I haven't). Valgrind claims to be able to do some types of profiling, but I've only used it as a tool to find errors.

[criezy]

I have used recently Valgrind (version 3.2 with Cachegrind tool and its Callgrind extension) for profiling some of my applications. Coupled with the KCacheGrind front-end I have found it very easy to use and powerful (at least much easier than oprofile). However it is quite slow (slower than other profiling tools I have tried).
You didn't say "free tool" so I will mention PurifyPlus (actually Quantify for the profiling part) which imho is still the best on Linux/Unix. But considering the price, if your university don't have it I suggest you use Valgrind.

[fingolfin]

All in all I think there is not much, if anything, to improve in ScummVM when it comes to terms of speed and data structures. Optimizing memory usage of our data structures might be helpful, though, as would reducing the number of malloc/new calls being made.

All in all, on desktops, ScummVM is fast enough as it is. The machines for which one should optimize are the small hand held devices. However, the profiler output on a regular PC is only very partially helpful to speed up these, as they might have totally different "tight" spots.

I think the spots were we "loose" most of our speed/time will be graphics blitting and sound generation. Data structure improvements won't help much there.

The other front which always needs optimization is memory usage, as many of those small devices have little memory.

[sev]

OKay, a data-related task just came to my mind. SAGA engine uses complex pathfinding on its isometric rooms. It takes noticeable time to calculate that, so there is a definite room for improvement.

It could be tested even with demo version of Inherit the Earth game which you could find on Wyrmkeep site. Leave first screen and you will find yourself in a isometric room.


Eugene