[Jastadd] Empty lists and efficiency

From: Jesper Mattsson <jesper.mattsson_at_modelon.com>
Date: Fri, 7 Dec 2012 12:42:02 +0000

Hi all

One thing we have recently noted while analyzing the memory use of our compiler is that there are many empty List nodes. In fact, for the (real-world) case we are currently studying, 83% of all Lists are empty. I'm not sure if this pattern can be found in other compilers, but I wouldn't be surprised. In the previously mentioned case, the memory cost for these Lists are 13.5% of the memory cost for the entire tree.

It strikes me that if it was possible to use a singleton for these empty lists, then it would be a rather large improvement in memory efficiency. Just doing so would of course be unsafe, but it would only be a very limited number of operations that would be unsafe, and these would be easily detected by JastAdd. All of this should apply to Opt as well, I think.

A possible way to implement this would be to add a flag to JastAdd that, when activated, disallows inherited attributes (and some other things?) on List and generated an additional class that extends List and overrides and disables (by throwing exceptions) some methods to give a fail-fast behavior for operations that are unsafe for singleton lists - getParent() and setChild() should be enough, I think.

I could easily experiment with this by adding the following aspect to our compiler and then using List.EMPTY for Lists that are empty and will not be changed.
public static List List.EMPTY = EmptyList.INSTANCE;

public class EmptyList extends List {
    public static List INSTANCE = new EmptyList();

    private EmptyList() {}

    public ASTNode getParent() {
        throw new UnsupportedOperationException();
    }

    public void setChild(ASTNode node, int i) {
        throw new UnsupportedOperationException();
    }
}

What do you think?
Would it be possible to make this safe (at least to the point where you only get exceptions for doing things like manually calling getParent() or adding nodes to an EmptyList)?
Are there any more methods on List that need to be overridden to detect operations that would break?

Jesper

Jesper MATTSSON, MSc
Software Developer & IT Administrator

Phone direct: +46 73 324 5909
Email: jesper.mattsson_at_modelon.com<mailto:jesper.mattsson_at_modelon.com>

[Description: Description: Modelon_2011_Gradient_RGB_400]
________________________________
Modelon AB
Ideon Science Park
SE-223 70 Lund, Sweden

Phone: +46 46 286 2200
Fax: +46 46 286 2201


Web: http://www.modelon.com<http://www.modelon.com/>



This email and any attachments are intended solely for the use of the individual or entity to whom it is addressed and may be confidential and/or privileged. If you are not one of the named recipients or have received this email in error, (i) you should not read, disclose, or copy it, (ii) please notify sender of your receipt by reply email and delete this email and all attachments, (iii) Modelon does not accept or assume any liability or responsibility for any use of or reliance on this email.




Received on Fri Dec 07 2012 - 13:42:27 CET