Bug Hunting Session
Bug 54396 - better algorithm to generate the conditional format render information
Summary: better algorithm to generate the conditional format render information
Status: RESOLVED FIXED
Alias: None
Product: LibreOffice
Classification: Unclassified
Component: Calc (show other bugs)
Version:
(earliest affected)
4.0.0.0.alpha0+ Master
Hardware: Other All
: medium normal
Assignee: Markus Mohrhard
URL:
Whiteboard: target:3.7.0
Keywords: difficultyBeginner, easyHack, skillCpp
Depends on:
Blocks: 50460
  Show dependency treegraph
 
Reported: 2012-09-02 16:13 UTC by Markus Mohrhard
Modified: 2015-12-15 16:46 UTC (History)
2 users (show)

See Also:
Crash report or crash signature:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Markus Mohrhard 2012-09-02 16:13:10 UTC
The current cond format render code is extremely slow when using the new color formats and duplicate/unique entries.

The idea is to create the cond formta render information for the whole cond format range at once which brings the algorithm to O(n) instead of O(n^2).

This should be the best we can do before w use a more radical idea to store the render information.
Comment 1 Markus Mohrhard 2012-09-18 15:50:50 UTC
Making it visible in my cond format search.
Comment 2 Markus Mohrhard 2012-09-19 19:06:36 UTC
Making this an EasyHack.

Changes to be done:

The current conditional format code evaluates for every cell the condition
again. The right way is to cache the result for one paint run. So add a method
in conditio.[ch]xx that signals the conditional formats that the cell data
should be cached between these two calls for color scales, data bars and the
unique and duplicate data. Then use these methods in fillinfo.cxx before and
after the cell render information are collected.
Comment 3 Not Assigned 2012-09-24 21:36:01 UTC
Markus Mohrhard committed a patch related to this issue.
It has been pushed to "master":

http://cgit.freedesktop.org/libreoffice/core/commit/?id=af0c93da33f2bf39a673c2dc29fb44b90322d137

kill O(N^2) algorithm generating cond format render information, fdo#54396



The patch should be included in the daily builds available at
http://dev-builds.libreoffice.org/daily/ in the next 24-48 hours. More
information about daily builds can be found at:
http://wiki.documentfoundation.org/Testing_Daily_Builds
Affected users are encouraged to test the fix and report feedback.
Comment 4 Robinson Tryon (qubit) 2015-12-15 16:46:25 UTC
Migrating Whiteboard tags to Keywords: (EasyHack DifficultyBeginner SkillCpp )
[NinjaEdit]