0

I have 2 version of a program I must analyze. One is recursive and the other is iterative. I must compare cache hit rate for both and examine as performance varies for both methods as well as their instructions count

For both methods regardless of block setting I get roughly 100 less memory access for the iterative method. both trigger 2 misses. I can only drop the cache hit rate to 85% if i set the setting to 1 block of size 256.

for the instructions count the iterative is roughly 1000 instructions less

Can someone explain to me why this happens or provide some literature I can read this in I can't seem to find anything. I would just like a general overview of why this occurs.

M_kul
  • 163
  • 2
  • 10
  • The recursive method likely uses significantly more stack space than the iterative method, resulting in more data cache misses. – markgz Apr 08 '16 at 22:34

1 Answers1

0

Took some info from this question: Recursion or Iteration? and some from in COMP 273 at McGill, which I assume you're also in and that's why you asked.

Each recursive call generally requires the return address of that call to be pushed onto the stack; in MIPS (assembly) this must be done manually otherwise the return address gets overwritten with each jal. As such, usually more cache space is used for a recursive solution and as such the memory access count is higher. In an iterative solution this isn't necessary whatsoever.

Community
  • 1
  • 1
F_Ryan
  • 18
  • 1
  • 1
  • 4
  • yea thanks thats what I was thinking in terms of amount of instructions and the amount of cache calls. Not sure if the cache hit/misses should change based on settings – M_kul Apr 09 '16 at 00:42