I am reading through Dybvig's thesis and it's very clearly written and helpful. (I only hope my own thesis is as useful to someone in the future). <div> </div><div>Jens's tip will help a lot. I have a very stupid representation for all my values right now. Perhaps making it slightly more clever will give me the enough speed up to not worry about performance anymore.</div> <div> </div><div>And, now that I check, yes I am in fact type-checking the list structure during variable lookup, which is completely unnecessary. That might be why the profiler is telling me that all the overhead is coming from typechecking. Thank you!</div> <div> </div><div> -Patrick <div class="gmail_quote">On Mon, Mar 21, 2011 at 2:43 PM, Jens Axel Søgaard <<a href="mailto:jensaxel@soegaard.net">jensaxel@soegaard.net</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> 2011/3/21 Patrick Li <<a href="mailto:patrickli.2001@gmail.com">patrickli.2001@gmail.com</a>>: <div class="im">> Thanks for all the suggestions! I'll look over those and see what's > happening. > I have profiled my code, and noticed that it spends most of the time in > typechecking the arguments to the cons, car, and cdr primitives. I currently > know of no simple way to eliminate those checks while still giving me > relatively sane error messages for when things go wrong. </div>Which representation do you use? Maybe you can speed up the type checks, by choosing a clever representation. A common trick is to embed type information into the pointers. In the representation used in the 1996 Scheme Workshop pointers to cons cells contains 010 in their lower 3 bits. A type check is thus compiled to a very fast and instruction. <a href="http://www.cs.indiana.edu/eip/compile/back.html" target="_blank">http://www.cs.indiana.edu/eip/compile/back.html</a> -- Jens Axel Søgaard <div><div></div><div class="h5"> > -Patrick > > On Mon, Mar 21, 2011 at 1:39 PM, Vincent St-Amour <<a href="mailto:stamourv@ccs.neu.edu">stamourv@ccs.neu.edu</a>> > wrote: >> >> David Kranz's dissertation has a lot of interesting material about >> implementing closures efficiently. >> <a href="http://repository.readscheme.org/ftp/papers/orbit-thesis.pdf" target="_blank">http://repository.readscheme.org/ftp/papers/orbit-thesis.pdf</a> >> >> Andrew Appel's book Compiling with Continuations also covers similar >> material. >> >> Vincent >> >> At Mon, 21 Mar 2011 12:42:07 -0400, >> Patrick Li wrote: >> > >> > [1 <multipart/alternative (7bit)>] >> > [1.1 <text/plain; ISO-8859-1 (7bit)>] >> > Hello everyone, >> > >> > For educational purposes, I've implemented a simple Scheme interpreter >> > in C, >> > but it's way too slow at the moment. (eg. just macroexpanding and >> > evaluating >> > a function definition takes a few seconds.) I would like some advice on >> > how >> > to proceed next to get a adequately performing Scheme system. >> > >> > My goal is simply to get out of C as quickly as possible. ie. Get the >> > basic >> > forms and a macro system working which will allow me to write the rest >> > of it >> > in Scheme. >> > >> > So far this is what I have done: >> > >> > I wrote a simple Scheme interpreter in Scheme in continuation-passing >> > style, >> > so that I can get call/cc working. >> > >> > Then I basically just manually translated that code into C. So all >> > continuations are heap allocated. >> > >> > How should I proceed from here? These are the options that I've come up >> > with: >> > >> > (1) Optimize variable lookup. Currently the environment is represented >> > as a >> > list of key-value pairs. Variable lookup is done by searching through >> > the >> > list. >> > >> > (2) "Analyze" the code before evaluating it (ie. as in SICP). Ie. for an >> > (if) form, it will determine that it is an if form during the analysis >> > phase, so that at execution stage it won't have to repeatedly figure out >> > what sort of form it is. >> > >> > (3) Write a very simple VM, and develop a simple byte-code compiler. >> > The >> > problem here is that I don't really know how to deal with first-class >> > continuations. >> > >> > Thanks for your help >> > -Patrick >> > [1.2 <text/html; ISO-8859-1 (quoted-printable)>] >> > >> > [2 <text/plain; us-ascii (7bit)>] >> > _________________________________________________ >> > For list-related administrative tasks: >> > <a href="http://lists.racket-lang.org/listinfo/users" target="_blank">http://lists.racket-lang.org/listinfo/users</a> > > > _________________________________________________ > For list-related administrative tasks: > <a href="http://lists.racket-lang.org/listinfo/users" target="_blank">http://lists.racket-lang.org/listinfo/users</a> > </div></div>-- -- Jens Axel Søgaard </blockquote></div> </div>