[MUD-Dev] Re: AFAP: As fast as possible, non linear...

[Greg Connor]

Your previous messages in this thread talked about optimization (i.e. "as
fast as possible" - thus the subject line), so I thought I would add some
general comments about optimizing that might be helpful for this example
(and might possibly stimulate thought and discussion about optimizing in
general)


quzah [softhome] wrote:
>Greetings everyone. I've got a simple maze generator working if anyone
>cares to take a peek at it. I replied to this message because it is the
>last one in this thread that I have saved. Anyway, regarding the above,
>yes, the old method was really bad and I scrapped it all together. This
>is what I do now:
>
>(1) Store only the inner E and S walls for each row. This fits nicely
>into a short integer for an 8x8 maze, requiring only 15 bits of each
>short integer. The even bits (starting with bit0) are used for "south
>walls" and the odd bits (starting with bit1) are used for "east walls".


You seem to be using bitwise storage, which implies that you would need to
do bitwise AND/OR operations to get yes/no decisions or to change data in
the bit array.  This seems like it would be an optimization in the "space"
domain at the expense of the "time" domain... probably this would be a good
place to investigate if you really want something to run as fast as possible.

Using the least amount of storage really needed is usually a good idea...
until you get down to the granularity smaller than the machine's native
units (probably bytes).  In particular, you may have a high-level language
that lets you write statements like 
   if bit 3 of integer x is set, do procedure y
but the machine code may turn out to be something more tortured like
  load quantity "1"
  shift left "3" places
  load integer x
  do "AND" on these two
  check result for 0, if so, terminate
  go to procedure y

There are quite a few optimizations that can be done regardless of how you
implement storage and parameter passing, and most compilers are smart
enough to do this on their own (like, not computing a value if you're never
going to check its result).  However, there are other optimizations that
you can make (or tell your compiler to make) where you have to make a
choice: do you want to optimize for "space" or for "time".  (Space/Time
optimizations are the main reason there are two versions of the Oxford
English Dictionary: one as a twenty-volume set, and one as a single volume
with a magnifying glass included :)

So, you may want to investigate what, for your particular computer, is the
smallest quantity that can be compared with zero in one step.


>(2) I only check east and south when generating the maze. If the room
>to the east is unused, or south is unused, pick one and remove the wall.
>
>The outer wall of the maze is never used. In addition, it is not even
>stored. It is assumed, and therefore it is never needed. Since it is
>not needed, why bother keeping track of it?


There is another optimization hidden here... sometimes you may choose to
store something that is redundant to speed up your lookups (such as all
four walls instead of only two).  If you are walking the maze, and your
position is 3,3, you will want to know whether you can go north, south,
east or west.  For east and south, no problem, look up 3,3 in the table.
But for north you have to subtract one from Y and lookup 3,2 for its
"south" number.  What is the performance penaly for subtracting (or
"decrementing" even) one of the integers?  

You have also set up a number of "special cases" or "border cases" where
you actually need to do the equvalent of two IF's instead of one most of
the time.  For example, if you want to go north, from 3,3, you have to read
the value from 3.2, but if you want to go north from 3,0 the answer is
automatically No, there is no North from here.  This means every time you
push N the computer needs to calculate:
if direction is north 
 if y = 0
    no
  else 
    lookup x,(y-1)
    is "south" open? return yes

There is a similar condition on the east and south frontier... only the
comparison is "less than 8" which a computer might translate as "subtract 8
and branch on minus"

One way to optimize in this situation might be to store all four values as
another index to the array... then instead of all the IF's you just have
"lookup 3,3,0, and branch if zero".

There's another place where you can choose to store actual data, or
remember an implicit assumption, which is the outer frontier (points past
8).  You said "Since it's not needed, why bother keeping track of it?"
Well, one reason might be to save the programmer additional grief when it
comes time to change the size.  Right now you are kind of stuck with 8
because of the reliance on bitwise operations, but let's assume you can get
around that or code it away.  What happens when you want to go to a 16x16
square instead of 8?  Replace all occurences of 8 with 16.  If you want to
specify any size square?  Replace 16 with "SIZE" and #define SIZE 16 at the
top.  If you decide you want rectangles instead of squares?  Replace SIZE
with either WIDTH or HEIGHT and set #defines.

Then there is the question of how to fill an arbitrary-sized space with
maze, like a circle.  Well, you immediately start thinking about how to
"store" the values at the edges rather than "assume" they are there :)
Assumptions like "where the edges are" are something that need to decide
early on whether you want to go for "more code" or "more data".


>I "cheat recurrsion" by using a switch/loop, and avoid any overhead that
>the recurrsion normally would produce. In addition, I was (I'm sure it
>was very inefficient) running out of stack space in the early versions
>of the old generator, and this avoids that aspect all together.


This is a clever technique.  If an algorithm is recursive, you can make a
recursive function, or "simulate" recursion with your own "stack" (such as
an array and counter).  You may still run out of "stack" but at least you
have more control over memory usage (ie. you don't have to store "return
address" of the calling function :)