2

I'm a student, new to scheme language. I'm trying to write efficient functions. I already know how to calculate the execution time of a function, but what I'd like to know is how to calculate the stack(or memory) utilization of this function. Because as I know, the less number of instructions waiting on the stack during the execution the better efficiency gets.

so is there a way to count the number of instructions waiting on the stack?

user3452013
  • 13
  • 3
user3452021
  • 31
  • 1
  • 1
    You might be interested in this http://stackoverflow.com/a/310980/1193075 – uselpa Mar 23 '14 at 12:13
  • 1
    You might want to read about [tail recursion](http://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html#%28part._tail-recursion%29) and [tail call optimization](http://en.wikipedia.org/wiki/Tail_call) as defined in the [specification](http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_sec_11.20). – Óscar López Mar 23 '14 at 14:59
  • 1
    Most Schemes don't provide a "userland" way to get this information. If you really wanted it you could find how exception backtraces are stored and constructed in the source of your implementation, however this is certainly not a task for a beginner. – amoe Mar 23 '14 at 21:09

1 Answers1

1

No there is not a 'way to count the number of instructions waiting on the stack' in standard Scheme.

If you are learning Scheme, focusing on efficiency, execution time of a function and stack/memory utilization are utterly the wrong focus. "Premature optimization is the root of all evil (or at least most of it) in programming." D. Knuth - way too much focus on optimization at the level you are questioning.

You should be thinking at the level of algorithmic computational complexity and if you start expressing algorithms recursively, as Scheme encourages, then start learning about tail recursion (because Scheme guarantees that they are optimized to iteration).

GoZoner
  • 67,920
  • 20
  • 95
  • 145
  • thanks. but unfortunately that's exactly what the professor is asking for after 5 sessions!! – user3452021 Mar 24 '14 at 11:00
  • No way to count? I imagine a typical binary tree recursion will use frame*log(n) average and frame*n/2 worst case. Wouldn't you agree? – Sylwester Mar 25 '14 at 17:53
  • 'frames' are not instructions; compilers optimize away frames; 'stack(or memory)' varies from function to function; in your 'order analysis' you left out a factor `C`'. – GoZoner Apr 14 '14 at 18:04