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