Eliminating "flag1".

1 view
Skip to first unread message

Peter Seebach

unread,
Feb 13, 2001, 1:10:41 PM2/13/01
to
Now that 2.9.2 is out, I'm going to have another look at replacing
flag1..flag6 with flags[6] and test/set macros smart enough to look for
flags in the appropriate word.

Does anyone have feedback, suggestions, or reasons for which this would
not be an unambiguous win? I think the current code is just horribly
crufty, to be honest. Testing a flag shouldn't require different code
for the first 32 flags than for the second 32.

-s
--
Copyright 2001, all wrongs reversed. Peter Seebach / se...@plethora.net
C/Unix wizard, Pro-commerce radical, Spam fighter. Boycott Spamazon!
Consulting & Computers: http://www.plethora.net/

Gwidon S. Naskrent

unread,
Feb 13, 2001, 5:02:38 PM2/13/01
to
On 13 Feb 2001, Peter Seebach wrote:

> Now that 2.9.2 is out, I'm going to have another look at replacing
> flag1..flag6 with flags[6] and test/set macros smart enough to look for
> flags in the appropriate word.

What do you want to achieve by this? How is an array of 6 bitfields better
that 6 separate bitfields? You will only get a headache when rewriting the
declarations in init1.c.

Do it the NH way at least: pour all the flags into one giant bitfield (or
appropriate Angband equivalent) and let the compiler worry where to find
them.

> Does anyone have feedback, suggestions, or reasons for which this would
> not be an unambiguous win? I think the current code is just horribly
> crufty, to be honest. Testing a flag shouldn't require different code
> for the first 32 flags than for the second 32.

How come? It doesn't, unless you call referencing another structure member
"different code".

GSN


Steven Fuerst

unread,
Feb 13, 2001, 6:35:39 PM2/13/01
to
Peter Seebach wrote:
>
> Now that 2.9.2 is out, I'm going to have another look at replacing
> flag1..flag6 with flags[6] and test/set macros smart enough to look for
> flags in the appropriate word.
>
> Does anyone have feedback, suggestions, or reasons for which this would
> not be an unambiguous win? I think the current code is just horribly
> crufty, to be honest. Testing a flag shouldn't require different code
> for the first 32 flags than for the second 32.

Testing flags in parallel is a good thing about the current system.
Look at the monster AI, which masks off the "useful" spells of a
particular type, for example.

That part of the game is designed for speed and portability, over
prettyness.

Steven

Peter Seebach

unread,
Feb 13, 2001, 10:02:36 PM2/13/01
to
In article <Pine.LNX.4.31.01021...@localhost.localdomain>,

Gwidon S. Naskrent <nask...@artemida.amu.edu.pl> wrote:
>On 13 Feb 2001, Peter Seebach wrote:
>> Now that 2.9.2 is out, I'm going to have another look at replacing
>> flag1..flag6 with flags[6] and test/set macros smart enough to look for
>> flags in the appropriate word.

>What do you want to achieve by this?

Eliminating any hint of caring which word is being set. Imagine,
for a moment, the implications of
if (flag3 & RF4_FOO)
if RF4 hints at something being in flag 4.

>How is an array of 6 bitfields better
>that 6 separate bitfields?

You don't need to remember which one is which. You don't have all
this crufty code copying all six flags into dummy variables, testing
things against them...

Also, we can drop the "RF1" vs "RF3" thing. All flags can just be "RF" or
whatever.

>You will only get a headache when rewriting the
>declarations in init1.c.

I don't see why. That code looks easy.

>Do it the NH way at least: pour all the flags into one giant bitfield (or
>appropriate Angband equivalent) and let the compiler worry where to find
>them.

Well, that depends. For compatability, it seems as though the same 96
or 192 or however many bits should be in use, but that's no big deal.

>> Does anyone have feedback, suggestions, or reasons for which this would
>> not be an unambiguous win? I think the current code is just horribly
>> crufty, to be honest. Testing a flag shouldn't require different code
>> for the first 32 flags than for the second 32.

>How come? It doesn't, unless you call referencing another structure member
>"different code".

Well, it's a point of possible failure. It allows for the *possibility*
of doing it wrong, and there's no *reason* for it.

Basically, I am unable to find anything in the code which *benefits* from
these being separately declared objects.

Note also:
object1.c: if (f2 & (TR2_RES_NEXUS))
wizard1.c: if (flags3 & (RF3_RES_NEXU)) vp[vn++] = "nexus";

Why should we need to remember that the TR RES_NEXUS flag is in TR2, but
the RF RES_NEXUS flag is in RF3? Why not just
if (flag(o_ptr, TR_RES_NEXUS))
or
if (flag(r_ptr, RF_RES_NEXUS))
or something similar?

These are not six separate and unrelated things; this is a single set of
flags. It should be spelled that way.

Peter Seebach

unread,
Feb 13, 2001, 10:07:47 PM2/13/01
to
In article <3A89C4...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>Testing flags in parallel is a good thing about the current system.
>Look at the monster AI, which masks off the "useful" spells of a
>particular type, for example.

I'm not sure I understand this explanation. What's it doing that it
couldn't do with a generic flag bit?

I do see some potential for things that you can currently do by or'ing
flags... but those are all annoyingly dependant on ordering and grouping,
and it'd be nice to solve the problem more generically.

>That part of the game is designed for speed and portability, over
>prettyness.

I see no portability issues here. This is easy to do with a macro that
will work everywhere. :)

Steven Fuerst

unread,
Feb 13, 2001, 10:11:06 PM2/13/01
to
Peter Seebach wrote:
>
> In article <Pine.LNX.4.31.01021...@localhost.localdomain>,
> Gwidon S. Naskrent <nask...@artemida.amu.edu.pl> wrote:
> >On 13 Feb 2001, Peter Seebach wrote:
> >> Now that 2.9.2 is out, I'm going to have another look at replacing
> >> flag1..flag6 with flags[6] and test/set macros smart enough to look for
> >> flags in the appropriate word.
>
> >What do you want to achieve by this?
>
> Eliminating any hint of caring which word is being set. Imagine,
> for a moment, the implications of
> if (flag3 & RF4_FOO)
> if RF4 hints at something being in flag 4.
>

I've seen this happen. Unlike most bugs - this one is fairly easy to
spot, and even easier to fix.


Steven

Steven Fuerst

unread,
Feb 13, 2001, 10:16:48 PM2/13/01
to
Peter Seebach wrote:
>
> In article <3A89C4...@physics.usyd.edu.au>,
> Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
> >Testing flags in parallel is a good thing about the current system.
> >Look at the monster AI, which masks off the "useful" spells of a
> >particular type, for example.
>
> I'm not sure I understand this explanation. What's it doing that it
> couldn't do with a generic flag bit?

You can do things in parallel for speed. This is done quite alot in the
more heavily optimised parts of the code.

>
> I do see some potential for things that you can currently do by or'ing
> flags... but those are all annoyingly dependant on ordering and grouping,
> and it'd be nice to solve the problem more generically.

Annoyingly dependant on ordering and grouping? Since when do you need
change the position of a flag?

>
> >That part of the game is designed for speed and portability, over
> >prettyness.
>
> I see no portability issues here. This is easy to do with a macro that
> will work everywhere. :)

Bitflags tend to have portability problems due to endian differences.

So you do see the speed issue then? Alot of the things in the code are
optimised for speed and lack of memory useage. The current flags code
is no exception.

I'd agree with you if the "ugliness" of the code was a big problem...
but it simply isn't one.

Steven

Peter Seebach

unread,
Feb 14, 2001, 12:51:08 AM2/14/01
to
In article <3A89F8...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>You can do things in parallel for speed. This is done quite alot in the
>more heavily optimised parts of the code.

I wouldn't worry about that, you can parallelize array ops.

>> I do see some potential for things that you can currently do by or'ing
>> flags... but those are all annoyingly dependant on ordering and grouping,
>> and it'd be nice to solve the problem more generically.

>Annoyingly dependant on ordering and grouping? Since when do you need
>change the position of a flag?

You rarely do, but why should you need to know?

>Bitflags tend to have portability problems due to endian differences.

Not at all, or at least, none they don't have right now.

>So you do see the speed issue then? Alot of the things in the code are
>optimised for speed and lack of memory useage. The current flags code
>is no exception.

I don't think there's a measurable speed issue on any modern compiler.

>I'd agree with you if the "ugliness" of the code was a big problem...
>but it simply isn't one.

I dunno. It looks ugly to me.

Steven Fuerst

unread,
Feb 14, 2001, 1:12:39 AM2/14/01
to
Peter Seebach wrote:
>
> In article <3A89F8...@physics.usyd.edu.au>,
> Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
> >You can do things in parallel for speed. This is done quite alot in the
> >more heavily optimised parts of the code.
>
> I wouldn't worry about that, you can parallelize array ops.

Really? Can you tell me how so I can speed up some other code?

>
> >> I do see some potential for things that you can currently do by or'ing
> >> flags... but those are all annoyingly dependant on ordering and grouping,
> >> and it'd be nice to solve the problem more generically.
>
> >Annoyingly dependant on ordering and grouping? Since when do you need
> >change the position of a flag?
>
> You rarely do, but why should you need to know?

Why not know? You can use the extra information to your advantage...

> >So you do see the speed issue then? Alot of the things in the code are
> >optimised for speed and lack of memory useage. The current flags code
> >is no exception.
>
> I don't think there's a measurable speed issue on any modern compiler.

Have a look at the AI code. It uses masking all over the place. The AI
is a major bottleneck of the game.

If you think you can make this faster - tell me how. It is very easy to
make it slower.



> >I'd agree with you if the "ugliness" of the code was a big problem...
> >but it simply isn't one.
>
> I dunno. It looks ugly to me.

Something to think about: I've seen a total of one instance where the
flags got mixed up, in some rather active development of the game. This
bug was fairly easy to find. Even though it may look bad to you - it
doesn't affect development in any real way. That is all that counts
IMHO.

Steven

Gwidon S. Naskrent

unread,
Feb 14, 2001, 4:09:30 AM2/14/01
to
On 14 Feb 2001, Peter Seebach wrote:

> Eliminating any hint of caring which word is being set. Imagine,
> for a moment, the implications of
> if (flag3 & RF4_FOO)
> if RF4 hints at something being in flag 4.

This is certainly a problem, however, any experienced maintainer does the
agreement unconsciously :)

> >How is an array of 6 bitfields better
> >that 6 separate bitfields?
>
> You don't need to remember which one is which. You don't have all
> this crufty code copying all six flags into dummy variables, testing
> things against them...

The flags are never copied, nor are they in need to.

After your change you'll get r_ptr->flags[1] & RF1_FOO. You have gained
nothing and added an extra pair of brackets.

> Also, we can drop the "RF1" vs "RF3" thing. All flags can just be "RF" or
> whatever.

No way, how will you remember which one goes into which bitfield?

> >You will only get a headache when rewriting the
> >declarations in init1.c.
>
> I don't see why. That code looks easy.

Oh, you'll have to join the six separate arrays into one, won't you?

>
> Why should we need to remember that the TR RES_NEXUS flag is in TR2, but
> the RF RES_NEXUS flag is in RF3? Why not just
> if (flag(o_ptr, TR_RES_NEXUS))
> or
> if (flag(r_ptr, RF_RES_NEXUS))
> or something similar?

Looks good in theory, but how about the details?

GSN


Hansjörg Malthaner

unread,
Feb 14, 2001, 8:24:59 AM2/14/01
to

Partability isn't lost if you change the six variables to an array of
six variables.
You acn still test them in parallel if you want. And you can use indexed
acces i.e. for iteraing all six fields if you need. Flexibility is the
gain you get.

Nevertheless I'd suggest a bitfield, like Gwidon did in the other branch
of the thread, this is the only proper solution.

> Steven

c.u.
Hajo

LucFrench

unread,
Feb 14, 2001, 11:27:10 AM2/14/01
to
Something everybody in this thread is forgetting.

If the current system exists because of speed, why not just do:

#define P_RES_NETHER (flag2 & RF2_RES_NETHER)

Thus gaining the best of both worlds. (Easier to read code, and fast code.)

Ah well.

Thanks
Luc "Simplistic" French

Gwidon S. Naskrent

unread,
Feb 14, 2001, 11:59:57 AM2/14/01
to
On 14 Feb 2001, LucFrench wrote:

> If the current system exists because of speed, why not just do:
> #define P_RES_NETHER (flag2 & RF2_RES_NETHER)

Of course you know that flag2 must be initialized prior to the expansion
of this macro, and there may be bugs galore if you forget about it. All in
all, it's how you should NOT write macros.

You could amend this by defining RES_NETHER(x) where x is the monster's
structure, but that sort of self-defeats itself.

GSN

Julian Lighton

unread,
Feb 14, 2001, 9:32:06 PM2/14/01
to
In article <Pine.LNX.4.31.01021...@localhost.localdomain>,
Gwidon S. Naskrent <nask...@artemida.amu.edu.pl> wrote:
>On 14 Feb 2001, Peter Seebach wrote:
>
>> Eliminating any hint of caring which word is being set. Imagine,
>> for a moment, the implications of
>> if (flag3 & RF4_FOO)
>> if RF4 hints at something being in flag 4.
>
>This is certainly a problem, however, any experienced maintainer does the
>agreement unconsciously :)

True.

>> >How is an array of 6 bitfields better
>> >that 6 separate bitfields?
>>
>> You don't need to remember which one is which. You don't have all
>> this crufty code copying all six flags into dummy variables, testing
>> things against them...
>
>The flags are never copied, nor are they in need to.

object_flags()

Of course, object_flags() may be somewhat awkward to re-do in this
manner.

>After your change you'll get r_ptr->flags[1] & RF1_FOO. You have gained
>nothing and added an extra pair of brackets.

He's talking macros that hide the precise location of the flag from you.

>> Also, we can drop the "RF1" vs "RF3" thing. All flags can just be "RF" or
>> whatever.
>
>No way, how will you remember which one goes into which bitfield?

You don't care; the idea is that the compiler knows.
--
Julian Lighton jl...@fragment.com
"ISO 9001 certification is a license to kill!" -- MST3K

Peter Seebach

unread,
Feb 17, 2001, 11:49:59 AM2/17/01
to
In article <3A8A21...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>Peter Seebach wrote:
>> In article <3A89F8...@physics.usyd.edu.au>,
>> Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>> >You can do things in parallel for speed. This is done quite alot in the
>> >more heavily optimised parts of the code.

>> I wouldn't worry about that, you can parallelize array ops.

>Really? Can you tell me how so I can speed up some other code?

The compiler does it. Explicitly parallelizing code is just plain silly
on modern compilers.

>> You rarely do, but why should you need to know?

>Why not know? You can use the extra information to your advantage...

No, you can't. You can do things which, on a PDP-11 compiler, might
have produced a marginal benefit. It's not *useful* now.

>Have a look at the AI code. It uses masking all over the place. The AI
>is a major bottleneck of the game.

Okay. That's a good thing to look at. To what extent is it depending on
certain groups of bits all being in the same word?

>Something to think about: I've seen a total of one instance where the
>flags got mixed up, in some rather active development of the game. This
>bug was fairly easy to find. Even though it may look bad to you - it
>doesn't affect development in any real way. That is all that counts
>IMHO.

It affects development all the time; witness debates about whether a flag
bit is "free", or why something is in flags3 or flags4. All of that is
an artifact of treating a single set of 192 flags as if it were six totally
unrelated objects.

Now, to be fair, there *are* groupings... but they aren't precisely on the
word boundaries, and a whole word is rarely a meaningful grouping.

That said, there's a good case to be made for an organization such that,
in general, sets of related flags are all in one place. I'm not sure how
much it matters.

If we're going to argue performance, we should probably be profiling the code
and finding out how much time we currently spend masking things, in different
ways. My guess is that there are a lot of other things that would go first;
for instance, if I wanted Angband to be fast, I'd calculate chances
"correctly" up front, rather than re-rolling until I got a result I liked
every time. That's an operation which has no upper bound on how long it
takes. :)

Peter Seebach

unread,
Feb 17, 2001, 11:56:06 AM2/17/01
to
In article <Pine.LNX.4.31.01021...@localhost.localdomain>,
Gwidon S. Naskrent <nask...@artemida.amu.edu.pl> wrote:
>> You don't need to remember which one is which. You don't have all
>> this crufty code copying all six flags into dummy variables, testing
>> things against them...

>The flags are never copied, nor are they in need to.

I had misread the object_flags stuff, but there are places in wizard where
flags are copied into variables named "flags1".

>> Also, we can drop the "RF1" vs "RF3" thing. All flags can just be "RF" or
>> whatever.

>No way, how will you remember which one goes into which bitfield?

I don't understand the question. My proposal just has flags be numbered,
e.g., 0 through 191, and they get set and masked in the corresponding
words of an array.

>> I don't see why. That code looks easy.

>Oh, you'll have to join the six separate arrays into one, won't you?

If my initial skimming is correct, yeah, but I'd probably prefer to make
it a generated thing so the enum and the array of strings line up.

>> Why should we need to remember that the TR RES_NEXUS flag is in TR2, but
>> the RF RES_NEXUS flag is in RF3? Why not just
>> if (flag(o_ptr, TR_RES_NEXUS))
>> or
>> if (flag(r_ptr, RF_RES_NEXUS))
>> or something similar?

>Looks good in theory, but how about the details?

I am *SO* glad I just wrote the code for the spellbook hack rather than
asking about it. It's obvious to a casual observer that you can't do this
to spellbooks, either.

Peter Seebach

unread,
Feb 17, 2001, 12:02:31 PM2/17/01
to
In article <GcHi6.442$9d.5...@newshog.newsread.com>,

Julian Lighton <jl...@fragment.com> wrote:
>Of course, object_flags() may be somewhat awkward to re-do in this
>manner.

It'll be marginally more expensive when you actually need all the flags,
and somewhat cheaper in the most common cases, where you only use a few
of them.

>>After your change you'll get r_ptr->flags[1] & RF1_FOO. You have gained
>>nothing and added an extra pair of brackets.

>He's talking macros that hide the precise location of the flag from you.

Yes. The code would be
flag(r_ptr, RF_FOO);
and no "RF1" or "RF2".
#define flag(p, n) ((p)->flags[(n)/32] & (1 << ((n) % 32)))

For extra credit, expand it to return 0 for n out of range. (Since range
differs, you might want "rflag" and "oflag".

Now, I know *someone* will jump on me for the expensive math, but remember,
RF_FOO is a *CONSTANT*. I doubt Angband targets a single compiler that
won't fold this all up at compile time.

>You don't care; the idea is that the compiler knows.

Exactly! And that, my friends, is the perceived "advantage".

Thinking about this further, there's a number of flag-related ops that
might want special treatment... but I think it'd be a win to centralize
that treatment. object_flags{,_aux} is useful, but it's doing more work
than it probably needs to in a lot of cases.

Honestly, the most expensive part of this is still the distinction between
flags a thing has and flags the player knows about, but that's pretty easy
to handle. Indeed, we can do exactly what we do now, except that instead
of declaring three objects to hold flag values, we declare one.

Steven Fuerst

unread,
Feb 18, 2001, 9:05:50 PM2/18/01
to
Peter Seebach wrote:
>
> In article <3A8A21...@physics.usyd.edu.au>,
> Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
> >Peter Seebach wrote:
> >> In article <3A89F8...@physics.usyd.edu.au>,
> >> Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
> >> >You can do things in parallel for speed. This is done quite alot in the
> >> >more heavily optimised parts of the code.
>
> >> I wouldn't worry about that, you can parallelize array ops.
>
> >Really? Can you tell me how so I can speed up some other code?
>
> The compiler does it. Explicitly parallelizing code is just plain silly
> on modern compilers.

"The compiler does it." doesn't help me. Which particular code
fragments does the compiler optimise to execute in that way? In my
experience, a human can quite often out-optimise a compiler by using
different data structures. This particular instance comes under that
case.

>
> >> You rarely do, but why should you need to know?
>
> >Why not know? You can use the extra information to your advantage...
>
> No, you can't. You can do things which, on a PDP-11 compiler, might
> have produced a marginal benefit. It's not *useful* now.

Really?

I'd like to see a compiler convert
for(i = 0; i < 96; i++)
{
if (mask[i] && flag_set(flag, i))
{
flag_on(flag, i);
}
else
{
flag_off(flag, i);
}
}


into

flag1 &= mask1;
flag2 &= mask2;
flag3 &= mask3;

In my experience, compilers aren't that smart.

>
> >Have a look at the AI code. It uses masking all over the place. The AI
> >is a major bottleneck of the game.
>
> Okay. That's a good thing to look at. To what extent is it depending on
> certain groups of bits all being in the same word?

It doesn't depend on that.

It depends on being fast.

>
> >Something to think about: I've seen a total of one instance where the
> >flags got mixed up, in some rather active development of the game. This
> >bug was fairly easy to find. Even though it may look bad to you - it
> >doesn't affect development in any real way. That is all that counts
> >IMHO.
>
> It affects development all the time; witness debates about whether a flag
> bit is "free", or why something is in flags3 or flags4.

Don't be silly. The "free flag" debates still need to look in defines.h
in any case. In most cases there is no reason "why" something is in a
particular flag - so there is no point arguing about that either.

> All of that is
> an artifact of treating a single set of 192 flags as if it were six totally
> unrelated objects.

Nope - it is an artifact of someone not understanding how the code
works.

>
> Now, to be fair, there *are* groupings... but they aren't precisely on the
> word boundaries, and a whole word is rarely a meaningful grouping.
>
> That said, there's a good case to be made for an organization such that,
> in general, sets of related flags are all in one place. I'm not sure how
> much it matters.
>
> If we're going to argue performance, we should probably be profiling the code
> and finding out how much time we currently spend masking things, in different
> ways.

I already have done this. There was a significant speedup when I
converted the code from something that uses masks, to something that
uses masks in parallel. You want to convert it to something that will
only be serial... that will be noticably slow.

> My guess is that there are a lot of other things that would go first;
> for instance, if I wanted Angband to be fast, I'd calculate chances
> "correctly" up front, rather than re-rolling until I got a result I liked
> every time. That's an operation which has no upper bound on how long it
> takes. :)

Are you talking about the autoroller? You might want to look at the
formula used to work out the acceptance or rejection of a roll.
Calculating the probability isn't trivial.

Steven

Julian Lighton

unread,
Feb 19, 2001, 12:36:39 AM2/19/01
to
In article <3a8eaea7$0$62904$3c09...@news.plethora.net>,

Peter Seebach <se...@plethora.net> wrote:
>In article <GcHi6.442$9d.5...@newshog.newsread.com>,
>Julian Lighton <jl...@fragment.com> wrote:
>>Of course, object_flags() may be somewhat awkward to re-do in this
>>manner.
>
>It'll be marginally more expensive when you actually need all the flags,
>and somewhat cheaper in the most common cases, where you only use a few
>of them.

Though object_flags is hardly an efficiency bottleneck.

>>>After your change you'll get r_ptr->flags[1] & RF1_FOO. You have gained
>>>nothing and added an extra pair of brackets.
>
>>He's talking macros that hide the precise location of the flag from you.
>
>Yes. The code would be
> flag(r_ptr, RF_FOO);
>and no "RF1" or "RF2".
> #define flag(p, n) ((p)->flags[(n)/32] & (1 << ((n) % 32)))
>
>For extra credit, expand it to return 0 for n out of range.

I think an error would be preferred, if possible. (Though an error
that would work even if it's used with run-time-determined flags,
while not complicating things the rest of the time, would be beyond
me.)

>Now, I know *someone* will jump on me for the expensive math, but remember,
>RF_FOO is a *CONSTANT*. I doubt Angband targets a single compiler that
>won't fold this all up at compile time.

In the simple case, I suspect it won't be any performance difference.
(When you're checking multiple flags in the same word, I'd expect it
to depend on how smart the compiler is.)

The place I see it possibly hurting is choose_attack_spell(). (melee2.c)

While it's not the efficiency bottleneck of the view/lite code, or of
find_safety and find_hiding, it's called a lot, while the player is
waiting for a turn, and does huge amounts of bit-masking. It might
become noticable on slow machines, (like this Mac LC here) under
semi-degenerate conditions. (Lots of spellcasters.)

(Still, one could always get behind the protective macros, and do
old-fashioned bit-bashing on the array itself. I'm sure one could use
macros to create a constant array of bit-masks based on the RF_
values. If not, it could be initialized at game start-up.)

I have to wonder how easy it would be to do macro up more complicated
flag-mangling, though it's not like I've thought too hard about it.

Having actually gone through the source to add additional flag
variables, I can say that it's a royal pain.

(And, if we're at it anyway, why not split the monster flags into
flags and spell flags?)
--
Julian Lighton jl...@fragment.com
"Sleep my friend and you will see / That dream is my reality
They keep me locked up in this cage
Can't they see it's why my brain says rage?" -- Metallica

Hallvard B Furuseth

unread,
Feb 19, 2001, 1:59:38 PM2/19/01
to
se...@plethora.net (Peter Seebach) writes:

> #define flag(p, n) ((p)->flags[(n)/32] & (1 << ((n) % 32)))

Replace (1 << foo) with ((1U & 0xffffffffU) << foo).

'U' suffix to make it unsigned, &0xffffffffU to make the type big enough
for 32-bit math without using unnecessary 'long' (and slower) types.


> For extra credit, expand it to return 0 for n out of range. (Since range
> differs, you might want "rflag" and "oflag".

Or cruftify the new flag macros so that simple constants give
compile-time errors, and the flags used outside your macros do too (in
case the old bit-mask flags are used as arguments to the new macro, or
the new flags in code which expects bit-masks). E.g.:

#define clear_flag(var,flag) ((void) FLAG_OP(var, &=~ , flag))
#define FLAG_OP(var,op,flag) (var[FLAG_NUM flag / 32] op \
(1U & 0xffffffffU) << (FLAG_NUM flag % 32))

#define FLAG_NUM(num,dummy) num

#define RF_UNIQUE (0, Unique Monster)
...

Now 'flag & RF_UNIQUE' is definitely not going to compile...

--
Hallvard

Hallvard B Furuseth

unread,
Feb 19, 2001, 2:01:49 PM2/19/01
to
se...@plethora.net (Peter Seebach) writes:

> #define flag(p, n) ((p)->flags[(n)/32] & (1 << ((n) % 32)))

Replace (1 << foo) with ((1U & 0xffffffffU) << foo).

'U' suffix to make it unsigned, &0xffffffffU to make the type big enough
for 32-bit math without using unnecessary 'long' (and slower) types.

> For extra credit, expand it to return 0 for n out of range. (Since range
> differs, you might want "rflag" and "oflag".

Or cruftify the new flag macros so that simple constants give


compile-time errors, and the flags used outside your macros do too (in
case the old bit-mask flags are used as arguments to the new macro, or
the new flags in code which expects bit-masks). E.g.:

#define clear_flag(var,flag) ((void) FLAG_OP(var, &=~ , flag))
#define FLAG_OP(var,op,flag) (var[FLAG_NUM flag / 32] op \

((1U & 0xffffffffU) << (FLAG_NUM flag % 32)))

Julian Lighton

unread,
Feb 19, 2001, 10:04:42 PM2/19/01
to
In article <3A907F...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>Peter Seebach wrote:
>> >> You rarely do, but why should you need to know?
>>
>> >Why not know? You can use the extra information to your advantage...
>>
>> No, you can't. You can do things which, on a PDP-11 compiler, might
>> have produced a marginal benefit. It's not *useful* now.
>
>Really?
>
>I'd like to see a compiler convert
>for(i = 0; i < 96; i++)
>{
> if (mask[i] && flag_set(flag, i))
> {
> flag_on(flag, i);
> }
> else
> {
> flag_off(flag, i);
> }
>}
>
>
>into
>
>flag1 &= mask1;
>flag2 &= mask2;
>flag3 &= mask3;
>
>In my experience, compilers aren't that smart.

Yeah, but that's heavily pessimized code there. Somebody's got to
write code to let you mask the flag array, but there's no reason why
it can't be the person who wrote the rest of the flag-handling macros.

(I suppose that if you wanted to do something weird, you'd need to
crack open the internal data structures, but I don't think
bulk-masking is that weird.)

>> >Have a look at the AI code. It uses masking all over the place. The AI
>> >is a major bottleneck of the game.
>>
>> Okay. That's a good thing to look at. To what extent is it depending on
>> certain groups of bits all being in the same word?
>
>It doesn't depend on that.
>
>It depends on being fast.

How fast does the spell-choosing code need to be? I know I optimized
it when I was working on the AI stuff, but that was partly just to
make it cleaner. I don't remember it ranking that highly when I
profiled the old version. (But that was quite a while back, so I could
be forgetting.)
--
Julian Lighton jl...@fragment.com
"Don't try to reach me, 'cause I'd tear up your mind" -- Black Sabbath

Steven Fuerst

unread,
Feb 19, 2001, 10:20:24 PM2/19/01
to
Julian Lighton wrote:

> >It depends on being fast.
>
> How fast does the spell-choosing code need to be? I know I optimized
> it when I was working on the AI stuff, but that was partly just to
> make it cleaner. I don't remember it ranking that highly when I
> profiled the old version. (But that was quite a while back, so I could
> be forgetting.)

[Z] has pits/nests where all the monsters are of the same type. Try
walking next to a ring mimic pit (for example - a ring mimic is a
'typical' monster with lots of spells), with and without that speedup.
The old code was so slow that the game used to freeze in such situations
on my 486 75. The current code is much faster, so that other areas
become the bottleneck.

> --
> Julian Lighton jl...@fragment.com
> "Don't try to reach me, 'cause I'd tear up your mind" -- Black Sabbath

Steven

Julian Lighton

unread,
Feb 19, 2001, 10:34:07 PM2/19/01
to
In article <3A91E2...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>Julian Lighton wrote:
>
>> >It depends on being fast.
>>
>> How fast does the spell-choosing code need to be? I know I optimized
>> it when I was working on the AI stuff, but that was partly just to
>> make it cleaner. I don't remember it ranking that highly when I
>> profiled the old version. (But that was quite a while back, so I could
>> be forgetting.)
>
>[Z] has pits/nests where all the monsters are of the same type.

I know. Z pits (That's Zephyr hound, not Zangband) were what caused
me to optimize find_hiding().

>Try
>walking next to a ring mimic pit (for example - a ring mimic is a
>'typical' monster with lots of spells), with and without that speedup.
>The old code was so slow that the game used to freeze in such situations
>on my 486 75.

I don't want to think about it on this 68020 here, then.

> The current code is much faster, so that other areas
>become the bottleneck.

I think the main speedup comes from removing all the function calls
Keldon's code used. You've still got a loop through 96 spells. The
code you posted would add another one, true, but I don't know how much
it would hurt.

(Btw, having just looked at the code again for the first time in ages,
you can combine all three of those loops at the end into one. There's
no reason I can think of that the flags4 spells have to go in before
the flags5, etc. Don't know how I missed that the first time around.)
--
Julian Lighton jl...@fragment.com
"He got feet down below his knee
Hold you in his armchair you can feel his disease"
-- The Beatles

Peter Seebach

unread,
Feb 19, 2001, 10:52:43 PM2/19/01
to
In article <Hh2k6.267$Hg.4...@monger.newsread.com>,

Julian Lighton <jl...@fragment.com> wrote:
>> flag(r_ptr, RF_FOO);
>>and no "RF1" or "RF2".
>> #define flag(p, n) ((p)->flags[(n)/32] & (1 << ((n) % 32)))

>>For extra credit, expand it to return 0 for n out of range.

>I think an error would be preferred, if possible. (Though an error
>that would work even if it's used with run-time-determined flags,
>while not complicating things the rest of the time, would be beyond
>me.)

Can't Be Done. Actually, it sorta can, but not portably. ;) It's
certainly possible to generate an error in some cases...

>The place I see it possibly hurting is choose_attack_spell(). (melee2.c)

Hmm.

>While it's not the efficiency bottleneck of the view/lite code, or of
>find_safety and find_hiding, it's called a lot, while the player is
>waiting for a turn, and does huge amounts of bit-masking. It might
>become noticable on slow machines, (like this Mac LC here) under
>semi-degenerate conditions. (Lots of spellcasters.)

True... although that might be easily solved by a little caching.

>(And, if we're at it anyway, why not split the monster flags into
>flags and spell flags?)

This would actually solve the problem *better*, because one of the
most common masking things would no longer be a problem.

If you find yourself doing a lot of masks involving bunches of bits, that's
a sign that you may be storing two distinct things in one variable, and that's
never a good sign. :)

My thinking is:

Phase 1: Just turn everything into arrays.
Phase 2: Start using test/set macros instead of bit twiddling.
Phase 3: Remove the hints as to which word a flag is in, because
they're irrelevant in most cases.
Phase 4: Split words up if certain subsets need to be masked *often*.

Peter Seebach

unread,
Feb 19, 2001, 10:57:35 PM2/19/01
to
In article <HBF.200...@bombur.uio.no>,

Hallvard B Furuseth <h.b.fu...@usit.uio.no> wrote:
>se...@plethora.net (Peter Seebach) writes:
>> #define flag(p, n) ((p)->flags[(n)/32] & (1 << ((n) % 32)))

>Replace (1 << foo) with ((1U & 0xffffffffU) << foo).

Why not just 1UL? :)

>'U' suffix to make it unsigned, &0xffffffffU to make the type big enough
>for 32-bit math without using unnecessary 'long' (and slower) types.

That's a little crufty, but I guess it's probably correct.

>> For extra credit, expand it to return 0 for n out of range. (Since range
>> differs, you might want "rflag" and "oflag".

>Or cruftify the new flag macros so that simple constants give
>compile-time errors, and the flags used outside your macros do too (in
>case the old bit-mask flags are used as arguments to the new macro, or
>the new flags in code which expects bit-masks). E.g.:
>
>#define clear_flag(var,flag) ((void) FLAG_OP(var, &=~ , flag))
>#define FLAG_OP(var,op,flag) (var[FLAG_NUM flag / 32] op \
> ((1U & 0xffffffffU) << (FLAG_NUM flag % 32)))
>
>#define FLAG_NUM(num,dummy) num
>
>#define RF_UNIQUE (0, Unique Monster)
>...

>Now 'flag & RF_UNIQUE' is definitely not going to compile...

Hmm. That's outright Evil. Sorta clever, though.

Peter Seebach

unread,
Feb 19, 2001, 11:16:58 PM2/19/01
to
In article <3A907F...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>Peter Seebach wrote:
>> The compiler does it. Explicitly parallelizing code is just plain silly
>> on modern compilers.

>"The compiler does it." doesn't help me.

In practice, it certainly does.

You can't outperform a modern compiler *on multiple platforms*. Write the
code as legibly as possible, and don't try to tweak it unless you can show
that it's a bottleneck.

>Which particular code
>fragments does the compiler optimise to execute in that way?

That will depend on the compiler and the platform... but it does *now*,
and the *current* code is not necessarily run in parallel on any given
platform.

>In my
>experience, a human can quite often out-optimise a compiler by using
>different data structures. This particular instance comes under that
>case.

It may for a specific, single, processor/compiler combo. This is portable
code.

>I'd like to see a compiler convert
>for(i = 0; i < 96; i++)
>{
> if (mask[i] && flag_set(flag, i))
> {
> flag_on(flag, i);
> }
> else
> {
> flag_off(flag, i);
> }
>}

As long as the flag things are macros, this is pretty reasonable.

>In my experience, compilers aren't that smart.

They may not all be that smart... but keep in mind, the *flag* code is
certainly welcome to know about this kind of magic... It's just the
normal code which should be staying clear.

In other words, inside the flag code, if I want to do
flags_and(int *a, int *b, int MAX_FLAG)
I can do it, and it'll parallelize well, and modern compilers will
even inline it.

>> Okay. That's a good thing to look at. To what extent is it depending on
>> certain groups of bits all being in the same word?

>It doesn't depend on that.

>It depends on being fast.

I don't think discussion on this point is useful without profiling. The
lore is full of examples of very careful optimization effort which was
totally misplaced.

>Don't be silly. The "free flag" debates still need to look in defines.h
>in any case. In most cases there is no reason "why" something is in a
>particular flag - so there is no point arguing about that either.

There's good reasons to batch them, though, because you could potentially
replace a check of multiple separate words with a single op.

>I already have done this. There was a significant speedup when I
>converted the code from something that uses masks, to something that
>uses masks in parallel. You want to convert it to something that will
>only be serial...

Not really. If there's a regular need for masking one thing with another,
great, let's add a flag_and function to and sets of flags.

>> My guess is that there are a lot of other things that would go first;
>> for instance, if I wanted Angband to be fast, I'd calculate chances
>> "correctly" up front, rather than re-rolling until I got a result I liked
>> every time. That's an operation which has no upper bound on how long it
>> takes. :)

>Are you talking about the autoroller?

And object generation, and monster generation, and level generation...
the game is *FULL* of things which just try things at random, with equal
probability, and then reject results to create higher or lower probabilities.

>You might want to look at the
>formula used to work out the acceptance or rejection of a roll.
>Calculating the probability isn't trivial.

Not at all... but if we did that for a bunch of the common ops (item
generation, monster generation), we could probably improve performance
noticably. It's doable.

Julian Lighton

unread,
Feb 20, 2001, 12:34:25 AM2/20/01
to
In article <3a91ea0a$0$62903$3c09...@news.plethora.net>,

Peter Seebach <se...@plethora.net> wrote:
>In article <Hh2k6.267$Hg.4...@monger.newsread.com>,
>Julian Lighton <jl...@fragment.com> wrote:
>>While it's not the efficiency bottleneck of the view/lite code, or of
>>find_safety and find_hiding, it's called a lot, while the player is
>>waiting for a turn, and does huge amounts of bit-masking. It might
>>become noticable on slow machines, (like this Mac LC here) under
>>semi-degenerate conditions. (Lots of spellcasters.)
>
>True... although that might be easily solved by a little caching.

Situations where it would help are not really common enough to be worth
the effort.

>>(And, if we're at it anyway, why not split the monster flags into
>>flags and spell flags?)
>
>This would actually solve the problem *better*, because one of the
>most common masking things would no longer be a problem.

No, it wouldn't help. Monster spells are in RF[4-6], while other
flags are in RF[1-3]. I was just thinking that, if we're doing the
work anyway, it's be nice to have r_ptr->flags and r_ptr->spells,
instead of just r_ptr->flags.

The bit-masking is being done to remove various sets of spells from
consideration, and to determine of the monster has any spells in the
sets.


--
Julian Lighton jl...@fragment.com
"In the dark I have heard a calling / Broken wings that beg to fly
Is there time or is it too late / Is the cut flower no longer alive"
-- Savatage

Julian Lighton

unread,
Feb 20, 2001, 1:00:51 AM2/20/01
to
In article <3a91efba$0$62903$3c09...@news.plethora.net>,

Peter Seebach <se...@plethora.net> wrote:
>In article <3A907F...@physics.usyd.edu.au>,
>Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>>In my
>>experience, a human can quite often out-optimise a compiler by using
>>different data structures. This particular instance comes under that
>>case.
>
>It may for a specific, single, processor/compiler combo. This is portable
>code.

Still, it is possible for a human to do better, portable, optimization
than a compiler can. This is usually by throwing out bad
algorithms/data structures, and replacing them with better ones. (The
AI code of the past is a good example of this.)

The spell choice code would be slower with the code below instead of
the current stuff. How much slower, I can't say. (You'd probably
have to loop over the spell list twice, instead of once, but the
amount of work done within each iteration is fairly small.)

>>I'd like to see a compiler convert
>>for(i = 0; i < 96; i++)
>>{
>> if (mask[i] && flag_set(flag, i))
>> {
>> flag_on(flag, i);
>> }
>> else
>> {
>> flag_off(flag, i);
>> }
>>}
>
>As long as the flag things are macros, this is pretty reasonable.

Though it has to be done for seven different classes of spells. (Still
probably fairly negligable.)

>>In my experience, compilers aren't that smart.
>
>They may not all be that smart... but keep in mind, the *flag* code is
>certainly welcome to know about this kind of magic... It's just the
>normal code which should be staying clear.

Since the flag code can do the magic, behind the scene, the code will
probably end up doing about the same thing.

>>> Okay. That's a good thing to look at. To what extent is it depending on
>>> certain groups of bits all being in the same word?
>
>>It doesn't depend on that.
>
>>It depends on being fast.
>
>I don't think discussion on this point is useful without profiling. The
>lore is full of examples of very careful optimization effort which was
>totally misplaced.

The code in question is, I think, known to be a possible bottleneck,
even if only when you have a buttload of spellcasters in the vicinity.

>>> My guess is that there are a lot of other things that would go first;
>>> for instance, if I wanted Angband to be fast, I'd calculate chances
>>> "correctly" up front, rather than re-rolling until I got a result I liked
>>> every time. That's an operation which has no upper bound on how long it
>>> takes. :)
>
>>Are you talking about the autoroller?
>
>And object generation, and monster generation, and level generation...
>the game is *FULL* of things which just try things at random, with equal
>probability, and then reject results to create higher or lower probabilities.

Those are things that it's likely a waste of time optimizing.
Compared to the monster behavior code, they're never called at all.

(Of course, the light and view code is the real bottleneck, but Ben
seems to have done a pretty good optimization job there.)
--
Julian Lighton jl...@fragment.com
"I try never to get involved in my own life - too much trouble."
-- Babylon 5

Steven Fuerst

unread,
Feb 20, 2001, 1:10:19 AM2/20/01
to
Peter Seebach wrote:
>
> In article <3A907F...@physics.usyd.edu.au>,
> Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
> >Peter Seebach wrote:
> >> The compiler does it. Explicitly parallelizing code is just plain silly
> >> on modern compilers.
>
> >"The compiler does it." doesn't help me.
>
> In practice, it certainly does.
>
> You can't outperform a modern compiler *on multiple platforms*. Write the
> code as legibly as possible, and don't try to tweak it unless you can show
> that it's a bottleneck.

Wrong. "The best optimiser is between you ears" is a good piece of
advice. You can outperform any compiler by changing to a different
algorithm.

>
> >Which particular code
> >fragments does the compiler optimise to execute in that way?
>
> That will depend on the compiler and the platform... but it does *now*,
> and the *current* code is not necessarily run in parallel on any given
> platform.

Of course not. However, I can guarantee that it will be faster than the
other method if you use any normal sort of processor. You just need to
know what operations are usually fast, and which ones usually are not.

> >In my
> >experience, a human can quite often out-optimise a compiler by using
> >different data structures. This particular instance comes under that
> >case.
>
> It may for a specific, single, processor/compiler combo. This is portable
> code.

Nope, I think you've missed the point. Changing the algorithm to
something more efficient will beat the compiler hands down. You know
what the code *does*, rather than what it *is*. The compiler doesn't
know this. You can use the extra information to do things the compiler
cannot.

>
> >I'd like to see a compiler convert
> >for(i = 0; i < 96; i++)
> >{
> > if (mask[i] && flag_set(flag, i))
> > {
> > flag_on(flag, i);
> > }
> > else
> > {
> > flag_off(flag, i);
> > }
> >}
>
> As long as the flag things are macros, this is pretty reasonable.

Is a factor of ten in speed reasonable?

> >In my experience, compilers aren't that smart.
>
> They may not all be that smart... but keep in mind, the *flag* code is
> certainly welcome to know about this kind of magic... It's just the
> normal code which should be staying clear.

Of course it is... but then you've abstracted all the "magic" one step
away - something that is much more likely to create bugs. It really
looks like this "fix" actually makes the code more problematic than
before. Wasn't that something you were hoping to change?

>
> In other words, inside the flag code, if I want to do
> flags_and(int *a, int *b, int MAX_FLAG)
> I can do it, and it'll parallelize well, and modern compilers will
> even inline it.

Yep - the problem is in defining what *b is... things aren't quite as
easy as you think. I can't see a compiler optimising an array of bools
into a flag of bits anytime soon.

>
> >> Okay. That's a good thing to look at. To what extent is it depending on
> >> certain groups of bits all being in the same word?
>
> >It doesn't depend on that.
>
> >It depends on being fast.
>
> I don't think discussion on this point is useful without profiling. The
> lore is full of examples of very careful optimization effort which was
> totally misplaced.

Yep - Would you believe that I've profiled Zangband a huge number of
times, under many different conditions. I'm not lying when I say that
that particular function can be a bottleneck in the code.

>
> >Don't be silly. The "free flag" debates still need to look in defines.h
> >in any case. In most cases there is no reason "why" something is in a
> >particular flag - so there is no point arguing about that either.
>
> There's good reasons to batch them, though, because you could potentially
> replace a check of multiple separate words with a single op.

Yep. However, the replacement flags code cannot do this without major
hacks.

>
> >I already have done this. There was a significant speedup when I
> >converted the code from something that uses masks, to something that
> >uses masks in parallel. You want to convert it to something that will
> >only be serial...
>
> Not really. If there's a regular need for masking one thing with another,
> great, let's add a flag_and function to and sets of flags.

Why? Why should we need to in the first place? All you've done is
concentrate the ugliness in one spot. Moving the dirt around doesn't
get rid of it. Perhaps we can't get rid of it? So why bother changing
something that isn't broken?



> >> My guess is that there are a lot of other things that would go first;
> >> for instance, if I wanted Angband to be fast, I'd calculate chances
> >> "correctly" up front, rather than re-rolling until I got a result I liked
> >> every time. That's an operation which has no upper bound on how long it
> >> takes. :)
>
> >Are you talking about the autoroller?
>
> And object generation, and monster generation, and level generation...
> the game is *FULL* of things which just try things at random, with equal
> probability, and then reject results to create higher or lower probabilities.

Have a look at the code. It probably is designed to be at least as
smart as the algorithm you have thought of. The object and monster
generation functions are probably over-optimised if anything.

>
> >You might want to look at the
> >formula used to work out the acceptance or rejection of a roll.
> >Calculating the probability isn't trivial.
>
> Not at all... but if we did that for a bunch of the common ops (item
> generation, monster generation), we could probably improve performance
> noticably. It's doable.

And it's been done already, for quite some time now.

Steven

Hallvard B Furuseth

unread,
Feb 20, 2001, 1:35:01 AM2/20/01
to
se...@plethora.net (Peter Seebach) wrote:
>Hallvard B Furuseth <h.b.fu...@usit.uio.no> wrote:
>>
>> #define RF_UNIQUE (0, Unique Monster)
>>
>> Now 'flag & RF_UNIQUE' is definitely not going to compile...
>
> Hmm. That's outright Evil. Sorta clever, though.

Maybe
#define RF_UNIQUE (0, "Unique Monster")
makes you feel a little better. That still catches 'flag & RF_UNIQUE',
but not printf("%x", RF_UNIQUE).

--
Hallvard

Hallvard B Furuseth

unread,
Feb 20, 2001, 1:52:37 AM2/20/01
to
Steven Fuerst <sfu...@physics.usyd.edu.au> writes:
>>> for(i = 0; i < 96; i++)
>>> if (mask[i] && flag_set(flag, i))
>>> (...)

>>
>> As long as the flag things are macros, this is pretty reasonable.
>
> Is a factor of ten in speed reasonable?


Look, here is one way to avoid that loop (which should in any case have
looped over 3 array elements instead of 96 bits):

In defines.h, which knows which bits go in which flag number:
#define RF_HASTE_MASK 0, \
(flag_bit(RF_SLOW) | flag_bit(RF_HOLD)), \
flag_bit(RF_HASTE)


#define has_flag3(var, flag) has_var3_internal(var, flag)
#define has_var3_internal(var, mask1, mask2, mask3)\
(((var)[0] & (mask1)) || ((var)[1] & (mask2)) || ((var)[2] & mask3))

In melee2.c:
has_haste = has_flag3(flags, RF_HASTE_MASK);


Can you stop saying this has to be done with hyperslow loops now?

--
Hallvard

Werner Baer

unread,
Feb 20, 2001, 5:51:28 AM2/20/01
to

Julian Lighton <jl...@fragment.com> wrote in message
news:e9lk6.382$Hg.5...@monger.newsread.com...

> >> >Have a look at the AI code. It uses masking all over the place. The
AI
> >> >is a major bottleneck of the game.
> >>
> >> Okay. That's a good thing to look at. To what extent is it depending
on
> >> certain groups of bits all being in the same word?
> >
> >It doesn't depend on that.
> >
> >It depends on being fast.
>
> How fast does the spell-choosing code need to be? I know I optimized
> it when I was working on the AI stuff, but that was partly just to
> make it cleaner. I don't remember it ranking that highly when I
> profiled the old version. (But that was quite a while back, so I could
> be forgetting.)

Old versions were slow on a 486/33 pc.
Far from unplayable, but too slow to enjoy the game IMHO.
Except if you got near a single monster pit in [Z] with spellcasters.
IIRC about 0.2 to 0.5 seconds per turn.

Werner.


Werner Baer

unread,
Feb 20, 2001, 5:59:25 AM2/20/01
to

Peter Seebach <se...@plethora.net> wrote in message
news:3a91efba$0$62903$3c09...@news.plethora.net...

> And object generation, and monster generation, and level generation...
> the game is *FULL* of things which just try things at random, with equal
> probability, and then reject results to create higher or lower
probabilities.

Can you be more specific?
For example, the code is optimized in a way the there is
no need to reroll normal items/monsters.
(Instead of making a probability roll for an uncommon item,
and reroll if it fails, the item is rolled less often in the first place).

Werner.

Peter Seebach

unread,
Feb 20, 2001, 3:41:26 PM2/20/01
to
In article <Blnk6.415$Hg.5...@monger.newsread.com>,

Julian Lighton <jl...@fragment.com> wrote:
>The bit-masking is being done to remove various sets of spells from
>consideration, and to determine of the monster has any spells in the
>sets.

Okay, but that's easy to do reasonably efficiently.

I skimmed the "smart" code, and it would be pretty much exactly as
efficient using an array and a flag set function. Oh, wait; that's the
learning code. The "has_escape", etc., stuff seems to be fairly...

!!

Why are we calculating this stuff on the fly? This could be 8 bits of
flags set at the time when we parse r_info.txt. It can't change, ever.
A monster type that has_escape will *ALWAYS* have escape spells. Why
are we calculating these? We could calculate them up-front when reading
r_info, or just do it when we create the monster. Then we're *done*.

As to efficiency, all we need is a function, called once in the entire
life of the program, that looks something like
u32b escape_mask[6];
and then populate it. Once. After that, we can mask out behaviors for
given monsters when we create them, easily enough.

I think an extra byte per monster actually created is a fair tradeoff for
never having to do those calculations again.

Some of the code would be a lot simpler; for instance, the current three
for loops at the bottom would just be
for (i = SPELL_MIN; i < SPELL_MAX; ++i)
if (flags(r_ptr, i))
spells[num++] = i;

Peter Seebach

unread,
Feb 20, 2001, 3:42:58 PM2/20/01
to
In article <nKnk6.419$Hg.5...@monger.newsread.com>,

Julian Lighton <jl...@fragment.com> wrote:
>Still, it is possible for a human to do better, portable, optimization
>than a compiler can. This is usually by throwing out bad
>algorithms/data structures, and replacing them with better ones. (The
>AI code of the past is a good example of this.)

Algorithms, yes.

>The spell choice code would be slower with the code below instead of
>the current stuff. How much slower, I can't say. (You'd probably
>have to loop over the spell list twice, instead of once, but the
>amount of work done within each iteration is fairly small.)

I could make it dramatically faster than it is now, though, with very
little effort. We don't need to be checking whether a creature has escape
spells every time it tries to think; the spell list for a creature is static.

At that point, the cost of the *single* calculation of whether or not it
has_escape is trivial, and the masking function is pretty fast.

Peter Seebach

unread,
Feb 20, 2001, 3:50:23 PM2/20/01
to
In article <3A920A...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>Wrong. "The best optimiser is between you ears" is a good piece of
>advice. You can outperform any compiler by changing to a different
>algorithm.

Yes. It has become apparent to me that you weren't using "parallelize" the
way I thought you were. I thought you were talking about pipelines. :)

>Nope, I think you've missed the point. Changing the algorithm to
>something more efficient will beat the compiler hands down. You know
>what the code *does*, rather than what it *is*. The compiler doesn't
>know this. You can use the extra information to do things the compiler
>cannot.

Yeah, but if we wanted an efficient algorithm, we would set the flags for
monster capabilities in r_info[...], rather than calculating has_escape
every time. :)

>Is a factor of ten in speed reasonable?

Often, yes. Is this a known bottleneck? Why are we doing this masking
so often?

>Of course it is... but then you've abstracted all the "magic" one step
>away - something that is much more likely to create bugs. It really
>looks like this "fix" actually makes the code more problematic than
>before. Wasn't that something you were hoping to change?

Yes. However, I firmly believe that the code would be dramatically clearer
if the code didn't have to look at flag words separately, and just referred
to flag sets.

Note that it's quite easy to do
struct flags { int flags[3]; };

struct flags flag_and(struct flags a, struct flags b) {
struct flags t;
t.flags[0] = a.flags[0] & b.flags[0];
t.flags[1] = a.flags[1] & b.flags[1];
t.flags[2] = a.flags[2] & b.flags[2];
}

>Yep - the problem is in defining what *b is... things aren't quite as
>easy as you think. I can't see a compiler optimising an array of bools
>into a flag of bits anytime soon.

Yeah, but it can do very rational things with a pointer to some number of
words.

>Yep - Would you believe that I've profiled Zangband a huge number of
>times, under many different conditions. I'm not lying when I say that
>that particular function can be a bottleneck in the code.

Okay. Well, then let's fix it properly. Move the has_escape and such
calculations out entirely; they can never change for any given monster,
so we've immediately removed them. At this point, all we need is a handful
of flag objects (which may be more than a single word) with ESCAPE_MASK and
such in them, and a flag_and function, and we're done.

>> Not really. If there's a regular need for masking one thing with another,
>> great, let's add a flag_and function to and sets of flags.

>Why? Why should we need to in the first place?

So that adding the 97th spell doesn't require you to hunt down every piece
of code that looks at spells and add a fourth totally identical for loop
to it.

>All you've done is
>concentrate the ugliness in one spot. Moving the dirt around doesn't
>get rid of it. Perhaps we can't get rid of it? So why bother changing
>something that isn't broken?

Because it *is* broken. Why should the code to pick a spell be aware that
there are precisely three words which contain spells, no more, no less?
Why shouldn't it just know that there is a vector containing some number of
bits, and that there are operations on that vector?

Julian Lighton

unread,
Feb 20, 2001, 4:15:18 PM2/20/01
to
In article <3a92d6d2$0$62904$3c09...@news.plethora.net>,

Peter Seebach <se...@plethora.net> wrote:
>In article <nKnk6.419$Hg.5...@monger.newsread.com>,
>Julian Lighton <jl...@fragment.com> wrote:
>>The spell choice code would be slower with the code below instead of
>>the current stuff. How much slower, I can't say. (You'd probably
>>have to loop over the spell list twice, instead of once, but the
>>amount of work done within each iteration is fairly small.)
>
>I could make it dramatically faster than it is now, though, with very
>little effort. We don't need to be checking whether a creature has escape
>spells every time it tries to think; the spell list for a creature is static.

It isn't, actually. Before the game gets to choosing the type of
spell to use, it will eliminate spells that are known to be useless at
the moment, and this can change. (For instance, it won't summon if
nothing can appear. But if a space adjacent to you opens up, or you
move or are moved, it will be able to choose summons again.)

Now, a good case could be made for moving all of that within
choose_attack_spell, but it wouldn't change the problem.
--
Julian Lighton jl...@fragment.com
"You will know pain, and you will know fear, and then you will die.
Have a pleasant flight." -- Babylon 5

Steven Fuerst

unread,
Feb 20, 2001, 6:28:51 PM2/20/01
to

Sorry, I should have been more explicit. I'm not assuming that the
resulting compiled code is the same as that loop.

If the compiler is smart, it will unroll it. It will also get rid of
the redundant setting of flags to TRUE, that are already known to be
TRUE. If the compiler is really really smart, it would be able to
reverse the logic so that it is setting flags to FALSE. (There are
fewer of these - so less checks to do.)

This will improve the factor of 96 times slower to around about a factor
of ten. (Of course a real compiler isn't this smart...)

A compiler would never be able to change the code in such a way that the
resulting statements are equivalent to the three masked logical ands.
That was my point. You need to use the organic optimisor between your
ears to do that. ;-)

>
> --
> Hallvard

Steven

Steven Fuerst

unread,
Feb 20, 2001, 6:45:38 PM2/20/01
to
Peter Seebach wrote:
>
> In article <3A920A...@physics.usyd.edu.au>,
> Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
> >Wrong. "The best optimiser is between you ears" is a good piece of
> >advice. You can outperform any compiler by changing to a different
> >algorithm.
>
> Yes. It has become apparent to me that you weren't using "parallelize" the
> way I thought you were. I thought you were talking about pipelines. :)
>

Ah... that expains your argument somewhat. :-)

> >Nope, I think you've missed the point. Changing the algorithm to
> >something more efficient will beat the compiler hands down. You know
> >what the code *does*, rather than what it *is*. The compiler doesn't
> >know this. You can use the extra information to do things the compiler
> >cannot.
>
> Yeah, but if we wanted an efficient algorithm, we would set the flags for
> monster capabilities in r_info[...], rather than calculating has_escape
> every time. :)

Yep. Caching the results would help alot. I plan to do this soon, in a
general rewrite of the AI code in [Z].

>
> >Is a factor of ten in speed reasonable?
>
> Often, yes. Is this a known bottleneck?

Yep

> Why are we doing this masking
> so often?

Because the masks used depend on the state of the monster. A monster
with low hp will try to teleport away for example.

>
> >Of course it is... but then you've abstracted all the "magic" one step
> >away - something that is much more likely to create bugs. It really
> >looks like this "fix" actually makes the code more problematic than
> >before. Wasn't that something you were hoping to change?
>
> Yes. However, I firmly believe that the code would be dramatically clearer
> if the code didn't have to look at flag words separately, and just referred
> to flag sets.

I disagree. All you've done is move the complexity around.

<snip>

> >Yep - Would you believe that I've profiled Zangband a huge number of
> >times, under many different conditions. I'm not lying when I say that
> >that particular function can be a bottleneck in the code.
>
> Okay. Well, then let's fix it properly. Move the has_escape and such
> calculations out entirely; they can never change for any given monster,
> so we've immediately removed them.

Things like this will be done eventually. The reason they probably
haven't been done until now is savefile compatibility.

> At this point, all we need is a handful
> of flag objects (which may be more than a single word) with ESCAPE_MASK and
> such in them, and a flag_and function, and we're done.

No we aren't. Why not improve things while we are at it? Think about
what that step really does:

What you've "just done" is abstract away some information and make the
monster store it over time. You've just given the monster a "memory".
This concept of a "memory" can be used in lots of places... It allows
monsters to have behaviours, to remember where you were when you ducked
behind a pillar, it allows them to have "tasks" that they do while you
aren't in their immediate area...

>
> >> Not really. If there's a regular need for masking one thing with another,
> >> great, let's add a flag_and function to and sets of flags.
>
> >Why? Why should we need to in the first place?
>
> So that adding the 97th spell doesn't require you to hunt down every piece
> of code that looks at spells and add a fourth totally identical for loop
> to it.

rotfl.

Really now. I've modified data types all over the place. It really
isn't that hard to propagate the changes throughout the code. "Grep is
your friend". By your logic, the data structures are fixed in stone,
and can never be changed. This simply isn't the case. They should
change over time to fit your needs.

[Z] has a heap more monster flags than [V], and it wasn't very hard to
add the "extra" ones. If it is too hard for someone - then perhaps they
shouldn't be a maintainer, or at least leave that bit until they know
more about the game and C.

>
> >All you've done is
> >concentrate the ugliness in one spot. Moving the dirt around doesn't
> >get rid of it. Perhaps we can't get rid of it? So why bother changing
> >something that isn't broken?
>
> Because it *is* broken. Why should the code to pick a spell be aware that
> there are precisely three words which contain spells, no more, no less?

Because that is equivalent to knowing how many spells there are? If you
add a new spell it will never be as easy as simply incrementing a
counter. You need to fiddle with the AI to make monsters use the spell,
react to the spell and so on. Things are not so self-contained as you
would like, and they never will be. (Of course the game is not so
"messy" as Nethack is - but you need some degree of messiness to get the
job done.)

One other thing... there is no constraint at all keeping the code to use
only three words for the spell flags. Changing that to four would only
take about half an hour. A small job compared to the changes which have
taken days and weeks to do.

> Why shouldn't it just know that there is a vector containing some number of
> bits, and that there are operations on that vector?

Because you simply don't need to abstract the information away? The
code doesn't need to be afraid of itself.

Steven

Stig E. Sandoe

unread,
Feb 20, 2001, 7:41:36 PM2/20/01
to
Steven Fuerst <sfu...@physics.usyd.edu.au> writes:

> Peter Seebach wrote:

> > Yeah, but if we wanted an efficient algorithm, we would set the flags for
> > monster capabilities in r_info[...], rather than calculating has_escape
> > every time. :)
>
> Yep. Caching the results would help alot. I plan to do this soon,
> in a general rewrite of the AI code in [Z].

Any other changes than more efficient caching planned?
</interested>

--
------------------------------------------------------------------
Stig Erik Sandoe st...@ii.uib.no http://www.ii.uib.no/~stig/

Steven Fuerst

unread,
Feb 20, 2001, 7:33:34 PM2/20/01
to
Stig E. Sandoe wrote:
>
> Steven Fuerst <sfu...@physics.usyd.edu.au> writes:
>
> > Peter Seebach wrote:
>
> > > Yeah, but if we wanted an efficient algorithm, we would set the flags for
> > > monster capabilities in r_info[...], rather than calculating has_escape
> > > every time. :)
> >
> > Yep. Caching the results would help alot. I plan to do this soon,
> > in a general rewrite of the AI code in [Z].
>
> Any other changes than more efficient caching planned?
> </interested>

Interaction with the monster AI and fields will be needed before effects
like "wall of fire" are added.

The addition of a general monster "memories" will allow state-machine
like behaviours to be made. The addition of the "monster targetting"
patch is only a small part of this change.

I also have a list of a heap of abuses with regards to LOS, targetting,
interactions with doors, etc. and I'd like to fix them.

>
> --
> ------------------------------------------------------------------
> Stig Erik Sandoe st...@ii.uib.no http://www.ii.uib.no/~stig/

Steven

Stig E. Sandoe

unread,
Feb 20, 2001, 8:21:58 PM2/20/01
to
Steven Fuerst <sfu...@physics.usyd.edu.au> writes:

> Stig E. Sandoe wrote:
> >
> > Steven Fuerst <sfu...@physics.usyd.edu.au> writes:
> >
> > > Yep. Caching the results would help alot. I plan to do this
> > > soon, in a general rewrite of the AI code in [Z].
> >
> > Any other changes than more efficient caching planned?
> > </interested>
>
> Interaction with the monster AI and fields will be needed before
> effects like "wall of fire" are added.

Can you please elaborate?

> The addition of a general monster "memories" will allow state-machine
> like behaviours to be made. The addition of the "monster targetting"
> patch is only a small part of this change.

Monster 'memory' and the possibility of plans and communication
between monsters, e.g if an orc spots you he will tell his friends,
are important things to do to prevent players from winning. The
number of YAWP should be restricted to at most one pr six month for
each variant. ;-)

> I also have a list of a heap of abuses with regards to LOS,
> targetting, interactions with doors, etc. and I'd like to fix them.

will you add intelligent targetting, e.g breath/balls next to a char
when out-of-sight and/or to prevent the monster's friends from getting
hurt?

Steven Fuerst

unread,
Feb 20, 2001, 8:46:51 PM2/20/01
to
Stig E. Sandoe wrote:
>
> Steven Fuerst <sfu...@physics.usyd.edu.au> writes:
>
> > Stig E. Sandoe wrote:
> > >
> > > Steven Fuerst <sfu...@physics.usyd.edu.au> writes:
> > >
> > > > Yep. Caching the results would help alot. I plan to do this
> > > > soon, in a general rewrite of the AI code in [Z].
> > >
> > > Any other changes than more efficient caching planned?
> > > </interested>
> >
> > Interaction with the monster AI and fields will be needed before
> > effects like "wall of fire" are added.
>
> Can you please elaborate?

Right now, monsters completely ignore fields. Later, that must be
changed. Otherwise they will behave extremely stupidly against the new
spells being thought up by Topi.

>
> > The addition of a general monster "memories" will allow state-machine
> > like behaviours to be made. The addition of the "monster targetting"
> > patch is only a small part of this change.
>
> Monster 'memory' and the possibility of plans and communication
> between monsters, e.g if an orc spots you he will tell his friends,
> are important things to do to prevent players from winning.

I don't think I am going to add communication between monsters just yet.

> The
> number of YAWP should be restricted to at most one pr six month for
> each variant. ;-)

*grin*

>
> > I also have a list of a heap of abuses with regards to LOS,
> > targetting, interactions with doors, etc. and I'd like to fix them.
>
> will you add intelligent targetting, e.g breath/balls next to a char
> when out-of-sight

Yep - that is sometimes called the "monster targetting patch".

> and/or to prevent the monster's friends from getting
> hurt?

No - that is wrong. Monsters should choose to do something that doesn't
hurt their friends, rather than changing their attacks so they cannot
hurt their friends. Sometimes they just might want to hurt friends who
are now enemies... The second method prevents that.

>
> --
> ------------------------------------------------------------------
> Stig Erik Sandoe st...@ii.uib.no http://www.ii.uib.no/~stig/

Steven

Julian Lighton

unread,
Feb 20, 2001, 8:55:04 PM2/20/01
to
In article <3A920A...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>Peter Seebach wrote:
>> >I'd like to see a compiler convert
>> >for(i = 0; i < 96; i++)
>> >{
>> > if (mask[i] && flag_set(flag, i))
>> > {
>> > flag_on(flag, i);
>> > }
>> > else
>> > {
>> > flag_off(flag, i);
>> > }
>> >}
>>
>> As long as the flag things are macros, this is pretty reasonable.
>
>Is a factor of ten in speed reasonable?

Would this slow things down by a factor of ten? I tend to doubt it.
(Was the old code slower by a factor of ten? Maybe, but this would be
a lot faster, just by avoiding the function call overhead. We're
looking at half a dozen ifs and one bit-mask operation for each spell.)

>> >Don't be silly. The "free flag" debates still need to look in defines.h
>> >in any case. In most cases there is no reason "why" something is in a
>> >particular flag - so there is no point arguing about that either.
>>
>> There's good reasons to batch them, though, because you could potentially
>> replace a check of multiple separate words with a single op.
>
>Yep. However, the replacement flags code cannot do this without major
>hacks.

Minor hacks, at most. Mainly, we need a way to turn a human-readable
list of flags into an array of u32bs with the appropriate bits set.
(Which probably isn't beyond my capabilities, much less those of
somebody good.) Once you have one of those, more macros can be used
to and and or them together, and most of the masks can be generated at
compile-time.

>> >I already have done this. There was a significant speedup when I
>> >converted the code from something that uses masks, to something that
>> >uses masks in parallel. You want to convert it to something that will
>> >only be serial...
>>
>> Not really. If there's a regular need for masking one thing with another,
>> great, let's add a flag_and function to and sets of flags.
>
>Why? Why should we need to in the first place? All you've done is
>concentrate the ugliness in one spot. Moving the dirt around doesn't
>get rid of it. Perhaps we can't get rid of it? So why bother changing
>something that isn't broken?

Because, while it isn't broken, it is limiting. I have gone through
the code to add more flag space. It's a royal pain. Doing this
wouldn't be much harder, and would mean that nobody has to do it
again.

There are also certain things that become easier. Sangband has a
generic monster-detection function. The ability to pass in arbitrary
sets of flags would be possibly useful, (detect all non-invisible
animals, or detect all monsters that are male or that resist fire) but
mostly it's a bit silly to pass in a bitmask and a number telling the
code what set of flags to check. (The other option being to pass in
half-a-dozen bitmasks, which is sillier.)

--
Julian Lighton jl...@fragment.com
"Don't tell me now, that there is nothing more
There is a how, just like there is a door" -- Savatage

Peter Seebach

unread,
Feb 20, 2001, 9:13:55 PM2/20/01
to
In article <G7Bk6.486$Hg.6...@monger.newsread.com>,

Julian Lighton <jl...@fragment.com> wrote:
>It isn't, actually. Before the game gets to choosing the type of
>spell to use, it will eliminate spells that are known to be useless at
>the moment, and this can change. (For instance, it won't summon if
>nothing can appear. But if a space adjacent to you opens up, or you
>move or are moved, it will be able to choose summons again.)

Yes. But whether a creature *has* an attack spell, or a summoning spell,
is completely static, and if I'm reading choose_attack_spell correctly,
they are being calculated every time:

if (smart_monsters && !(r_ptr->flags2 & (RF2_STUPID)))
{
/* What have we got? */
has_escape = ((f4 & (RF4_ESCAPE_MASK)) ||
(f5 & (RF5_ESCAPE_MASK)) ||
(f6 & (RF6_ESCAPE_MASK)));

Why are we doing this every time any creature picks a spell? If we just
put some bits in the run-time representation of r_info, we could have all
of those calculations done already. That removes all of that code. Any
given value of r_ptr either has escape spells or doesn't. The 2000th
novice mage I kill will still have "blink away" the fifth time he gets to move
before I kill him.

Assume we've split out the spell flags (seems useful). Next, then, we do
stuff like the current
else if (has_heal && m_ptr->hp < m_ptr->maxhp / 4)
{
/* Choose heal spell */
f4_mask = (RF4_HEAL_MASK);
f5_mask = (RF5_HEAL_MASK);
f6_mask = (RF6_HEAL_MASK);
}
but we spell it
else if (r_ptr->has_heal && m_ptr->hp < m_ptr->maxhp / 4)
{
flag_and(spell_mask, heal_mask, NUM_SPELLS);
}

The difference is, if we add a 97th spell, or a 129th spell, the code
doesn't change; NUM_SPELLS changes, heal_mask and spells are larger,
but the code is the same.

Then, down at the bottom, instead of

/* Extract the "innate" spells */
for (i = 0; i < 32; i++)
{
if (f4 & (1L << i)) spells[num++] = i + RF4_OFFSET;
}

/* Extract the "normal" spells */
for (i = 0; i < 32; i++)
{
if (f5 & (1L << i)) spells[num++] = i + RF5_OFFSET;
}

/* Extract the "bizarre" spells */
for (i = 0; i < 32; i++)
{
if (f6 & (1L << i)) spells[num++] = i + RF6_OFFSET;
}

We just write
/* Extract spells */
for (i = 0; i < NUM_SPELLS; ++i)
{
if (flag(spell_mask, i))
spells[num++] = i;
}

I think that's substantially cleaner code. The masking is a little more
hidden, but I think it's at worst marginally more expensive... and it will
scale nicely if the set of spells changes.

Peter Seebach

unread,
Feb 20, 2001, 9:22:34 PM2/20/01
to
In article <3A9301...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>> Why are we doing this masking
>> so often?

>Because the masks used depend on the state of the monster. A monster
>with low hp will try to teleport away for example.

Okay, there's two separate sets.

One is the masking we do to find out what a monsters options *are*. That
doesn't need to be done all the time, and if we cache it, it gets a lot
cheaper.

The second is the masking from "what we have" down to "which options might
make sense". That has to happen every time, but a trivial mask function
can do it.

>> Yes. However, I firmly believe that the code would be dramatically clearer
>> if the code didn't have to look at flag words separately, and just referred
>> to flag sets.

>I disagree. All you've done is move the complexity around.

*Centralized* it. Which is easier to add a fourth flag word to:

1. A function that simply declares a number of words sufficient to hold
N bits, and masks that many words.
2. Twenty different instances of masking three specific words in order.

>Things like this will be done eventually. The reason they probably
>haven't been done until now is savefile compatibility.

Agreed, that's why I was thinking of patching it into the runtime r_info.

>> At this point, all we need is a handful
>> of flag objects (which may be more than a single word) with ESCAPE_MASK and
>> such in them, and a flag_and function, and we're done.

>No we aren't. Why not improve things while we are at it?

Not a bad idea.

>What you've "just done" is abstract away some information and make the
>monster store it over time. You've just given the monster a "memory".

Not really. I've just given the *game* some memory. We know that, for
novice mage, has_escape is true. It's always true. It will never not
be true. It doesn't need to be calculated.

>This concept of a "memory" can be used in lots of places... It allows
>monsters to have behaviours, to remember where you were when you ducked
>behind a pillar, it allows them to have "tasks" that they do while you
>aren't in their immediate area...

Yes, but that's a different project. I wasn't planning to store anything
per individual *creature*, just to remember that all of the creatures with
index N have the same set of spells.

>Really now. I've modified data types all over the place. It really
>isn't that hard to propagate the changes throughout the code. "Grep is
>your friend". By your logic, the data structures are fixed in stone,
>and can never be changed. This simply isn't the case. They should
>change over time to fit your needs.

Sure, but it should be less work. There's a *LOT* of places where we iterate
through the flag words manually. Those could all be automatic.

It makes it *less* work. It doesn't have to be a *lot* less work to be worth
it eventually...

>[Z] has a heap more monster flags than [V], and it wasn't very hard to
>add the "extra" ones. If it is too hard for someone - then perhaps they
>shouldn't be a maintainer, or at least leave that bit until they know
>more about the game and C.

Part of the point, as I see it, is to show them how properly maintained code
looks. Well-maintained code would have an array and iterate through it, not
N separate variables which you just have to always use together.

>> Because it *is* broken. Why should the code to pick a spell be aware that
>> there are precisely three words which contain spells, no more, no less?

>Because that is equivalent to knowing how many spells there are?

Why should the way I add a spell be pretty much the same for the 91st, 92nd,
93rd, 94th, 95th, and 96th spells, but radically different for the 97th?
Abstraction frees us from the piddly details. This is why we have compilers.

>If you
>add a new spell it will never be as easy as simply incrementing a
>counter. You need to fiddle with the AI to make monsters use the spell,
>react to the spell and so on.

I need to add it to, say, heal_mask, or escape_mask. Why should it be any
more work than that? (Oh, well, of course, I have to add it to a few
monsters.)

>One other thing... there is no constraint at all keeping the code to use
>only three words for the spell flags. Changing that to four would only
>take about half an hour. A small job compared to the changes which have
>taken days and weeks to do.

With the hypothetical changes in place, it would take *ZERO* minutes. It
would simply be a side-effect of having a 97th spell. (Of course, you'd
probably need to update save files, at that point. Eww.)

>> Why shouldn't it just know that there is a vector containing some number of
>> bits, and that there are operations on that vector?

>Because you simply don't need to abstract the information away? The
>code doesn't need to be afraid of itself.

Any simplification that isn't *stupidly* expensive in CPU time is probably
a win.

I don't think it's fair to characterize information hiding as a kind of
"fear". It's simply a good engineering practice. It reduces future work
by abstracting away things that aren't relevant to the task at hand.

Julian Lighton

unread,
Feb 20, 2001, 9:38:13 PM2/20/01
to
In article <3a932460$0$62904$3c09...@news.plethora.net>,

Peter Seebach <se...@plethora.net> wrote:
>In article <G7Bk6.486$Hg.6...@monger.newsread.com>,
>Julian Lighton <jl...@fragment.com> wrote:
>>It isn't, actually. Before the game gets to choosing the type of
>>spell to use, it will eliminate spells that are known to be useless at
>>the moment, and this can change. (For instance, it won't summon if
>>nothing can appear. But if a space adjacent to you opens up, or you
>>move or are moved, it will be able to choose summons again.)
>
>Yes. But whether a creature *has* an attack spell, or a summoning spell,
>is completely static, and if I'm reading choose_attack_spell correctly,
>they are being calculated every time:

That's because it isn't static.

/* Check whether summons and bolts are worth it. */


if (smart_monsters && !(r_ptr->flags2 & (RF2_STUPID)))
{

/* Check for a clean bolt shot */
if ((f4 & (RF4_BOLT_MASK) ||
f5 & (RF5_BOLT_MASK) ||
f6 & (RF6_BOLT_MASK)) &&
!clean_shot(m_ptr->fy, m_ptr->fx, py, px))
{
/* Remove spells that will only hurt friends */
f4 &= ~(RF4_BOLT_MASK);
f5 &= ~(RF5_BOLT_MASK);
f6 &= ~(RF6_BOLT_MASK);
}

/* Check for a possible summon */
if (!(summon_possible(py,px)))
{
/* Remove summoning spells */
f4 &= ~(RF4_SUMMON_MASK);
f5 &= ~(RF5_SUMMON_MASK);
f6 &= ~(RF6_SUMMON_MASK);
}

/* No spells left */
if (!f4 && !f5 && !f6) return (FALSE);
}
#endif /* MONSTER_AI */

[...]
/* Choose a spell to cast */
thrown_spell = choose_attack_spell(m_idx, f4, f5, f6);

(As I said, the elimination of spells should probably all be in
choose_attack_spell, (The perils of code that grows over time, with
multiple people working on it) but the list of spells the monster has
acailable to choose from can change from turn to turn.)


> if (smart_monsters && !(r_ptr->flags2 & (RF2_STUPID)))
> {
> /* What have we got? */
> has_escape = ((f4 & (RF4_ESCAPE_MASK)) ||
> (f5 & (RF5_ESCAPE_MASK)) ||
> (f6 & (RF6_ESCAPE_MASK)));
>
>Why are we doing this every time any creature picks a spell? If we just
>put some bits in the run-time representation of r_info, we could have all
>of those calculations done already. That removes all of that code. Any
>given value of r_ptr either has escape spells or doesn't. The 2000th
>novice mage I kill will still have "blink away" the fifth time he gets to move
>before I kill him.

Yeah, but the other critter whose escape spell is to teleport-level
you effectively doesn't have it anymore once he knows you have nexus
resistance.

>The difference is, if we add a 97th spell, or a 129th spell, the code
>doesn't change; NUM_SPELLS changes, heal_mask and spells are larger,
>but the code is the same.

I'm not the one arguing about that. :)


--
Julian Lighton jl...@fragment.com
"Some will die in hot pursuit, in fiery auto crashes
Some will die in hot pursuit, while sifting through my ashes"
-- Butthole Surfers

Julian Lighton

unread,
Feb 20, 2001, 10:02:20 PM2/20/01
to
In article <3A9301...@physics.usyd.edu.au>,
Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:

>Peter Seebach wrote:
>> Yeah, but if we wanted an efficient algorithm, we would set the flags for
>> monster capabilities in r_info[...], rather than calculating has_escape
>> every time. :)
>
>Yep. Caching the results would help alot. I plan to do this soon, in a
>general rewrite of the AI code in [Z].

Too many things can change on a turn-to-turn basis to make me think
that caching will be worth it.

>> Why are we doing this masking
>> so often?
>
>Because the masks used depend on the state of the monster. A monster
>with low hp will try to teleport away for example.

I think it's more that list being masked changes depending on the
state of the player and his surroundings, and what the monster knows
of the player. (And even the resistance-knowledge doesn't just turn
stuff off. For instance, known Chaos resist means that, half the
time, the critter won't consider breathing chaos. This is done by
masking out RF4_BR_CHAOS 50% of the time.)

>> >> Not really. If there's a regular need for masking one thing with another,
>> >> great, let's add a flag_and function to and sets of flags.
>>
>> >Why? Why should we need to in the first place?
>>
>> So that adding the 97th spell doesn't require you to hunt down every piece
>> of code that looks at spells and add a fourth totally identical for loop
>> to it.
>
>rotfl.
>
>Really now. I've modified data types all over the place. It really
>isn't that hard to propagate the changes throughout the code. "Grep is
>your friend". By your logic, the data structures are fixed in stone,
>and can never be changed. This simply isn't the case. They should
>change over time to fit your needs.
>
>[Z] has a heap more monster flags than [V], and it wasn't very hard to
>add the "extra" ones.

Does it have more possible flags, or just more flags in use? The
latter, I thought. Adding flags7 really is a nuisance.

>One other thing... there is no constraint at all keeping the code to use
>only three words for the spell flags. Changing that to four would only
>take about half an hour.

Maybe. IIRC, it was the object flags that were everywhere.


--
Julian Lighton jl...@fragment.com
"Can I play with madness?" -- Iron Maiden

Steven Fuerst

unread,
Feb 20, 2001, 10:03:48 PM2/20/01
to
Peter Seebach wrote:
>
> In article <3A9301...@physics.usyd.edu.au>,
> Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
> >> Why are we doing this masking
> >> so often?
>
> >Because the masks used depend on the state of the monster. A monster
> >with low hp will try to teleport away for example.
>
> Okay, there's two separate sets.
>
> One is the masking we do to find out what a monsters options *are*. That
> doesn't need to be done all the time, and if we cache it, it gets a lot
> cheaper.
>
> The second is the masking from "what we have" down to "which options might
> make sense". That has to happen every time, but a trivial mask function
> can do it.

And both set of operations are very fast in the current code. I doubt
looking up the result of of doing the masking operation is going to be
much faster than doing the masking operation using logical operators.
You save on memory as well.

See what I mean about unneeded complexity?

>
> >> Yes. However, I firmly believe that the code would be dramatically clearer
> >> if the code didn't have to look at flag words separately, and just referred
> >> to flag sets.
>
> >I disagree. All you've done is move the complexity around.
>
> *Centralized* it.

Same diff. Really now, all you've done is put the mess in one spot.
That doesn't make it look any less ugly.

> Which is easier to add a fourth flag word to:
>
> 1. A function that simply declares a number of words sufficient to hold
> N bits, and masks that many words.
> 2. Twenty different instances of masking three specific words in order.

2) is only marginally easier. The effort involved in either case is so
small that I don't know what you are complaining about.

>
> >Things like this will be done eventually. The reason they probably
> >haven't been done until now is savefile compatibility.
>
> Agreed, that's why I was thinking of patching it into the runtime r_info.

Bad idea... Think about this a little harder.

>
> >> At this point, all we need is a handful
> >> of flag objects (which may be more than a single word) with ESCAPE_MASK and
> >> such in them, and a flag_and function, and we're done.
>
> >No we aren't. Why not improve things while we are at it?
>
> Not a bad idea.
>
> >What you've "just done" is abstract away some information and make the
> >monster store it over time. You've just given the monster a "memory".
>
> Not really. I've just given the *game* some memory. We know that, for
> novice mage, has_escape is true. It's always true. It will never not
> be true. It doesn't need to be calculated.

That depends... Is it faster to use a cached result, or to calculate it
every time? Is the memory cost worth the extra speed? Things are not
quite so simple as you are saying.

> >This concept of a "memory" can be used in lots of places... It allows
> >monsters to have behaviours, to remember where you were when you ducked
> >behind a pillar, it allows them to have "tasks" that they do while you
> >aren't in their immediate area...
>
> Yes, but that's a different project. I wasn't planning to store anything
> per individual *creature*, just to remember that all of the creatures with
> index N have the same set of spells.

You are forgetting... the state of the creature is important. A monster
that is "losing" a battle will have a different set of spells readied,
than a monster that hasn't seen the player yet. You can use this
information to only change things as the monsters internal state
changes.

>
> >Really now. I've modified data types all over the place. It really
> >isn't that hard to propagate the changes throughout the code. "Grep is
> >your friend". By your logic, the data structures are fixed in stone,
> >and can never be changed. This simply isn't the case. They should
> >change over time to fit your needs.
>
> Sure, but it should be less work.

Less work than what? It isn't much work at all.

> There's a *LOT* of places where we iterate
> through the flag words manually.

Not really. I can only think of a few. Why don't you look at the code
before you start making silly statements like this. ;-)

> Those could all be automatic.

I don't understand. I s'pose you could make a generic function to do it
- but that wouldn't gain you much.



> It makes it *less* work. It doesn't have to be a *lot* less work to be worth
> it eventually...

Ask yourself this question: How often does the size of the flags in
words increase?

The correct answer is "not often at all".

Optimising for the rare case is silly. Why don't you pick on something
that changes all the time?



> >[Z] has a heap more monster flags than [V], and it wasn't very hard to
> >add the "extra" ones. If it is too hard for someone - then perhaps they
> >shouldn't be a maintainer, or at least leave that bit until they know
> >more about the game and C.
>
> Part of the point, as I see it, is to show them how properly maintained code
> looks. Well-maintained code would have an array and iterate through it, not
> N separate variables which you just have to always use together.

Says who? Well-maintained code can look like anything it wants to.

>
> >> Because it *is* broken. Why should the code to pick a spell be aware that
> >> there are precisely three words which contain spells, no more, no less?
>
> >Because that is equivalent to knowing how many spells there are?
>
> Why should the way I add a spell be pretty much the same for the 91st, 92nd,
> 93rd, 94th, 95th, and 96th spells, but radically different for the 97th?

Because optimisation often means that the codes response to changes
becomes quantised. This is perfectly normal. It means that the author
of the code has realised that a certain parameter doesn't need to range
over all the values that it normally would. This allows one to make
assumptions that would not otherwise hold - and thus to speed up things
in ways impossible for a compiler to do.

Think like a human - not a compiler, and you to can do this.

> Abstraction frees us from the piddly details. This is why we have compilers.

Wrong. Sometimes abstraction is a bad thing. You don't always have to
abstract away everything. The C++ approach is flawed IMHO. Sometimes
you just need to get into the dirt and play with the raw metal. Why
should we be prevented from doing that when it matters?

>
> >If you
> >add a new spell it will never be as easy as simply incrementing a
> >counter. You need to fiddle with the AI to make monsters use the spell,
> >react to the spell and so on.
>
> I need to add it to, say, heal_mask, or escape_mask. Why should it be any
> more work than that? (Oh, well, of course, I have to add it to a few
> monsters.)

Look harder... you've missed a few things. If that's all you do - then
the spell still doesn't do anything yet. The effort involved in
actually writing the spell far outshadows the effort in allowing it to
be used.

I've added new spells to the game. I know.

>
> >One other thing... there is no constraint at all keeping the code to use
> >only three words for the spell flags. Changing that to four would only
> >take about half an hour. A small job compared to the changes which have
> >taken days and weeks to do.
>
> With the hypothetical changes in place, it would take *ZERO* minutes. It
> would simply be a side-effect of having a 97th spell. (Of course, you'd
> probably need to update save files, at that point. Eww.)

You also need to edit the code the parses the info.txt files.
You also need to create the spells
You also need to add the spell to the monsters in r_info.txt
You also need to add the monster-player and monster-monster hooks for
the spell.

The time taken to fiddle with the flags is approximately 1-2 minutes.
(What is half an hour divided by 32) This is insignificant compared to
the couple of hours or so you need to write a new spell from scratch.


>
> >> Why shouldn't it just know that there is a vector containing some number of
> >> bits, and that there are operations on that vector?
>
> >Because you simply don't need to abstract the information away? The
> >code doesn't need to be afraid of itself.
>
> Any simplification that isn't *stupidly* expensive in CPU time is probably
> a win.

That's true in most cases. However, you need to be careful in code
bottlenecks. This is one such case where you need to be careful. Just
any-old-thing won't do here.

>
> I don't think it's fair to characterize information hiding as a kind of
> "fear". It's simply a good engineering practice. It reduces future work
> by abstracting away things that aren't relevant to the task at hand.

That is true in general. However, there are always exceptions to rules,
and this is one such exception.

You mean well - but I think your effort is misplaced.

Steven

Eric Bock

unread,
Feb 21, 2001, 1:50:19 AM2/21/01
to
The Angband Inquisition is investigating this, which Julian Lighton wrote on Wed, 21 Feb 2001 03:02:20 GMT:
> In article <3A9301...@physics.usyd.edu.au>,
> Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
> >Peter Seebach wrote:
> >> Yeah, but if we wanted an efficient algorithm, we would set the flags for
> >> monster capabilities in r_info[...], rather than calculating has_escape
> >> every time. :)
> >
> >Yep. Caching the results would help alot. I plan to do this soon, in a
> >general rewrite of the AI code in [Z].
>
> Too many things can change on a turn-to-turn basis to make me think
> that caching will be worth it.

I agree. Saving 'has_escape' just because some flags are never masked out
doesn't seem particularly useful when we still need to check whether the
other 'has_*' have changed. This amounts to a hack that just 'happens to
work' now, without gaining anything.

--
/* Eric */main(s,i,j,k,c){char*p=malloc(s=1),*a=p+(*p=i=j=k=0)/* Bock */
;while(~(*a=getchar())&&(++a-p<s||(a=(p=realloc(p,s+s))+s)&&(s+=s))||(*a
=0));for(a=malloc(s=1),*a=0;(c=p[i])&&(c=='+'&&++a[j]||c=='-'&&--a[j]||c
=='>'&&(++j<s||(a=realloc(a,s+s))&&memset(a+s,0,s)&&(s+=s))||c=='<'&&j--
||c=='.'&&~putchar(a[j])||c==','&&~(a[j]=getchar()))|!strchr("><.,",c);i
++)while((c=='['&&!a[j]||c==']'&&a[j])&&(k+=(p[i]=='[')-(p[i]==']'))&&p[
i+=c/* Brainf*** */=='[']&&(/* worse than */i-=c==']'/* this sig! */));}

Peter Seebach

unread,
Feb 21, 2001, 10:58:19 AM2/21/01
to
In article <pSFk6.571$9d.7...@newshog.newsread.com>,

Julian Lighton <jl...@fragment.com> wrote:
>>Yes. But whether a creature *has* an attack spell, or a summoning spell,
>>is completely static, and if I'm reading choose_attack_spell correctly,
>>they are being calculated every time:

>That's because it isn't static.

Oh, geeze. f4/f5/f6 are taken from r_info, then masked based on per-monster
stuff.

At that point, I think the correct thing to do is probably to add spell flags
to each monster, so that you can mask those out, and only calculate
has_escape, etc., *per monster*, when they change.

>(As I said, the elimination of spells should probably all be in
>choose_attack_spell, (The perils of code that grows over time, with
>multiple people working on it) but the list of spells the monster has
>acailable to choose from can change from turn to turn.)

Ugh. I see why the AI is so expensive. We could make it dramatically
faster by adding boatloads of cachable data...

>Yeah, but the other critter whose escape spell is to teleport-level
>you effectively doesn't have it anymore once he knows you have nexus
>resistance.

Okay. So, in that case, we should recalculate has_escape, etc., whenever
a spell is removed from the monster's personal list... but perhaps we should
keep that list around, rather than re-creating it every time we want to
cast a spell.

Peter Seebach

unread,
Feb 21, 2001, 11:01:41 AM2/21/01
to
In article <2yJk6.6768$ag1.7...@news.uswest.net>,

Eric Bock <eb...@uswest.net> wrote:
>I agree. Saving 'has_escape' just because some flags are never masked out
>doesn't seem particularly useful when we still need to check whether the
>other 'has_*' have changed. This amounts to a hack that just 'happens to
>work' now, without gaining anything.

Well, in the absence of the monster learning about resistances, they never
change. With that, though, it would arguably be useful to give each monster
a spell flags set, and mask things out when the monster realizes the player
has an immunity. Then we can just recalculate has_foo when the monster
learns that an option doesn't work. Some of them may not change.

Of course, it's still very expensive. And, for monsters that only have a
couple of spells, there's a lot of testing being done that isn't necessary.
A monster that has no fire spells never needs to know that the player has
fire resist.

So, I suppose one could do it the other way; calculate the monster's list
of spells, then remove the ones that don't apply. This would reduce the
number of "irrelevant" tests made. Maybe.

UGH.

Peter Seebach

unread,
Feb 21, 2001, 11:22:12 AM2/21/01
to
In article <3A9330...@physics.usyd.edu.au>,

Steven Fuerst <sfu...@physics.usyd.edu.au> wrote:
>And both set of operations are very fast in the current code. I doubt
>looking up the result of of doing the masking operation is going to be
>much faster than doing the masking operation using logical operators.

Fine; even then, changing from inline masks to a trivial function has very,
very, little cost.

>See what I mean about unneeded complexity?

The whole thing is unneeded complexity, we just haven't figured out how
it *should* work. It's clear that, in any case, we will end up doing
work we don't need to. For instance, every time any monster thinks about
spells, it calculates whether or not it can summon near the player. Whether
or not it has summon spells.

>> >I disagree. All you've done is move the complexity around.

>> *Centralized* it.

>Same diff. Really now, all you've done is put the mess in one spot.
>That doesn't make it look any less ugly.

It makes the code *as a whole* much less ugly, because information is
effectively hidden.

Complexity in one place is better than the same complexity in ten places.

>> 1. A function that simply declares a number of words sufficient to hold
>> N bits, and masks that many words.
>> 2. Twenty different instances of masking three specific words in order.

>2) is only marginally easier. The effort involved in either case is so
>small that I don't know what you are complaining about.

The mere fact that it's *not clean*. We shouldn't have thirty instances
of code that carefully does the same thing to each of three flag words,
when *conceptually*, it's just modifying "the set of flags".

>Bad idea... Think about this a little harder.

I hadn't realized that we had two or three different places where we start
making sets of masks. This code is *ugly* right now, although it's
probably fixable.

>> Not really. I've just given the *game* some memory. We know that, for
>> novice mage, has_escape is true. It's always true. It will never not
>> be true. It doesn't need to be calculated.

>That depends... Is it faster to use a cached result, or to calculate it
>every time?

Generally to use a cached result; there are very few systems on which
two logical ors (which have sequence points) and three bitwise or's are
faster than a single bitwise or.

>Is the memory cost worth the extra speed? Things are not
>quite so simple as you are saying.

True. But on the other hand, I guess... imagine, for a moment, that the
game *currently* used flags in a more opaque way, and that none of the code
knew (or cared) whether spell flags were 6 16-bit objects, or 3 32-bit
objects, or two 64-bit objects one of which was only half full.

Would anyone *WANT* to propogate explicit references to these words to all
the code?

>You are forgetting... the state of the creature is important. A monster
>that is "losing" a battle will have a different set of spells readied,
>than a monster that hasn't seen the player yet. You can use this
>information to only change things as the monsters internal state
>changes.

That calculation is mostly done after the original calculation of has_escape.
(Not entirely, but perhaps this, too, is a mistake.)

>Not really. I can only think of a few. Why don't you look at the code
>before you start making silly statements like this. ;-)

I have. Every time someone writes
f4 = (f4 & RF4_FOO_MASK);
f5 = (f5 & RF5_FOO_MASK);
f6 = (f6 & RF6_FOO_MASK);
we're iterating through the flags manually. Is it easy to update this
with cut and paste? Sure. Is it a sane use of time? Not really.

>I don't understand. I s'pose you could make a generic function to do it
>- but that wouldn't gain you much.

It would do one crucial thing: It would hide the number of flag words,
and eliminate all need for the *rest* of the code to know which flags
are in which words.

Right now, if you want to mask all the breaths, they're all in one word,
so you really only need to check one word... but if you want to do all
the fire attacks, you need to do two words. Summons are all in one word.
RF5 is full, though, so if you wanted to add a new ball, it would have
to go somewhere else... which means that, if someone used to have a BALL_MASK,
it would no longer work, and you'd need to create RF4_BALL_MASK.

In the "opaque" flags system, that doesn't happen.

>Ask yourself this question: How often does the size of the flags in
>words increase?

Not very. However, that could well be a result, in some part, of the
annoyance factor of doing it.

>Optimising for the rare case is silly. Why don't you pick on something
>that changes all the time?

For the same reason I did the spellbook hack. Because it's ugly code.

>> Part of the point, as I see it, is to show them how properly maintained code
>> looks. Well-maintained code would have an array and iterate through it, not
>> N separate variables which you just have to always use together.

>Says who? Well-maintained code can look like anything it wants to.

No. Well-maintained code avoids accumulated cruft, and having three separate
objects that are used in all cases as if they were an array is silly.

>Because optimisation often means that the codes response to changes
>becomes quantised.

That still doesn't change anything; the code using appropriate functions
and data hiding is within a couple percentage points either way of the
code unrolling everything.

>> Abstraction frees us from the piddly details. This is why we have compilers.

>Wrong. Sometimes abstraction i