Match on parse trees can be twice as fast or more

[jurgenvinju]

This is a note to self. I came acros this code while debugging the formatter:

rascal/src/org/rascalmpl/values/RascalValueFactory.java

Lines 1518 to 1540 in 91e8487

	public boolean match(IValue other) {
	if (isMatchIgnorable) {
	return true;
	}
	if (other instanceof IConstructor) {
	IConstructor cons = (IConstructor) other;
	return cons.getConstructorType() == getConstructorType()
	&& cons.get(0).equals(get(0))
	&& cons.get(1).match(get(1));
	}
	return false;
	}
	@Override
	abstract public IList getArgs();
	@Override
	public Iterator<IValue> iterator() {
	return new Iterator<IValue>() {

• this code was written for a bootstrap situation, where sometimes appl constructors could come out of other factories. So it matches non-specialized to specialized objects and vice versa. The non-specialized case does not exist anymore, as long as we use the right factory. The fast path can be chosen now and the old code removed.
• this code allocates memory while matching, because the getArgs and get functions will wrap the individual children in an object that simulates IList. However, in most case we compare nodes of the same arity, and a pairwise field recursion suffices (without any memory allocation or simulation of IConstructor). This could be a significant win.

This code lies below := and the concrete pattern matching code. So when we see that those operations are expensive, this is a possible explanation.