Widelands

El 18/01/2010 8:39, Reece Dunn escribió:
> Hi,
>
> I am still working on improving the game start time (especially around
> the time it takes to load the animations).
>
> The benchmark I use is the time it takes to load all 3 tribes on the
> Atoll map on a debug build, running the test 4 times in the same
> widelands instance and taking the average of the 4 times. I am also
> only timing the warm cache load time at the moment (the time it takes
> to load, having previously loaded the animations) -- the cold cache
> load time is slower than the warm cache by almost a factor of 2.
>
> The reason I am focusing on warm cache time is that this will give the
> most benefit at the moment. The MNG change is likely to improve them
> both as well.
>
> I have written some fairly extensive test cases for the path logic as
> a safety net for the rework effort. These tests are posix-specific, so
> will fail on Windows as I do not have a Windows box at home to build
> and test this on.
>
> Times:
>   -- 2.97s (100%) - before any work on FS_CanonicalizeName
>   -- 2.70s (91%) - with svn 4981 and 4982 (my initial patches to
> improve performance)
>   -- 2.40s (81%) - my current effort on the fs-optimisation branch of
> the git tree (specifically 2da2aedcbab08d5267234b26b405a3c3b37636b6)
>
> NOTE: I tried replacing FS_Tokenize with boost::split, but this made
> the performance worse (3.4s on my tests, from the 2.7s base version).
>
> The output of git log for my changes:
>
> commit 2da2aedcbab08d5267234b26b405a3c3b37636b6
> Author: Reece Dunn<msclrhd@...>
> Date:   Sun Jan 17 20:00:38 2010 +0000
>
>      Add the results from FS_Tokenize directly into the node list.
>
>      FS_Tokenize was returning a list of file path nodes that were
>      being inserted into the start of the path nodes list being
>      canonicalized. This is inefficient, as it produces copies of the
>      nodes being tokenised.
>
>      The algorithm has been changed to take an output iterator, and an
>      inserter is being used to add the nodes directly into the
>      components list.
>
> commit 347b4912565565e91c3921456071f5737ce5a81c
> Author: Reece Dunn<msclrhd@...>
> Date:   Sun Jan 17 19:42:03 2010 +0000
>
>      The nexti variable is not used, so remove it.
>
> commit 6c6600ee4f842dcd326defd471881229d6ada153
> Author: Reece Dunn<msclrhd@...>
> Date:   Sun Jan 17 17:56:03 2010 +0000
>
>      Don't reset to the start of a list when erasing path nodes.
>
>      The FS_CanonicalizeName algorithm would restart from the beginning
>      if it erased path nodes that were not needed, however the erase
>      method returns a valid iterator. Use that iterator instead of
>      begin().
>
> commit a9e1dd212e5cc78975b2af044d505c53eab81521
> Author: Reece Dunn<msclrhd@...>
> Date:   Sun Jan 17 17:47:22 2010 +0000
>
>      Use a list instead of a vector for path elements.
>
>      The FS_CanonicalizeName algorithm makes heavy use of erase(),
>      which can cause excessive memory copying when used on a vector. A
>      list does not have this overhead, so is ultimately more efficient.
>
> commit 706b1d16f6be0ddc579929e9ed3411b32b92949a
> Author: Reece Dunn<msclrhd@...>
> Date:   Sat Jan 16 21:38:27 2010 +0000
>
>      Move FS_Tokenize into src/io/filesystem/filesystem.cc.
>
>      The FS_Tokenize function is a helper function that is only ever
>      called by FileSystem::FS_CanonicalizeName, so make it internal to
>      the C++ source file.
>
> commit ac35dff001daf3c1a3c58f7c61a410efe0d6c943
> Author: Reece Dunn<msclrhd@...>
> Date:   Sat Jan 16 21:22:43 2010 +0000
>
>      Add tests for canonicalizing paths with '..' parent directory specifiers.
>
> commit d50083fcfc69cf0cc51acb2c178e9b7e02cf9374
> Author: Reece Dunn<msclrhd@...>
> Date:   Sat Jan 16 17:48:18 2010 +0000
>
>      Add tests for empty path nodes being canonicalized.
>
> commit b1cf24c8ec226a2483b25ef4f4a0f723b6719b41
> Author: Reece Dunn<msclrhd@...>
> Date:   Fri Jan 15 09:46:21 2010 +0000
>
>      Added more tests for file system ~ expansion behaviour.
>
> commit 03d4974de5dd44c90448c040c3e9009339aa13d9
> Author: Reece Dunn<msclrhd@...>
> Date:   Thu Jan 14 09:27:21 2010 +0000
>
>      Get tests that rely on  expansion working.
>
> commit c1c6fe45f95f81deac5e3fb470d3d193df66374a
> Author: Reece Dunn<msclrhd@...>
> Date:   Thu Jan 14 09:24:31 2010 +0000
>
>      Move the '~' expansion tests out into a separate test.
>
> commit 48b620b543be48bd66f483286bf55268e438e532
> Author: Reece Dunn<msclrhd@...>
> Date:   Thu Jan 14 08:35:26 2010 +0000
>
>      Add tests for using a '.' in a path.
>
> commit 5b0a90d58c4342fda7f8443b9dcd5e22ea969098
> Author: Reece Dunn<msclrhd@...>
> Date:   Wed Jan 13 22:17:10 2010 +0000
>
>      Adding some basic tests for FileSystem::FS_CanonicalizeName.
>
> - Reece
>
> ------------------------------------------------------------------------------
>
>    
Hello Reece!

Cool, could you provide a public repo where to pull your changes to test 
it on more systems? I would like to see how much your changes improves 
loading animations in an AsusEEE901.

> Hello Reece!
>
> Cool, could you provide a public repo where to pull your changes to test
> it on more systems? I would like to see how much your changes improves
> loading animations in an AsusEEE901.

It's on the sourceforge git repository
(git://widelands.git.sourceforge.net/gitroot/widelands/widelands).

http://widelands.git.sourceforge.net/git/gitweb.cgi?p=widelands/widelands;a=shortlog;h=refs/heads/fs-optimisation

- Reece

El 18/01/2010 9:04, Reece Dunn escribió:
>> Hello Reece!
>>
>> Cool, could you provide a public repo where to pull your changes to test
>> it on more systems? I would like to see how much your changes improves
>> loading animations in an AsusEEE901.
>>      
> It's on the sourceforge git repository
> (git://widelands.git.sourceforge.net/gitroot/widelands/widelands).
>
> http://widelands.git.sourceforge.net/git/gitweb.cgi?p=widelands/widelands;a=shortlog;h=refs/heads/fs-optimisation
>
> - Reece
>    
Oh! Git repo is working? Cool!

Reece Dunn skrev:
> The benchmark I use is the time it takes to load all 3 tribes on the
> Atoll map on a debug build

Note that the relevant benchmark is the release build. That is our
product. The debug build is just for use with debuggers.

> Reece Dunn skrev:
>> The benchmark I use is the time it takes to load all 3 tribes on the
>> Atoll map on a debug build
>
> Note that the relevant benchmark is the release build. That is our
> product. The debug build is just for use with debuggers.
Right you are. Reece changes bring the load time from 3.900500s (100%)  
to 3.403568s (87,28%) while launching the editor on my box. This is  
not as much as in the debug builds but still significant. Also the  
speedup in the debug builds is a blessing for us developers.

Cheers,
Holger

010/1/22 Holger Rapp <HolgerRapp@...>:
>
>> Reece Dunn skrev:
>>> The benchmark I use is the time it takes to load all 3 tribes on the
>>> Atoll map on a debug build
>>
>> Note that the relevant benchmark is the release build. That is our
>> product. The debug build is just for use with debuggers.
> Right you are. Reece changes bring the load time from 3.900500s (100%)
> to 3.403568s (87,28%) while launching the editor on my box. This is
> not as much as in the debug builds but still significant. Also the
> speedup in the debug builds is a blessing for us developers.

I have added numbers for release builds on my spreadsheet for the base
and latest commits. I am getting 83.86% (2.422 - 2.031) on my box,
which is likely from the filesystem (ext4). This is compared to 77.44%
(2.89 - 2.238) for debug, which makes the release version 9% faster
than debug for the current version on my setup (2.031/2.238 = 0.91 ==>
91%).

I'm sure I can speed up this further, but there is a limit to what
gains can be made. The changes I have made thus far have focused on
simplifying the code where possible. More exotic optimisations are
likely to make the code more complex (e.g. instead of storing a
substring in the list of split file path nodes, I am thinking of
storing pointers to the c_str buffer as either a (begin, end) pair, or
with the '\' changed to a '\0' -- the idea being to reduce the string
copy that results from the substring call).

Another thing I am considering is using valgrind+callgrind+kcallgrind
to see where the hotspots are -- I suspect that there are a lot of
redundant FS_CanonicalizeName/IsDirectory/FileExists calls that are
made. These will be harder to make, but should also speed things up --
especially in the cold-cache case (which on my tests is about 4 times
slower than the warm-cache case!).

- Reece

Hi,

>
> I'm sure I can speed up this further, but there is a limit to what
> gains can be made. The changes I have made thus far have focused on
> simplifying the code where possible. More exotic optimisations are
> likely to make the code more complex (e.g. instead of storing a
> substring in the list of split file path nodes, I am thinking of
> storing pointers to the c_str buffer as either a (begin, end) pair, or
> with the '\' changed to a '\0' -- the idea being to reduce the string
> copy that results from the substring call).
make sure to properly profile the code before doing performance  
changes. My experience tells me that one is always wrong when guessing  
were the slowest part of the code is ;).
>
> Another thing I am considering is using valgrind+callgrind+kcallgrind
> to see where the hotspots are -- I suspect that there are a lot of
> redundant FS_CanonicalizeName/IsDirectory/FileExists calls that are
> made. These will be harder to make, but should also speed things up --
> especially in the cold-cache case (which on my tests is about 4 times
> slower than the warm-cache case!).
I urge you to go this way. Profiling will help a lot in finding the  
hotspots.

Cheers,
Holger

2010/1/22 Holger Rapp <HolgerRapp@...>:
>> I'm sure I can speed up this further, but there is a limit to what
>> gains can be made. The changes I have made thus far have focused on
>> simplifying the code where possible. More exotic optimisations are
>> likely to make the code more complex (e.g. instead of storing a
>> substring in the list of split file path nodes, I am thinking of
>> storing pointers to the c_str buffer as either a (begin, end) pair, or
>> with the '\' changed to a '\0' -- the idea being to reduce the string
>> copy that results from the substring call).
> make sure to properly profile the code before doing performance
> changes. My experience tells me that one is always wrong when guessing
> were the slowest part of the code is ;).

I use the load animations time results for my current work, checking
if the changes do yield speed improvements.

My feeling is that this change will make the code harder to read (and
thus maintain), so it is unlikely that I will make the change.

>> Another thing I am considering is using valgrind+callgrind+kcallgrind
>> to see where the hotspots are -- I suspect that there are a lot of
>> redundant FS_CanonicalizeName/IsDirectory/FileExists calls that are
>> made. These will be harder to make, but should also speed things up --
>> especially in the cold-cache case (which on my tests is about 4 times
>> slower than the warm-cache case!).
> I urge you to go this way. Profiling will help a lot in finding the
> hotspots.

That is the near to long-term aim.

- Reece