[[BackLinksMenu]]

[[TicketQuery(summary=SMOOTH_TEXT_RENDERING_R0, format=table, col=summary|owner|status|type|component|priority|effort|importance, rows=description|analysis_owners|analysis_reviewers|analysis_score|design_owners|design_reviewers|design_score|implementation_owners|implementation_reviewers|implementation_score|test_owners|test_reviewers|test_score|)]]



= Analysis =

== Overview ==
 * The purpose of this task is to improve text rendering in terms of time performance.
 * Main focus
  * Improve the text layout itself
  * Improve how and when text layout is used (when the text is reflowed, etc.)
 * LayoutBuilderTest is used to measure the time of laying out text that exactly fills a frame with standard size (width: 280p, height: 210p).
  * Test runs in around 0.5 seconds.

== Task requirements ==
 * Improve layout performance with 40%.
 * Test should run in around 0.3 seconds.

== Task result ==
 * The result of this task is code

== Implementation idea ==
 * Ratings of performance improvement solutions:
  * Hardness: 1(easiest) - 4(hardest)
  * Expected effectiveness: 4(smallest) - 1(biggest)
 * Rated possibilities to improve the layout algorithm:
  * Improve logging - (hardness)1 + (effectiveness)2 = (cumulative)3
  * Implement the issues commented as "performance" - 2 + 3 = 5
  * Improve badness calculation - 3 + 3 = 6
  * Refactor badness - 4 + 3 = 7
  * Memoization (part of a path, edge, etc.) - 4 + 1 = 5
  * Check for existing useless updates and reflowing (e.g. selecting the frame with highest z-order) - 2 + 3 = 5
  * Check for large amounts of objects cloning - 2 + 3 = 5
 * During design and implementation handle the improvement possibilities in the order of the least cumulative rating.

== Related ==
[wiki:WRAPPING_TEXT_RENDERING_R0]

== How to demo ==

= Design =
 * Logging:
  * Performance problems found
   * EdgeKind.findLayoutHillClimb logs the Vertex on each step of the algorithm. This log includes all VertexKinds with their values.
   * HotTextLayout.draw logs the Edge on each transition between two vertexes, including the Vertexes with their properties.
   * Both loggings result in a large amount of very long strings, making them not usable.
   * These logs are usually not interesting for tracing or for tracking bugs.
  * Solutions
   * Modify EdgeKind.findLayoutHillClimb to log only the EdgeKinds to track the correct work of the layout algorithm.
   * Modify HotTextLayout.draw to log only the path size.
   * Further logs will be introduced on demand.
  * Measured performance improvement - around 20%
 * Implement methods marked as fake and/or performance:
  * ImmArea.contains method added. Atom.canFit method modified to use it.
  * Modify Vertex methods getMinX, getMaxX, getMinY, getMaxY to cache the min and max coordinates.
  * Measured performance improvement - 2-3%
 * Check for existing useless updates and reflowing:
  * Cases pending improvement after implementation of [wiki:GROUP_CHANGES_R0] in relation to Layout performance.
   * Usage of text resource:
    * resource.text().get().replaceText(newText) results in reflowing of the text on each character from the new text.  
    * resource.text().set(newText) results in reflowing of the text only once.
    * All problematic occurrences of the first case are replaced by the second, but this is still error prone until solved by group changes.
   * In PageElementLogic.SELECT_DESELECT_PAGE_ELEMENT.handle the call pwa.allSelectedElementViews().get().clear() results in numerous updates and reflowing of text.
    * To be solved with group changes.
    * Performance improvement: Add a check if the frame needing selection is not already the only selected frame.
    * Measured performance improvement - 0% for the layout itself, but less calls to it in some specific cases.
 * Refactor the Layout algorithm
  * Change Atom implementation
   * Create a new static abstract class AtomKind inside Atom to:
    * Encapsulate usage of effective units (Atom.effUnit and Atom.units moved to AtomKind).
    * Replace the fake solution using a single unit with a real one allowing managing of atoms with a bigger size (with multiple units).
    * Have functionality to switch internally to the next consecutive AtomKind if the current does not provide a good implementation
   * Create inside AtomKind new private static classes subclassing AtomKind to provide different management of unit chunks
    * UnitKind - represents the simple management of units
     * The atom contains only one unit.
     * This is the same as the current implementation and is needed if the other kinds do not provide a solution for a specific case. 
    * WordKind - represents the management of units by words
     * The atom contains grouped units ending at a separator.
     * Will decrease the number of steps of the algorithm when separators exist in text on a regular basis (which should be the common case).
    * SentenceKind
     * The atom contains grouped units ending at a line, paragraph or document break.
     * Will decrease the number of steps of the algorithm when breaks exist in text on a regular basis
      * This is often not the case, so this kind will produce worse performance in a lot of cases.
      * If useful cases are localized during implementation and it does not affect others it will be preserved (and design will be updated).
      * Remains as optional.
    * Optionally add other Kinds, following the idea to split the units in chucks relative to the bounds of the frame.
     * Design will be updated if implemented.
   * Add Atom.kind field to keep the current AtomKind of the atom.
    * Note: The notion of a kind is kept internal for the atom. The client code has simply an interface to decrease the atom's size.
   * Add Atom.decreaseSize method to trigger the switching to the next AtomKind.
  * Modify EdgeKind.SEGMENT and EdgeKind.OPEN_LINE to use Atom.decreaseSize if the atom can not be placed with its current size (that is, with its current kind)
  * Measured performance improvement - 10% on average, depending on the specific text. To be improved further during the implementation phase.
 * Test: [3607]

= Implementation =
 * Design changes
  * Method names in the layout are logged at INFO level.
  * Layout algorithm refactoring
   * The basic design idea is preserved, but moved out of Atom, because it does not take into account that each unit can have a different pre-style, post-style, etc. Thus, units can not be grouped inside an atom, and the Atom should still represent a separate glyph, laid out at once.
    * The grouping of units in Atom is replaced by grouping of atoms in TextRange.
    * The atom grouping idea is implemented in a new abstract class AtomManager (renamed from design's AtomKind)
    * WordManager extending AtomManager is added (renamed from design's WordKind)
    * UnitManager extending AtomManager is added (renamed from design's UnitKind)
    * AtomManager is with package visibility in the layout package.
    * Method TextRange.getAtomManager() is added to be able to get the atoms related to the current TextRange.
     * Delegation is not used, because TextRange does not need to be polluted by the Atom handling interface.
      * Side effect of this is that AtomManager is not extracted to a separate package so that is could be used in the layout algorithm directly.
  * Solutions for bottlenecks found by profiling
   * NaiveHotText methods are refactored to extract ProLib properties in local variables for each method.
   * Atom.getAdvance() is refactored to cache the advance.
   * Usage of Navigator.GetIndex is decreased.
 * Layout performance is improved by around 40% (LayoutBuilderTest.testLayoutPerformance runs in 0.3-0.32 sec on average).
 * Implementation is committed to a separate branch: [http://www.sophie2.org/trac/browser/branches/private/vlado/layout-performance-changes branches/private/vlado/layout-performance-changes].
  * [3608]
  * [3750]
  * [3751]
  * [3768]
  * The other changesets in the branch are redundant.

 * Issues to be addressed in the next revision
  * Bottlenecks found after profiling (in order of influence on layout performance)
   * NaiveHotText's methods and their utilization of ProLib ()
    * HotTextLogic.INPUT_CHAR -> text.replaceText -> units().get().addAll
    * getUnits
    * NaiveNavigator.getIndex
    * NaiveNavigator.isPresent
    * Cycles on units elements (even with iterators)
   * HotTextFontMapping.createInitialFont() -> Toolkit.getDefaultToolkit().getScreenResolution()
   * Atom.getAdvance() -> FontDesignMetrics.stringWidth
  * Improve bottleneck functionality in two directions
   * Fix it.
   * Decrease its usage.
  * Implement new AtomManagers
   * SizeManager - groups atoms by means of an area to fit in.
   * RowManager - groups the atoms belonging to one row/line of text.
   * SentenceManager - groups atoms belonging to one sentence.
  * Refactor HotTextSceneElement as specified in design review comments.
  * Check analyzed issues not handled in the current revision.
   * Improve badness calculation.
   * Refactor badness.
   * Memoization (part of a path, edge, etc.).
   * Check for large amounts of objects cloning.

All merged to the trunk in [3770].

= Testing =

= Comments =
^(Write comments for this or later revisions here.)