Tag Archives: Containers

Next Container Library

Developing “Rush for Glory” game is going to be finished. so I decided to rewrite some parts of the engine recently. this may cause you to rewrite the whole source code. In the first step, I rewrote the containers library. in this new version, I changed the structure of containers to decrease the usage of templates<> to more easier to understand. I used a sampler to decrease allocations. also implementing memory allocators is more easy than before and changeable during the code in some cases. finally implementing a new memory allocator that uses stack memory to avoid calling the malloc function.

Note that some new features are not designed for general purposes. there are many limitations to using them and must be used with care because those features are designed to develop the game and most of the capabilities depend on the needs of a game engine.

Here are some highlights :

Added math base functions to the library with some fast functions like :

// fast sqrt root using Log Base 2 Approximation With One Extra Babylonian Steps
float sx_sqrt_fast( const float x );

// return sine( x ) from table. maximum absolute error is 0.001f
float sx_sin_fast( const float x );

// return cosine( x ) from table. maximum absolute error is 0.001f
float sx_cos_fast( const float x );

// compute the sine and cosine of the angle x at the same time. maximum absolute error is 0.001f
void sx_sin_cos_fast( const float IN x, float& OUT s, float& OUT c);

and some useful conventional functions

MemManFixed::SetBuffer(void* buffer);
I can change the memory buffer of the allocator by setting a new buffer. this feature is available only on the fixed memory manager. it means that it’s suitable just for arrays and strings.
For example, I wanna change/fill a string in a structure. in this example when I set members of the structure to the allocator, all string functions can be applied easily.

struct FileInfo {
    wchar   path[256];
    wchar   name[64];
    wchar   type[32];
}

FileIfo fileInfo;

MemManFixed memTmp;
String strTmp( 0, &memTmp );

// extract file path from file name and copy that to fileInfo.path
memTmp.SetBuffer( &fileInfo.path );
strTmp = fileName;
strTmp.ExtractFilePath();

// extract the name of the file and copy that to fileInfo.name
memTmp.SetBuffer( &fileInfo.name );
strTmp = fileName;
strTmp.ExtractFileName();

// extract file type and copy that to the fileInfo.type
memTmp.SetBuffer( &fileInfo.type );
strTmp = fileName;
strTmp.ExtractFileExtension();

MemManFixed_inline<memSizeInByte>
This memory manager uses a memory stack of functions. by the way, this feature is available only on the fixed memory manager. this means that it’s suitable just for arrays and strings.

In this example, I try to collect some nodes from the scene manager. this will happen at each frame more than once, at the renderer, AI system &, etc. Implementing a new Array class causes calling allocation/deallocation. the other solution is declaring a static array. the other solution is using a memory stack with some limitations but fast and easy memory management.
example :

MemManFixed_inline<MAX_NODE_COUNT> tmpMem;
Array<Node*> nodes( 0, &tmpMem );

// collect nodes from the scene manager
g_engine->m_scene->GetNodesByFrustum( cameraFrustum, nodes );

for ( int i = 0; i < nodes.Count(); i++ )
{
    // ... do something !
}

Although there are some changes like adding new functions and changing algorithms in the other stuff to increase performance and capabilities, but those still need to be optimized more and more.

Address Spaces Problem

As you know the Windows operating system defines an address space area for each process to prevent data hacks and data corruption that may occur by other processes. This approach has some advantages but with a few problems.
A simple (but popular) problem appears when memory blocks are allocated in one process (a DLL for instance) and transported to the other (an application for instance) and then should be reallocated or free in another process! The exception will rise at this point because different memory managers in different address spaces want to operate on non-shared blocks of memory.
You may never see this problem because people usually use default shared libraries, but for me, this is another test and practice 😀
At this time to manage memory block transitions between engine and application address spaces, I added sxAlloc object to the sxLib that can redirect memory allocators in sxMemory to the engine from other address spaces. So all default data containers represented in the last post will use engine address space and become safe to transport data between engine and other processes. however, I can still redefine any container with a different allocator to use anywhere I like.
here is the concept in the image:

Data transition between Engine and Application address spaces

SeganX Foundation

Well. after more attempts finally the SeganX foundation is now completed and ready to use. It separated into different groups and namespaces without any STL footprints.
At first glance, the reason is purely personal, but when you look deeply into this decision, you will find the most important technical advantage of writing the entire internal library!
Practice!
Just as every athlete needs to practice his skills, this exercise, in addition to increasing knowledge about data containers and algorithms, increases your coding skills and makes you think more and more about solving problems.

The SeganX foundation covers the tools listed below:

sxLib: the most independent library that contains the basic container classes and functions.

String: Standard String that uses standard OS memory management to store data.
String_inline: Fast String that uses a hybrid memory pool to store data. It’s suitable for local/temp variables in functions. and should not implemented in classes as a member!
String_256: Type of String that uses 256 fixed-size string.
String_512: Type of String that uses 512 fixed-size string.
String_1024: Type of String that uses 1024 fixed size string.

Array: Standard Array that uses standard OS memory management to store data.
Array_inline: Fast type of Array that uses a hybrid memory pool to store data. It’s suitable for local/temp variables in functions. and should not implemented in classes as a member!
Array_fix<T, MaxPush>: Fast type of Array that uses fixed size memory block to store/restore data.

List: Standard List that uses OS memory management to store/restore data.
List_256: Fast type of List that can hold a maximum 256 number of objects.
List_512: Fast type of List that can hold a maximum 512 number of objects.
List_fix<T, MaxPush>: Fast type of List that uses a memory pool to store/restore data.

Queue: Standard Queue that uses OS memory management to store/restore data.
Queue_fix<T, MaxPush>: Fast type of Queue that uses a memory pool to store/restore data.
Queue_256: Fast type of Queue that can hold a maximum 256 number of objects.
Queue_512: Fast type of Queue that can hold a maximum 512 number of objects.

Stack: Standard Stack that uses standard OS memory management to store data.
Stack_inline: Fast type of Stack that uses a hybrid memory pool to store data. It’s suitable for local/temp variables in functions. and should not implemented in classes as a member!
Stack_fix<T, MaxPush>: Fast type of Stack that uses fixed size memory block to store/restore data.

Here the Map container uses AVL Tree and as you know it’s one of the Self-Balanced Binary Search Tree. Although there are some drawbacks in insertion and deletion it has a fast search ( O(log n) ) and I will use its search frequently. here are some types of my maps:
Map<key, type>: Standard Map that uses OS memory management to store/restore data.
Map_256<key, type>: Fast type of Map that can hold a maximum 256 number of objects.
Map_512<key, type>: Fast type of Map that can hold a maximum 512 number of objects.
Map_fix<key, type, MaxPush>: Fast type of Map that uses a memory pool to store/restore data.

In addition, there are two memory pool types, three memory manager types, a base of streams a memory stream class, and some tools in sxClasses that are boring to describe.

sxSys: this library contains more system tools and functions:
Window class is a simple class to create and modify a window.
Application Is the main class that no need to create. this class is responsible for managing windows, running, and controlling the project.
System Functions are a series of functions to get system info, CPU cores monitoring, power management monitoring to keep the system wake up full, working with files, folders, disk drives, etc.
The other things that exist in namespace sxSys are threads and task manager, log system, and some additional useful functions for numbers and strings. these tools and functions need sxLib to compile.

some other parts, rendering system, engine, editor, etc are under development.