Login
User Name:

Password:



Register
Forgot your password?
Vote for Us!
 Couple bugs
Today, 5:42 pm
By Remcon
Bug in disarm( )
Nov 12, 2017, 6:54 pm
By GatewaySysop
Bug in will_fall( )
Oct 23, 2017, 1:35 am
By GatewaySysop
Bug in do_zap( ), do_brandish( )
Oct 18, 2017, 1:52 pm
By GatewaySysop
Bug in get_exp_worth( )
Oct 10, 2017, 1:26 am
By GatewaySysop
LOP 1.45
Author: Remcon
Submitted by: Remcon
LOP Heroes Edition
Author: Vladaar
Submitted by: Vladaar
Heroes sound extras
Author: Vladaar
Submitted by: Vladaar
6Dragons 4.3
Author: Vladaar
Submitted by: Vladaar
Memwatch
Author: Johan Lindh
Submitted by: Vladaar
Users Online
CommonCrawl, Yahoo!, Exalead, DotBot, Sogou, Yandex

Members: 0
Guests: 21
Stats
Files
Topics
Posts
Members
Newest Member
477
3,705
19,232
608
LAntorcha
Today's Birthdays
There are no member birthdays today.
Related Links
» SmaugMuds.org » Codebases » SWR FUSS » SWR and Extended Bitvectors
Forum Rules | Mark all | Recent Posts

SWR and Extended Bitvectors
< Newer Topic :: Older Topic >

Pages:<< prev 1, 2 next >>
Post is unread #21 Sep 28, 2009, 2:11 pm
Go to the top of the page
Go to the bottom of the page

Keirath
Magician
GroupMembers
Posts144
JoinedJan 24, 2008

Alright thats what I needed to know. I'm looking into using the std::bitset but it'll take some studying. For nwo I have everything as extended, and to be honest I doubt I'd have over 128 bits to begin with.
       
Post is unread #22 Oct 3, 2009, 7:40 am
Go to the top of the page
Go to the bottom of the page

Andril
Magician
GroupMembers
Posts147
JoinedJun 9, 2009

One thing I forgot to mention before was that, if you ever do decide to go with std::bitset, besides the fact that it's part of the STL, which means C++, you need to include the bitset header. Oops.
       
Post is unread #23 Nov 21, 2009, 11:24 am
Go to the top of the page
Go to the bottom of the page

Keirath
Magician
GroupMembers
Posts144
JoinedJan 24, 2008

Alright, so is this something that we want to do for the FUSS project itself?

I really am clueless when it comes to std::bitset but I definitely like the idea of encaspulation.

I need to learn C++. Any good books I can take a look at or anything like that?
       
Post is unread #24 Nov 21, 2009, 5:24 pm
Go to the top of the page
Go to the bottom of the page

Kayle
Off the Edge of the Map
GroupAdministrators
Posts1,195
JoinedMar 21, 2006

Books, there are plenty. There was a thread on MudBytes not long ago about books on C++ I believe it was on the C/C++ Board there.

As for whether this is something that we want to do for the project itself, Yet to be seen. I'm still reviewing my own implementation and there seem to be certain drawbacks to using std::bitset. A rather large memory footprint being one of them.
       
Post is unread #25 Nov 21, 2009, 6:39 pm
Go to the top of the page
Go to the bottom of the page

Samson
Black Hand
GroupAdministrators
Posts3,639
JoinedJan 1, 2002

I have a feeling that large memory footprint has more to do with the STL and C++ binaries in general than it does specifically with std::bitset. I saw memory size increase by quite a bit before ever getting to the bitset stage of AFKMud's conversion.
       
Post is unread #26 Nov 21, 2009, 7:14 pm
Go to the top of the page
Go to the bottom of the page

Caius
Magician
GroupMembers
Posts132
JoinedJan 29, 2006

The thing about bit_set is that it is a template class parameterized by its size. This means that if you have one bit_set with 32 elements, and one with 48 elements, these are two completely unrelated classes, each producing additional code. So if all your bit_sets are of equal size, then your compiler produces less code.
       
Post is unread #27 Nov 21, 2009, 8:47 pm
Go to the top of the page
Go to the bottom of the page

Quixadhal
Conjurer
GroupMembers
Posts398
JoinedMar 8, 2005

Personally, I'd like to see SmaugFUSS start down the full C++ conversion road. Not only is memory use not such a big concern these days, but C itself is a dinosaur that's mostly relegated to maintenance code. Even drivers seem to be written in C++ now.

Besides, I hate char *'s. :evil:
       
Post is unread #28 Nov 21, 2009, 9:15 pm
Go to the top of the page
Go to the bottom of the page

Kayle
Off the Edge of the Map
GroupAdministrators
Posts1,195
JoinedMar 21, 2006

The memory footprint nearly doubles because XBVs are integers, and bitsets use bools.

signed integer = 4 bytes
boolean = 1 byte
32 boolean flags = 32 bytes
32 toggled bitvector = 4 bytes.
XBVs are nearly 2.5x faster in testing as well (0.27s in comparison to 0.67s).

The only disadvantage is that XBVs can't dynamically resize themselves. If I want 256 flags with an XBV all I do is change the 4 to an 8 and max_bit to 256.

256 booleans is 256 bytes...


Now, while I agree that I'd like to see the project move toward a full C++ conversion, I doubt it's worth the effort given the fundamental flaws in the core design, like those encountered with the proposed Affects revision.
       
Post is unread #29 Nov 21, 2009, 9:50 pm
Go to the top of the page
Go to the bottom of the page

Samson
Black Hand
GroupAdministrators
Posts3,639
JoinedJan 1, 2002

I'd have to agree that doing a full blown conversion of the existing base would be a pain in the ass. It seems far more useful in that case to just write an entirely new codebase and make it emulate Smaug's feature set.

As far as the memory footprint, I don't have any hard data on that one way or the other but I doubt very much that adding std::bitset to all the fields that use it doubled the memory footprint of the entire codebase. I think I would have noticed something like that :)
       
Post is unread #30 Nov 22, 2009, 2:14 am
Go to the top of the page
Go to the bottom of the page

Quixadhal
Conjurer
GroupMembers
Posts398
JoinedMar 8, 2005

Kayle said:

The only disadvantage is that XBVs can't dynamically resize themselves. If I want 256 flags with an XBV all I do is change the 4 to an 8 and max_bit to 256.

Be aware that as more and more people start using 64-bit hardware, you have to change the macro formulas to recognize which you're on, otherwise you're wasting 32-bits of every element in your XBV array (at best), or introducing weird errors if anyone actually does a bit rotate or shift.

I still don't understand why nobody ever used bitfields. It's a C contruct that's effectively a structure with bits encoded as individual fields based on how many you assign to them.

struct flags {
  unsigned Dark : 1;
  unsigned Indoors: 1;
  unsigned Terrain: 3; /* allowing 8 types of terrain */
};


You can have any number of them... the only caveat is that the C standard doesn't guarentee in-memory ordering, so if you used binary data files, you might not be cross-platform... but you probably wouldn't be anyways.
       
Post is unread #31 Nov 22, 2009, 2:26 am
Go to the top of the page
Go to the bottom of the page

David Haley
Sorcerer
GroupMembers
Posts903
JoinedJan 29, 2007

The bitset I published to MB is very memory efficient -- it uses actual bits, not bools -- if people care about such things. I have a C++ version of the interface lying around. It also isn't templatized, so there is no code duplication, although I suspect that code duplication isn't the memory problem that people are complaining about.

(I'm a little surprised at the claim that the std::bitset doesn't use bits, by the way. But go figure.)
       
Post is unread #32 Nov 22, 2009, 4:28 am
Go to the top of the page
Go to the bottom of the page

Kayle
Off the Edge of the Map
GroupAdministrators
Posts1,195
JoinedMar 21, 2006


Samson said:

As far as the memory footprint, I don't have any hard data on that one way or the other but I doubt very much that adding std::bitset to all the fields that use it doubled the memory footprint of the entire codebase. I think I would have noticed something like that :)


I just provided you with hard evidence...
       
Post is unread #33 Nov 22, 2009, 2:10 pm   Last edited Nov 22, 2009, 2:40 pm by Quixadhal
Go to the top of the page
Go to the bottom of the page

Quixadhal
Conjurer
GroupMembers
Posts398
JoinedMar 8, 2005

Hmmm...

A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1, true or false, ...).

The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).

Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.

Because no such small elemental type exists in most C++ environments, the individual elements are accessed as special references which mimic bool elements:


Sooooo, anyone tested this? I find it hard to believe that GNU's C++ compiler wouldn't implement this, and also hard to believe the site would be flat-out wrong.

EDIT: Ok, quick test:

quixadhal@andropov:~$ cat bittest.cpp
#include <iostream>
#include <bitset>
#include <string>

using namespace std;

class foo {
  public:
    bitset<13> chunk;
    string stuff;
};

int main(int argc, char **argv) {

  class foo f;

  cout << "sizeof(f): " << sizeof(f) << endl;
  f.chunk[3] = true;
  cout << "sizeof(f): " << sizeof(f) << endl;
  f.chunk[5] = true;
  cout << "sizeof(f): " << sizeof(f) << endl;
  f.stuff = f.chunk.to_string<char,char_traits<char>,allocator<char> >();
  cout << "sizeof(f): " << sizeof(f) << endl;
  cout << "f.stuff: " << f.stuff << endl;
}
quixadhal@andropov:~$ !g++
g++ -o bittest bittest.cpp
quixadhal@andropov:~$ ./bittest
sizeof(f): 8
sizeof(f): 8
sizeof(f): 8
sizeof(f): 8
f.stuff: 0000000101000


Change the number of bits from 13 to 113 and....

quixadhal@andropov:~$ g++ -o bittest bittest.cpp
quixadhal@andropov:~$ ./bittest
sizeof(f): 20
sizeof(f): 20
sizeof(f): 20
sizeof(f): 20
f.stuff: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101000


So, not 100% compact to the individual bit, but close to the machine word boundary? 113/8 would be 15 bytes... so we used 16 bytes + 4 for the string pointer. Testing with a value of 1024 yields 132 bytes used.
       
Post is unread #34 Nov 22, 2009, 3:44 pm
Go to the top of the page
Go to the bottom of the page

Samson
Black Hand
GroupAdministrators
Posts3,639
JoinedJan 1, 2002

Well that's more or less in line with what I figured. However, both of your tests were on std::bitset. Kayle is saying switching everything in Smaug from XBV/BV to std::bitset doubles the memory footprint of the entire codebase. I cannot see any possible way this would happen just because it's including all the STL associated with it and the memory footprint on AFKMud certainly didn't jump from 30MB to 60MB which is what it should have done if std::bitset usage doubles the memory footprint.
       
Post is unread #35 Nov 22, 2009, 8:09 pm
Go to the top of the page
Go to the bottom of the page

Quixadhal
Conjurer
GroupMembers
Posts398
JoinedMar 8, 2005

Kayle's argument was based on the assumption that std::bitset used "bool" as the storage type. According to the documentation, and the tests I ran, that cannot be true, at least not using gcc 4.1.2 under Debian linux on a 32-bit platform. Clearly it is packing bits, otherwise my use of 113 bits would have caused the storage to be at least 113 bytes, and as shown, it was only using 20 bytes for the entire structure.

Now, it certainly IS possible that you'd see memory use go from 5 bytes to 8 bytes, if you were using say 40 bits. I could see the XBV system allocating 5 unsigned char's instead of the 2 unsigned int's bitset would use. In that case, it would seem to double... but if you were using 129 bits, it would only be inflated from 17 bytes to 20 bytes.
       
Post is unread #36 Nov 23, 2009, 2:29 am
Go to the top of the page
Go to the bottom of the page

David Haley
Sorcerer
GroupMembers
Posts903
JoinedJan 29, 2007

Your test isn't conclusive, Quix, as it assumes that all bitset storage is allocated internally and not on the heap. Now, that said, given the memory usage increase, it seems extremely likely that the bitset isn't using the heap, but you'd have to look at its .h file entry to be sure of its implementation.
       
Post is unread #37 Nov 23, 2009, 11:36 am
Go to the top of the page
Go to the bottom of the page

Quixadhal
Conjurer
GroupMembers
Posts398
JoinedMar 8, 2005

True enough. Although I wouldn't expect it to use the heap, since the size of the bitset is determined at compile-time and isn't alterable. Now, a vector, on the other hand... that probably would be heap allocated.

quixadhal@andropov:~$ valgrind ./bittest
==14235== Memcheck, a memory error detector.
==14235== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al.
==14235== Using LibVEX rev 1658, a library for dynamic binary translation.
==14235== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP.
==14235== Using valgrind-3.2.1-Debian, a dynamic binary instrumentation framework.
==14235== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al.
==14235== For more details, rerun with: -v
==14235==
sizeof(f): 20
sizeof(f): 20
sizeof(f): 20
sizeof(f): 20
f.stuff: 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101000
==14235==
==14235== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 17 from 1)
==14235== malloc/free: in use at exit: 0 bytes in 0 blocks.
==14235== malloc/free: 2 allocs, 2 frees, 252 bytes allocated.
==14235== For counts of detected errors, rerun with: -v
==14235== All heap blocks were freed -- no leaks are possible.


I would guess the 252 bytes are 2 copies of the string representation of the bitset. One as it was generated and put in f.stuff, one as it was copied into the cout stream? Just guessing there though....
       
Pages:<< prev 1, 2 next >>