Function varibales vs. extern variables Optimization Problem

[TillB]

Hi, this is my first post here so I hope I do everything right. Im trieing to optimize my fortran95 code and I stumbled over something I couldnt solve with google or the forum search here. Maybe I dont now the right keywords to search for.

Given an recursive function that could be called several million times (recursion depth is about 10). This functzion operates on several variables. Would it be better to always pass those variables in the function call, or store them as modulvariables to reduce the cost of putting thoses variables on the functionstack every time the function is called? (Im not quite sure how this works in Fortran)
My function uses several Integer variables and a few multidimensional arrays. It could look like this:

recursive function max(a, b, c, array1, array2, array3) result(best)
  Integer:: a, b, c, best
  Integer, dimension(:,:) array1, array2
  Integer dimension(:,:,:) array3
  !Do something with thoses Variables
end function max

as I understand this, Fortran passes those variables as references anyway, so would it make a difference in the access time if those were module variables:

module rek
  Integer:: a, b, c
  Integer, dimension(:,:) array1, array2
  Integer dimension(:,:,:) array3

  contains
  recursive function max() result(best)
    !Do something with thoses Variables
  end function max
end module rek

thx in advance

 

[FJacq]

With optimization, you need to measure, measure and measure again. It is sure that passing arguments to a recursive function has a cost. But you need to know that cost BEFORE starting to optimize. Use a tool like gprof for instance.

My first idea, with a cost problem concerning a recursive function, would be to replace that recursive function by a normal one without recursion (but, in that case, you need to keep the tree path in specific data which makes the programming more complicated)...

François Jacq

 

[TillB]

Thx for the fast reply. I probably will implement both versions and mesure the time. Im not sure about a non recursive version though xD. Would be pretty hard to do that.
What I'm doing here is a MiniMax algorithm (

http://en.wikipedia.org/wiki/Minimax)

finding the best move for an AI Player.

But lets take the recursion aside. Its still the same problem, isn't it?
Imagine I would call a function in a loop about a million times. What would be the better solution? Function variables or extern variables? I hoped someone would have made this experience before.

 

[salgerman]

I am a little bit at a loss, here...maybe because I never use recursion.

First, you wonder whether to pass the variables (by reference, fortran default), or to 'use' the variables...this confuses me, because, after all, I doubt you will be calling the function with the same exact variables or will you? Unfortunately your simplified recursive function does not show how you are going to call the recursive function from within itself...I would like to see that!...I mean, I know it has (a,b,c,arr1,arr2,arr3) but it is still possible to call it by placing other variables in place of a,b,c and even subset of the arrays (x,y,z,arr1(i:j),arr2(m:n),arr3(p:q)).

Second...I forgot, now, but I thought I had another question...oh, well.

 

[TillB]

let me try to clarify this. Basically I have two options:

module ai
  function makeYourTurn(_playingField)
    Integer :: makeYourTurn
    Integer, dimension(:,:) :: _playingField
    makeYourTurn=max(0, _playingField)
  end function makeYourTurn   

  recursive function max(searchDepth, playingField) result(best)
   Integer:: searchDepth, value, best,
   Integer, dimension(:,:) playingField
   
   if(searchDepth== maxSearchDepth) then
       best= evaluateCurrentSituation(playingField)
       return !breaks recursion
   else

     do while(movesLeft())
       doMove !changes the state on the playingField
       value=min(searchDepth+1, playingField) !recursion
       undoMove !returns to the old state of the playingField
       if(value>best) best=value
     end do

   end if
 end function max

end modul ai

(function min does basicly the same as max, but returns the minimum value

So I have to pass searchDepth of course, but I could change the code like this

module ai
  Integer, dimension(:,:) playingField

  function makeYourTurn(_playingField)
    Integer :: makeYourTurn
    Integer, dimension(:,:) :: _playingField
    playingField=_playingField
    makeYourTurn=max(0)
  end function makeYourTurn    

  recursive function max(searchDepth) result(best)
   Integer:: searchDepth, value, best,
   
   if(searchDepth== maxSearchDepth) then
       best= evaluateCurrentSituation(playingField)
       return !breaks recursion
   else
     do while(movesLeft())
       doMove !changes the state on the playingField
       value=min(searchDepth+1, playingField) !recursion
       undoMove !returns to the old state of the playingField
       if(value>best) best=value
     end do
   end if
 end function max

end modul ai

I wonder, because those functions will be called many times, if it would be better to pass playingField every time or to store it in an modul variable. My actual functions uses some more variables of that kind

 

[TillB]

So actually the variable playingField will be the same for every recursive call, and will not be replaced.

 

[salgerman]

In that case, I would say you do not need to keep passing it around; then, again, BECAUSE fortran uses pass-by-reference by default, it does not take much to simply pass a pointer...it is not like it is actually passing a bunch of numbers, etc.

By the way, as it is, I don't see recursion...does the 'min' function, in turn, calls 'max'? ...still.

Where is maxSearchDepth coming from?

Oh...I just remember the second thing I wanted to mention: You never seem to see it, but it is possible in fortran to pass-by-value, too...but you need to explicitely request it, or course, since that is not the default.

 

[TillB]

Thank you for your answer

Yes "max" calls "min" and "min" calls "max". It simulates something like this: I choose the move that is best for me (max) and then my oponent chooses his move that is worst for me (min) and then I choose the best move for me again (max) and so on. It simulates that til searchDepth reaches maxSearchDepth which is a parameter I defined to stop the recursion. Currently its about 10. Pretend you have 5 valid possible moves to choose from at any given time in the game. The function max would call min 5 time (for every valid move to make). Min would then call max 5 times... that makes 5^10 calls of either min or max.

By the way how can I tell Fortran to pass-by-value? Im currently porting my code from Java to Fortran (I wrote it in Java first). Java uses pass-by-reference for everything except for basic types like int and float, so i didn't think about that when I ported it xD. Got me some pretty bad bugs. Now I do something like "call foo(a+0)" int fortran to pass a by value.

 

[salgerman]

Hhhhmmm...if you have bugs, you have bugs....don't blame it on passing by reference or by value

If you just need the value and not planning on modifying the input variable, you can always specify 'intent'

Or

You can make a copy of it right away and work with the local copy of the variable.

I have never needed to pass by value while working with Fortan, alone; the only time when I needed to worry about passing by value is when I was working with both Fortran and C at the same time, given that C's default is pass-by-value.

In Fortran, to force a pass-by-value simply enclose your variable in "%val()" as you list it as argument in the call to the subroutine or function.

I think there is something new, too, when declaring the pass-by-value variable local to the function...something about adding "[VALUE]" after the variable name.

this you can google...

 

[gummibaer]

Nothing to contribute to the problem of passing of variables here.

One of my hobbies is numbers and figures, especially in exponential functions. So, what about the numbers that are involved? 5^10 is about 10 million. Even if your system could handle this number of calls within a decent timeframe, this would come to an end pretty soon if you change the parameters just a little bit. If the number of valid moves goes up to 6 it would be 60 million calls to your routine, 7 would be 282 million. Your search depth has the same effect. 5 moves at a depth of 11 would create 110 million calls, a depth of 12 more than half a billion. 7 moves at the depth of 12 would make something about 13 billion calls. I'd say this is kind of a suicide tack and about to explode if you increase some of the parameters just a little bit.

Even if you are successful in optimising data handling in your code, I guess a much better paying approach would be to look for a better strategy to define the next move. Can you find some criteria to exclude possible moves from the list and not to follow them any further ? Is there something in the rules or in the target of the game that could be used to rate the moves ? Something more brainy than just brutal force ?

My two cents.
Norbert


The optimist believes we live in the best of all possible worlds - the pessimist fears this might be true.

 

[TillB]

Hi Norbert,

The algorithm I'm using is pretty well known as MiniMax algorithm. Ther is indeed a optimization called Alpha-Beta-Search, which cuts of alot!
I try to implement this strategie for a connect4 game which in general has 6 rows and 7 columns one could put a stone into. (7 possible moves). So with no optimization and a searchDepth of 10 7^10 = 282.475.249. function calls.

My program uses Alpha Beta optimization and I count 9.261.962 function calls in the worst case til now. (I cant give you an average atm. Just started testing but its much better. Maybe about 1.000.000).
However my algorithm should be able to handle larger fields than 6*7 so I probably have to cut down the searchDepth a bit.

Strangely my Java program is much faster (with the same function call count) than my Fortran program. I know that doesnt speak for my programming skils xD. But it shows me that I can do a lot of optimization with the fortran program even without doing less function calls. (Atm both programs have the same count of function calls and handel things pretty equal. I guess Java compiles with more optimizations or what?)

 

[xwb]

I've never coded mini-max: only alpha beta and m&n. Anyway, since playing field is the same identifier, make it a module level variable. Just pass the search depth in.

Fortran splits the functions into functions for the ones that return values and subroutines for the void functions. You do not appear to be setting the return values in the functions. After the endif, you still need a max = best.

Performance on mutual recursion should be the same as C/C++. Should be faster than Java/C# since it is not going through a bytecode interpreter. That is unless the Java compiles to native, in which case the speeds should be comparable.

There are lots of optimizations with Fortran but it depends on which compiler you're using. Recursion has been available in Fortran since 77 though not many people used it. Most engineering type apps don't really require recursion.