Jump to content
  • Advertisement
Sign in to follow this  
  • entries
    4
  • comments
    2
  • views
    4480

About this blog

Learning C++ and creating an engine.

Entries in this blog

 

Scheduling updated

This post is really just an update for the scheduling algorithm. I ran a lot of tests, to see which factors had an effect on performance, and ended up with removing all function calls (including the inline'd ones) and changing strutures inside the threads to arrays, two of which were placed on the stack, while the third (and now only expandable one) is on the heap.

The result was an up to 20% improvement in speed (or rather - reduction in the overhead), so that now, jobs of sizes smaller than a single microsecond can be scheduled efficiently.

New efficiency measurements with relation to my previous post (again in ns):
100 - 131.6%
300 - 293.6%
1000 - 370.5%
10000 - 400.7%

Note that we exceed the hard-limit of 400 % in the last case. I reason that this is due to OS scheduling overhead in the single processor case, which should be reduced in the multiprocessor case due to me forcing each of my threads to run in a specific core, and due to the loadbalancing, rather than a simple four way split (meaning that if a single core turns out to have a lower throughput, it will receive fewer jobs).

I am currently satisfied with the scheduler, so I do not expect to perform major updates on it again.

If anyone has a chance to run this algorithm on a computer with more than 4 cores, I would love to hear how it handles.

Thomas Brinck

Thomas Brinck

 

Scheduling

A word from our sponsors:
Ok, finally, it has become time for another update.

Since it seems that posts disappear after some time(edit: ok, seems it isn't the case after all, but lets leave it anyway), let me start by restating my current project:

I am currently self-employed, and is working on learning C++ and creating a game engine for games like the battle field part of the Total War series. My current goal is a job the Creative Assembly, however realistic that may be, or a job at any company, dealing with large scale environments with high demand for efficiency.

I was new to C++ when I started the project, but I hold a Masters Degree in Computer Science, and had been working in the automation industry with compiler construction for a few years, so I am a pretty experienced programmer / developer. To maximize learning speed, I have created everything from scratch, including the utilities I use. This reduces portability, but that has never been my goal either. I want to understand as many nooks and crannies of C++ as possible. A single exception is the OpenGL code currently in the source. That is pretty much just lesson 1 from NeHe.

In my thesis, I examined BVH based, real time collision detection algorithms in a 1 x 1 Km sandbox with primitive AI and up to 10K movable objects.

Since june / july, I have been working on rewriting this in C++, and on learning how to code efficiently in the language as well. My goal is to release it bit by bit, as elements of the code nears completion, with a liberal license (if you like it, use it, but I would appreciate you saying thank you), in the hopes that other people playing with it, can give me feedback that I am not able to find myself.

The current source for my project is pretty much structured, as I expect it to be in the final version. There is quite a bit of code in it, but only a few pieces that I do not expect to perform major rewrites on in the future. These parts can be found by looking for a description comment in the header with version 1.0 in the changelog.

Todays piece:
For those of you, who primarily work with graphics, this is probably going to be boring, so you may want to look away now. Todays piece is a low-overhead scheduler for use with multithreading in games. It is similar to a Thread Pool Pattern, except that I use a fixed number of threads, and I schedule a number of jobs for each thread, based on the weight of each job.
I have created it to be able to run parts of a game engine as jobs with asynchronous executions in several processors / cores, without overhead killing the advantage.



I am not completely done with adjusting the variables (ok, I haven't really started), but the algorithm is done and should be working now.
All relevant code is in the multiThreading sub-package, and importing MultiThreading.h will give you complete access to the scheduler, while Job.h in multiThreading/objects will allow you to implement a new job object for scheduling.

To use it, you first initialize the scheduler. This is done once for the program (for instance during initialization of the program). At this point, a number of threads is created, based on the values in the MultiThreadingControl class.

Then you create a number of jobs (extending the Job object), with access to all data needed to run the job (must be either fixed or disjoint from the data to other processes), and with a container for the result. Splitting into jobs and reconnecting the results isn't handled by the scheduler. If you can create a batch of jobs and add them all at once, you can gain some speed (less locking means less waiting), but otherwise, you can add jobs as they are created (for instance if a job creates another job or a series of jobs).
As soon as multithreading has been initialized, the threads will try to buffer jobs for execution, and will idle (using the CPU fully while doing so).

When you are done adding jobs from the main thread, you can call a function to use the main thread for scheduling and execution as well, to maximize your use of your system. This function will return when all jobs have been executed, allowing you to start gathering the results, and resynchronizing the execution.

Finally, you can uninitialize the multithreading, to make sure that the threads are shut down properly. Windows should handle this anyway when you shut down the program, but i don't know that for certain.

To see it in action, you can run the unit test.

With regard to efficiency, it is highly dependant on the size and number of the jobs. I have run some tests with a specific job, that indicates the efficiency on my (quad core) system (browse MultiThreading.h for a full table):

Average jobsize in nanoseconds:
100 - 104.5%
300 - 219.0%
1000 - 321.3%
10000 - 394.3%

These number can of cause vary dependant on a number of variables, and should never be taken as facts. However, they do give a general idea of the usefullness.

That is all for this time. I expect to increase the frequency of my postings, now that I no longer has to travel through loads of tutorials each time I need to write a line of code. ;o)

If you try downloading the code and playing around with it, then please give some feedback (especially with regard to bugs). I tend to get very focused, when I work with my projects, so I can guarantee that I have overlooked something.

Thomas Brinck

Thomas Brinck

 

First entry

Ok, here goes...

I am currently developing a battle field simultation engine from scratch (ok, almost from scratch), as a C++ learning project, and for use as a portfolio when applying for jobs. My goal is to become an engine developer working with large scale environments, including massive object counts, realistic physics and challenging AI.

The specific aim of the project is scenarios like the ones used by the Total War series, albeit without the graphics and with some reduction to the number of features (at least until I get the basics up and running).

I am basing this on my Masters Thesis regarding Bounding Volume based collision detection in large scale environments similar to the ones from the Battlefield series. Along with my thesis, I created a basic physics engine in java (source included in the link above), and currently, I am moving this to C++, both to learn the language, and to be able to base the engine on this.

More info will follow in time, when I get the basics up and running, and when I learn how to use this journal properly.

Thomas Brinck

Thomas Brinck

 

First entry

Ok, here goes...

I am currently developing a battle field simultation engine from scratch (ok, almost from scratch), as a C++ learning project, and for use as a portfolio when applying for jobs. My goal is to become an engine developer working with large scale environments, including massive object counts, realistic physics and challenging AI.

The specific aim of the project is scenarios like the ones used by the Total War series, albeit without the graphics and with some reduction to the number of features (at least until I get the basics up and running).

I am basing this on my Masters Thesis regarding Bounding Volume based collision detection in large scale environments similar to the ones from the Battlefield series. Along my thesis, I created a basic physics engine in java (source included in the link above), and currently, I am moving this to C++, both to learn the language, and to be able to base the engine on this.

More info will follow in time, when I get the basics up and running, and when I learn how to use this journal properly.

Thomas Brinck

Thomas Brinck

Sign in to follow this  
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!