Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Vanilla

Reply
 
Thread Tools Display Modes
Old December 20, 2007, 19:26   #1
Bandobras
Knight
 
Join Date: Apr 2007
Posts: 725
Bandobras is on a distinguished road
Will we get rid of the 32 bit flag variables?

Here is another old rant of mine (from the same post as the one about indentation). Any news? I know it's not so essential for V, because it does not expand (so much), but since V is a base for variants...

Quote:
One more question --- was there any attempt to rewrite the ugly multiple 32 bit flag variables (bitfields) into some decent scheme, like packed bit arrays or even byte arrays or linked lists of flags, etc.? I mean, any attempt other than the new TOME engine. If not, why is it not the first priority of the V maintainer? (I know one answer --- because V does not need more flags.smile

Edit: I've found two implementations of bit vectors license-compatible with Angband: publib and libbit-vector-perl (which is a C library under the hood, despite the name). I guess linked lists would be much more efficient and understandable, but bit vectors will induce the least code changes (in particular, no problems with serialization).

Edit2: Here a relevant r.g.r.a thread: http://groups.google.pl/group/rec.ga...&lnk=ol&hl=en&
Several years later and several variants later people still expand the number of TR1_, TR2_, TR3_, ... bitfields by hand over and over again. BTW, one of the advocates of bit vectors in this thread was the current V mainanter, so there is still hope...
P.S. I have no clue which licence or which maintainer I had in mind...
Bandobras is offline   Reply With Quote
Old December 20, 2007, 22:25   #2
konijn_
Hellband maintainer
 
konijn_'s Avatar
 
Join Date: Jul 2007
Location: New York, the Big Apple
Age: 43
Posts: 367
Donated: $120
konijn_ is on a distinguished road
Quote:
Originally Posted by Bandobras View Post
Here is another old rant of mine (from the same post as the one about indentation). Any news? I know it's not so essential for V, because it does not expand (so much), but since V is a base for variants...

P.S. I have no clue which licence or which maintainer I had in mind...
I just dont know, there was stuff out there in 2001 that made the bitflags look saintly. So I am assuming that was really a pet peeve instead of a serious problem

I would say the number 1 issues for V are to have mouse-code and big screen for all platforms and small screen for portable devices and makefiles for RISC OS and makefiles that make nice OSX applications and makefiles that can create .deb files etc.

But that's me of course

Cheers,
T.
__________________
* Are you ready for something else ? Hellband 0.8.8 is out! *
konijn_ is offline   Reply With Quote
Old December 21, 2007, 01:13   #3
zaimoni
Knight
 
zaimoni's Avatar
 
Join Date: Apr 2007
Posts: 590
zaimoni is on a distinguished road
"Edit: ... I guess linked lists would be much more efficient and understandable, but bit vectors will induce the least code changes (in particular, no problems with serialization)."

In this particular application, linked lists are automatically bloated. (Generally, any of the one-datum one-node data structures are automatically bloated and should be avoided whenever either RAM efficiency or memory manager efficiency dominates other considerations. For V, it's RAM efficiency.)

Also: C vs. C++ makes a huge difference. Efficient bitvectors with the high-level flags proposed in the Google-indexed thread are much easier to do in C++.
zaimoni is offline   Reply With Quote
Old December 21, 2007, 06:54   #4
Bandobras
Knight
 
Join Date: Apr 2007
Posts: 725
Bandobras is on a distinguished road
Quote:
Originally Posted by konijn_ View Post
I just dont know, there was stuff out there in 2001 that made the bitflags look saintly. So I am assuming that was really a pet peeve instead of a serious problem
As a person that added a couple of stats, and so a few bits to the bitfields all around the code in a certain variant, I assure you this is a nightmare. And I didn't even have the ambition to add a whole new TR17_* bitfield, though the bits I added didn't quite fit in the old bitfields. That was just too horrible to attempt. (In the result a certain variant has rings of sustain two stats and mushrooms of restore two stats, because one bit had to be used for two stats in many cases --- which turned out a good game-play idea, surprisingly. ) Moreover, variants have different number of TR* bitfields which makes their code unnecessarily divergent even in places that don't use the new features.

Quote:
Originally Posted by zaimoni View Post
In this particular application, linked lists are automatically bloated.
This is not so automatic.

Quote:
Originally Posted by zaimoni View Post
(Generally, any of the one-datum one-node data structures are automatically bloated and should be avoided whenever either RAM efficiency or memory manager efficiency dominates other considerations. For V, it's RAM efficiency.)
In that case, lists may be better than bitvectors, because items and monsters usually have only a few of the tens or hundreds of flags, depending on variant. Then, for an average item, you have, say, one two-word list node with the only flag the item actually has. The alternative is a set of fixed 4- or 6- or 10-word long bitvectors with all but one flags at 0.

If the optional properties were integers instead of booleans, the lists would be unbeatable. But there are still only a few such properties, e.g. monster mana that many monsters just don't have.

Quote:
Also: C vs. C++ makes a huge difference. Efficient bitvectors with the high-level flags proposed in the Google-indexed thread are much easier to do in C++.
I think the main issue is ease of use. If we employ an external library, we don't even have to worry about details (until we try to port the library to some obscure mobile phone, that is...). I wonder if there are any simple tried solutions...
Bandobras is offline   Reply With Quote
Old December 21, 2007, 13:42   #5
konijn_
Hellband maintainer
 
konijn_'s Avatar
 
Join Date: Jul 2007
Location: New York, the Big Apple
Age: 43
Posts: 367
Donated: $120
konijn_ is on a distinguished road
Quote:
Originally Posted by Bandobras View Post
As a person that added a couple of stats, and so a few bits to the bitfields all around the code in a certain variant, I assure you this is a nightmare. And I didn't even have the ambition to add a whole new TR17_* bitfield, though the bits I added didn't quite fit in the old bitfields. That was just too horrible to attempt. (In the result a certain variant has rings of sustain two stats and mushrooms of restore two stats, because one bit had to be used for two stats in many cases --- which turned out a good game-play idea, surprisingly. ) Moreover, variants have different number of TR* bitfields which makes their code unnecessarily divergent even in places that don't use the new features.
Well, I added to a certain variant several bitfields and it worked out just great.

Cheers,
T.
__________________
* Are you ready for something else ? Hellband 0.8.8 is out! *
konijn_ is offline   Reply With Quote
Old December 21, 2007, 14:35   #6
Bandobras
Knight
 
Join Date: Apr 2007
Posts: 725
Bandobras is on a distinguished road
Well, everybody knows, primitive evil variants are easy to expand. ;P

Seriously, it may be easier with no 4GAI and no extended (pseudo-)ID logic. Or perhaps you are just a boy-genius with a nice IDE or 'grep' mastery. Or perhaps you are a variant maintainer, which means you keep the whole code in your head all time time, anyway. Me, I'm just a sidekick.

Last edited by Bandobras; December 21, 2007 at 17:27.
Bandobras is offline   Reply With Quote
Old December 21, 2007, 16:04   #7
zaimoni
Knight
 
zaimoni's Avatar
 
Join Date: Apr 2007
Posts: 590
zaimoni is on a distinguished road
Quote:
Originally Posted by Bandobras View Post
Seriously, it may be easier with no 4GAI and no extended (pseudo-)ID logic.
Let's not give me yet more excuses for reimplementing the 4GAI.
Quote:
Originally Posted by Bandobras View Post
Or perhaps you are just a boy-genius with a nice IDE or 'grep' mastery.
It would seem to me that average intellect is well up to

Code:
grep -n -F ____ > Test.txt
where ___ is any fixed-length string of exact case of interest.
zaimoni is offline   Reply With Quote
Old December 21, 2007, 16:31   #8
Bandobras
Knight
 
Join Date: Apr 2007
Posts: 725
Bandobras is on a distinguished road
Well,

Code:
grep -n -F "&f4" * > Test.txt
as in (but also in several other related functions' invocations)

Code:
/* Extract the flags */
object_flags(o_ptr, &f1, &f2, &f3, &f4);
produced 58 matches in the Un code and this is just a randomly chosen pattern of all those that have to be checked when adding f5... ;<
Bandobras is offline   Reply With Quote
Old December 21, 2007, 16:47   #9
zaimoni
Knight
 
zaimoni's Avatar
 
Join Date: Apr 2007
Posts: 590
zaimoni is on a distinguished road
Quote:
Originally Posted by Bandobras View Post
In that case, lists may be better than bitvectors, because items and monsters usually have only a few of the tens or hundreds of flags, depending on variant. Then, for an average item, you have, say, one two-word list node with the only flag the item actually has. The alternative is a set of fixed 4- or 6- or 10-word long bitvectors with all but one flags at 0.
This is truer for the savefile size than the in-memory size. Any moderately-full level's going to have enough nodes (about a thousand should be enough) to take minutes to load if those linked lists are ultimately malloc'd, even with a non-debugging memory manager. And if you're using an alternate method to allocate memory for the linked lists -- any "simplicity gains" are a mirage, even if they're wrapped in an external library.

With a linked list, the RAM cost per node includes
* at least one pointer to the next node [one for a singly-linked list]
* memory manager overhead for the node itself. I suspect the typical minimum is 8 bytes on a 32-bit pointer system with a traditional *NIX tree-indexed free memory heap and no automatic debugging checks. My reimplementation for Windows costs 16 bytes in overhead.

Using a C external library doesn't change any of this. And I don't see how a C external library can get you the efficient AND/OR testing of bitwise conditions.
Quote:
Originally Posted by Bandobras View Post
I think the main issue is ease of use.
Within C:
* Yes, tracking which flag goes with which bitmap bucket is a pain.
* The simplest way to handle that as a bitmap
** convert the bitmap flag holders to an array of uint32_t
** provide an alternate set of macros that doesn't have the TR mess, just the logical names
** tests then become (bitmap[FLAG/32] & (1<<(FLAG%32))), which a competent optimizing compiler should handle as efficiently as the current code.

Compile-time detecting when logical AND/OR tests can be merged is a bit trickier; we may have to retain the TR macros to support this transparently. The Boost preprocessor library wipes out at 256, which isn't really enough for all variants.
zaimoni is offline   Reply With Quote
Old December 21, 2007, 16:55   #10
zaimoni
Knight
 
zaimoni's Avatar
 
Join Date: Apr 2007
Posts: 590
zaimoni is on a distinguished road
Quote:
Originally Posted by zaimoni View Post
Within C:
* Yes, tracking which flag goes with which bitmap bucket is a pain.
* The simplest way to handle that as a bitmap
** convert the bitmap flag holders to an array of uint32_t
** provide an alternate set of macros that doesn't have the TR mess, just the logical names
** tests then become (bitmap[FLAG/32] & (1<<(FLAG%32))), which a competent optimizing compiler should handle as efficiently as the current code.

Compile-time detecting when logical AND/OR tests can be merged is a bit trickier; we may have to retain the TR macros to support this transparently. The Boost preprocessor library wipes out at 256, which isn't really enough for all variants.
Once V starts seeing SVN commits again, I'd be comfortable providing this patch (to see what it does to the source code readability).
zaimoni is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +1. The time now is 10:20.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, vBulletin Solutions Inc.