Asking about base types (eventually)

My apologies in advance if this is the wrong place for this.

I'm currently in the early stages of developing a game, specifically creating the 'building blocks'. With this game being turn-based, I am concentrating more on memory economy than processor usage. For this and other reasons, I have started working on a 'variable-size variable' to hold values of different sizes. Here is a code fragment that I whipped up on this computer. Since it wasn't my computer, I'm afraid error-checking has been restricted to a quick once-over.

Code:

// Conceptual example of dynamically-sized variable.
// Assumes single-byte alignment for space efficiency.
template <class hold_val> struct var_var {
	BYTE *ptr[sizeof(hold_var)];

	var_var() // Complete version will have more constructors.
	{
		for(register int i=0;i<(sizeof(hold_val));i++) {
			ptr[i] = new BYTE;
			*ptr[i] = 0;
		}
	}
	~var_var()
	{
		for(register int i=0;i<(sizeof(hold_val));i++) {
			delete ptr[i];
		}
	}
};

While I'll explain the theory if asked, the main point is this: hold_val is an integer of a size sufficient to hold the value being stored. With, say, 16-bit or 32-bit integers this is no problem, but with 48 or 72-bit values, for example, the predefined integer types won't do. So, I'm asking if someone can tell me how the predefined types are made so I can copy that technique to make my own non-standard sizes.

I'm really confused by what you are trying to do. So you want to allocate space for the struct based on the size of the template class? Could you explain in more detail what you want to do and especially why you want to do it?

I think ruthgrin wants a 72 bit number.

You can't use a built-in type for that.

That still doesn't explain the struct. If he wanted to store an n-byte value, then he might do something like:

Code:

template <int n> 
struct NByte
{
   BYTE array[n];
}

which also seems pretty useless.

So, I'm asking if someone can tell me how the predefined types are made so I can copy that technique to make my own non-standard sizes.

I think the OP wants to see the code for a built-in type, or something, to copy it as a larger number.

Maybe not. That's the best I could make out.

BTW, you can use a class as a template parameter.

I usually have trouble explaining what I'm thinking. I'll try elaborating.

Reply 1:
I'm really confused by what you are trying to do. So you want to allocate space for the struct based on the size of the template class? Could you explain in more detail what you want to do and especially why you want to do it?

What I'm trying to do is make a variable (which might not be the best word) whose size dynamically resizes to take up the minimum amount of space (to the nearest byte) required to hold a given integer value. To cut down on the code size posted, I only put up a small portion of the structure, objects of which could be used in place of integers or other simple value holding types. Parts that weren't presented include those responsible for 'resizing' the 'variable' (by creating a new instance of var_var that had the appropriate size, copying the data into it, deleting the now obsolete var_var and returning a reference/pointer to the new one) and those responsible for translating the stored data into (presumably) an integer value (done by creating a temporary variable of type hold_val to hold the value, at which point the temp variable could by used for relevent calculations/returned, depending on the situation).

While I'm not sure if this is actually correct, I think that memory fragmentation (caused by smaller blocks of memory being freed that aren't large enough for, say, large object types) is one of the issues which results in allocation failing due to no sufficiently large block of memory being available. This is why I employ the byte-size-value pointers despite their memory footprint and dynam-alloc the individual bytes, in the hope that they will instead occupy these small blocks of memory that are otherwise useless.

As for why I want to do it. The simplest way I can think of putting it is so that I don't have to know the size of a variable at compile-time. The reason for dynamic resizing, aside from occupying the smallest amount of memory at any one time, is to handle extreme
possible value ranges. For example, if Level is unlikely to exceed 60 during typical game play, then having it as a 32-bit integer is a waste of space. On the other hand, since I don't plan on limiting the value of Level to something like 99, a longer game might result in a level above 255/256, making it too large for a char to hold. This sort of broad range makes it impractical to choose a smallest-footprint variable at compile-time and I expect many similar situations to pop up elsewhere in the game. Since I seem to have forgotten to mention it elsewhere, I'm actually a beginner to programming, so if I'm missing something seemingly obvious, please let me know.

Finally, in case it hasn't been explained well enough, the line

Code:

BYTE *ptr[sizeof(hold_var)]

is an array of pointers to bytes. Since var_var is supposed to be capable of holding the value of a hold_var, it seems logical that the array should point to the same number of bytes as hold_var occupies. I hope that answers your questions.

Reply 4:
I think the OP wants to see the code for a built-in type, or something, to copy it as a larger number.

Maybe not. That's the best I could make out.

BTW, you can use a class as a template parameter.

The idea is basically to be capable of making my own integers that have sizes and value ranges not found in the standard library, so I don't have to use a 32-bit integer to hold a value only slightly too large for a 16-bit integer, or so that I can handle numbers larger than 64-bits (I admit this seems beyond reason, but I'm trying to prevent all the problems I can forsee). I realize that some of the information I gave may seem excessive, but I figure that it's preferable to give more information than less.


I think that constitutes an attempt to answer all your questions. If necessary, I could probably post a 'working' version with troubleshooting information, but I doubt it would be a small amount of code and I'm not too sure on the policy regarding maximum postable code size, so if any of you know, please include that information with requests.

Have you realized that your approach is actually using much more memory then the normal way.
e.g.
if you want to allocate a variable in the range of a short. That would be normally be 2 bytes.
Doing it your way you will have a var_var that contains 2 pointers to byte. on ia32 that would be 8-bytes plus the actual 2 bytes ( witch would normally occupy much more then 2 bytes because of the granularity of the memorymanager ) plus your var_var would need some more space for some book-keeping variables to know the size of the actual value it manages.
So you would end up with minimum 11 bytes of used memory instead of just 2. plus the trouble you would have to actually be able to use your var_var to do useful calculations.
I would say that doesn't make much sense
Kurt

Indeed, aside from the learning experience of implementing arithmetic primitives, the idea is utterly useless. Even in the ideal case, the memory savings would be irrelevant. The thing that costs memory is game resources: sound and graphics. Everything else is peanuts.

The built-in types of C or C++ have a strong logical link to the type of data that hardware, i.e., the processors that are built with high-level language support in mind, has support for directly (in the machine-code instruction set). To take the PowerPC 970 (the G5) processor as an example, it has direct support for 8-, 16-, 32-, 64- and 128-bit integer data in various forms, signed and unsigned, and 32- and 64-bit floating point data. What you want to achieve is basicly a user-defined type of N-bits and operations on this type like unary +, unary -, binary +, binary -, multiplication, division, modulo, logical NOT, logical AND, logical OR, logical XOR, etc, etc, and possible conversions between built-in integer types and your user-defined integer type.
In C++ you can use operator overloading, and in C just simle functions or macros. You should work out the algorithms for the arithmetics you want to operate on your type and then you can bear in mind also that it will most probably not be as efficient as using built-in types because more instructions will be involved, but that is natural of course! In your structure or class you can use an array for a type of known bit-length, etc. Figure out what is efficient for your target platforms, using 8-, 16- or 32-bit, etc, as the element type for that array/vector. Hope this gives you some usefull idéas. Remember, C/C++ built-in types was designed with the typical bit-ranges modelled on the typical bit-lengths of registers in the commonly available processors of the time those languages were invented, but it is up to the compiler to select the instruction-stream for the operations, and it does not have to be single-instructions, although that is often the idéa with built-in types, that they shall be very efficient, yielding the most efficient instruction stream.

I would've posted sooner, but I've been a bit occupied. Since my previous attempt at a post just went up in smoke, I'll be comparatively brief.

Have you realized that your approach is actually using much more memory then the normal way.
e.g.
if you want to allocate a variable in the range of a short. That would be normally be 2 bytes.
Doing it your way you will have a var_var that contains 2 pointers to byte. on ia32 that would be 8-bytes plus the actual 2 bytes ( witch would normally occupy much more then 2 bytes because of the granularity of the memorymanager ) plus your var_var would need some more space for some book-keeping variables to know the size of the actual value it manages.
So you would end up with minimum 11 bytes of used memory instead of just 2. plus the trouble you would have to actually be able to use your var_var to do useful calculations.
I would say that doesn't make much sense
Kurt

Within a minute of logging off. I've since been working on a version which I hope will leave me looking less like a dunce.

Indeed, aside from the learning experience of implementing arithmetic primitives, the idea is utterly useless. Even in the ideal case, the memory savings would be irrelevant. The thing that costs memory is game resources: sound and graphics. Everything else is peanuts.

While I haven't worked on graphics or sound, I suspect this game might be an exception to the rule.

The built-in types of C or C++ have a strong logical link to the type of data that hardware, i.e., the processors that are built with high-level language support in mind, has support for directly (in the machine-code instruction set). To take the PowerPC 970 (the G5) processor as an example, it has direct support for 8-, 16-, 32-, 64- and 128-bit integer data in various forms, signed and unsigned, and 32- and 64-bit floating point data. What you want to achieve is basicly a user-defined type of N-bits and operations on this type like unary +, unary -, binary +, binary -, multiplication, division, modulo, logical NOT, logical AND, logical OR, logical XOR, etc, etc, and possible conversions between built-in integer types and your user-defined integer type.
In C++ you can use operator overloading, and in C just simle functions or macros. You should work out the algorithms for the arithmetics you want to operate on your type and then you can bear in mind also that it will most probably not be as efficient as using built-in types because more instructions will be involved, but that is natural of course! In your structure or class you can use an array for a type of known bit-length, etc. Figure out what is efficient for your target platforms, using 8-, 16- or 32-bit, etc, as the element type for that array/vector. Hope this gives you some usefull idéas. Remember, C/C++ built-in types was designed with the typical bit-ranges modelled on the typical bit-lengths of registers in the commonly available processors of the time those languages were invented, but it is up to the compiler to select the instruction-stream for the operations, and it does not have to be single-instructions, although that is often the idéa with built-in types, that they shall be very efficient, yielding the most efficient instruction stream.

Thanks, that's some of the information I was after. Can you please elaborate a couple of points?:
1. Even if a 24-bit variable occupied a 32-bit register, it would still only take up 3 bytes in RAM right?
2. Does that mean that the maximum size of a variable such as an integer is hardware-dependent?

Hopefully attached to this is a trimmed-down WIP of my current effort. I'm afraid only the + operator is implemented and only for limited situations, but it's enough for this example. Yes, I realize that it takes 9 bytes to store a 1 byte value, more on that below.

Firstly, is there any 'conventional' way to make smaller pointers (say, ones that only take the lower 8 bits of an address in the local area, or store the difference between the pointer's address and the target)?
Second, is there a trick around using virtual pointers (like using typeid() on the object being pointed to, then using the result of that to call the correct function, or would the information typeid() needs add to the size of the object as well)?

Thanks for your help so far.

Originally Posted by ruthgrin

1. Even if a 24-bit variable occupied a 32-bit register, it would still only take up 3 bytes in RAM right?

The x86 doesn't have any 24-bit variables, so you'd have to emulate, probably with three 8-bits. If so, chances are that it doesn't map to a 32-bit register, thus slowing it down a lot. Chances are also that your compiler won't care about your want of memory savings and pad the variable to 32 bits anyway, unless you explicitely tell it not to.
EDIT: This is actually incorrect. It's possible to create 24-bit variables using the explicit bitcount. But I believe that can be done only within structures.

2. Does that mean that the maximum size of a variable such as an integer is hardware-dependent?

Effectively, yes, in more than one way. The maximum size depends on various factors:
1) The largest unit that can be processed in a single step is limited by the register size.
2) The largest possible variable is limited by physical memory, address space, and most importantly free memory. (Unless you come up with a chunked representation for the really big stuff, you eventually won't find a large enough continuous block of free memory.)
On the other hand, none of the latter restriction will ever touch you unless you're doing numeric games with a few thousand or much much more digits.

Firstly, is there any 'conventional' way to make smaller pointers (say, ones that only take the lower 8 bits of an address in the local area, or store the difference between the pointer's address and the target)?

Nope, no conventional way. It's possible to store one pointer and then offsets, of course, but that's yet another severe performance impact.


Tell me, why don't you write your game first and then find out whether this low-level stuff makes any sense? Chances are that it won't.

I believe this information will prove enriching, as will the (diversity of terminology?) in your replies. While I am currently encountering other problems in relation to making my little project work without virtual pointers, they are unrelated to this thread and will be posted elsewhere if I am unable to resolve them myself.

Tell me, why don't you write your game first and then find out whether this low-level stuff makes any sense? Chances are that it won't.

While it would be preferable for the end product to be functional, I'll be quite content with simply learning more information and techniques that can be applied elsewhere. As I said previously, I'm still a beginner so that is the greatest priority for me at present.

If you want to learn something, here it is: Memory is cheap. The space you may (or may not) gain is not worth the problems and complexity that you are introducing into your design. Try to learn to write clear and simple code and you will be much better off. Trust me, when you get knee-deep in coding this thing, it will be complex enough.