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.

Loading loose files in Unreal

Running on MAC or PC (but not iPhone) the Unreal file system will just pull loose from your content directory. When it comes to the iPhone its time to package.

I couldn't find any details on how to package txt, json, xml, csv etc files (basically anything that is not an Unreal data type but the answer came back as something pretty straightforward.

Here's the response from Unreal

And now I have something to search on some documentation.

The reason I'd missed these settings is they are "hidden". See below - click that little icon in the editor!

Running Unreal on an Old(ish) MAC

Porting my project to MAC within Unreal wasn't too bad, took about a day longer than the two days my gut had predicted. About a day's work left (I think!) but not unexpected work, just work I didn't realise I'd need to do to get working on iPhone - mainly packaging related.

Expected

• Compiling! My code was mostly clean of Windows (thanks to Unreal doing all the heavy lifting and trying to stick to Epic's functions for anything OS related) but XCode was a bit stricter on some code issues. Everything pointed out was valid and the only real library difference was the lack of XXX_s versions of string functions and a couple of other string manipulation functions that turn out to not be in the standard libs (_ttoi). A couple of hours spent here working out what the compiler was talking about in my small project (~100 smallish files).
• Signing and packaging. At least semi expected. Even now when I've got things working I'm still waiting for the house of cards to all fall down around my ears. The system for signing code is fairly complicated and then I think made more complicated by unreal taking over some of it for you. It took me over half a day to get this right (I think).

Unexpected:

• Breakpoints: Didn't work out of the box - though the fix is simple and did work (and easy to find online).
• Horrible stability: My assumption would be terrible performance with lots of virtual memory used but so far I think I crash about every three meaningful actions - including just browsing blueprints or changing project settings. Given the number of malloc references in the callstacks, or obvious null pointer derefs I currently assume a link between the lack of memory and the stability. Will only know if I get around to upgrading the machines memory, for now I'm just about able to package and run and that's enough.
• Packaging: So far I've been loading loose files from the Content directory. These don't seem to load on the iPhone. Time to start packaging. I couldn't find much documentation but asking on AnswerHub got me pointed in the right direction.
• Output: Need to look into this but vswprintf seems to handle wide char's differently on MAC, so its treating the first character as a NULL terminated string and ignoring the rest. Likely just a format string change?

New to GIT

I'm not going to go back over the technical details of GIT here but have a couple of pointers.

I developed a project using a local GIT repository for a while. This allowed me to track changes over time, undo changes, generally feel more secure in development. As I want to keep the code private until it reaches some level of maturity this also allowed me to avoid the $7 monthly charge for an offsite private depo.

When it came time to share the code on a different machine it became time to bite the $7 bullet - at this point though I found myself wasting a day of dev time learning how to setup a remote depot, copy my existing depot to it while maintaining history.

Short lessons learnt:
- GitHUB applications are useful, but slightly unstable
- It is much easier to start the depot online from the start. if you can then do so
- When scrubbing large files from the depot so you can upload it (there is a 100Mb limit) pay attention to any platform specific semantics (" vs ') and the fact that filenames are case sensitive
- The "bfg" sounds useful but I haven't managed to get it to run on my PC, will try on my MAC. For small solo projects the git filter-branch command isn't too slow - but you do have to be careful with the syntax (see above!).

Overall GIT is a very powerful tool with huge numbers of settings and seems like a good choice for solo or small scale development. As a windows developer who sometimes finds themselves in Linux, UNIX, MAC etc I'd say the learning curve is steep even with GitHUB (which has a tendency to say useful things like "failed" rather than give you the full output) and when setting up a new depot would allow yourself some time to get things working just right.

Having used Perforce, SVN, CVS, GIT and SourceSafe I'm still sitting in the Perforce camp but mainly because of the nice frontend and GIT is growing on me fast.