Performance optimization for javascript runtime

[luwenhou-the-coder]

We know that javascript allows only simple types such as string for object keys. When antlr uses objects as keys, there could be performance concerns as .toString() will be automatically invoked on those keys, which can take quite long time and result in performance issue.

For example, in PredictionContext.js:

function getCachedPredictionContext(context, contextCache, visited) {
	if (context.isEmpty()) {
		return context;
	}
	var existing = visited[context] || null;
	if (existing !== null) {
		return existing;
	}
	existing = contextCache.get(context);
	if (existing !== null) {
		visited[context] = existing;
		return existing;
	}
...

So when we have visited[context], SingletonPredictionContext.toString() will be called (I thought this is meant to serve only displaying purpose).

There are many other examples like this. So I tried to replace those keys with .hashCode() whenever I see context object is used as key. As a result, a query parsing that used to take 13 to 14 seconds now drops to 7 to 8, which seems reasonable (btw after the change I have to use LL change as SLL will throw syntax error).

The other piece of code that has this issue is in get() and set() methods of DoubleDict in Util.js. Changing them using the same method will result in syntax error during parsing. I'm still looking at more details and trying to figure out a solution. At the same time I'm also looking forward to comments from other contributors. Please also feel free to correct me if you find anything wrong from the above approaches.

Any input will be appreciated!

[KvanTTT]

btw after the change I have to use LL change as SLL will throw syntax error.

BTW, SLL mode is not always correct. You can parse a file correcly in LL mode but with errors in SLL mode. See #192 (comment)

[ericvergnaud]

Hi,

thanks for this.

as a matter of fact, String.hashCode and Hash were implemented precisely to address performance issues, and if some of them were missed, let's fix them.

replacing cache string keys by hash codes is not a solution, because they may collide (which is maybe why you observe syntax errors)

rather you probably want to replace the PredictionContextCache by a Map

please be aware that the size of the buckets is critical, so you might want a customised hash function instead of String.hashCode

looking forward to your PR.

Eric

n.b. not sure I agree with the statement that 'toString is for display only', since as you observed the standard way for js to generate object keys is to call toString

[ericvergnaud]

I think this is already fixed