[ stepmania-Bugs-1052585 ] Loading files into the Cache should take O(n) but doesn't

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 454-5900

Bugs item #1052585, was opened at 2004-10-22 18:22
Message generated for change (Comment added) made by stevecheckoway
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=421366&aid=1052585&group_id=37892

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: None
Group: (old) v3.9 rc1
>Status: Closed
>Resolution: Fixed
Priority: 3
Private: No
Submitted By: Leif Huhn (volfy)
>Assigned to: Steve Checkoway (stevecheckoway)
Summary: Loading files into the Cache should take O(n) but doesn't

Initial Comment:
StepMania loads SLOOOOOW before things get put into the
cache.  It only gets slower the more files it loads. 
It used over 3 hours CPU time on my box last night
loading up a couple thousand files.  

To try to figure out why I ran 

rm -R Cache/*
strace -o /tmp/out ./stepmania
egrep '^(stat64\("[0-9]{4,20}|chdir.*Cache)' /tmp/out

This revealed that every time StepMania puts 1 file
into the Cache, it stats *every* file in the cache
*twice*.  So we should expect the loading time to
lengthen geometrically rather than linearly.  Why does
it have to stat anything?  I think StepMania even keeps
track of what files are in the cache.

----------------------------------------------------------------------

>Comment By: Steve Checkoway (stevecheckoway)
Date: 2009-09-14 01:24

Message:
5 years latter, this has been fixed! Talk about response time!

----------------------------------------------------------------------

Comment By: Ben Anderson (bashmaster)
Date: 2005-03-26 08:37

Message:
Logged In: YES 
user_id=564758

lower priority -- load times aren't THAT important

----------------------------------------------------------------------

Comment By: Leif Huhn (volfy)
Date: 2004-10-23 23:38

Message:
Logged In: YES 
user_id=61401

Eh...stat is fast, but not that fast for me.

execve("./stepmania", ["./stepmania"], [/* 86 vars */]) = 0
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- ---------
----------------
 58.34   24.591571          34    733412         6 stat64

Ok, who knows if this is accurate but it's a good jumping
off point.  This is the time it took to load StepMania w/
566 song files.  We can expect 2 stats per cache miss, times
2 caches (banner and song) times the formula for the sum of
an arithmatic series (1/2)*566*(1+566) times 34 microseconds
per stat call = 2*2*(1/2)*566*(1+566) * 34 / 1000000 = 22
seconds.  Sounds about right.  Now make that 4000 songs. 
For that, it's 18 minutes.  Of course, it took over 3 hours
(I quit at 3 hours) on my machine, so I guess relatively
speaking it's still insignificant, but it really seems like
the songs load slower and slower as it loads.

----------------------------------------------------------------------

Comment By: Glenn Maynard (gmaynard)
Date: 2004-10-22 19:30

Message:
Logged In: YES 
user_id=561109

Not quite correct: running stats on the same files repeatly 
won't take much time, since it'll be cached by the kernel, and 
most initial load time is spend on processing song data.  The 
only case where it'll matter is if stat() is very slow for large 
directories, or if you have so little memory, it's not being 
cached.

StepMania caches stat data internally, but flushes this data 
when it writes a file to disk, since it's out of date.  It should 
update the existing data, instead of flushing it entirely, but 
that's tricky; I hope to do it, but not for the 3.9 release.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=421366&aid=1052585&group_id=37892