Tile Engine question

[Bakkon]

Oh, a nice comeback by Gyro. Let's see what Avan has to counter... What do you think Eatcomics?
Well I'd have to say that Gyro has this one wrapped up, and I think Avan's offense is lacking this season, but we'll just have to see... oh and the shot is up....

Goddamn, shut the fuck up.

[XianForce]

Hmm...

So, from what I'm seeing... It is NOT advantageous to make your map a dynamically allocated 3D array ?

That's what I've been using, just so I can specify the dimensions of the map at runtime...

[avansc]

At first i was not going to reply because i dont want this to be turned into something its not, that being this scenario where im just trying to disagree with you, or forks along those lines.

1. Having the map size being varied does not mean its "fuck knows what size", just means its not static, nothing stops you from calculating the size and knowing how much memory you have left.

2.Not sure what you mean by thrashing the heap, its one allocation, of contiguous memory.

3. yes i said dynamically allocating memory is VERY SLOW. but it was obviously a hyperbole. I think we call can agree that allocating at map change once is negligible. you will spend more time loading images in.

4. Smarter, more meaningful... well thats your opinion and thats fine. not sure if wasting space is smart or meaningful.

5. Wasting stack space can adversely affect stack intensive functions.

6. 4-8 BIGGER? no sure how you get to that.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define DEPTH 3
#define WIDTH 1024
#define HEIGHT 1024

void set(char *p, int l, int x, int y, char data)
{
	p[DEPTH*HEIGHT*l+WIDTH*y+x] = data;
}

char get(char *p, int l, int x, int y)
{
	return p[DEPTH*HEIGHT*l+WIDTH*y+x];
}

int main(int argc, char * const argv[])
{
	
	char stack[DEPTH][HEIGHT][WIDTH];
	
	printf("stack = %d\n", sizeof(stack));
	
	char* local = (char*)malloc(sizeof(char)*DEPTH*WIDTH*HEIGHT);
	char* mover = local;
	
	for(int a = 0;a < 3;a++)
		for(int b = 0;b < 1024;b++)
			for(int c = 0;c < 1024;c++)
				++mover;
	
	printf("heap = %d\n", mover - local);
	 
	getchar();
    return 0;
}

in closing i would just like to say in no way was i just trying to disagree, just said what i like to do and why.

[MrDeathNote]

3. yes i said dynamically allocating memory is VERY SLOW. but it was obviously a hyperbole. I think we call can agree that allocating at map change once is negligible. you will spend more time loading images in.

That really depends on if you have maps of different sizes, if you do then you need to reallocate every time or it kinda destroys the point of making it dynamic in the first place. If you have to reallocate every time you hit a warp that could cause problems, especially on DC and PSP.

[avansc]

3. yes i said dynamically allocating memory is VERY SLOW. but it was obviously a hyperbole. I think we call can agree that allocating at map change once is negligible. you will spend more time loading images in.

That really depends on if you have maps of different sizes, if you do then you need to reallocate every time or it kinda destroys the point of making it dynamic in the first place. If you have to reallocate every time you hit a warp that could cause problems, especially on DC and PSP.

Im not sure what you are trying to say, but the allocating time point is irrelevant, loading the actual map data and textures (disk access) is your bottle neck here. they will take MUCH MUCH longer then allocating memory on the heap.

Edit: here are some numbers so you can think about it

allocated [7][256][256] bytes on heap and stack, i was going to do 7.1024.1024 but the stack crapped out.

iterations 100,1000,10000,100000,100000
time for heap in microseconds 55,444,4393,44969,438256
time for stack in microseconds 1,3,28,282,3071

stack is faster by factor of 55x,148x,157x,159x,143x respectively

Now you can see why i said the heap** is VERY SLOW.


okay... now lets actually look at the numbers.

if you so happen to change the map 1000000 timer consecutively, you'll spend less than half a second allocating memory on the heap. yes its ~150 times faster on the stack. BUT, in no situation will you change the map that many times. its just not possible.

not if you were going to change the map ummm 2 or 3 times very fast (you go into a map and realize you dont need to and directly go back)
you will be spending less than a millionth of a second to allocate memory.

Ultimately, if you have a pallet or sprite sheet to load, or anything you have to load off disk, will take MUCH longer.

at 100 iterations to open and only READ ONE LINE of text from a file, it took 1391us, or 1.4 ms (im sure you can speed this up by maintaining open a few file pointers, as well as saving data in binary format ie, serialize objects so you can just read them in one big chunk).

[Falco Girgis]

At first i was not going to reply because i dont want this to be turned into something its not, that being this scenario where im just trying to disagree with you, or forks along those lines.

1. Having the map size being varied does not mean its "fuck knows what size", just means its not static, nothing stops you from calculating the size and knowing how much memory you have left.

2.Not sure what you mean by thrashing the heap, its one allocation, of contiguous memory.

3. yes i said dynamically allocating memory is VERY SLOW. but it was obviously a hyperbole. I think we call can agree that allocating at map change once is negligible. you will spend more time loading images in.

4. Smarter, more meaningful... well thats your opinion and thats fine. not sure if wasting space is smart or meaningful.

5. Wasting stack space can adversely affect stack intensive functions.

6. 4-8 BIGGER? no sure how you get to that.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define DEPTH 3
#define WIDTH 1024
#define HEIGHT 1024

void set(char *p, int l, int x, int y, char data)
{
	p[DEPTH*HEIGHT*l+WIDTH*y+x] = data;
}

char get(char *p, int l, int x, int y)
{
	return p[DEPTH*HEIGHT*l+WIDTH*y+x];
}

int main(int argc, char * const argv[])
{
	
	char stack[DEPTH][HEIGHT][WIDTH];
	
	printf("stack = %d\n", sizeof(stack));
	
	char* local = (char*)malloc(sizeof(char)*DEPTH*WIDTH*HEIGHT);
	char* mover = local;
	
	for(int a = 0;a < 3;a++)
		for(int b = 0;b < 1024;b++)
			for(int c = 0;c < 1024;c++)
				++mover;
	
	printf("heap = %d\n", mover - local);
	 
	getchar();
    return 0;
}

in closing i would just like to say in no way was i just trying to disagree, just said what i like to do and why.

1) Then you don't understand the point. Just because one particular map takes up 4k rather than 24k (which is the size of the largest map) doesn't mean that I have an additional 20k to fill up with assets and other allocations. The point is that you still have to have space remaining, because you're going to need that 20k for when you DO switch to your bigger map. It's smarter to just allocate one chunk with a set size, so that you know how much memory you ACTUALLY have to work with.

2) Yeah, it's one allocation of contiguous memory. And what happens when you SWITCH MAPS? You're deallocating a gigantic chunk of memory from the heap and allocating a new one. You're leaving giant holes in the heap, which IS "thrashing the heap."

3) Yes, it is negligible. In your previous post, you apparently thought it WASN'T negligible, because you felt the need to point out the fact that it was "much slower." You're changing your mind now, and that's called hypocrisy. You have a pretty well documented tendency to chose whatever side the mainstream is against.

4) YOUR method wastes space. See number 6.

5) Absolute fucking bullshit. If you think that the amount of data sitting on the stack has ANY affect on speed, you obviously have no clue how a stack or frame pointers work.

6) How big is a pointer? 4 bytes on 32-bit machines, and 8 bytes on 64-bit machines. How big is a character? 1 byte. In order for your method to even have ANY memory advantage whatsoever, your map has to be 4 to 8 times SMALLER than the static character method, which nullifies your entire point. You aren't even saving space with this method.

Your code example isn't even fair. You CLEARLY said:

Code: Select all

i prefer doing ***tiles. here is why.

that you prefer POINTERS. You're allocating CHARACTERS on the heap, which is what I said. Why don't you go code up an example that dynamically allocates POINTERS as you said and compare it to a map of CHARACTERS? You don't get to change your argument in the middle just because you were CLEARLY full of shit.

The argument was about dynamically allocating a 2D array of pointers to tiles (Tile*** for every map location) versus a static 2D array of characters. It was NOT about simple heap vs stack character allocation.

You're arguing for something that's uglier, slower, and actually larger (unless it's less than a quarter to an eighth the size of the character approach). The fact that you're even still arguing proves that you are just arguing for the sake of arguing.

Maybe you should stop trying so hard to make other people look bad and take a look at your own goddamn posts.

[Falco Girgis]

3. yes i said dynamically allocating memory is VERY SLOW. but it was obviously a hyperbole. I think we call can agree that allocating at map change once is negligible. you will spend more time loading images in.

That really depends on if you have maps of different sizes, if you do then you need to reallocate every time or it kinda destroys the point of making it dynamic in the first place. If you have to reallocate every time you hit a warp that could cause problems, especially on DC and PSP.

Yeah, it's not going to be a big deal at all on a PC. There's absolutely nothing wrong with allocating it on the heap. You have 4GB of virtual memory. On an embedded system (DC/PSP), you have 16-32MB (which is already over half taken up by other things). You can't just be allocating and deallocating gigantic chunks of memory every time you hit a warp.

[RyanPridgeon]

Isn't this just a simple design choice?

The benefits and problems of each method have already been listed thoroughly. @OP: In the end it's just something you'll have to decide on. Sometimes it works better to use heap allocation, and sometimes stack. Depends what you're aiming for, like Gyro said, heap can be pretty problematic on less powerful / lower memory systems, but stack can get messy & limited if you're going to be using a large map, for example, on the PC.

[avansc]

look, im not trying to make you look bad. an i was not being hypocritical with the dynamic allocation,comparatively the heap is dog slow to the stack, but that does not mean its too slow, id avoid using it in a loop, but its fine to allocate memory at the start.

you comment about leaving holes in the memory... you telling me that memory is not usable? im not sure what you mean.

yes to be fair i said char*** (altho i think making it char* and indexing my self does not really constitute a giant design change.)
but never the less.

i used some profiling tools because i was struggling to get a absolute memory usages, im not 100 percent confident that this is accurate, but i double checked and
have enough confidence to say that its most likely correct



so char map[Z][Y][X] uses 192KB (3*256*256/1024)

and char ***pmap, uses a total of 192KB+6KB+32B, so a fraction over 198 KB, so if the sizes were the same.. the ***char would use 1.03 times as much memory.
note: sizeof(char*) == sizeof(char*****************)

anyways, it really does not matter, i didnt mean to offend you, or try and make you look bad or anything like that. just throwing an opinion out there. so i apologize.


edit: id just like to add that doing it with char*** CAN fragment the memory, so its best if you so choose to do it dynamically allocate it char* and do the indexing your self. and if you do that it will be same size.

[RyanPridgeon]

If you're heap allocating a multi dimensional array only once, wouldn't it be better to malloc all in one go then point to seperate parts?

Code: Select all

#include <stdlib.h>

int** map; // 2d map array

int main(int argc, char** argv){
    int i, width, height;
    int* memory;

    width = 5; // can be dynamic
    height = 5;

    memory = (int*)malloc(sizeof(int)*width*height); // one contiguous block of memory

    map = (int**)malloc(sizeof(int*)*width);
    for (i = 0; i < width; i++){
        map[i] = memory + i*height;
    }

    return 0;
}

[avansc]

If you're heap allocating a multi dimensional array only once, wouldn't it be better to malloc all in one go then point to seperate parts?

Code: Select all

#include <stdlib.h>

int** map; // 2d map array

int main(int argc, char** argv){
    int i, width, height;
    int* memory;

    width = 5; // can be dynamic
    height = 5;

    memory = (int*)malloc(sizeof(int)*width*height); // one contiguous block of memory

    map = (int**)malloc(sizeof(int*)*width);
    for (i = 0; i < width; i++){
        map[i] = memory + i*height;
    }

    return 0;
}

yup, one of my previous post does exactly that, well you make a map** for the indexing, in my example i just do that self. but same difference.

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define DEPTH 3
#define WIDTH 1024
#define HEIGHT 1024

void set(char *p, int l, int x, int y, char data)
{
   p[DEPTH*HEIGHT*l+WIDTH*y+x] = data;
}

char get(char *p, int l, int x, int y)
{
   return p[DEPTH*HEIGHT*l+WIDTH*y+x];
}

int main(int argc, char * const argv[])
{
   
   char stack[DEPTH][HEIGHT][WIDTH];
   
   printf("stack = %d\n", sizeof(stack));
   
   char* local = (char*)malloc(sizeof(char)*DEPTH*WIDTH*HEIGHT);
   char* mover = local;
   
   for(int a = 0;a < 3;a++)
      for(int b = 0;b < 1024;b++)
         for(int c = 0;c < 1024;c++)
            ++mover;
   
   printf("heap = %d\n", mover - local);
    
   getchar();
    return 0;
}

[Falco Girgis]

I'm going to have to look at just how you're measuring the RAM usage when I get home. But that cannot be correct.

Yes, sizeof(char*) == sizeof(char********). But sizeof(char*) is 4/8bytes while sizeof(char) is just a single byte. Your method MUST use way more than mine.

[avansc]

I'm going to have to look at just how you're measuring the RAM usage when I get home. But that cannot be correct.

Yes, sizeof(char*) == sizeof(char********). But sizeof(char*) is 4/8bytes while sizeof(char) is just a single byte. Your method MUST use way more than mine.

kk.

and yeah it confused me for a bit too,

this is how it breaks down. (i think at least)

Code: Select all

char ***pmap = (char***)malloc(sizeof(char**)*Z);

pmap*** is 3 pointers and the pointer to the identifier pmap, so thats where 32Bytes come form. (the *** has nothing to do with 3, Z is defined as being 3, and the extra 8 bytes i can only assuming is a pointer to the pmap identifier address)

so that gives us 8*4 = 32Bytes

Code: Select all

pmap[z] = (char**)malloc(sizeof(char*)*Y);

pmap[z] (can be 0 - 2, the three pointers we allocated), each one gets allocated space for 256 pointers, so
3*256*8 = 6144 Bytes or 6KB

now we are done allocating pointers, we have all the pointers we need to represent the depth and height of the map, the width are allocated as characters. IE just 1 byte.

Code: Select all

pmap[z][y] = (char*)malloc(sizeof(char)*X);

pmap[z][y] (z goes 0 to 2, y goes 0 to 255) each one gets allocated 256 bytes.

so that gives up 3*256*256*1 bytes = 196608 bytes or, 192 KB.

so, all together we have 192KB+6KB+32B, thus comes to a fraction over 198KB.

[MrDeathNote]

I'm going to have to look at just how you're measuring the RAM usage when I get home. But that cannot be correct.

Yes, sizeof(char*) == sizeof(char********). But sizeof(char*) is 4/8bytes while sizeof(char) is just a single byte. Your method MUST use way more than mine.

kk.

and yeah it confused me for a bit too,

this is how it breaks down. (i think at least)

Code: Select all

char ***pmap = (char***)malloc(sizeof(char**)*Z);

pmap*** is 3 pointers and the pointer to the identifier pmap, so thats where 32Bytes come form. (the *** has nothing to do with 3, Z is defined as being 3, and the extra 8 bytes i can only assuming is a pointer to the pmap identifier address)

so that gives us 8*4 = 32Bytes

Code: Select all

pmap[z] = (char**)malloc(sizeof(char*)*Y);

pmap[z] (can be 0 - 2, the three pointers we allocated), each one gets allocated space for 256 pointers, so
3*256*8 = 6144 Bytes or 6KB

now we are done allocating pointers, we have all the pointers we need to represent the depth and height of the map, the width are allocated as characters. IE just 1 byte.

Code: Select all

pmap[z][y] = (char*)malloc(sizeof(char)*X);

pmap[z][y] (z goes 0 to 2, y goes 0 to 255) each one gets allocated 256 bytes.

so that gives up 3*256*256*1 bytes = 196608 bytes or, 192 KB.

so, all together we have 192KB+6KB+32B, thus comes to a fraction over 198KB.

Right, i see where your getting that and it makes sense. But its still too slow to use for embedded systems. It would be fine if you only had one map, or one map size but that would be a pretty shit game and ruins your whole point. Youd have to reallocate the memory every map change, this is gonna be a noticable performance hit for DC/PSP. So i guess it's fine to use your method on PC but not for embedded systems.

[avansc]

yeah i cant comment on that with certainty, never developed for either of those platforms,

however, i will wager that dynamic memory allocation(depending on size but he mentioned 24K) does not take more than a millisecond one either platform.

AND IVE SAID THIS BEFORE! if he is loading in graphics and the map from the file system, that will take MUCH longer than any memory allocation.