Using the Moving Average Filter for Profiling Stats

October 19, 2011 Leave a comment



Simple Moving Average

tFloat MeanValue = 0.0f;
    MeanValue += RecentValues[i];
MeanValue /= n;


Exponential Moving Average

MeanValue = MeanValue * 0.99f + CurrentValue * 0.01f;


Here’s a graph comparing the two solutions:




Categories: Mathematics, Programming Tags:

Hashing Strings and Pointers – Avoiding Common Pitfalls

October 12, 2011 7 comments

In a previous post, I suggested using fixed size hash tables to map strings and pointers. Since this code really needs to be fast, reducing hash collisions probabilities is very important to maximize the hash table performances. But there is other pitfalls that needs to be addressed too.

Hashing Strings
The most common error when hashing strings is to perform a string comparison (using strcmp) when traversing the hash bin list. Even if the hash function is quite bad and has a very high probability of generating the same hash value for different strings, this is not required at all.

For my tests, I hashed the complete dictionary found in /usr/dict/words which contained 212710 unique words. Here’s some of the results:

hairbrush hash_value=0x7f3ef2bb hash_bin=0x32bb
encomiums hash_value=0xa758b2bb hash_bin=0x32bb
engrained hash_value=0x32abb2bb hash_bin=0x32bb
   seavir hash_value=0x32abb2bb hash_bin=0x32bb

As you can see, all of these strings ended up in the same hash bin 0x32bb, but have different hash values (except for ‘engrained’ and ‘seavir’).

In the hash table, it looks like this:

[0x32ba] phrenologically(0x888fb2ba)->Alfreda(0xee9432ba)->...
[0x32bb] encomiums(0xa758b2bb)->engrained(0x32abb2bb)->seavir(0x32abb2bb)->...
[0x32bc] centillion(0xb44232bc)->cyclometer(0xc5a172bc)->...

As an optimization, we can only compare the original hash value (ie the value before it was made to fit the hash table size) until we found a match. Then, we need to do a string comparison in order to make sure that the strings match. This greatly optimize the hash performances and can be used with all non-PODs data types.

Attentive readers might have noticed that, in my previous post on memory tracking, I totally skipped the string comparison when hashing the allocation tags. I decided to trade possible errors due to hash value collisions with execution speed, simply because the hash function is so efficient that I never hit a single collision.

The hash function I’m using was published in Dr. Dobb’s Algorithm Alley by Bob Jenkins, in September 1997. I’ve been using this function in several games over the years and never hit a single hash collision, sometimes hashing hundreds of thousands of unique strings.

Hashing Pointers
When hashing pointers, special care must be taken due to alignment. It is tempting to simply use the pointer itself to index in the hash table, but this is a very bad idea, as pointers are mostly aligned on 4, 8, 16 bytes or even more. Alignment makes the lowest bits set to 0, and depending on the hash table size, it may lead to a non-uniform distribution, thus reducing the hash table to a simple linked-list in the worst case.

Over the years, I’ve been using Thomas Wang’s hash function to hash pointers on several platforms and it worked very well in all cases:

tU32 HashPointer(void* Ptr)
    tU32 Value = (tU32)Ptr;
    Value = ~Value + (Value << 15);
    Value = Value ^ (Value >> 12);
    Value = Value + (Value << 2);
    Value = Value ^ (Value >> 4);
    Value = Value * 2057;
    Value = Value ^ (Value >> 16);
    return Value;

Always test your hash functions to make sure distribution is uniform, especially for complex types (strings, GUIDs, etc). Pay special attention to types that may vary on different platforms (pointers, etc). Also, whenever possible, prefer a fixed-size hash table that fits the data you’re hashing, as opposed to using a templated, varying size one that may use more memory and won’t allow custom traversal comparison code.

Categories: Programming Tags:

Memory Management Part 2: Allocations Tracking

October 6, 2011 7 comments


Here’s what we want to achieve:

  • Track memory leaks and generate categorized memory usage reports.

Minimizing Impacts


template<class T> class FreeList
    T* Free;

    : Free(NULL)

    inline T* New()
            const tU32 AllocSize = 65536;
            const tU32 NumAllocPerBatch = AllocSize / sizeof(T);



        T* Result = Free;
        Free = *((T**)Free);
        return Result;

    inline void Delete(T* Ptr)
        *(T**)Ptr = Free;
        Free = Ptr;




Tracking Allocations Hook

    void* Result = malloc(Size);
    return Result;

    void* Result = realloc(Ptr, Size);
    return Result;

void _Free(void* Ptr)
    return free(Ptr);


struct AllocDesc
    void* Ptr;        // Allocation address
    tU32 Size;        // Allocation size
    TagDesc* Tag;     // Pointer to the allocation category
    AllocDesc* Next;  // Next allocation in the hashtable
struct TagDesc
    tU32 CRC;         // Category description string CRC
    tChar Tag[128];   // Category name
    TagDesc* Next;    // Next category in the hashtable

The steps for registering an allocation looks like this:

    // Allocate a new AllocDesc from the freelist
    AllocDesc* NewAllocDesc = FreeAllocs.Allocate();

    // Set the allocation info
    NewAllocDesc->Ptr = Ptr;
    NewAllocDesc->Size = Size;
    NewAllocDesc->File = File;
    NewAllocDesc->Line = Line;


    // Register the allocation in the fixed-size hashtable
    NewAllocDesc->Next = Hash[PtrHash];
    Hash[PtrHash] = NewAllocDesc;

Registering a new category goes like this:

    tU32 TagCRC = Strhash(Tag);
    tU32 TagHash = TagCRC & (ALLOC_DESC_SIZE - 1);
    TagDesc* CurTag = CurTag = Hash[TagHash];

        if(CurTag->CRC == TagCRC)
            CurTag->Size += Size;
            return CurTag;

        CurTag = CurTag->Next;

    // Allocate a new TagDesc from the freelist
    CurTag = FreeTags.Allocate();

    // Set the category info
    CurTag->CRC = TagCRC;
    CurTag->Size = Size;

    memcpy(CurTag->Tag, Tag, TagLen);
    CurTag->Tag[TagLen] = 0;

    // Register the category in the fixed-size hashtable
    CurTag->Next = Hash[TagHash];
    Hash[TagHash] = CurTag;

    return CurTag;


Analyzing the Data

void DumpAllocs()
        AllocDesc* Alloc = Hash[i];
            Alloc = Alloc->Next;


  Meshes 11336K
  Sounds 41553K
Textures 7867K

Tracking memory leaks


Memory Management Part 1: Introduction

October 3, 2011 4 comments


Series Outline

  • Allocation strategy
  • Usage tracking
  • Leaks detection
  • Allocators design
  • Multithread issues
  • Fragmentation
  • False sharing
  • Contention
  • Waste/overhead


Allocation Strategy


void _Free(void* Ptr);








#define Delete delete


Third-party external libraries


class MemoryInterface
    virtual void* malloc(int Size)=0;
    virtual void free(void* Ptr)=0;

Implementing this interface should look like this:

class EngineMemoryInterface: public MemoryInterface




Generating primes

September 27, 2011 1 comment

Here’s my implementation of the sieve of Eratosthenes in pyhton:

cur_num = 2
multiples = {2 : 2}

while True:
    is_prime = True

    for v in multiples:
        nv = multiples[v] - 1
        if nv == 0:
            is_prime = False
            multiples[v] = v
            multiples[v] = nv

    if is_prime == True:
        print cur_num
        multiples[cur_num] = cur_num

    cur_num = cur_num + 1




cur_num = 2
multiples = {2 : 2}

while True:
    is_prime = True

    for v in multiples:
        nv = multiples[v] - 1
        if nv == 0:
            is_prime = False
            multiples[v] = v
            multiples[v] = nv
    if is_prime == True:
        print cur_num, "[prime]"
        multiples[cur_num] = cur_num
        primes = list()
        for v in multiples:
            if multiples[v] == v:
        print cur_num, "[nonprime] ", primes

    cur_num = cur_num + 1

Which outputs this:

83 [prime]
84 [nonprime]  [2, 3, 7]
85 [nonprime]  [5, 17]
86 [nonprime]  [2, 43]
87 [nonprime]  [3, 29]
88 [nonprime]  [2, 11]
89 [prime]
90 [nonprime]  [2, 3, 5]
91 [nonprime]  [7, 13]
92 [nonprime]  [2, 23]
93 [nonprime]  [3, 31]
94 [nonprime]  [2, 47]
95 [nonprime]  [5, 19]
96 [nonprime]  [2, 3]
97 [prime]


Lessons learnt while spinning

September 24, 2011 3 comments

In a recent project I worked on, I tried to minimize context switches by strategically replacing a critical section in our memory allocator by a custom spinlock that looked like this:

class SpinLock
    volatile tInt LockSem;

    FORCEINLINE SpinLock()
    : LockSem(0)

    FORCEINLINE tBool Lock()
            // Atomically swap the lock variable with 1 if it's currently equal to 0
            if(!InterlockedCompareExchange(&LockSem, 1, 0))
                // We successfully acquired the lock

    FORCEINLINE void Unlock()
        LockSem = 0;

This indeed worked as predicted, but produced an unwanted side-effect on platforms without threads priority inversion (where a high-priority thread spins in a loop while waiting for a low-priority thread to release a lock) as the Xbox 360 (described in this technical article).

It created rare situations where the game was deadlocked, and the time spent to figure-out what was going on was quite high. At first, we played with threads priorities and affinities, but it had other unwanted side-effects. Another solution tried was to yield after a certain amount of spin loops, generating a context switch that let the OS reschedule threads correctly. In the end, we reverted to a critical section.

Lesson learnt? We have to be very careful when busy-waiting, especially on OSs that don’t have priority inversion protection mechanisms. Using the OS synchronization primitives is the best way of coordinating multiple threads. When locking becomes a performance bottleneck, we have to address the underlying problem (using lockless programming, etc).

Categories: Programming Tags:

GUID generation

September 21, 2011 1 comment

I recently had to generate globally unique identifiers (GUIDs) for a personal project that I have at home. They could be generated concurrently on several threads and on multiple machines over the network, and the only rules I wanted to stick with were to avoid duplicates and be as fast as possible. Here’s what I ended up with:

void GUID::GenerateUnique()
    Time Time;

    static tU16 StaticMask = 0;
    StaticMask = InterlockedIncrement(StaticMask);

    A = GUUID;
    B = GMACAddress >> 16;
    C = (StaticMask << 16) | (GMACAddress & 0xffff);
    D = (Time.Second + Time.Minute * 60 + Time.Hour * 60 * 60) | (Time.Month << 17) | (Time.Day << 22) | ((Time.Year - 2011) << 27);

    // Simple encryption
    tU32 Mask = (StaticMask << 16) | ((StaticMask * 0x0bb38435) + 0x3619636b);
    A = ~A ^ Mask;
    B = ~B ^ Mask;
    C = ~C ^ StaticMask; // don't encrypt the mask itself
    D = ~D ^ Mask;

A, B, C and D are 32-bits unsigned values. A contains a CRC32 of the PC’s username. The PC’s MAC address is encoded in B and C parts. The remaining 16 bits of C also contains a sequential number which is atomically incremented at each call to avoid generating the same GUID when called from multiple threads. D contains a timestamp, similar to a Unix Time. At the end, a quite simple encryption scheme is used to make sure that the MAC address isn’t easily exposed directly in the GUID.

One cool thing about this is that at any point, a GUID can be decrypted and everything can be extracted from it; the CRC32 of the user who generated it, the MAC address and the timestamp:

String GUID::GetDescStr() const
    tU16 StaticMask = ~(C >> 16);
    tU32 Mask = (StaticMask << 16) | (StaticMask * 0x0bb38435) + 0x3619636b;
    tU32 Mac0 = ~(B ^ Mask);
    tU32 Mac1 = ~(C ^ StaticMask);

    String Result = String::Printf(
        "UUID:%08x MAC:%02x-%02x-%02x-%02x-%02x-%02x ",
        ~(A ^ Mask),
        (tU32)((Mac0 & 0xff000000) >> 24),
        (tU32)((Mac0 & 0xff0000) >> 16),
        (tU32)((Mac0 & 0xff00) >> 8),
        (tU32)((Mac0 & 0xff)),
        (tU32)((Mac1 & 0xff00) >> 8),
        (tU32)((Mac1 & 0xff))

    tU32 Timestamp = ~(D ^ Mask);
    tU32 Seconds = (Timestamp & 0x1ffff);
    tU32 Month = ((Timestamp >> 17) & 0x1f);
    tU32 Day = ((Timestamp >> 22) & 0x1f);
    tU32 Year = (Timestamp >> 27) + 2011;
    tU32 Hour = (Seconds / (60 * 60));
    Seconds -= Hour * 60 * 60;
    tU32 Minute = (Seconds / 60);
    Seconds -= Minute * 60;

    Result += String::Printf("Date:%d-%02d-%02d %d:%02d:%02d ", Year, Month, Day, Hour, Minute, Seconds);
    Result += String::Printf("Mask:0x%08x", Mask);

    return Result;

Size didn’t matter in my case, but this could be easily reduced to 96-bits by removing the CRC32 of the username, without changing the uniqueness of the GUIDs. If the size really matters, one could possibly reduce it to 64-bits by using the CRC32 of the username and the timestamp, but the function would possibly need to be protected by a critical-section to avoid 2 threads generating the exact same GUID.

Categories: Programming Tags:
%d bloggers like this: