Last modified 11 years ago Last modified on 06/26/09 14:34:28

Error: Macro BackLinksMenu(None) failed
compressed data is corrupt

Error: Macro 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|) failed
current transaction is aborted, commands ignored until end of transaction block



  • 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.


How to demo


  • 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 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]


  • 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: branches/private/vlado/layout-performance-changes.
  • 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].



(Write comments for this or later revisions here.)