SmaugMuds.org - Topic: SWR and Extended Bitvectors

SWR and Extended Bitvectors

nobody@example.com (Quixadhal) — Mon, 23 Nov 2009 11:36:58 PST

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.

[code]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,

SWR and Extended Bitvectors

nobody@example.com (David Haley) — Mon, 23 Nov 2009 02:29:26 PST

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.

SWR and Extended Bitvectors

nobody@example.com (Quixadhal) — Sun, 22 Nov 2009 20:09:37 PST

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

SWR and Extended Bitvectors

nobody@example.com (Samson) — Sun, 22 Nov 2009 15:44:51 PST

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.

SWR and Extended Bitvectors

nobody@example.com (Quixadhal) — Sun, 22 Nov 2009 14:10:30 PST

[url=http://www.cplusplus.com/reference/stl/bitset/]Hmmm...[/url]

[quote]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: [color=limegreen]each element occupies only one bit[/color] (which is eight times less than the smallest elemental type in C++: char).

Each element (each bit) can be accessed individually: for exa

SWR and Extended Bitvectors

nobody@example.com (Kayle) — Sun, 22 Nov 2009 04:28:52 PST

[quote=Samson]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 :)[/quote]

I just provided you with hard evidence...

SWR and Extended Bitvectors

nobody@example.com (David Haley) — Sun, 22 Nov 2009 02:26:21 PST

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.)

SWR and Extended Bitvectors

nobody@example.com (Quixadhal) — Sun, 22 Nov 2009 02:14:03 PST

[quote=Kayle]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.[/quote]
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

SWR and Extended Bitvectors

nobody@example.com (Samson) — Sat, 21 Nov 2009 21:50:25 PST

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 :)

SWR and Extended Bitvectors

nobody@example.com (Kayle) — Sat, 21 Nov 2009 21:15:53 PST

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