Loading images takes a tremendous amount of time

[Sigra]

Widelands uses far too many small image files. For example simply starting the editor from the game main menu takes over 16 seconds. Some numbers:
$ find tribes/barbarians -name *.png|wc -l
3401
$ find tribes/empire -name *.png|wc -l
3413
$ find worlds/greenland -name *.png|wc -l
195
$ find worlds/blackland -name *.png|wc -l
211
$ find worlds/desert -name *.png|wc -l
187
$ find worlds/winterland -name *.png|wc -l
213

The images should be combined in MNGs, image maps or tars. The issue has been discussed:
http://www.libsdl.org/pipermail/sdl/2001-May/035869.html

[Sigra (sigra)]

Logged In: YES
user_id=31104
Originator: YES

Sorry, but revision 2074 did NOT fix this problem, it fixed bug #1670140.

[Sigra (sigra)]

Logged In: YES
user_id=31104
Originator: YES

Here are my findings:

Using MNG from SDL:
===================
SDL_mng [http://cryptology.org/research/SDL MNG Library/]
SDL_mng-0.1 test report:
SDL_mng-0.1> ./autogen.sh
Generating aclocal.m4
/usr/share/aclocal/sdlmm.m4:12: warning: underquoted definition of AM_PATH_SDLMM
/usr/share/aclocal/sdlmm.m4:12: run info '(automake)Extending aclocal'
/usr/share/aclocal/sdlmm.m4:12: or see http://sources.redhat.com/automake/automake.html#Extending-aclocal
Generating Makefile.in
configure.ac:6: installing `./config.sub'
configure.ac:10: installing `./missing'
configure.ac:10: installing `./install-sh'
configure.ac:6: installing `./config.guess'
Makefile.am: installing `./depcomp'
configure.ac:14: required file `./ltmain.sh' not found
Generating configure file

I worked around the problem:
SDL_mng-0.1> ln -s /usr/share/libtool/ltmain.sh .
SDL_mng-0.1> ./autogen.sh
Generating aclocal.m4
/usr/share/aclocal/sdlmm.m4:12: warning: underquoted definition of AM_PATH_SDLMM
/usr/share/aclocal/sdlmm.m4:12: run info '(automake)Extending aclocal'
/usr/share/aclocal/sdlmm.m4:12: or see http://sources.redhat.com/automake/automake.html#Extending-aclocal
Generating Makefile.in
Generating configure file

Then configure works. But make ends with:
/bin/sh ./libtool --tag=CC --mode=link gcc -g -O2 -DLOAD_PNG -I/usr/include/SDL -D_GNU_SOURCE=1 -D_REENTRANT -o libSDL_mng.la -rpath /usr/local/lib SDL_mng.lo @IMG_LIBS@ -lpng -lz -lSDL -lpthread
gcc -shared .libs/SDL_mng.o /usr/lib/libpng12.so -lz /usr/lib/libSDL.so -L/usr/lib -lpthread @IMG_LIBS@ -Wl,-soname -Wl,libSDL_mng.so.0 -o .libs/libSDL_mng.so.0.0.0
gcc: @IMG_LIBS@: No such file or directory
make: *** [libSDL_mng.la] Fel 1

I commented out the line "libSDL_mng_la_LIBADD = @IMG_LIBS@" in Makefile.am and did "./autogen.sh;configure;make" again. Then I could run ./mngtest and see the dancing panda.

Creating MNG files:
===================
png2mng.pl (in kdesdk-scripts)
It is hardcoded for 4-digit frame numbers, but changing this line:
 $file = $basename.sprintf('%04d.png', $i+1);
to
 $file = $basename.sprintf('%02d.png', $i+1);
makes it accept files with 2-digit frame numbers, like in Widelands.

I tried to create a mng for the empire flag (tribes/empire/pics/flag_??.png):
png2mng.pl flag_ 32 42>flag.mng but the resulting file is not shown in
konqueror nor the SDL_mng test program. advmng can not handle it either.

Optimizing MNG files:
=====================
advancecomp (Gentoo package exists)
Manual says it is not general-purpouse but specifically for files generated by
the AdvanceMAME emulator.

[Sigra (sigra)]

Logged In: YES
user_id=31104
Originator: YES

The script for building MNGs actually does work. The problem was most likely that I did not put a space between "42" and ">flag.mng", which seems to be necessary, since the shell interprets a decimal digit immediately followed by a '>' specially.

[Sigra (sigra)]

Logged In: YES
user_id=31104
Originator: YES

Upon request Michael Pyne has improved png2mng.pl so that it can easily be used for converting Widelands animations to MNG. He added command line options for:
* Framerate
* Number of digits in frame number part of filename (such as "flag_??.png" versus "flag_????????.png")
* First frame number (such as "flag_00.png" versus "flag_01.png").
The improved version of the script and information about the change can be reached from [http://websvn.kde.org/trunk/KDE/kdesdk/scripts/png2mng.pl]. Many thanks to Michael Pyne for this.

I have opened a tracker item for integrating SDL_mng into SDL_image and got a positive response from Dennis Payne, see [http://bugzilla.libsdl.org/show_bug.cgi?id=401].

[Nicolai Hähnle (nha)]

Logged In: YES
user_id=211820
Originator: NO

Is libsdl-mng typically available in distributions? It doesn't seem to be in Ubuntu.

That's a pity, but I don't really fancy maintaining my own copy of it. The other question is whether this would actually speed up the load time. Have you done any experiments?

[Sigra (sigra)]

Logged In: YES
user_id=31104
Originator: YES

I have contacted the author of SDL_anim about bringing it up to date and making it useful for Widelands and he responded positively with a lot of interesting thoughts. I hope he will comment here.

I have of course not made any measurements, because there is no implementation to measure. But some basic thinking indicates that MGN would be much more effective for storing animations than PNG. MNG can do compression over multiple frames, which is absolutely necessary for compressing animations efficiently. Storing each frame separately is grossly inefficient, since it has to store the whole image for each frame, even if only a few pixels differ.

Suppose we have an animation of a man waving his hand. With PNG we would have to store the look of the man in every frame, just because the hand differs. With MNG the look of the man is only stored once. Same if we have a large building with a small animated part, like a wheel or fire.

Smaller size means faster loading assuming that the loading is I/O bound. It also means fewer files to load, which means fewer system calls and less and faster filesystem searches.

[mquinson (mquinson-users)]

The link provided is not valid anymore. I digged a bit and found this link probably being the current replacement:
http://lists.libsdl.org/pipermail/sdl-libsdl.org/2001-May/017244.html

[SirVer (sirver)]

Gabriel, we discussed MNG back in the days and found that it was not very well supported. Not by graphics program (creating/viewing) and not by libraries (most solution we found were quite hackish). Also, the reduction of the files to read would not be dramatic.

I suggest that you make a quick-n-dirty hack first and profile this if it really makes significant improvements in the loading of the graphics (cold harddrive cache will be important). I doubt it. And if this is the case, we need to roll a system of our own - I have an idea for that which would also give some other advantages - we could discuss this then.

[Gabriel Margiani (gamag)]

Ok, I pushed a version with mng-support (needs libmng) and all animations in mngs.

The support is really a problem. To make the mng's as little as possible
they need to use the mng-delta format, witch isn't supported by most converters
and libs. advmng (advanceComp) supports delta, but not all depths used by the pngs,
convert doesn't support delta but can read more pngs.
I used advmng if possible and convert on the rest.
so I could reduce the size of the tribes folder by 50% to ~33mb
In the worlds folder I lost the transparency of many animations using advmng, so I used
convert and the folder is now approx . 1mb bigger than before.

At the moment we have a little bit more images than when this bug was reported
no mng:
$ find tribes/ -name *.png|wc -l
36854

$ find worlds/ -name *.png|wc -l
5860

mng:
$ find tribes/ -name *.mng|wc -l
2128
$ find tribes/ -name *.png|wc -l
1157

$ find worlds/ -name *.mng|wc -l
386
$ find worlds/ -name *.png|wc -l
512

Loading the barbarians and greenland mng animations takes 80% of the normal loading time
(say using mng 12 sec, no mng 15 sec).

[Nasenbaer (nasenbaer)]

hmmm 12 sec vs 15 secs is not really worth the trouble.

Did you try this with a debug or a release build? I think only the compared loading times off release time would be interesting in this case, as that would be the "end user version"

if those numbers are from a release build, I would vote for "Won't fix!"

In any case thank you a lot Gabriel for your effort :) !

[Jens Beyer (qcumber-some)]

12s and 15s sounds a lot like filesystem cache...

Those are close to the numbers I'm getting by loading from TMPFS... are you sure you measured with cold cache?

If this is from FS cache, it would be necessary to have the same measurement for example directly after starting the computer.

Another way to achieve maybe the same goal but without the poor MNG support would be delivering small ZIP archives containing one animation each. This archive could be built by build script, it would be possible to use the same caching algorithm which is used for languages, so it would not slow down regular development.

[SirVer (sirver)]

The last two comments are very valid: HD cache must be disabled/taken
into account and release builds are the only thing that matters.

Also: widelands is able to read from .zip files. We could just zip the
tribes directory up and widelands would only need one big file - this
should speed loading up also.

I want to write quickly about the alternative idea I had in my head:
It is thought out to solve two problems: redundancy in animation frames
of buildings/bobs (frame 1 is basically the same as frame 2 except for a
few pixels, maybe just the door opening or so) and the ability to
'stack' animations (e.g. the mine-empty sign we now have vanishes when
the mine tries to work because mine-empty is a new animation, similar to
'idle' but entirely separated).

My idea was the following: each building/bob gets a 'base' animation
that contains unchanged pixels, those that never change. All animations
are then 'stacked' upon this. E.g. empty mine would be "base + idle +
empty_mine" and a working empty mine would be "base + working +
empty_mine". The phases are drawn after each other.

The magic would be in a script that would convert from our current
representation to a single .png file that would basically be a sprite
image (see CSS sprites, the original idea comes from Amiga days) with
x,y offsets to be plotted. The same script can also revert back from the
new representation + conf files to the individual frames of each
'stacked' animation. For the graphics people this would involve one more
step after rendering, namely running this script. The graphic files
would be less intuitive in the directories, but still easy to understand
(I assume). I discussed this with ixprefect on the wihack and with chuck
afterwards, but I have not started implementing this in any way.

[Gabriel Margiani (gamag)]

First, I used a debug build, but I think it wouldn't be bigger difference in a realse.
Then, FS cache seems to be cold.
After starting the game 3 or 4 times, I get values of 5 vs. 6 sec. or something.
(only loading barbarians in greenland, editor takes longer)

SirVer, your idea is exactly what mng-delta does with the animations,
but doing it with all animations of a thing together is much better.
Putting the results in zip files (compressed or not) would then be a good ting.

I thought of writing our image objects directly to files, but this is
impossible since a image is hold in display format.

Maybe it woud be nice to have the playercolor masks as one bit black/withe
image, so we could save lots of menory on the harddisk and in ram. At the moment,
they have some grey parts so they can't be converted.

[SirVer (sirver)]

>SirVer, your idea is exactly what mng-delta does with the animations,
>but doing it with all animations of a thing together is much better.
>Putting the results in zip files (compressed or not) would then be a good ting.
Except that I would add the stacking logic which adds flexibility like
the empty-mine sign for free.

>I thought of writing our image objects directly to files, but this is
>impossible since a image is hold in display format.
One could create a cache while loading graphics for the first time. But
frankly, the first impression a user gets from widelands is most
important so taking then even longer to load is really not a good
solution at all (imho). I'd like to avoid this approach.

>Maybe it woud be nice to have the playercolor masks as one bit black/withe
>image, so we could save lots of menory on the harddisk and in ram. At the moment,
>they have some grey parts so they can't be converted.
Gray color is needed to do shading. And frankly, we are talking some
hundred MBs which is a non issue on HD and a small issue (for a video
game) in RAM. I see no reason to cut this down currently - except to
improve loading speed. Again, only my opinion.

[Gabriel Margiani (gamag)]

To improve loading speed, maybe we don't need to convert
the pc-mask to display format, I am not sure but ...

It seems to me to be quite difficult to write a script,
which can decide if an change between to frames is part
of a empty mine sign or the underlying idle animations ...
Or did you mean to put always the hole frame in
the sprite png?
So maybe it would be a little more work to the
graphics people, but on the other hand, then they
could do the stacking thing over a hole tribe.
(Render things needed by different bobs/buildings
with a transparent background ...)
I hope you understand what I mean.

[Tino (tino79)]

I am going to test this on win32 this weekend, in my opinion the number of those single png files had always a big perfomance impact (install time/loading time). Don't forget most win users have always a virus scan engine active. All games i know use some form of container format (MPQ,BSP, etc...).

And i don't agree with Nasenbaer, 12 to 15 seconds does mean an improvement of 20%, and the 5 vs 6 seconds is still a 13% speed improvement. I think this would worth the trouble to run those scripts which do the packing and building mngs for release. This combined with zip files for world/tribes conf files should help a lot...

[Jens Beyer (qcumber-some)]

Indeed, on Windows many small files have a tremendous impact not only because of the virus scanner, but also because it bloats the MFT which makes NTFS very slow.

Also, on Notebook harddisks, that's also slow for Linux ;-)

I fully support packing those files into an archive, but if I read #9 correctly, I would say the lacking MNG support of tools is really a problem. Thus, the better way would be simply zipping that stuff up.
It should not be necessary, nor is it useful, to implement both (MNG, then packed in archives) as this increases complexity, doesn't solve the support problem and doesn't improve filesystem parameters.

[SirVer (sirver)]

#15: no, I didn't understand what you meant. However, finding an algorithm that makes an efficient sprite sheet from the existing graphics should not be too difficult (though it isn't trivial either).

I do agree with Jens: MNG is not the way to go. We buy a lot of inconvenience for a little speedup (I agree that 20% is not worth the trouble). We could (maybe) get a lot of speedup for the same inconvenience.

[Gabriel Margiani (gamag)]

Ok, I mean that something like a mine empty sign, which is used by all
mines
could be saved only in one sprite and shard by the mines. if the thing
isn't a
rectangle, it needs to have a transparent background.

If we have an idle, and idle-empty o.ä. animation, and we want to create a
base animation
with and sprites for idle and empty, and we want to combine them like
base-empty
(something without the idle part), we need to know the background of the
parts changing
in the idle animations to build an valid base. That's what I thought to be
difficult to do by a
script. Now I see that giving also a base to the script would solve the
problem.

[SirVer (sirver)]

Hi,

>Ok, I mean that something like a mine empty sign, which is used by all
>mines
>could be saved only in one sprite and shard by the mines. if the thing
>isn't a
>rectangle, it needs to have a transparent background.
I do not see a real need for sharing. This particular animation is only
1 frame 20x10 pixels (or even smaller). I would only make the sprite
sheets for one building.
The base could just be the unchanging pixels in all animations. The mine
empty shield could be manually added as a 'layer' animation - i.e. there
would not be the need to create all layered animations with the script.

[Tino (tino79)]

Ok, on windows (lenovo t410i, win7 prof x64, widelands release build,virus scan active) the performance gain with mng is significant.
What i did is stopping the time with "widelands.exe --editor", with each build i did this at least 5 times and to avoid cache issues:
With mng after a few starts i only took 16 seconds to start the editor. With the current trunk build i was not able to get loading time below 41 seconds!

So some form of container would really help on win32...

[Gabriel Margiani (gamag)]

>So some form of container would really help on win32...
I tried to use the worlds/* and tribes/* directories as zip
files, but at the moment this isn't possible, and it would
be quit a lot of work to implement that because it's needed
to write a proper glob() (FindFiles) function for zip files (!) and
maybe adjust the file system things to support paths like
xx/yy/zipfile/zz/ without manually adding the zip file as
file system layer.

[Jens Beyer (qcumber-some)]

The globbing would IMHO not be necessary if you add a line in the conf per animation signalling the length of the animation in frames.

[walk]
dirpics=walk_!!_??.png
hotspot=7 24
playercolor=true
fps=10
frames=50

[Gabriel Margiani (gamag)]

glob isn't used to find animations. Instead it is needed on things
we don't have a conf file for.
I tried a little more and got it to work with a worlds dir as zip file
until the loading of a game starts, then it crashes. But that's enough
to see a new problem: to open such a big zip file takes some seconds
(even if its not compressed, on my 1.8 GHz machine). So first I see
2-3 seconds longer than normal a black screen. Then when I click on
new game in the single player menu I have to wait approx. half a minute
until the the map select menu is shown (normally I have to wait approx. 3 sec.
here, until all scripts are registered).
(everything tested with a debug build, OpenSuse, 1.8GHz, 740Mb ram)

This seems to be more worse than loading 40 sec with a loading screen.

[Jens Beyer (qcumber-some)]

In https://code.launchpad.net/~qcumber-some/widelands/animations you can find a proof-of-concept for testing (this is not yet intended for merge into trunk) what happens if we load the animations on demand, not as preload function.
Of course this first means tremendous improvement in the startup time of a game/map/match/scenario. On a second note, this also does it for the editor, which was basically the worst case for tribes (but not for other animations).
Then, even loading a game of 3 hours "sun of fire" map with all players and tribes, feels much better.
Even on my old slow computer, loading a single animation does not really take much time, so this does not really block the game. Starting a new map triggers immediate loading of about 20 animations - also not much, this goes within 200ms.
And the third note (which is puzzling...): Starting a new game "sun of fire" without fog of war with all players and tribes, my computer gets *with preloading* an average 10fps on the starting point of player1. With this branch and on-demand loading of animations, the game starts with a whopping 16fps average.
I didn't compare memory footprint yet.

Feel for yourself, I'd say. Give it a try.

If this way is blocking the game too much for only some people, I can imagine having an option saying "preload animations on map start/loading". I would prefer the on-demand loading.

This should of course only be a stepstone to implementing MNG support which has other advantages. But I believe those two things don't exclude each other.

[SirVer (sirver)]

Really nice initiative, Jens! I will test this when I find some time.
Note that MNG is not really a favorite solution at this point in time.

[Jens Beyer (qcumber-some)]

MNG support or packing up archives of some sort, both would not interfere with on-demand loading, that's what I wanted to say. Sorry for being inaccurate/lazy ;-)

[Chuck Wilder (chuckw20)]

I, too, plan to check out your branch. I am for anything (well almost anything) that will reduce the guilt I feel when I add more graphic files to the trunk. ;)

[Jens Beyer (qcumber-some)]

I added a review request to further discuss this topic there instead of this bug. I'm feeling the review request is a better place to discuss this.

[SirVer (sirver)]

Released in build-18 rc1.