ace123 wrote:Sorry, I downloaded this patch to my desktop but never got around to applying it.
I'll commit it to SVN tonight
Great.
Did you want me to make the changes discussed below (implementing it as a class, and using Boost's dynamic_bitset class), or do you already have it half done?
ace123 wrote:I like most of it--specifically that you used an array. (though we may want to rethink that if we get more than 64k serials--I wouldn't want a 512MB array for serial numbers--switching to a 64-bit integer and assuming that they never wrap would be easier.
Yeah, good thought. Even if you never free serial numbers (
as is currently the case, so tracking their allocation is useless), you're unlikely to run out with 64bit. Note that in VS currently, nothing ever frees a serial number. I originally ran into problems (VS got stuck in an infinite loop) when it ran out of serial numbers after running for a long time and making several jumps between systems with lots of ships (in and around Sol). So this is currently a major problem, and nothing in my patch fixes it. I do provide a function that _can_ be called, but as I said, I didn't know where to put any calls to it, because there aren't any calls to usedSerial(n, false) anywhere
A bunch of new serial numbers are allocated when you jump, even to a system you've been to recently. AFAICT, one per ship in the system.
But I don't like that you rely on that non-constant initializer--who knows if that works in GCC3 or 2.95, or Visual C++, exactly how you want. However, I do see what you mean about not wanting this to be a lot of 0's in the executable file. I'm going to make a simple class whose constructor initializes all the elements of the array to make it more compatible unless you have another idea.
The non-constant initializer was sort of a hack job, yeah. The've been supported since before gcc3 IIRC, but the best thing would be to put a line of code somewhere to do the initialization in some other init function in the same file. (or in the constructor, of course. Then you can make the array part one of the class's private vars (along with the last offset history), instead of static, if you want to be able to use multiple objects to track allocations of different things. BTW, what compilers is VS supposed to be portable to? Obviously not just GNU.
As long as we don't have a non-zero constant initializer for a static array, it won't take up any space in the exe.
Then that class could also take care of bitmasking in its inline [] operator...
speaking of which, doesn't vector<bool> take care of this? I thought that was required to be implemented as a bitmap...
Wouldn't it be better to make a serial number allocator class, instead of just a bitmap class with an overloaded [] operator? Too many overloaded operators makes code hard to read. Esp. bitmaps apparently have nasty [] overloading semantics. They seem to need a proxy reference helper class, since they need to return a reference to a bit. Yuck.
I don't really know STL, but here's what I found out looking stuff up (mostly via references from
http://en.wikipedia.org/wiki/Bit_array): Boost has a find operator, but none of the STL stuff does. So you'd just have to loop over elements one at a time. If the first position you try is available, then it won't matter, but it's probably 64 times faster to test whole 64bit longs at a time than it is to loop over the bits. That is what makes my getUniqueSerial fast even if it has to search a decent fraction of the bitmap.
vector<bool> will be a bitmap when the compiler supports template partial specialization. (
http://www.sgi.com/tech/stl/bit_vector.html). There's also a bitset<N> class (
http://www.sgi.com/tech/stl/bitset.html), for bitsets of fixed length. It has more bit-op member functions, but its initializer is a single unsigned long, so I don't know if it's intended for use as a large bit array. bitset has a none() function, so you could use an array of bitset<64> efficiently, at least if the class doesn't have a lot of overhead. I wouldn't expect overhead; it doesn't have iterators or dynamic resizing or anything that would require storage except the bits themselves. So that would work. You'd still have to search in the bitset<64> for the first free element yourself, or call ffs(3) on bitset<64>.to_ulong(). ffs(3) is the only real portability problem in my code, and none of the STL classes solve that.
Ah, Boost has a dynamic_bitset class with a find_first(), and a even a find_next(size_type pos). So that would do the trick. It might even compile to something as efficient as my code, since it's a template, so the constant size can be evaluated at compile time.
http://www.boost.org/doc/libs/1_37_0/li ... itset.html And it has some comments about how nasty std:vector<bool> is, pretending to be a Container, when it's really not.... So since we have Boost anyway, this sounds like a good way to avoid ffs() portability problems. (It's only in POSIX-2001. and ffsl(3), which I actually use, is only a GNU extension.
)
EDIT: Damnit, I just realized that since the find functions only find set bits, we'd have to use 1 == free, and initialize the bitmap to (almost) all ones, not all zeros. This will probably waste some RAM that otherwise would never have been touched, since the bitmap probably won't end up perfectly page-aligned. Oh well, it's still small, so it's not slow to init with:
Code: Select all
boost::dynamic_bitset<> bmap(MAXSERIAL/2 + 1, SERVER?0:1);
bmap.flip();
EDIT2: Double damn, boost's find_next() function doesn't use anything like ffs(3). It uses a shift-and-test loop, i.e. Boost's integer_log2. Oh well, at least it will be efficient getting to the right unsigned long, which is what could potentially be very slow.
I wonder if gcc is smart enough to compile that shift&test loop to a bsf instruction... Nope, it isn't.
EDIT3: here's a Boost version of the functions, which does look nice, but isn't as efficent (code size or speed) as my plain C version. I'd rather keep my plain C version, but only if it's not too hard to detect if we need to provide our own ffsl(3) implementation on non-GNU platforms. I guess just #ifndef __GNUC__.
Code: Select all
#include <boost/dynamic_bitset.hpp>
// init the first ulong here, resize to fill with ones later.
static boost::dynamic_bitset<> usedSerials(sizeof(unsigned long)*CHAR_BIT, SERVER?~0UL:~1UL);
ObjSerial getUniqueSerial(void)
{
static int trynext = 0;
unsigned int ret;
ret = usedSerials.find_next(trynext);
if (usedSerials.npos == ret) ret = usedSerials.find_first(); // we don't have a find operator that starts in the middle and loops
if (usedSerials.npos == ret){
cerr<<"**** Bad problem: Ran out of unique object serial numbers; returning 0 ****"<<endl;
return 0;
}
trynext = (ret+1)%(MAXSERIAL/2 + 1);
usedSerials[ret] = 0;
if (SERVER) ret |= (MAXSERIAL/2 + 1); // set the high bit on server serials
return ret;
}
void freeSerial(ObjSerial s)
{
// discard the high bit regardless of previous setting. If we want to catch the server trying to free client serials, maybe just subtract instead.
/* if (SERVER) */ s &= ~(MAXSERIAL/2 + 1); // no harm in always masking off the high bit
usedSerials[s] = 1;
}
int main(void)
{
usedSerials.resize(MAXSERIAL/2 + 1, 1);
...
}
.
.
) I didn't put my name in a copyright anywhere, but obviously I'm putting this code under the GPL. share and enjoy.
. VS still runs normally with it, and I tested it with my main() function to make sure it still does what it's supposed to.