Question: How To Reduce DOM Manipulations on Lists of Primitives?

[dwighthouse]

I know from this issue that hyperHTML focuses on preventing unnecessary updates by checking object references against previous render versions. If an object is retained from update to update, the elements wired via that object will be retained in the dom.

However, in my specific use case, the data to wire is inherently non-object.

The high level task I'm trying to accomplish is to mirror the text content of a textarea via spans behind the words of the textarea, keeping scrolling synced so that I can apply "highlights" to words in a textarea, something whose individual parts are hidden by browser sandboxing.

I've tried multiple methods including:

1. Regenerate new spans every update of the textarea with innerHTML - not the fastest to update, but the most consistent and fastest for large inserts
2. Use a contentEditable area and handle all the complexities of imitating a textarea - surprisingly, this is slower than option 1.
3. Using hyperHTML, find a way to create and cache object references for string values and use its existing system for updating - the fastest for editing existing words and appending to the end, but slowest for inserting new words at the beginning and mass inserts.

The problem appears to be coming down to how to retain objects from the last render in the new render. I have confirmed that the amount of time I spend parsing and tracking values from render to render is trivial compared to the DOM update time (about 10 times longer).

The strategy I came up with was to keep an object cache in which the key was the text of each "word" (separated non-whitespace sequences and whitespace sequences), and the value was the list of individual objects representing each copy of that string used in the entire textarea. Each of these objects are merely a simple object wrapper for a string of text to make it compatible with hyperHTML. By looping through the new text of a new render, I would pull off data from the old list into the new list, as needed, thus retaining the maximum number of object references.

While this retains the maximum number of references from render to render, it doesn't know where the insertions or deletions occurred. It only knows about the text before and after. As a result, changes towards the beginning of the string tend to have cascade effects on the rest of the string, even if it hasn't changed. Though the number of dom insertions and deletions are minimized, the number of dom moves remains very high.

This is most easily seen when adding a new word at the beginning of the text that has already been used later in the text. Because the new first instance will use the first instance in the cache, the previous first user of that item will now have to shift to using the next object in the cache, and so on. In the worst case (which is often), every single span after the span where the text is changed will have to be updated.

I know this is not the typical use case of hyperHTML, but it is representative of problem scenarios where object references either are not or cannot be known from render to render.

How would you recommend approaching this problem?

PS - Here is a simplified example of my caching strategy for arbitrary text.

let cache = {};

const parseWordsAsPositionedObjects = (text) => {
    // Splitting with the group capture retains the delimiter
    const parts = text.split(/(\s+)/g);

    const wordsUsedCounts = {};
    const wordsUsedLists = {};

    // Preserve object references from call to call by checking references before creating
    const partsObjs = parts.map((part, index) => {
        wordsUsedCounts[part] = wordsUsedCounts[part] || 0;
        wordsUsedLists[part] = wordsUsedLists[part] || [];

        let ref;
        if (wordsUsedCounts[part] < (cache[part] || []).length) {
            ref = cache[part][wordsUsedCounts[part]];
            wordsUsedCounts[part] += 1;
        }
        else {
            ref = {
                t: part,
            };
        }

        wordsUsedLists[part].push(ref);
        return ref;
    });

    // Update object caches with actual used words
    // GC will remove object references no longer used
    cache = wordsUsedLists;

    return partsObjs;
};

[pinguxx]

my two cents here, i think you can reuse the same base array/object just pass a dif id to the wires:
https://viperhtml.js.org/hyperhtml/documentation/#essentials-3

wire(array, ':list-' + item)`<li>${item}</li>`

Not 100% sure it will do what you are expecting

[WebReflection]

@dwighthouse I'm afraid I've read it twice and still not sure what you are after there ... if you can have duplicated words in the list, beside the spaces in between, I am not sure you should cache anything at all but if you have single, unique, entries only, relating any object and using an ID is the way to go, as @pinguxx mentioned already, i.e.

wire(search, `:word-${any}`)`<li>Hello ${any}</li>`

For anything more complex, you can always create your own map of primitives, and relate any wire to it.

const cache = Object.create(null);
const related = primitive => cache[primitive] ||
                             (cache[primitive] = wire()`<b>hi ${primitive}</b>`);

In that case related(1) and related(2), or passing just strings, would work as well.

That being said, you can also create DOM nodes and pass all of them at once to any render/view as Array, it should handle all cases without issues but, if it has issues, then maybe simply wiping all nodes and putting back all of them at once is better.

I mean, domdiff, the engine used by hyperHTML, is good 99% of the time, performance wise, but in some super random case, it might be way slower than just fresh new content each time.

If that's your case, consider alternatives for that very specific node.

At the end of the day, hyperHTML is a tool to help, it doesn't want to be on your way.

[WebReflection]

P.S. the on-demand wires pattern can also be used as such:

const related = primitive => cache[primitive] ||
                             (cache[primitive] = wire());

In that case you can:

related(1)`Same content for <b>${1}</b>`

and be sure you'll always deal with the same wire/node

[dwighthouse]

Thanks @WebReflection and @pinguxx . My list of words is not unique. Duplicate words are not just allowed, but common, as would be with any regular writing (such as multiple instances of the word "the").

Unless I'm misunderstanding the proposed solutions, using the above mentioned methods results in only one instance of a given word string being rendered, rather than one for each.

@WebReflection I had also tried to inject the spans manually via hyperHTML calling innerHTML directly at the appropriate place. However, not only is that slower than simply not using hyperHTML at all (due to the minimal, but still there overhead of a framework), the whole point of using hyperHTML at all for my project is to gain the performance advantage of preventing unnecessary DOM updates. If hyperHTML can't help with that in this case, the rest of my app is more simply implemented in manual DOM manipulations from scratch.

I've reduced my code to the minimal possible set to demonstrate the problem.

1. Copy the following web page locally and run it locally.
2. Open the inspector and expand the div with the "app" ID.
3. Place the cursor in the textarea to the right of the first "on" in the first line.
4. Press the spacebar key.
5. Notice how about half of the spans rerender, instead of just the creation and insertion of one new span.

<!doctype html>
<meta charset="utf-8">
<title>Span Test</title>

<style>
span {
    white-space: pre-wrap;
    background: rgba(255,200,200,0.3);
}
</style>

<div id="app"></div>

<script src="https://unpkg.com/hyperhtml@2.13.0/min.js"></script>
<script>

const {bind, wire} = hyperHTML;

// Text can have lots of duplicates
const state = {
    text: `Knox on fox in socks in box.
Socks on Knox and Knox in box.
Fox in socks on box on Knox.`,
};

let cache = {};

const parseWordsAsPositionedObjects = (text) => {
    // Splitting with the group capture retains the delimiter
    const parts = text.split(/(\s+)/g);

    const wordsUsedCounts = {};
    const wordsUsedLists = {};

    // Preserve object references from call to call by checking references before creating
    const partsObjs = parts.map((part, index) => {
        wordsUsedCounts[part] = wordsUsedCounts[part] || 0;
        wordsUsedLists[part] = wordsUsedLists[part] || [];

        let ref;
        if (wordsUsedCounts[part] < (cache[part] || []).length) {
            ref = cache[part][wordsUsedCounts[part]];
            wordsUsedCounts[part] += 1;
        }
        else {
            ref = {
                t: part,
            };
        }

        wordsUsedLists[part].push(ref);
        return ref;
    });

    // Update object caches with actual used words
    // GC will remove object references no longer used
    cache = wordsUsedLists;

    return partsObjs;
};

const onChangeText = (e) => {
    state.text = e.target.value;
    render(state);
};

const render = (state) => {
    const parts = parseWordsAsPositionedObjects(state.text, state.title);

    // Have a look at the data structure
    console.log(cache);

    bind(document.getElementById('app'))`
        <div>
            <textarea value=${state.text} oninput=${onChangeText} rows="5" cols="60"></textarea>
        </div>
        ${parts.map((part, index) => (
            wire(part, ':Span')`
                <span class=${`type${index % 2}`}>${part.t}</span>
            `
        ))}
    `;
};

// Initial render
render(state);

</script>

The reason it's roughly half is probably because pressing the spacebar creates a new "word" of empty string in the list, and therefore pulling every following space object reference from the cache one place forward, causing tons of DOM moves.

Again, I don't consider this a problem with hyperHTML per se. It appears to be operating as expected. Rather, I'm looking for suggestions on how to arrange, manipulate, or track this sort of primitive data in a way that hyperHTML can still be efficient with it. In theory, with the right tracking/manipulation of objects from render to render, the minimum set of DOM manipulations can be performed. I just can't figure out how to do that when at most, all I have to work with is the old string, the new string, and in what way the cursor/selection position changed.

Ideas:

• Implement a simple text diffing algorithm that will reduce the size of the manipulatable area to a relatively small portion of the text (plus or minus 2 words for each change). The problem with that is that I'd have to track a history of change sets because the data in the cache would no longer be regular.
• Rather than allowing the text editor to enter data directly, I keep track of entries and deletions in my own tree data structure that retains position information.Then, both rendering the new text content to the textarea, as well as rendering the spans, becomes a tree traversal with two different outputs.

Thoughts?

[pinguxx]

Can you create a jsbin or fiddle or similar please

[dwighthouse]

@pinguxx Done. https://jsfiddle.net/pz49xkq5/

[WebReflection]

Thoughts?

Well, to start with, diffing efficiently is everything but a simple task. AFAIK the best way to diff is described by this paper and implemented in petit-dom and its size and complexity is way higher than domdiff.

I also used to ship hyperHTML with a Levenshtein distance based engine called majin-buu, but being exponentially slow, it wasn't a great solution able to scale.

The current engine is half borrowed from snabdom, and it's a best compromise engine, but it might perform very slow in random changes.

This is to explain that nothing will change for the time being in hyperHTML so that, if you still believe you have performance issues once you've mapped all your changes properly, I invite you to look elsewhere (i.e. petit-dom) and see how that works because I won't change anything to the current diff also since it's purposely a best compromise one, and it works freaking well for my, and many others, production needs.

Last, but not least, be sure when you say "a lot of spans are rendered" you are not simply seeing spans being moved, because the inspector shows movements, not necessarily new spans.

TL;DR those spans look re-arranged to me, which is fine, and I also didn't see any performance issue, but I guess with much bigger text there is an impact, right?

[dwighthouse]

@WebReflection Hmmm. I may look into some form of virtual DOM, since I've already established that the speed issue is from the actual touching of the DOM, not the construction of strings/data structures.

The thing is, as you say, this isn't a problem with hyperHTML. I was just wondering about structures for arranging the data that plugs into hyperHTML to make use of it better. I came upon using a Hash Array Mapped Trie, or some variant of it, to manage the insertions/deletions in a structured way, rather than relying on a pure string, since all edits to the textarea will be controlled. Apparently it has linear time traversal, and strongly preserves references in the same location/order between changes. Sadly, I think that such a thing is far beyond the scope of my project. It is interesting as a possible solution, however.

I'm aware of the new span vs move. I recognized the majority of the issues were related to catastrophic moves of existing DOM nodes when using phrases like "causing tons of DOM moves". I was using "render" in the sense that "the changes reflected in the new data model were rendered to the DOM". But it is an important distinction.

Yes, in large text sequences, I see a 10x speed degradation during catastrophic DOM movements, as opposed to editing existing nodes without moves, the latter of which is about 2 to 3 times faster than regenerating and dumping masses of spans via an innerHTML. The difference is clearly visible from a user interaction point of view, with non-moving edits not registering as delayed, but inserting new words registering as a full browser hiccup.

Thanks for hashing this out with me, everyone.

[WebReflection]

FYI I'm tired to tell everyone that petit-dom is the fastest diffing algo out there so I went ahead and updated domdiff to bring basically exact same performance in
https://github.com/WebReflection/domdiff#domdiff

It would be awesome if you could double check with petit-dom performance is better, 'cause for what I could test, and specially on big lists, is that it's 3X faster on average than domdiff V1 and also way more reliable in updates (never a failure so far).

[WebReflection]

P.S. please give hyperHTML 2.14 a try ;-)

[dwighthouse]

@WebReflection WOW! That is FAR faster.

In my very unscientific tests, I'm seeing:

• 2x speed up in worst case
• ~1.2x speed up in normal case
• ~1.2x speed up in mass insert (which I didn't expect to speed up at all regardless of what was done)

In my problem case specifically, I'm maybe 1/3 done implementing a very simple text diffing algorithm that takes advantage of the fact that I can access the caret/selection positions of the textarea to figure out what was added or removed, and where in the string. Hopefully, I will be able to reduce the worse case down to the same timescale as the best case, because I will, at maximum, change only one existing dom node for each change insert, and only remove dom nodes that were removed from the string. No side effects on other dom nodes.

[WebReflection]

In theory, the change one for many case is well covered by pre optimizations ... It'd be awesome to live test your case.

Anyway, since O(ND) is the best algorithm since that academic publication, and all but one optimizations are in place, unless there's something obvious I'm missing, there's not much else I can do but thanks a ton for double checking and coming back with feedbacks!

[dwighthouse]

@WebReflection You're welcome! I will try to update with my text-diff results later.

In the meantime, I noticed the message in the changelog about the new algorithm adding 0.6K to the final size. You might want to have a look at some research I did for my library, where I optimized the code for its final gzip size, not it's minified size. The unnecessary repetitions and odd ways of writing the code resulted in significant savings to the gzipped size, without adversely affecting the performance of the runtime, at least not significantly:

https://github.com/dwighthouse/onfontready/blob/master/docs/compressionTechniques.md

[dwighthouse]

An update to my problem:

Over the next few days, I worked on the diffing. Several iterations later, I determined that the most performant solution was the easiest one. Since I couldn't fully determine the caret position for some modifications of the textarea, I simply loop from the end and the beginning over known words, comparing them to the newly generated words from the existing string. Array looping and string comparisons are far faster than any other kind of clever parsing, so I did that. From there, I could determine the minimum set of changed words and only modify those objects.

This lead to consistent speed regardless of where the change occurred, since, at most, 6 words would ever be modified. However, now that I know exactly what words are modified, and therefore, which indices of the childNodes need to change, I no longer need hyperHTML either. By removing that, I was able to save the cost of the loop over the existing elements in the list, where hyperHTML simply determines that nothing changed.

With the use of my large sample text as a baseline, modifications of any word or making a new word, anywhere in the textarea, takes 30 to 80 milliseconds, a 10x speedup.

hyperHTML is great. I will keep it in my belt for future projects.