Node replacement with a threshold

Say that we have a node that may or may not need to be replaced a few times. If it doesn’t get replaced, all is good. If it needs to be replaced once or twice, that’s OK as well. However, if it needs to be replaced hundreds or thousands of times, the performance overhead would outweigh it being immutable in the first place. This is where a sort of threshold for mutable replacement might be useful.

package com.wordpress.hextruffle.tests;

import java.util.Random;

import com.oracle.truffle.api.CallTarget;
import com.oracle.truffle.api.Truffle;
import com.oracle.truffle.api.TruffleRuntime;
import com.oracle.truffle.api.frame.VirtualFrame;
import com.oracle.truffle.api.nodes.Node;
import com.oracle.truffle.api.nodes.RootNode;

public class MutliReplacementTest {

    static abstract class ReadWriteIntNode extends Node {

        public ReadWriteIntNode() {
            super(null);
        }

        abstract void executeWrite(int newVal);

        abstract int executeRead();
    }

    static class MutableNode extends ReadWriteIntNode {
        private int value;

        public MutableNode(int value_) {
            super();
            this.value = value_;
        }

        @Override
        void executeWrite(int newVal) {
            System.out.println("TRACE: Wrote to a mutable node.");
            this.value = newVal;
        }

        @Override
        int executeRead() {
            return value;
        }
    }

    static class ImmutableNode extends ReadWriteIntNode {
        private final int replacementsSoFar;
        private final int value;

        public ImmutableNode(int value, int replacementsSoFar) {
            super();
            this.value = value;
            this.replacementsSoFar = replacementsSoFar;
        }

        public ImmutableNode(int value) {
            super();
            this.value = value;
            this.replacementsSoFar = 0;
        }

        @Override
        void executeWrite(int newVal) {
            System.out.println("TRACE: Need to replace node, with " + replacementsSoFar + " replacements so far.");
            if (newVal != value) {
                if (replacementsSoFar > 2) {
                    System.out.println("TRACE: Enough replacements, moving to a mutable node.");
                    this.replace(new MutableNode(newVal));
                    return;
                } else {
                    System.out.println("TRACE: Replacing with another immutable node.");
                    ImmutableNode newNode = new ImmutableNode(value, replacementsSoFar + 1);
                    this.replace(newNode);
                }
            }

        }

        @Override
        int executeRead() {
            return value;
        }
    }

    static class TestNode extends RootNode {

        public String getNodeType() {
            return internalNode.getClass().getName();
        }

        private @Child ReadWriteIntNode internalNode;

        public TestNode(ReadWriteIntNode internalNode) {
            super();
            this.internalNode = internalNode;
        }

        @Override
        public Object execute(VirtualFrame frame) {
            int toWrite = new Random().nextInt(100);
            internalNode.executeWrite(toWrite);
            return toWrite;
        }

    }

    public static void main(String[] args) {
        TruffleRuntime runtime = Truffle.getRuntime();
        TestNode root = new TestNode(new ImmutableNode(42));
        CallTarget tgt = runtime.createCallTarget(root);
        for (int i = 0; i < 6; i++) {
            System.out.println("The node is a " + root.getNodeType());
            System.out.println("Wrote "+tgt.call());
        }
    }
}

There is a single ImmutableNode to start. Each time the root node is invoked, a request is made for the node under test to be modified. Since it’s immutable at first, the only way to do that is a replacement. With each replacement, an internal final field, replacementsSoFar is assigned a value one higher in the new replacement node than in the old node. Once this value reaches a threshold of 3 replacements, the replacement is no longer immutable, but is now mutable with a non-final field for the value contained. This keeps the node from being JIT’ed as aggressively (if to JIT is even a verb), but will allow any subsequent replacements to happen at relatively low cost. Of course, a more powerful heuristic than a constant threshold for replacements will improve the performance of this setup even further.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s