react-hot-loader: 100% CPU stuck in levenshtein calculation

Description

Browser gets stuck in 100% CPU for a long time whenever reloading after a code change, via Webpack.

Expected behavior

Shouldn’t do that.

Actual behavior

Gets stuck in haveTextSimilarity calling levenshtein.get() on two strings that are 96227 characters long.

Suffice to say, the Levenshtein implementation in fast-levenshtein might be “fast”, but it’s not fast. If I modify haveTextSimilarity to return false on huge strings, it no longer gets bogged down.

Why are the strings being compared so big? I don’t know; I’m not using Webpack in any unusual way. My components are importing CSS such as ionicons and which end up containing Base64-encoded source maps, which certainly contributes to the size.

Environment

React Hot Loader version: 4.3.11

Operating system: macOS
Browser and version: Chrome 69.0.3497.100

About this issue

Original URL
State: closed
Created 6 years ago
Reactions: 3
Comments: 17

Commits related to this issue

fix: speedup levenshtein comparison, fixes #1087 — committed to gaearon/react-hot-loader by theKashey 5 years ago
fix: speedup levenshtein comparison, fixes #1087 — committed to gaearon/react-hot-loader by theKashey 5 years ago

Most upvoted comments

I am not sure if this is an issue with the algorithm or an issue with the browser. I am not seeing this behavior in Firefox. I did some profiling and it looks like Chrome is churning at this line of code in fast-levenshtein:

strCmp = str1.charCodeAt(i) === str2Char[j];

I created some snippets that reproduce the issue, but the reproduction is highly dependent on the contents of the strings being compared. I can reproduce this issue with a long string of source code, but cannot reproduce it with randomly generated strings. I also took the source strings in question and randomly re-arranged the the lines of code and the issue disappeared. I also appended random junk to the end of the strings and the issue disappeared. I made arbitrary changes to the strings (removing all instances of a given character) and the issue disappears.

One change I made that I think would be harmless is to remove all the leading whitespace on every line, then run the comparison. This resolves the issue on chrome, but I am not sure why this is. It looks like a bug in V8, but i need to better isolate the repro steps.

If you could put a workaround in for this issue, it would be appreciated. This workaround works for me:

var haveTextSimilarity = function haveTextSimilarity(a, b) {
    return (
        // equal or slight changed
        a === b || levenshtein.get(a.replace(/\n(\s+)/g, '\n'), b.replace(/\n(\s+)/g, '\n')) < a.length * 0.2
     );
};

petesantos on Aug 21, 2019

I’m experiencing something similar here (react-hot-loader@4.3.12), but on a component that shouldn’t be ‘hidden’ as far as I can tell, since it’s a default export:

export default class PropertyPage extends React.Component
{
	render()
	{
		// about 52k of code (after babel/webpack)
	}
}

When reloading, haveTextSimilarity calculates the Levenshtein distance on the old and new code of the render function (why?). Both strings are about 52k characters long (non-minified).

From what I read the Levenshtein distance is not O(n) but O(n^2). I did a quick benchmark with two variations of a random string, 52k characters long, with a Levenshtein distance of 1. This takes 45 seconds, run from Node.

It doesn’t seem like a good idea to use such a costly function when hot reloading large pieces of code.

meinders on Dec 21, 2018