Simple Bitset

As mentioned yesterday I was going to need to implement a bitset and would post it here when working. Below is the code.

Operators returning copies of a bitset are intentionally left out, the idea being these are expensive operations due to the memory allocations for the bit array. They could easily be implemented using the implemented Copy and Copy Constructor functions though if needed.

*NOTE* A lack of bounds checking in the functions. Could be implemented easily but left out in this v0.1 implementation.

Use any code posted on this blog freely but completely at your own risk, it will work within the parameters I have tested but may contain leaks or other obvious flaws include crashes, endless loops and any other coding issue you care to think of.

#pragma once

class LogicalBitset
{
unsigned int *m_Bits = 0;
int m_NumInts = 0;
int m_NumBits = 0;

public:
LogicalBitset()
{}

LogicalBitset(const LogicalBitset &rOther)
{
Copy(rOther);
}

~LogicalBitset()
{
delete m_Bits;
}

void Init(int iNumBitsNeeded)
{
delete m_Bits;
m_NumInts = (iNumBitsNeeded >> 5) + 1;
m_NumBits = iNumBitsNeeded;
m_Bits = new unsigned int[m_NumInts];
memset(m_Bits, 0, sizeof(m_Bits[0]) * m_NumInts);
}

void Copy(const LogicalBitset &rOther)
{
if (rOther.m_NumInts)
{
Init(rOther.m_NumBits);
for (int i = 0; i < m_NumInts; i++)
{
m_Bits[i] = rOther.m_Bits[i];
}
}
else
{
Reset();
}
}

void Reset()
{
delete m_Bits;
m_Bits = nullptr;
m_NumInts = 0;
m_NumBits = 0;
}

int GetNumBits() const
{
return m_NumBits;
}

void Resize(int neededBits)
{
//Grow only for now
if (neededBits > m_NumBits)
{
int neededInts = (neededBits >> 5) + 1;
if (neededInts > m_NumInts)
{
//Copy old data across to new container
unsigned int *pIntArray = new unsigned int[neededInts];
for (int i = 0; i < m_NumInts; i++)
{
pIntArray[i] = m_Bits[i];
}
delete m_Bits;
pIntArray[m_NumInts] = 0;
m_Bits = pIntArray;
m_NumInts = neededInts;
}
m_NumBits = neededBits;
}
}

void AddBit(bool bValue)
{
int neededBits = m_NumBits+1;
int neededInts = (neededBits >> 5) + 1;
if (neededInts > m_NumInts)
{
//Copy old data across to new container
unsigned int *pIntArray = new unsigned int[neededInts];
for (int i = 0; i < m_NumInts; i++)
{
pIntArray[i] = m_Bits[i];
}
delete m_Bits;
pIntArray[m_NumInts] = 0;
m_Bits = pIntArray;
m_NumInts = neededInts;
}
m_NumBits = neededBits;
SetBit(m_NumBits - 1, bValue);
}

bool IsSet() const
{
return m_NumInts > 0;
}

void SetBit(int iIndex, bool bValue)
{
int iInt = iIndex >> 5;
int iValue = m_Bits[iInt];
int iBit = iIndex & 31;
int iBitMask = 1 << iBit;
m_Bits[iInt] = (iValue & (~iBitMask)) | (bValue ? iBitMask : 0);
}

bool GetBit(int iIndex)
{
int iInt = iIndex >> 5;
int iBit = iIndex & 31;
return (m_Bits[iInt] & (1 << iBit)) != 0;
}

bool operator==(const LogicalBitset &rOther) const
{
if (m_NumInts != rOther.m_NumBits)
return false;

for (int i = 0; i < m_NumInts; i++)
{
if (m_Bits[i] != rOther.m_Bits[i])
return false;
}
return true;
}

void operator=(const LogicalBitset &rOther)
{
Copy(rOther);
}

void Zero()
{
for (int i = 0; i < m_NumInts; i++)
{
m_Bits[i] = 0;
}
}

bool IsNonZero() const
{
for (int i = 0; i < m_NumInts; i++)
{
if (m_Bits[i] != 0)
return true;
}
return false;
}

bool ContainsSomeBits(const LogicalBitset &rOther) const
{
for (int i = 0; i < m_NumInts; i++)
{
if (m_Bits[i] & rOther.m_Bits[i])
return true;
}
return false;
}

bool ContainsAllBits(const LogicalBitset &rOther) const
{
for (int i = 0; i < m_NumInts; i++)
{
const unsigned int iOtherBits = rOther.m_Bits[i];
if ((m_Bits[i] & iOtherBits) != iOtherBits)
return false;
}
return true;
}
};

VS Community profiling

Some notes jotted down while I was playing with this profiler for the first time.

Profiling

• Open the "Performance Explorer"
• Right click on a project - "Start profiling"
• If asked to upgrade your profile, say yes
• Switch of sampling on your target until at the point you want to profile.
• Once you are finished look at the .vsp file, it may take some processing to show up
• You need to sample long enough to get some moderaly accurate samples
• Current View (top selection box): Modules is very useful in Unreal as you might want to differentiate between your code and engine code.
• Sample for long enough to get > 1 samples in functions you care about (or enough in functions you don't to eliminate the need to care). More samples makes your game perform slower!
• If you don't have "Collect Samples" ticked at launch it will complain about not having any executables selected for profiling, that's okay.
• I've found that sometimes the application doesn't launch through the performance explorer, in which case you can simply launch normally and "attach"
• When you stop profiling and first see the result you see a time line in seconds - you can select a section of this to generate data from, by default the whole time is used.
• On that same summary page - top rightish, there is an option to "Show Just My Code", this is very helpful to getting to the bits you are working on.

Unreal editor - finding your update code - look here:

UE4Editor-UnrealEd.dll
-FEngineLoop::Tick
--GuardedMain
---WinMain
----_tmainCRTStartup
-----UE4Editor.exe
------My update functions should be here

Plan, just the right amount, not too much, not too little.

A few months ago I built some code that I knew would fail, in a few months time when the data had matured.

Plan was to come up with a plan on how to deal with it when it needed to be dealt with. I put some clear errors in my data editor telling me I was hitting the problem and continued development.

Then I added procedural data packs, and forgot to put the same warnings there. Today I spent a few hours debugging the problem until the light dawned and I realized my plan to make a plan had failed.

Time to really make a plan!

The problem involves fast searches by category in a dictionary of categorized words. The searches take a set of categories and the form "match any, match all, exclude any, exclude all".

switch (rFilter.m_MatchType)
{
case MatchFilterRuntime::eInactive:
return true;
case MatchFilterRuntime::eMatchAll:
//Include if ALL were found
return ((CategoryFlags & rFilter.m_CategoryFlags) == rFilter.m_CategoryFlags);
case MatchFilterRuntime::eMatchAny:
//Includ if ANY were fould
return ((CategoryFlags & rFilter.m_CategoryFlags) != 0);
case MatchFilterRuntime::eExcludeAll:
//Include if not all were found
return !((CategoryFlags & rFilter.m_CategoryFlags) == rFilter.m_CategoryFlags);
case MatchFilterRuntime::eExcludeAny:
//Include if NONE were found
return ((CategoryFlags & rFilter.m_CategoryFlags) == 0);
}

As you can see above up to now I've been able to reduce my category checks from a set of strings to fast and furious bitwise operations. The error I just is is having more than 32 categories in a single dictionary.

When I first wrote the code I had the sneaky hope that 32 categories in a dictionary would be plenty, that I could just split my data into more dictionaries but as the data takes shape this now seems unlikely. So plan A [my favorite, do nothing] is a fail.

Now I'm contemplating my options:

- Larger single sized bit storage size. 64 bits might buy another three months development right? 128?

- A proper bitset object

I think the second option is the winner and should be fun to implement.

Given I already have category sets the bitset could just be a byte collection of known size for any dictionary. I looked at TBitSet in unreal C++ but it doesn't seem to provide the functionality I want and adds some level of complication.

Of course, now I look at how much code I've got passing these flags around as int's and I don't whether to be proud of the quanity or sad that I didn't just bite this off when I knew it was a problem and save the cost of retro fitting the new structure everywhere! Don't over engineer until you know the requirements right? Actually, I'll stand by that, which this will waste a day of my time, I've saved that time elsewhere by not engineering to specs made to suit the elegance of the solution, not the problem. So I hope anyway.

I'll post the code for the new bitset here when it's working smoothly, probably tomorrow.

Leaderboard reading without crashing

I've been getting crashes while closing the editor and while building packages. These are often during the leadboard system destruction.

Turns out my simple implementation using a static FOnlineLeaderboardRead was flawed. My guess is that the game module gets torn down before the editor module leaving the editor pointing at now corrupt static data. To alleviate this I've put them on the heap for now.

IOnlineLeaderboardsPtr leaderBoards = pSubSystem->GetLeaderboardsInterface();
if (leaderBoards.IsValid())
{
if (!leaderBoardRead)
{
leaderBoardRead = new FOnlineLeaderboardRead;
leaderBoardReadRef = new FOnlineLeaderboardReadRef(leaderBoardRead);
}
if (leaderBoards->ReadLeaderboardsForFriends(0, *leaderBoardReadRef))

I really must look up any sample code on getting these systems up and running, the documentation is very WIP and there are probably a load of gotchas like this that are not apparent to my nOOb eyes from what documentation exists.

VS Community

As my friend Rich pointed out Visual Studio Community, a more fully fledged IDE than the Express version, is now available.

20 minutes into use...

• Peek definition is cool - you can even edit in the definition
• Intellisense is faster - perhaps usable with Unreal? The jury is out... but working intellisense is a huge productivity booster
• Working debugging visualiser macros (see this and follow directions at the bottom for UE4.natvis)
• NOTE: The installation under My Documents worked for me, not the other one
• This allows you to see strings and arrays in the debugger without the 
• Profiling support
• Better symbol resolution - I always meant to get engine symbols working with VSExpress but they just worked out of the box with the community edition.

Gameplay anyone?

Games building and running pretty well on all three supported platforms. Seems it can be packaged for release and there is a internet depot that seems to let you download and run the game.

Tomorrow is a new day and new dawn and time to go back to writing some gameplay!

Least crashing during Unreal iphone development

Running Unreal on my old MAC is troublesome, lots of crashes. As mentioned previously these seem largely memory related but it does sound like others find Unreal less stable on the MAC.

Here's what I do to improve the situation:

• Close everything, EVERYTHING, except the editor
• Close the launcher once the editor is
• Close iphoto as it probably booted up when you plugged in your phone
• Close itunes
• Close source control
• Close XCode
• Don't touch anything if you can help it.....
• Edit your project on a PC if possible, just use the MAC to cook - to do this open Unreal (close stuff!) launch on iphone then exit and iterate using XCode

Open up the activity monitor and purge anything with CPU or memory use that seems non critical and expensive.

I would guess that the MAC build stabilizes over time, though I am likely to buy more memory in the meantime.