4

since I'm a newbie to Common Lisp I tried to solve problems on SPOJ by using Common Lisp (SBCL). The first problem is a simple task of reading numbers until number 42 is found. Here's my solution:

(defun study-num () (let ((num (parse-integer (read-line t)))) (when (not (= num 42)) (format t "~A~%" num) (study-num)))) (study-num)

The solution is accepted. But when I looked into the details of the result I found it used 57M of MEM! It's bloody unreasonable but I can't figure out why. What can I do to make an optimization?

Improve this question
5
  • How did you measure the 57M? (when using time to measure (study-num) with three guesses I get 100k consed - I guess I could get a much lower number with optimizations). Running (room) on a fresh instance of SBCL on x64 shows that it uses about 100M of RAM (about half the amount is used on x86). Commented Jan 25, 2012 at 19:17
  • @MironBrezuleanu That data is given by SPOJ. even a (format t "test") program would cost that much since I tested with it yesterday. Commented Jan 26, 2012 at 16:02
  • I'm asking about the memory consumption figure you gave (57M) - where does it come from? top or ps in the shell? (room) or (time ...) in the Lisp REPL? My hypothesis is that you used ps or something similar in the shell, and you basically saw the minimal memory usage of SBCL - which isn't that great, if you compare it to a loaded JVM (or .NET VM). Commented Jan 26, 2012 at 17:51
  • @MironBrezuleanu I mean the memory usage information is not from top or (room) or anything else on my computer, but given by SPOJ. Commented Jan 27, 2012 at 12:38
  • 2
    OK, so I guess they look at how much memory the process uses. ~50M is consistent with what SBCL needs initially on x86. Considering there's a lot of stuff in there, this is not a huge number IMO. If you need to see how much memory your code really conses, use (time) (consed bytes are a bit different from 'max memory used at one point', as you could have 2MB consed, but a GC after the first MB, thus the second MB uses the space of the first, so just 1MB of memory actually used). Commented Jan 27, 2012 at 14:16

3 Answers 3

Reset to default
7

You are making repeated recursive calls, without enough optimization switched on to enable tail-call elimination (SBCL does do this, but only when you have "optimize for speed" set high and "optimize for debug info" set low).

The Common Lisp standard leaves tail-call elimination as an implementation quality issue and provides other looping constructs (like LOOP or DO, both possibly suitable for this application).

In addition, a freshly started SBCL is probably going to be larger than you expect, due to needing to pull in its runtime environment and base image.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thanks. But the problem remains after the (proclaim '(optimize (speed 3) (debug 0))) is added to the beginning of my program. What shall I do if I want to solve this problem by using tail-recursive code?
@lastland Try it in a REPL while tracing STUDY-NUM and see if it actually does TCE? Otherwise, converting the code to use LOOP should be pretty trivial. I don't, off-hand, know how close 57 MB is to the "freshly started SBCL image" is, it may be close to as small as it gets.
I tried another program without LOOP, the memory usage stays 57M. But the exactly same program run on clisp would only use 12M (still too much but better). I guess the this problem is caused by sbcl, isn't it? So there's almost nothing I can do?
clisp and SBCL have a very different way of handling "code". In clisp, things are (mostly) byte-compiled and interpreted by a bytecode machine. In SBCL, things are (mostly) compiled to native code and the start-up process includes mapping in an image with the initial lisp environment.
Thank you. So the 57M memory is needed for the start environment of SBCL, right? I'd love to accept this answer if you're willing to make an edit.
5

I think yo are not realizing that Common Lisp is an online language environment with full library and compiler loaded into RAM just to give you the first prompt. After that, load in your program is probably a hardly even noticeable increase in size. Lisp does not compile and link an independent executable file made of only your code and whatever lib routines reachable from your code. That's what C and similar languages do. Instead, Lisp adds your code into its already sizeable online environment. As a new user it seams horrible. But if you have a modern general purpose computer with 100's MB of RAM, it quickly becomes something you can forget about as you enjoy the benefits of the online environment. Thins is also called a "dynamic language environment."

Improve this answer

Comments

4

Various Lisp implementations have different ways to create programs. One is to dump an image of the memory of a Lisp system and to write that to disk. On restart this image is loaded with a runtime and then started again. This is quite common.

This is also what SBCL does when it saves an executable. Thus this executable includes the full SBCL.

Some other implementations are creating smaller executables using images (CLISP), some can remove unused code from executables (Allegro CL, LispWorks) and others are creating very small programs via compilation to C (mocl).

SBCL has only one easy way to reduce the size of an executable: one can compress the image.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.