Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 12 Mar 2005
Offline Last Active Today, 02:35 PM

#5236502 how to get length of a int vector without overflow on 32 bit int

Posted by frob on 23 June 2015 - 11:22 PM

Also... that's a lot of cubes.


Minecraft is popular right now so I assume that's what you're basing it on.  The development team needed to do quite a lot of engineering work to make it mostly transparent to the user.


While logically the world may have your 31 billion cubes in it, there is no way you are fitting those into an array on today's hardware.


Think about what that means in terms of space.  If they have 32 bytes of data each, that's one terabyte of memory.


Home computers don't ship with 1TB of ram, and probably won't for a few more years.

#5236500 (Picture) C#: Can anyone explain how this is possible? IF statement is false,...

Posted by frob on 23 June 2015 - 11:11 PM

I'm seconding the guess that something was out of date.  It is easy to make changes that don't get detected and trigger a recompile.


But without seeing your code, it also COULD be a race condition.  


Maybe it's a rare corner case scenario, who knows?

Possibly, Unity makes adding asynchronous behavior -- and therefore bugs from race conditions -- easy to implement.


While some of their tasks work well on the side, for instance co-routines are not distinct threads, if you are setting or modifying the values in any way that could lead to parallel behavior you need to properly manage it values with locks.


If you are taking advantage of asynchronous processing, and especially if you are doing any threading yourself, you need to understand all cases where systems might interact between processes.


The built-in stuff is generally cooperative and does not interrupt each other (except where documented), but if you're doing any multiprocessing yourself, beware, and ensure you follow proper locking semantics.

#5236494 Entity component system, cache and parent-child relationship anomaly

Posted by frob on 23 June 2015 - 10:31 PM

That is an option, and if your code base is designed that way, go ahead.


But it can also be designed around a base component interface, where objects have any and every type of component potentially attached.  While it can be bloated or over-engineered, that does not mean it must be bloated or over-engineered.  


I don't care for Unreal's hierarchies, where the base classes are regimented based on who or what they do or can be attached as.  However, I do like how Unity does it.  And I like how other engines like The Sims 3 did it. 


In Unity you can take any game object and assign whatever components you want to it... although you likely based it on Behaviours instead.  You want to attach a camera to it, just add a camera behavior.  Want to add an AI or steering behavior, just attach a behavior. Built yourself a homing missile behavior? You can add it to any object you want.  No worries about if it is an ActorComponent or SceneComponent, they're interchangable; a behavior is a behavior, attach them however makes sense for your game..


Similar thing in Sims 3, although their architecture was a bit more convoluted due to the nature of the product.  Want to find the nearest radio? Just search for the nearest IStereo component, it can be a boom-box, or desk radio, or DJ station, or wall speaker, or even a tricked-out car, lots of things were assigned with the component and instantly that's what it was.  Want to make something hauntable for ghosts? Add hauntable. Same with destructable, repairable, upgradable, sittable, and more.  Then programmers could search for anything with that component in range, and they'd find it. 

#5236413 Entity component system, cache and parent-child relationship anomaly

Posted by frob on 23 June 2015 - 01:25 PM

I'd argue they share the same basic Component behavior for ECS systems.


That probably means several common queries and responses, parenting information and behavior, broadcast message handling, serialization and validation, possibly some CRTP behavior (our basic ECS components usually end up with a few self-referential templates), some script hookups, maybe even some auto-reload behavior.  


Basically, lots of things could be in common for all ECS components. 


Of course it depends on the design of the system, but having a base ECS component interface can greatly simplify some designs.

#5236347 what really get and set do?

Posted by frob on 23 June 2015 - 09:03 AM

It is a shorthand in the language.

It creates a variable named x, and it creates a default mutator and accessor.

Mutators (set methods) allow the programmer to control access and specify additional behavior when the value is modified. The default one is x=value;.

Accessors (get methods) allow the programmer to control or modify behavior when the value is read. The default one is return x;

You can add more complete get and set bodies later, if you have reason to specify additional behavior.

#5236227 Entity component system, cache and parent-child relationship anomaly

Posted by frob on 22 June 2015 - 04:24 PM

and the whole purpose of this new system is to improve cache coherence by avoiding these jumps.
Do you have evidence that your version is not cache friendly?


CPU caches work in various-sized blocks. While it is ideal to walk sequentially, it can potentially be cache friendly to walk them in a not-quite linear fashion as they stay within those blocks.  You may not be in L1, but instead in L2. 


If you've got evidence that it doesn't work, then you'll likely want to reorder your objects so that every parent object is immediately followed by its children. Nested items are further placed sequential with their children, and so on.


Fortunately for you, there is already a data structure for that, called a "heap", not to be confused with the memory area also called a heap.  Heaps are amazingly useful for many different algorithms, such as keeping things sorted by priority for algorithms like A* pathfinding or similar priority-based modifications.  The functions make_heap(), push_heap(), sort_heap() and the rest of that family can make working with heaps very easy.  The data remains in a cache-friendly order for traversal, and can be modified easily.

#5236225 SQL, Ms Acess Question

Posted by frob on 22 June 2015 - 04:00 PM

Also be careful about database nulls.  They do not compare equal to anything, not even to other nulls. In databases, null is a state and not a value.
For the operand truth table, you've got:


Most likely, you're falling into one of those combinations on the table and accidentally propagating a null.

#5236077 Care to share some words of wisdom/advice, come click this thread.

Posted by frob on 21 June 2015 - 05:21 PM

Moved to the job section of the site.  Each of those questions (and many others like them) are addressed in this forum's FAQs.


Happy reading.

#5235984 Help creating sim game

Posted by frob on 21 June 2015 - 01:40 AM

Start smaller.

Much smaller.

Like "guess the number" and later "tic tac toe".

#5235915 LibGDX move to point

Posted by frob on 20 June 2015 - 02:17 PM

What do you mean by "normalize"...?

That's a good sign that you need more study of mathematics.  Games require significant amounts of math.


A normalized vector has unit length.  That is, if you combined the axis values into a directional arrow, that arrow would be length 1.


You compute it by finding the length of the vector and then dividing each axis by that length.  Since this is 2D, that is sqrt(x2+y2), then divide both x and y by the result.  Be sure to test for zero length vectors to avoid dividing by zero.

#5235570 Feedback to build good resume for game industr

Posted by frob on 18 June 2015 - 04:16 PM

In US and some other nations, attaching a photo is a bad idea due to discrimination concerns.


Depends on where you are on the globe, but some recruiters in US and UK will immediately dump the application if you include a photo.


Other HR screeners will remove photos or marital status information before passing the other details to the interviewers.


While Krohm dislikes the projects, I'd rather see that you have game related projects, even if they are not stellar.  It shows you have an interest.  At the entry level that is something one of the biggest signs that you are interested.

#5235505 Hi there, freshman here =]

Posted by frob on 18 June 2015 - 09:47 AM

i guess as josh said, ill stick to Java for now, learn everything i can in that field and then move on to another language, game engine etc'.
one last question though, where in this site can i view toturials, guides and stuff about that subject? i mean like basic stuff =]?

What "basic stuff", specifically?


You write in one post that you are familiar with these things, specifically:  

i am already familiar with most things pretty fluently (sorting algorithms, data structurs, just finished a Lempel ziv project 2 weeks ago =])

At a fundamental level, a GUI is little more than a few data collections.


You've got a collection of data, probably either some tree format or a flat structure with indexes, that contains all your UI elements. Each entry may have some callbacks/events/listeners for when the element is used, and may have a link to some renderable images or drawing options or whatever.


You update regularly and travel over the collection in a reasonable way that makes sense for your app, processing each collection entry in turn.


There are plenty of fun implementation details, but like almost all programming, it quickly boils down to the same boring fundamental data structures and algorithms. 

#5235463 Hi there, freshman here =]

Posted by frob on 18 June 2015 - 07:19 AM

If you've seen those tutorials, they (and the rest of the Internet) should be enough to help push through the barriers --- IF YOU ARE READY.

At this point in your education you are learning the foundations, the building blocks. A large game GUI is a big undertaking. You need to master all the pieces. You need to learn all the fundamental data structures and algorithms necessary to build that kind of system.

There are tutorials like those already mentioned, and more besides. If those are not enough, then keep learning the fundamentals until you do know enough. Even though you may not feel like all the stuff at school applies, it really does. At the fundamental level they teach during school are important. When they spend hours going over collections of data, over algorithms like sorting and searching, those are tools you will use every day for the whole career.

I'm not sure if the comments about making tetris and pong in a few days was meant to be serious, but it is good advice. You wrote that you built a checkers game. Next up probably are a pong clone, a falling block game (not necessarily tetris, but it is a popular one), a brekout/arkanoid game, etc. They will help with your learning.

#5234982 Slow down when using OpenMP with stl vector per thread

Posted by frob on 15 June 2015 - 05:48 PM

Well all that code is interesting.
It looks like you are trying to find the minimum path for each node to each other node, but rather than using an all-pairs algorithm, you are using a single-source algorithm and repeating it for every pair.

If you are serious about performance, use the right algorithm for the job.

There are several good all-pairs shortest path algorithms, like this and this.  If you really must do this for every point on your node, use A* which is generally faster than Dijkstra's algorithm; if you don't provide a heuristic value (which is the worst case for it) then A* degenerates into Dijkstra's. 

I was tempted to go through your code and do line-by-line reviews, but quickly ran out of time.

> for (int i=0; i<list.size(); i++)
Size of list never changes. Only test the value once.

> std::vector<float> min_distance;
> min_distance.clear(); <-- Was brand new object, why clearing it?
> min_distance.resize(n, max_weight); <-- Icky.

The function resize() is equivalent to -- and sometimes implemented as, calling pop_back() a bunch of times. Reserve the space first. You have potentially just caused n reallocations to trigger, and potentially just triggered n! (n factorial) moves.  Most standard library implementations use bigger buckets, but some of them only allocate in very small increments, a few memory-conscious implementations only increment by one by default.


> std::vector<int> previous;
> previous.clear();
> previous.resize(n, -1);

Same as above. You potentially just caused a bajillion unnecessary operations by not reserving the space.

> vertex_queue.erase(vertex_queue.begin());

Slow. You've just caused every element to be shifted by one position, calling bunches of move constructors and destructors in the process. You've got several of these in your algorithm. If you must do that pattern, start at the end and work backwards. Or use a data structure that has better handling of removal from the beginning, like a deque.

There are many more, but I'm out of time for now.




Still, start with the right algorithm, an all-node shortest path routine.  Then after you've got it, profile the code to remove all the crazy-huge unnecessary work you're doing.

#5234929 Slow down when using OpenMP with stl vector per thread

Posted by frob on 15 June 2015 - 12:07 PM


Wait, what? One line of code is not worth implementing?

It's not that easy - putting the reserve() in the inner loop does not change much: Still every thread has to allocate from heap.
I'd need to create memory objects for each core before the loop and change all involved functions to use those objects, making them less portable, readable and independent.
I'd end up creating my own containers and replacing STL completely - not worth for a pre-processing tool.



With the limited information you've given us, nobody knows.

What we can see in your code sample is that you create two vectors: min_distance, and previous. They have no sizes reserved and are passed into functions we cannot see.

All we are shown is "this grows both vectors" without any description, and without copies of those functions to study.

What happens inside those functions is a black box for what you've posted. For all we know, they could be doing thousands of .push_back() operations, causing an enormous number of re-allocations and moving the contents. If that is the case, a single .reserve() could after you create them could give a big performance difference.

There could be other issues in those functions that may also be tripping up parallelism, such as reading and writing from potentially shared buffers, potential locks, and potential other problems.


You need to share more code.  But from what you have shown, you don't reserve the right amount of space for your buffers.  Maybe that is the first thing you do in your functions, but without sharing the code, we don't know.



Our game uses a mix of our own thread class plus a job system where X number of threads pull jobs off a queue to run in parallel

Thanks for clarification. This raises another question i'm always thinking about.
On GPU multi threading means just 'Do the same small thing in parallel', let's call this 'parallelization'.
On CPU we can also do completely different things at same time, like one thread feeding graphics API, other thread doing game logic, another one for physics - call this 'multi-threading'
Now when graphics APIs go multi threaded, i assume parallelization is the way to go on CPU as well because better cache usage.
And multi-threading should only be used to a small degree to fight sync problems like 'doing nothing while waiting on a result from GPU'.
Is this true?



It gets complicated. There are many different methods and goals to make something run in parallel.

There are multi-processor parallel operations where each effectively operates as a data stream, basically what you get with GPU processing. There are SIMD parallel operations -- working on multiple pieces of data with a single instructions. There are parallel processes where chunks of work are handed off to other processes in a producer/consumer model. There are parallel processes where different processors handle different tasks and share work back and forth as they process. There are parallel processes where completely different processor architectures are used for different tasks based on what processing is faster on the other device. And many more!

Some problems are trivially parallel, and graphics rendering is one of them. It is really easy to break these into an enormous number of identical tasks and run them all independently.

Other problems can benefit from different types of parallel processing. Some, like a parallel search, can be simplified by dividing the space into n pieces and stopping all of them the moment any finds a match.

Other problems can be computed faster by building intermediate values on a single processor, like SIMD matrix multiply. A direct non-SIMD implementation requires 64 multiplications and 48 additions. A SIMD multiply requires 16 parallel multiplies and 12 parallel adds.

Still other problems require more comprehensive processing on multiple nodes, like parallel sorting.  Each node is doing it's own section of the sort, and communicating with other nodes as necessary, potentially even load balancing between machines. 


And other problems, particularly those with harder computational work within each node, can have wildly different tasks on each parallel node. Think more in terms of weather prediction supercomputers. 



As was written in your first reply, it is not a "magic wand".  A small number of problems are trivially parallelizable where you only need to tell the computer "do this in parallel".  most other applications that does not work work, and it requires thoughtful design. 


If you happen to have one of those trivially parallel tasks, and your program is fairly small and straightforward, then OpenMP can be a wonderful solution.  If it isn't, then not so much.