Jump to content

  • Log In with Google      Sign In   
  • Create Account




King Mir

Member Since 11 Jun 2006
Offline Last Active Dec 13 2014 05:04 PM

Topics I've Started

Help me with my design

05 December 2013 - 11:25 PM


I'm writing a compiler, and I'm trying to come up with a good design for an abstract syntax tree, and it's conversion into code.


The Problem
The AST is built in depth first order, such that every node added will only ever refer to previously added nodes, and in most cases referenced nodes are the most recently added nodes. It is naturally a tree, so each node except the root node is referenced by one parent. For data, an AST node has a type, which can optionally be represented as an enum, a string value, and references to a usually small number of other nodes.

The above naturally leads to an implementation of a std::deque of nodes, acting like a stack. This takes advantage of the fact that elements in a deque tend to be adjacent in memory. It also allows the tree to grow without reallocation as it is built.

To convert the ast to code, I need to traverse the ast in essentially the same depth first traversal, except it may be convenient to start at the root node instead of the first node added. This would make make code generation a recursive algorithm, implementing depth first traversal. How to convert each node depends mostly on the logical type of the node. There may be a hierarchy to this conversion, that is it may make sense to say that converting a constructor is similar to converting a function. A hierarchy may organize code better.

So it strikes me as prudent to use virtual dispatch to implement the conversion. That is, each node type has an associated virtual convert/code_gen/compile function somewhere.

These two designs are at odds with each other, and I'd like your input on how to graft them together. There may also be other considerations that I've overlooked.



How to have a near continuous in memory and simply structured data, but use virtual dispatch to do operate on that data?

Thanks for your replies.

Critical size to pass by value

09 September 2013 - 10:31 PM

How big is a class or struct when it's cheaper to pass by reference than by value?

Large structs are cheaper pass by reference, but structs containing just an primitive type, or no objects at all are cheaper to pass by value. But what about types in between? what size is the cut off point? Is the number and mix of types a consideration?

This is essentially the same as asking "when should RVO kick in?"

There is some advantage to passing by value in alias analysis, and for my purposes I want to separate this effect. I'm curious what effect alias analysis has, but I'm also interested when the expense of the copy itself matters.

I'm pretty sure that for non trivially copyable types, passing by reference will always be cheaper, except for aliasing implications, but for POD types that's not so clear.

Garbage collection algorithim

15 July 2012 - 06:34 PM

I'm looking for a garbage collection algorithim that would behave like the following psudo code example specifies.
Class Foo {
  int id;
  GraphNodePtr<Foo> next //defaultly null
  Foo(int theID):id(theID){}

GraphNodePtr<Foo> graph(0);
  GraphNodePtr<Foo> node1(1);
  GraphNodePtr<Foo> node2(2);
  GraphNodePtr<Foo> node3(3);
  node1->next = node2;
  node2->next = node3;
  node3->next = node1; //circular loop
  graph->next = node1;
graph.next.release()//nodes 1, 2, and 3 are immediately deleted here

That is, you have a a single pointer type that can detect orphaned loops. And the garbage collection needs to guarantee that orphaned objects are released once they are orphaned.

Python global variable problem

26 June 2012 - 07:14 AM

So I have 3 files like so:
[source lang="python"]#Test1.pyimport Test2, Test.Test3if __name__ == '__main__': Test2.initVal() print Test2.getVal() Test.Test3.func()[/source]
[source lang="python"]#Test2.pyval = {}def initVal(): val[0] = 1 def getVal(): return val[0][/source]
[source lang="python"]#Test/Test3.pyimport Blobs.Test2def func(): print Blobs.Test2.getVal() #blobs is top level package[/source]

This prints 1, then gives me an exception, because func() sees val as empty the second time. How do I make it see the properly changed variable?

EDIT: clarified behavior

[java] Server with timeout.

11 August 2008 - 09:34 AM

I'm trying to implement a Server which will timeout after a period of inactivity and stop replying. I have the following code, but it seems to use up my cpu and leaks memmory. Is there a better way to do this?
//various imports

public class LoggingServer extends Thread{
    private static final long IDLE_TIME_MILLIS = 15000;
    private static final int LOGGING_SERVER_PORT = 9091;
    private Collection<TraceLogData> log = Collections.synchronizedCollection(
			new ArrayList<TraceLogData>() );
    private static ServerSocketChannel ssChannel;
    private AtomicBoolean CallCompleate = new AtomicBoolean(false);
    static {
        try {
            ssChannel = ServerSocketChannel.open();
            ssChannel.socket().bind(new InetSocketAddress(LOGGING_SERVER_PORT));
        } catch (IOException e) {}

    public void run(){
        try {
            long lastConnect = System.currentTimeMillis();
            while( !CallCompleate.get() || System.currentTimeMillis() 
                    < lastConnect + IDLE_TIME_MILLIS ){
                SocketChannel sChannel = ssChannel.accept();
       	            LoggingConnectionHandler handler =
                        new LoggingConnectionHandler(sChannel.socket(), log);
                    lastConnect = System.currentTimeMillis();
                } else {
        } catch (IOException e) {

    public boolean getCallCompleate() {
        return CallCompleate.get();

    public void setCallCompleate(boolean callCompleate) {

Sorry about the mixed tabs and spaces.