www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Compiling to Heap for CTFE

reply "Craig Black" <craigblack2 cox.net> writes:
Currently, CTFE only supports a subset of the language, and it relies on the 
compiler acting as an interpreter, which is slow.  It just occured to me 
that if we could compile code to the heap, there would be no need for a CTFE 
interpreter.  CTFE code could be compiled to the heap and executed at full 
speed.  Further, all the features of D would be available at compile time.

Thoughts?

-Craig 
Dec 17 2007
next sibling parent reply "Bruce Adams" <tortoise_74 yeah.who.co.uk> writes:
On Tue, 18 Dec 2007 02:27:06 -0000, Craig Black <craigblack2 cox.net>  
wrote:

 Currently, CTFE only supports a subset of the language, and it relies on  
 the compiler acting as an interpreter, which is slow.  It just occured  
 to me that if we could compile code to the heap, there would be no need  
 for a CTFE interpreter.  CTFE code could be compiled to the heap and  
 executed at full speed.  Further, all the features of D would be  
 available at compile time.

 Thoughts?

 -Craig

Its not necessarily that simple. You might be on a machine which distinguishes memory used by a program with memory that contains executable code. What you may end up with there is effectively the same as compiling and then running an exe. You also need some mechanism for the resulting 'stage 1 (or n)' exe to feed back into the compiler for 'stage 2 (or n+1)'. Presumably you are generating code as text tokens for the compiler but ideally with context that can be backtraced.
Dec 17 2007
parent bearophile <bearophileHUGS lycos.com> writes:
Craig:
 It just occured
 to me that if we could compile code to the heap, there would be no need  
 for a CTFE interpreter.

This is the "Staged compilers" or "Multi-stage Programming (MSP)": http://www.cs.rice.edu/~taha/MSP/ http://okmij.org/ftp/Computation/staging/metafx.pdf They are studying on it for lot of time. Bye, bearophile
Dec 18 2007
prev sibling next sibling parent Gregor Richards <Richards codu.org> writes:
Craig Black wrote:
 Currently, CTFE only supports a subset of the language, and it relies on 
 the compiler acting as an interpreter, which is slow.  It just occured 
 to me that if we could compile code to the heap, there would be no need 
 for a CTFE interpreter.  CTFE code could be compiled to the heap and 
 executed at full speed.  Further, all the features of D would be 
 available at compile time.
 
 Thoughts?
 
 -Craig

== death to cross-compilation. - Gregor Richards PS: Well, not necessarily, but it certainly would make things difficult.
Dec 17 2007
prev sibling next sibling parent reply Don Clugston <dac nospam.com.au> writes:
Craig Black wrote:
 Currently, CTFE only supports a subset of the language, and it relies on 
 the compiler acting as an interpreter, which is slow.

I'm encountering some severe slowdowns through CTFE; I've had to optimise my CTFE code for speed. Interestingly, at the present time, the interpreter doesn't seem to be the problem. The real problem is that DMD doesn't seem to release CTFE memory properly. For example, when you change an element of a string, AFACT it creates a new string and NEVER deletes the original! So at present, CTFE optimisation is about minimising the number of variables created or modified, rather than minimising the number of operations. It just occured
 to me that if we could compile code to the heap, there would be no need 
 for a CTFE interpreter.  CTFE code could be compiled to the heap and 
 executed at full speed.  Further, all the features of D would be 
 available at compile time.
 
 Thoughts?

In my code, the CTFE is normally heavily templated; it's rare that the same code is run multiple times, so compilation wouldn't help much. And we probably don't want to allow arbitrary code to run at compile-time (try detecting a virus that only exists in source-code format!) Some simple suggestions that would be major leaps forward in practical CTFE programming are: * gc at compile time, to stop the symbol table getting clogged up. * some version statement to detect if you are in CTFE. This would mean (a) you could create CTFE-able versions of code that uses (for example) asm at run-time; and far more importantly: (b) you could insert printf/writefln statements in the non-CTFE version, for assistance with debugging.
Dec 18 2007
next sibling parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Don Clugston" <dac nospam.com.au> wrote in message 
news:fk8083$1cgb$1 digitalmars.com...

 The real problem is that DMD doesn't seem to release CTFE memory properly.

Now, if only we had a D frontend written in D, then this wouldn't be a problem. Hmm...
Dec 18 2007
next sibling parent "Bruce Adams" <tortoise_74 yeah.who.co.uk> writes:
On Tue, 18 Dec 2007 13:33:18 -0000, Jarrett Billingsley  =

<kb3ctd2 yahoo.com> wrote:

 "Don Clugston" <dac nospam.com.au> wrote in message
 news:fk8083$1cgb$1 digitalmars.com...

 The real problem is that DMD doesn't seem to release CTFE memory  =


 properly.

Now, if only we had a D frontend written in D, then this wouldn't be a=

 problem.  Hmm...

I thought several people were already working on this. Though it might = be = nice to see a gcc style self bootstraping monster too. stage 1 - lowest common denominator =3D C - basic D compiler stage 2 - compile D version of D compiler using itself stage 3 - recompile D compiler using stage 2 compiler for more = optimisation.
Dec 18 2007
prev sibling parent "Craig Black" <craigblack2 cox.net> writes:
"Jarrett Billingsley" <kb3ctd2 yahoo.com> wrote in message 
news:fk8i6s$4d$1 digitalmars.com...
 "Don Clugston" <dac nospam.com.au> wrote in message 
 news:fk8083$1cgb$1 digitalmars.com...

 The real problem is that DMD doesn't seem to release CTFE memory 
 properly.

Now, if only we had a D frontend written in D, then this wouldn't be a problem. Hmm...

How would this help? From what I hear, Walter uses GC in his C++ code.
Dec 18 2007
prev sibling next sibling parent Christian Kamm <kamm.incasoftware shift-at-left-and-remove-this.de> writes:
Don Clugston wrote:

 I'm encountering some severe slowdowns through CTFE; I've had to optimise
 my CTFE code for speed. Interestingly, at the present time, the
 interpreter doesn't seem to be the problem. The real problem is that DMD
 doesn't seem to release CTFE memory properly. For example, when you change
 an element of a string, AFACT it creates a new string and NEVER deletes
 the original! So at present, CTFE optimisation is about minimising the
 number of variables created or modified, rather than minimising the number
 of operations.

 Some simple suggestions that would be major leaps forward in practical
 CTFE programming are:
 * gc at compile time, to stop the symbol table getting clogged up.

I have observed the same thing: the interpreter seems fast enough, but memory usage grows rapidly when doing string/array operations. It's very easy to use up all available memory. This is the bugzilla issue, by the way: http://d.puremagic.com/issues/show_bug.cgi?id=1382 Christian Kamm
Dec 18 2007
prev sibling parent BCS <ao pathlink.com> writes:
Reply to Don,

 
 Some simple suggestions that would be major leaps forward in practical
 CTFE
 programming are:
 * gc at compile time, to stop the symbol table getting clogged up.

a re working of the symbol table system would help a lot. With nested template, I see no reasons that the data of the base template should be copied for every sub template. IMHO it should be carried by reference, alos the full name should never be built until it needs to be output. Lastly for large char[] terms in templates some form of slicing would cut down a lot on memory usage. But what do I know, I've never written a full compiler. (just a lexer and a parser that won't compile because it's make DMD use to much ram :)
 * some version statement to detect if you are in CTFE. This would mean
 (a) you could create CTFE-able versions of code that uses (for
 example) asm
 at run-time; and far more importantly:
 (b) you could insert printf/writefln statements in the non-CTFE
 version, for
 assistance with debugging.

Dec 18 2007
prev sibling parent reply Chad J <gamerChad _spamIsBad_gmail.com> writes:
Craig Black wrote:
 Currently, CTFE only supports a subset of the language, and it relies on 
 the compiler acting as an interpreter, which is slow.  It just occured 
 to me that if we could compile code to the heap, there would be no need 
 for a CTFE interpreter.  CTFE code could be compiled to the heap and 
 executed at full speed.  Further, all the features of D would be 
 available at compile time.
 
 Thoughts?
 
 -Craig

In response to concerns about cross-compilation and security concerns: Perhaps if D had a VM then we could do it? At compile time, compile all of the CTFE code to bytecode, and interpret it. The intrepreter would be compiled by whatever is compiling the compiler, so it should make cross-compiling easier. Also, the VM and compiler can sandbox the CTFE code. Bytecode interpretation is not native speed execution, but probably close enough, and this approach allows use of D's high level features. Only problem is, that would be a lot of work. It involves writing a D backend for the bytecode, implementing security restrictions, and maybe even implementing the VM itself (if we can't find a ready-made one).
Dec 18 2007
parent reply "Bruce Adams" <tortoise_74 yeah.who.co.uk> writes:
On Tue, 18 Dec 2007 15:53:27 -0000, Chad J  
<gamerChad _spamIsBad_gmail.com> wrote:

 Craig Black wrote:
 Currently, CTFE only supports a subset of the language, and it relies  
 on the compiler acting as an interpreter, which is slow.  It just  
 occured to me that if we could compile code to the heap, there would be  
 no need for a CTFE interpreter.  CTFE code could be compiled to the  
 heap and executed at full speed.  Further, all the features of D would  
 be available at compile time.
  Thoughts?
  -Craig

In response to concerns about cross-compilation and security concerns: Perhaps if D had a VM then we could do it? At compile time, compile all of the CTFE code to bytecode, and interpret it. The intrepreter would be compiled by whatever is compiling the compiler, so it should make cross-compiling easier. Also, the VM and compiler can sandbox the CTFE code. Bytecode interpretation is not native speed execution, but probably close enough, and this approach allows use of D's high level features. Only problem is, that would be a lot of work. It involves writing a D backend for the bytecode, implementing security restrictions, and maybe even implementing the VM itself (if we can't find a ready-made one).

It would complete the set to have a D front end to one a VM and to have a D compiler/front end in D. There are plenty of VMs out there that may or may not be suitable. Its just a different target. You'd need the front end to support cross compilation and it would be nice to have a command line switch like gcc does. I don't think I've seen a VM used as a target for gcc otherwise gdc would already have most of the functionality needed. Probably because p-code and gcc itself is so damned ugly inside. Someone should port it to D - and clean up the mess. It would make a good community project but I guess porting is less satisfying than re-inventing the wheel, especially when you have better constructs to work with from the start. With regard to VMs to target apart from the obvious JVM and .NET/Mono (makes my unix bones shudder in horror) there's also Neko which is supposedly designed to be ported to http://nekovm.org/. But there is no reason why you couldn't port to your favourite language (tm)'s VM with enough hard work. A D VM would be best able to exploit the language features but would be a hell of a lot of work (albeit highly rewarding). Bruce.
Dec 18 2007
parent BC <notmi_emayl_adreznot hotmail.com.remove.not> writes:
On Tue, 18 Dec 2007 20:59:48 -0000, Bruce Adams  
<tortoise_74 yeah.who.co.uk> wrote:

 On Tue, 18 Dec 2007 15:53:27 -0000, Chad J  
 <gamerChad _spamIsBad_gmail.com> wrote:

 Craig Black wrote:
 Currently, CTFE only supports a subset of the language, and it relies  
 on the compiler acting as an interpreter, which is slow.  It just  
 occured to me that if we could compile code to the heap, there would  
 be no need for a CTFE interpreter.  CTFE code could be compiled to the  
 heap and executed at full speed.  Further, all the features of D would  
 be available at compile time.
  Thoughts?
  -Craig

In response to concerns about cross-compilation and security concerns: Perhaps if D had a VM then we could do it? At compile time, compile all of the CTFE code to bytecode, and interpret it. The intrepreter would be compiled by whatever is compiling the compiler, so it should make cross-compiling easier. Also, the VM and compiler can sandbox the CTFE code. Bytecode interpretation is not native speed execution, but probably close enough, and this approach allows use of D's high level features. Only problem is, that would be a lot of work. It involves writing a D backend for the bytecode, implementing security restrictions, and maybe even implementing the VM itself (if we can't find a ready-made one).

It would complete the set to have a D front end to one a VM and to have a D compiler/front end in D. There are plenty of VMs out there that may or may not be suitable. Its just a different target. You'd need the front end to support cross compilation and it would be nice to have a command line switch like gcc does. I don't think I've seen a VM used as a target for gcc otherwise gdc would already have most of the functionality needed. Probably because p-code and gcc itself is so damned ugly inside. Someone should port it to D - and clean up the mess. It would make a good community project but I guess porting is less satisfying than re-inventing the wheel, especially when you have better constructs to work with from the start. With regard to VMs to target apart from the obvious JVM and .NET/Mono (makes my unix bones shudder in horror) there's also Neko which is supposedly designed to be ported to http://nekovm.org/. But there is no reason why you couldn't port to your favourite language (tm)'s VM with enough hard work. A D VM would be best able to exploit the language features but would be a hell of a lot of work (albeit highly rewarding). Bruce.

maybe a x86 emulator could be used instead... just a thought
Jan 04 2008