@WhattayaBrian What is your job?

First Riot Post
Comment below rating threshold, click here to show it.

AtlaStar

Senior Member

11-13-2012

Quote:
Originally Posted by WhattayaBrian View Post

So, in school, you're generally taught about time and space complexity of algorithms, but those are not the only aspects that determine a data structure's or algorithm's runtime speed. Another huge part of those determinations is Locality of Reference. That is to say, contiguous data is best data.

So the "classic" definition of a binary tree involves something like this:

struct Node
{
MyData data;
Node * left;
Node * right;
};

And whenever you need a new child, you do something like:

node->left = new Node;

But, barring overloading operator new(), these allocations are fragmenting your data. If you're traversing through a tree, you may repeatedly cache miss as you go from child to child, heavily impacting your runtime.

One alternative is to use an array to hold your binary tree. The parent is index 0, and the children of any index follow this pattern:

left = 2n + 1
right = 2n + 2

As a natural consequence of this, a breadth-first search is just an iteration from beginning to end of the entire array. That's pretty neat.

But do you want to do that? Well, what are we using this tree for? Is it used a lot, or a little? Is it a heap? Is it being used for breadth-first or depth-first searches? Are things being removed from it constantly?

The algorithms are extremely important, but so are the underlying data structures. In some situations, you may want to resize this "array-based binary tree" just like a vector would when it hits its cap. But if "MyData" is large, maybe that's to large a cost. Maybe instead we implement blocks of memory like a deque, so that we never have to move things and we still get lots of locality of reference. But if we're doing depth-first searches, we could be jumping blocks all the time, which is bad...

My lesson to you is this: programming is about using the right tool for the job, but the reason it's so hard is that there's a lot of stuff to consider. :P

(Also you can pretty much always use vector because locality of reference is that powerful.)
In all honesty I'm a self taught programmer, and I never really considered the consequences of fragmenting your data.

So what I presume you are saying is that fragmentation like this causes only part of the data structure to be cached since calling new doesn't care about locality essentially...which is why a vector is so powerful I take it. because when it is created it allocates memory in a way that it selects a RAM slice for the whole data structure like an array, but allows you to dynamically alter the size unlike an array...good information to know, and something I had never considered before.

So that being said I feel it safe to assume that a BST would only really be useful in a data structure so large that locality of reference isn't possible? Say a data structure that holds 50,000 references to a class that stores an int and a char array of size 20? or would 1,200,000 bytes of ram (around 1171 KB) still be small enough to share the same slice of RAM efficiently enough to justify using vector


Comment below rating threshold, click here to show it.

WhattayaBrian

Engineer

11-13-2012
10 of 10 Riot Posts

Quote:
Originally Posted by AtlaStar View Post
In all honesty I'm a self taught programmer, and I never really considered the consequences of fragmenting your data.

So what I presume you are saying is that fragmentation like this causes only part of the data structure to be cached since calling new doesn't care about locality essentially...which is why a vector is so powerful I take it. because when it is created it allocates memory in a way that it selects a RAM slice for the whole data structure like an array, but allows you to dynamically alter the size unlike an array...good information to know, and something I had never considered before.

So that being said I feel it safe to assume that a BST would only really be useful in a data structure so large that locality of reference isn't possible? Say a data structure that holds 50,000 references to a class that stores an int and a char array of size 20? or would 1,200,000 bytes of ram (around 1171 KB) still be small enough to share the same slice of RAM efficiently enough to justify using vector
Hard to say! That's why we benchmark.

You can get a feel for certain qualitative measurements: "little" vs "lot", but nothing beats straight up perf testing.


Comment below rating threshold, click here to show it.

AtlaStar

Senior Member

11-13-2012

Quote:
Originally Posted by WhattayaBrian View Post
Hard to say! That's why we benchmark.

You can get a feel for certain qualitative measurements: "little" vs "lot", but nothing beats straight up perf testing.
Good to know! thanks for taking the time to answer, and definitely thank you for the insight!


Comment below rating threshold, click here to show it.

Lagom0rph

Junior Member

11-13-2012

Quote:
Originally Posted by AtlaStar View Post
In all honesty I'm a self taught programmer, and I never really considered the consequences of fragmenting your data.

So what I presume you are saying is that fragmentation like this causes only part of the data structure to be cached since calling new doesn't care about locality essentially...which is why a vector is so powerful I take it. because when it is created it allocates memory in a way that it selects a RAM slice for the whole data structure like an array, but allows you to dynamically alter the size unlike an array...good information to know, and something I had never considered before.

So that being said I feel it safe to assume that a BST would only really be useful in a data structure so large that locality of reference isn't possible? Say a data structure that holds 50,000 references to a class that stores an int and a char array of size 20? or would 1,200,000 bytes of ram (around 1171 KB) still be small enough to share the same slice of RAM efficiently enough to justify using vector
There is more than one level of caching. You're either dealing with something HUGE or just doing it wrong if you're consistently going all the way out to RAM. (In the context of most run-time video game applications.)
Low level caches might be referred to as the L1 and the L2 cache. These are chunks of memory that actually reside ON your processor. (The L1 might be per processor with the L2 shared by multiple cores, for example.) You can typically find exact values for the size of those buffers even as a consumer purchasing CPUs on your own. (But that variability for PC games is one thing that actually makes console games easier to ultra-optimize for in a way.)


Comment below rating threshold, click here to show it.

babyriots

Senior Member

11-13-2012

Quote:
Originally Posted by WhattayaBrian View Post
Hard to say! That's why we benchmark.

You can get a feel for certain qualitative measurements: "little" vs "lot", but nothing beats straight up perf testing.
Do you like fish sticks?


Comment below rating threshold, click here to show it.

Gurei Fullbuster

Senior Member

11-13-2012

Thank you for taking time out of your day to talk with us Brian. I personally am going to bookmark this thread, as I am also a programmer in training (going for CS degree atm).