Using bitwise operations for boolean checks

[OneManClan]

Hi all,

I'm doing a bit of 'code housekeeping', and noticed that there are at least 15 .float variables in defs which are only used to do boolean, (ie ON/OFF) checks, eg:

Code: Select all

.float       is_removed;         // TRUE if the entity has been removed
.float      is_undercover;      // TRUE for a SPY if they're undercover
.float      is_building;       // TRUE for an ENGINEER if they're building something
.float      is_detpacking;       // TRUE for a DEMOMAN if they're setting a detpack
.float      is_feigning;      // TRUE for a SPY if they're feigning death


Elsewhere in the QuakeC (eg weapons.qc), bitwise checks are done for such situations, where something is either TRUE or FALSE. Is there any reason why the (original CustomTF) programmers would have programmed it this way? Should I rewrite the code so that ONE (32 bit) .float variable stores a whole bunch of these values, and use bitwise operations to check ON/OFF states instead?

1. "YES"
Wasting a whole .float just for a TRUE/FALSE setting is silly. Use one .float for 32(?) of them. The code will run faster, because .float's take up heaps of memory, and checking the individual bits in one .field variable is a significantly faster (and overall smarter) way to do boolean stuff.

or:

2. "NO"
This is pointless nitpicking, a waste of time, and won't really make that much difference; 15 (or so) .float variables aren't such a big deal, besides, those who came before you must have had a reason to do it that way, so DON'T question the Gurus. Besides, the mod now runs on FTE which can handle (almost) anything you throw at it. Leave it be.

Yes or No?

thanks,


OneManClan

[andrewj]

NO
This is pointless nitpicking, a waste of time, and won't really make that much difference

That.

It would save a bit of memory, but I doubt it will be any faster (it could even be slower due to extra bitmask operations).

[OneManClan]

NO
This is pointless nitpicking, a waste of time, and won't really make that much difference

That.

It would save a bit of memory, but I doubt it will be any faster (it could even be slower due to extra bitmask operations).

Really? I was under the impression that:

Code: Select all

if (self.has_foo == 1){};

is not as fast as:

Code: Select all

if (self.current_state & #HAS_FOO) {};

[Note: I realise this is probably nitpicking, I'm just curious as to what the Gurus consider 'best practice' for Quake C coding]

[Spike]

on an x86 chip, with everything else equal...

first form:
cmp $1,%somereg

second form:
tst $HAS_FOO,%somereg

The rest is identical.
Logically, tst is a simpler operation, but both are highly optimised and you'll not measure a difference.


However, this is not native code. This is QuakeC which is run through a VM, with the datatypes as floats.

In qc bytecode:
first form:
OP_LOAD_F self, has_foo, tmp
OP_EQ_F tmp, $1, tmp2
OP_IFNOT tmp2, endofblock

second form:
OP_LOAD_F self, current_state, tmp
OP_BITAND tmp, $HAS_FOO, tmp2
OP_IFNOT tmp2, endofblock

The first form keeps everything as floats. There are no conversions (supposedly).
The second form converts both arguments to the OP_BITAND instruction to ints, does the bitwise and, converts back to float. Conversions of float->int are generally slow on x86, as it typically requires using an entire subroutine to do it.
Conversely, OP_EQ_F will likely contain a small true/false branch in order to store either true or false. This will always be faster than the two subroutines invoked by OP_BITAND.
So the first form is faster, always, on x86.

Of course, the first form could be written without the == 1, which would be effectively != 0.
If there is no explicit comparison then the qcc can save an instruction, thus:
OP_LOAD_F self, current_state, tmp
OP_IFNOT tmp, endofblock
There's no way to optimise it beyond that, other than by reusing 'tmp'.


Memory wise:
An extra field will consume 4 bytes for every entity which is instanciated. Memory is in abundance nowadays anyway. So 2k for a server with 512 ents (original quakeworld protocol max). Its not really a problem on any modern computer.


Summary:
The fastest, and smallest, way to check a field is
if (self.field) {}
The second fastest way is:
if (self.field == 1) {}
The slowest way is:
if (self.field & BIT) {}

But really it doesn't matter. Use whatever is the most maintainable for you.

[mh]

"Using less memory" != "always faster". An extremely rough generalization could be that it's not how much memory you use, it's how you use it.

As always, profile your code, determine where your bottlenecks are, and tackle those bottlenecks. Don't prematurely optimize because what you're optimizing may not even be a bottleneck and you risk making your code more complex and harder to maintain or expand in the future. If something isn't a bottleneck it's valid to do absolutely nothing about it because it will have zero impact on your performance and you've better things to be doing with your time. Memory is cheap and plentiful, programmer time isn't.

[frag.machine]

"Using less memory" != "always faster". An extremely rough generalization could be that it's not how much memory you use, it's how you use it.

As always, profile your code, determine where your bottlenecks are, and tackle those bottlenecks. Don't prematurely optimize because what you're optimizing may not even be a bottleneck and you risk making your code more complex and harder to maintain or expand in the future. If something isn't a bottleneck it's valid to do absolutely nothing about it because it will have zero impact on your performance and you've better things to be doing with your time. Memory is cheap and plentiful, programmer time isn't.

tl;dr version to what mh said: if isn't broken, don't fix it.
It could be wise in the past to save memory (every new float adds 4 bytes to the entity space), but nowadays the gain is negligible.

[mankrip]

The gain isn't negligible when trying to squeeze all of that data into something like a Dreamcast VMU.

My JoyMenu mod (and iirc Makaqu's progs.dat too) has tons of optimizations to limit the number and size of the QC fields stored into saves. IIRC, some saves had their sizes cut in half thanks to this (or maybe it was due to the combination of Makaqu's progs.dat + engine optimizations - I really don't remember it very well, it was many years ago).

[OneManClan]

Summary:
The fastest, and smallest, way to check a field is
if (self.field) {}
The second fastest way is:
if (self.field == 1) {}
The slowest way is:
if (self.field & BIT) {}

Wow, thanks Spike, I had no idea.

I realise my focus on memory and conserving CPU cycles is antiquated in 2011, and possibly I've RTFMed some QuakeC stuff from the 90's which emphasised reusing entity .fields. The original Classic CustomTF source (1999?) even came with an excel spreadsheet which listed the variables that had been reused, so I assumed that some 'max' was close to being reached, and that one must only create a new .variable when absolutely necessary.

I recall a discussion with LordH where he said (IIRC) that the 'performance' issue with multiplayer games on modern computers isn't the QW server's memory, or CPU cycles - it's the business of 'sending and receiving packets from each player'.

Nevetheless, it would be nice to have some kind of 'measurement device', some way to know exactly how a mod is 'performing' given a certain number of ents (which I know FTE increased massively), and the affect of having x number of .variables, just to get a 'feel' for exactly how much a qw engine can 'handle'.

Thanks for the feedback guys.

[frag.machine]

The gain isn't negligible when trying to squeeze all of that data into something like a Dreamcast VMU.

My JoyMenu mod (and iirc Makaqu's progs.dat too) has tons of optimizations to limit the number and size of the QC fields stored into saves. IIRC, some saves had their sizes cut in half thanks to this (or maybe it was due to the combination of Makaqu's progs.dat + engine optimizations - I really don't remember it very well, it was many years ago).

Sure, this kind of optimization stills valid for memory-constrained platforms. But not for PC mods anymore.

[DukeInstinct]

I personally would use bitwise operations regardless of the target platform, but that's just me.

I feel like it's not that big of a hassle to use bitwise operations compared to the memory it will save and it will free up space for features that actually need an entire float to itself.