Performance issue with selectCharacters

[izhan]

Hello!

First off, thank you for creating a kickass project :)

I am currently using rangy to analyze sentences (such as grammar, etc) within contenteditables and highlighting the text. Here are my steps:

Every time a user enters text into a contenteditable...

1. Get the text of a contenteditable from rangy.innerText(el) and analyze it, returning an array of start & end tuples marking which characters should be highlighted
2. Clear already highlighted elements using range.selectNode(el) and applier.undoToRange(range)
3. Rehighlighting the text I specify using range.selectCharacters

I noticed that as the number of highlights increase, the performance gets exponentially worse. I ran a Chrome profiler and it seems that the selectCharacters call is the culprit. I dug into the code a bit, and noticed you use caches extensively — could it be one of the caches are no longer being hit?

If it helps, I've created a JSFiddle! Start typing some text into the contenteditable and you'll see what I mean. https://jsfiddle.net/3zz5pLgx/

1 — Do you know why selectCharacters might have this performance issue?
2 — In general, do you think that my approach to this problem (highlighting characters in text based on start & end values) is correct?

Thanks in advance!

[rsimon]

I've run into the same issue. I need to render a lot of highlights (several 100s) on a page and I'm desperately looking for a way to improve rendering performance.

I applied your patch, and implemented a lazy loading mechanism in my application that only draws the highlights if they are inside the viewport - both of which helped a little bit. But my bottleneck remains .selectCharacters (which I need to call even in the lazy loading case, in order to determine whether the range inside the viewport).

Any thoughts or ideas greatly appreciated!

[rsimon]

P.S.: as an alternative, I wonder if it's possible to use rangy for server-side rendering of the page (see issue #376). Again - any thoughts and ideas appreciated!

[izhan]

Hey @rsimon, I ended up rolling out my own solution after some investigations. It's been a while since I worked with this library so I don't remember the exact details, but the reason the performance dropped so much was that for each highlight, rangy did a linear scan of the text from the beginning to advance the marker to that position before highlighting. Essentially, range.selectCharacters took time proportional to the length of the entire body text times the number of highlights (therefore worst-case quadratic, not linear time to length of text). For instance, to highlight two words at the end of the body text, rangy would make two entire passes of the body text to do so.

I could not find an easy fix for this, and recommend rolling out your own solution if possible.

[rsimon]

Thx @izhan, I did now roll my own solution as well. Basically fetches all the text nodes in a given container recursively, and then determines which node & internal char offset corresponds to the 'global' char offset relative to the parent container. Probably not fit for every use- and edge-case, but does the trick and seems quite fast.

My code is here in case someone wants to take a look.