Loader Cache improvements

[David Hyatt]

In case you're curious, I implemented the LRU-SP algorithm in the 
loader after reading this paper:

http://www.is.kyusan-u.ac.jp/~chengk/pub/papers/compsac00_A07-07.pdf

dave

On Jan 11, 2004, at 10:50 PM, Dirk Mueller wrote:

>
> Hi,
>
> Lets bring some life into the list again. I've sat down and debugged 
> the
> Loader memory cache after we merged the improved "sliced" LRU 
> implementation.
> The existing code had many faults, and at least some of them should 
> apply to
> your tree too (at least in the latest public release):
>
> a) setRequest was not properly tracking LRU list state
>
> b) There were pages that referenced the same url as external 
> stylesheet and as
> image. This crashed, since we were returning the wrong CachedObject
> derivative from the cache. oops.
>
> c) There was an ugly deletion race upon deref(). The actual details 
> are not
> interesting, the cleanest solution was to introduce a "free list" that 
> is
> deleted upon every flush() call.
>
> d) The handling of "uncachable" objects was flawed. Not only that most 
> images
> ended up being "uncachable". Even very big images were kept around in 
> the
> uncacheable linked list until the next flush succeeded (which might 
> take a
> long time since it needed enough regular, cacheable derefs until the
> flushcount was triggered). Browsing sites with big images produced 
> unbearable
> pixmap leaks. I've actually seen the X server running out of memory 
> because
> of that already.
>
> Now, I didn't waste much time on fixing the issue. instead I removed 
> the whole
> clumsy uncachable handling alltogether. the LRU handling is a lot 
> better and
> much better performing, and it was just a very old, crude hack. Rest in
> peace.
>
> e) the triggering of flushes based on flushCount is flawed. We have a 
> good
> measure of "cost", namely the totalSizeofLRULists, so use that one.
> Significantly reduces pixmap pressure for the porn browsing case and 
> also
> flushes much less often for the tiny tiny image case. Basically, it 
> just
> keeps the average size of the cache way nearer the configured one 
> without
> doing unnecessary work.
>
> f) Centralized the code a bit since there was much duplication. 
> Manually
> inlined methods that were only called from one place.
>
> g) make sure that "free" objects don't end up on the LRU list.
>
> h) more cleverness in KURL<->QString handling. I was noticing today 
> that in
> some pathological cases we spent much more time inside KURL than in the
> actual layouting and rendering. Crazy.
>
> i) Removed a linked list in DocLoader that was very poorly performing 
> in the
> many-different-images case. I actually got a testcase that contained 
> 100000
> different images. We're still performing bad on this one, but at least 
> we're
> in the minutes range and not in the hours range anymore. We're using a 
> seeded
> hash table so it should scale enough while not wasting enormous 
> amounts of
> memory. After removing the DocLoader list bottleneck and optimizing 
> the KURL
> handling, the bottleneck is now in RenderTable (since the images 
> didn't have
> size hints in the source, it produces table relayouts like crazy).
>
> j) remove a lot of old, totally unused code cruft in the cache 
> validation
> handling. the code is still not nice,but at least its a lot shorter 
> now.
>
> h) remove some redundant checks that were always passing.
>
> I've run it on a couple of test cases and I'm very pleased with the new
> behavior, but its quite likely that I overlooked something (besides 
> that it
> doesn't immediately LRU recycle the images from the "last" page - thats
> intention to have  an immediate page-back behavior). So I'd like to 
> hear your
> feedback.
>
>
> Dirk
> <loader.diff>_______________________________________________
> Khtml-devel at kde.org
> https://mail.kde.org/mailman/listinfo/khtml-devel