Concepts of memory

Hello,

I had a few questions about memory. I scraped up these lectures today while wandering the web.
Free Online Computer Science Course | Bits | Harvard Extension School

While listening to the lectures about entropy and bit storage I couldn't help but feel like I was using way to much data over the course of my programs. In situations where I use built in data types like int that never reach anywhere near their maximum possibility am I wasting a ton of data at runtime if my average number in my program only uses numbers under 1000?

If a 32 bit int is used for a number that has a max value of 1000 (and never is negative) am I wasting 21 bits for every integer I declare in the program? If I had say 1000 classes active that all carried these integers in them would I be wasting 21,000 bits as it could be reprsented as 11 bits (or possibly less using frequency compression concepts) of information instead?

If these do reduce space is it storage space (size of the file) or the runtime memory I guess that you would see in the RAM.

Sorry if one question turned into five. I just became paranoid that I was throwing tons of bits in the trash (declaring and alloting but never using them) in my programs.

I realized I am kinda confused on the subject.

You have to calm down. I remember that when memory was precious, people in C used to handle unions so that they can gain some space. I think you are overreacting :)

In gaming memory still is precious. ;o)

Have you ever looked into how many games treat memory?

The point is, int is easiest to handle. You don't have to think too much about it, and the CPU is usually most efficient with it. Unless you're in a situation where memory is really scarce or you have millions and millions of data points (not just a few thousand), stay with int.

You can use short if you want to really save memory, but on modern computers the difference is so negligible that it's usually not worth the hassle.

Edit: Also, i don't think there is a guarantee from the standard that a short is less than an int, so it might not get you a memory advantage in the end anyways.

Quote:

---

Originally Posted by Neo1

Edit: Also, i don't think there is a guarantee from the standard that a short is less than an int, so it might not get you a memory advantage in the end anyways.

---

If you're ever in the situation where you have to care about the size of your data, use the <cstdint> header. It contains types with guaranteed sizes. For example, int16_t is guaranteed to have 16 bits (but is not guaranteed to actually exist), while int_least16_t is guaranteed to exist, guaranteed to have at least 16 bits, and will be the smallest such type the compiler can provide. (Meaning that on an architecture with 9-bit bytes, it might be 18 bits large, or even 36 bits if the machine cannot address smaller things, but there won't be a different type that you could use instead.)

Lesshardtofind, you are talking like a hardware designer! (Not a bad thing)

Memory usage and performance are inextricably linked through the CPU cache. The more data you can fit in cache, the fewer cache misses per datum will be incurred. However, the processor might be faster when working with some data types rather than others. The tradeoff may be different from processor to processor. And the data access pattern matters as well -- the CPU/cache may be efficient at streaming access but worse at random access.

Let actual requirements drive your decisions, not some vague need to be "more efficient." Decide how much memory you need the thing to use and how fast it has to work, then figure out how to satisfy those requirements.

Thanks for the responses all. I appreciate the information.

I have read some more about how the processor has trouble handling things smaller than 32 bits or sometimes just won't. So I thought of some ways to make one int represent multiple different types of data so that all 32 bits were used, but I realized the drawback would come with arithmetic when needing to perform arithmetic one data point in the integer as I woukd either have to write my own functions for this arithmetic or just seperate them which would require more CPU calls and probably negate any memory saved.

Though I guess when transfering data, compressing two or three int into one could save space and also maybe with file save functions reducing every variable down to only its needed size could be useful.

As for the why I am so interested in saving space: I am producing a game for the Indie xboxlive market and I have run into a few points where I can't do what I want with my classes because having 500 (bullets) on the screen at once starts to slow the gpu. I realize that 250 bullets that do twice the damage would accomplish the same, but I want some boss battles to be visually overwhelming for the user, making deaths more likely to occur.

As with any new subjects that I learn every answer I find has my brain posing six more questions on its implications. I am starting to wonder if these frameworks (XNA game studio). Carry a bit of overhead along with them.

I did notice no one has addressed the example as to if these 21 bits are wasted as file size memory or ram.

Also I learned how to make a particle engine from a tutorial site and just recently thought about the fact that the author had said to put a particle owning a texture. Well if I have 5000 particles on screen (which I do occasionally.) And they all share one picture why do I have 5000 diff particle textures when the engine could just own one and pass it to the renderer. While I would still have to make 5000 calls with the texture I am guessing it would reduce file size but overhead woukd still be the same.

Quote:

---

Originally Posted by Neo1

i don't think there is a guarantee from the standard that a short is less than an int, so it might not get you a memory advantage in the end anyways.

---

what the standard guarantees is this: sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long)

long long is only part of the new C++11 standard, but existed as an extension in many compilers before.

Memory is cheap, but the cache is small. So it is ok to have a large resevoir of infriquently accessed data in memory. But for things that are frequently accessed, you want to try to limmit it to as few 64 -Byte chunchs as you can.

This does mean that there is some speedup to having arrays use char or short instead of int, but typical classes are less than 64 bytes, so shrinking them further is generally pointless. In those cases, using int is prefered, because that's the easiest thing for the CPU to handle.

Quote:

---

As for the why I am so interested in saving space: I am producing a game for the Indie xboxlive market and I have run into a few points where I can't do what I want with my classes because having 500 (bullets) on the screen at once starts to slow the gpu.

---

I think it's rather unlikely that this has anything to do with memory. But you would have to profile your game to find out where it really spends its time.
Anyway, the GPU generally deals in single-precision floats (32 bits) and there's little you can do about it. GPUs are, after all, pretty specialized in what they do. They have very impressive data throughput, but at the cost of generality.
So generally speaking, changing from 32-bit integers to 16-bit integers is going to do absolutely nothing to the GPU because it won't ever see the difference.

Well one of the lectures covered that data can only be transfered error free when the Channel capacity is not exceeded. It was another lecture on Shannon's rules about data transfer. Thats where I was thinkng reducing the amount of data required to make a graphical command through the system would reduce the chance of errors or (appearance of lag) on the screen, but as you pointed out without a profiler I have not idea what is actually lagging the system.

I could be guessing that the GPU is overloaded when its just waiting on the CPU to give it coordinates and vice versa. I will have to look into how to profile a XNA Game_Sudio 4.0 file in VS 2010 express. I should have just started at that solution, but the lectures really opened my mind to how data works and I wanted to apply the information lol.

You first need to see what the APIs require, so what actual data structure the graphical methods have that will transfer it to the GPU. So if you were to change the color of a set of pixels and you are passing an array, this question makes sense if you actually have a choice between int16 and int32 on the given API, which I would doubt. The point is that you most likely want to avoid trasnforming your data all the time, so compressing the data to save space can mean that the GPU will be waiting for the CPU to decompress the data before it passes it.

Quote:

---

Originally Posted by Elkvis

what the standard guarantees is this: sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long)

---

Not true. In practice it usually works out that sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long). However, that is not actually a requirement in the standard.

The standard only requires that the set of values that can be represented by a char is a subset of the values that can be represented by a short, which in turn is a subset of the values that can be represented by a short .....

Actually, the standard is even weirder than that, specifying (in [basic.fundamental]p2): "There are five standard signed integer types : “signed char”, “short int”, “int”, “long int”, and “long long int”. In this list, each type provides at least as much storage as those preceding it in the list."
The fun thing? The standard never defines what "providing storage" means. So it's actually somewhat open to interpretation. I would personally actually go more with the sizeof interpretation than the value range interpretation.
I don't have the C standard to check what that says, though.

Quote:

---

Originally Posted by grumpy

Not true.
....
The standard only requires that the set of values that can be represented by a char is a subset of the values that can be represented by a short, which in turn is a subset of the values that can be represented by a short .....

---

How are those two different ?
Can you give an example? (Sticking to integral types)

Quote:

---

Originally Posted by CornedBee

The fun thing? The standard never defines what "providing storage" means. So it's actually somewhat open to interpretation. I would personally actually go more with the sizeof interpretation than the value range interpretation.
I don't have the C standard to check what that says, though.

---

The C standard only talks about the ranges of values that can be represented. It does not make reference to sizeof() at all in discussing storage of a value in an integral (or any other) type.

Part of the ambiguity is that the word "storage" can mean "representing a value using a variable" as well as "allocating memory".

Quote:

---

Originally Posted by grumpy

Not true. In practice it usually works out that sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long). However, that is not actually a requirement in the standard.

The standard only requires that the set of values that can be represented by a char is a subset of the values that can be represented by a short, which in turn is a subset of the values that can be represented by a short .....

---

Regardless of how numbers are represented, fundamental mathematics seems to imply that if the above statement is true, then the statement about sizeof() is also true. You can't have sizeof(short) < sizeof(char) if short can represent every value that char can represent.

It is common implementation choices that lead to the rule of thumb about sizeof(), not "fundamental mathematics" or laws of physics.

All that can be implied from the implementation limits is minimum number of bits needed to represent a type (and that is assuming a binary computer - a ternary computer does not work with bits). The is no "fundamental mathematics" that implies a lower bound (on size of a given type, in this case) is equal to the upper bound.

Quote:

---

Originally Posted by grumpy

It is common implementation choices that lead to the rule of thumb about sizeof(), not "fundamental mathematics" or laws of physics.

All that can be implied from the implementation limits is minimum number of bits needed to represent a type (and that is assuming a binary computer - a ternary computer does not work with bits). The is no "fundamental mathematics" that implies a lower bound (on size of a given type, in this case) is equal to the upper bound.

---

Which is why the statement about sizeof() uses '<=' and not '<'. I do not follow you. How can sizeof(short) < sizeof(char) if short can represent everything char can represent?

Quote:

---

Originally Posted by brewbuck

How can sizeof(short) < sizeof(char) if short can represent everything char can represent?

---

It can't, since sizeof(char) is defined to be 1, and sizeof(any other complete type) is defined to a positive value.

But that's got nothing to do with there being a one-to-one relationship of "supporting a larger range mandates a bigger variable".

In response to a debate like this, a colleague implemented a bare bones C compiler that had sizeof(short) equal to 4 and sizeof(int) equal to 2, and enforced ranges of values on each type. He then challenged the team to find any clauses in the C standard that would make that compiler non-conformant. The team could not find such clauses.

In other words, you can't rely on the sizes of types being greater or equal. One instead has to rely on the set of all representable numbers being greater or equal for every type.
So, if U is the set of all representable numbers, then

U(char) <= U(short) <= U(int) <= U(long) <= U(long long)

Still, one has to wonder what sorts of expensive checks one has to do to enforce an upper bound on a type.

Quote:

---

Originally Posted by grumpy

In response to a debate like this, a colleague implemented a bare bones C compiler that had sizeof(short) equal to 4 and sizeof(int) equal to 2, and enforced ranges of values on each type. He then challenged the team to find any clauses in the C standard that would make that compiler non-conformant. The team could not find such clauses.

---

Ok, I get it now.

In theory, if you changed all your ints to shorts in an attempt to save space you might actually use more space. In practice, I wouldn't lose sleep over the possibility.

actually, while we're at it, what about an implementation of C that runs on an analog computer? I think that's where the "range of values" interpretation would really take on significance, since we'd be talking about a gradient of voltage levels, rather than combinations of ones and zeroes.

The property of being able to have a discrete type is inherently digital; by having an integer type a computer is necessarily digital. You can have a programmable analog device, but you can't use c++ to program it. You'd need to use Verilog-A or invent something new.

Quote:

---

Originally Posted by Elkvis

actually, while we're at it, what about an implementation of C that runs on an analog computer? I think that's where the "range of values" interpretation would really take on significance, since we'd be talking about a gradient of voltage levels, rather than combinations of ones and zeroes.

---

I'm having trouble imagining what sizeof would actually do on such an architecture. Or what a pointer would mean. I don't think C maps to analog.

Quote:

---

Originally Posted by brewbuck

I'm having trouble imagining what sizeof would actually do on such an architecture. Or what a pointer would mean. I don't think C maps to analog.

---

On such an architecture, sizeof() could be 1 for all basic integral types (char, int, long, unsigned, etc) since the physical manifestation of a variable would be a single voltage line.

Implementing formatted I/O on such an architecture would be highly entertaining though.

Quote:

---

Originally Posted by King Mir

The property of being able to have a discrete type is inherently digital; by having an integer type a computer is necessarily digital. You can have a programmable analog device, but you can't use c++ to program it. You'd need to use Verilog-A or invent something new.

---

the only reason you "can't" use C++ to program an analog device is that it has simply never been done. I don't think the language has anything in it (other than bitwise operators, and they would be largely irrelevant) that would preclude its use with an analog device.

Quote:

---

Originally Posted by Elkvis

the only reason you "can't" use C++ to program an analog device is that it has simply never been done. I don't think the language has anything in it (other than bitwise operators, and they would be largely irrelevant) that would preclude its use with an analog device.

---

You can use a device that's part analog, but to read a value as an integer requires breaking it down into discrete voltage level, a process that would make the device digital, at least in that part. So what you'd have is digital device that uses modulo N instead of 1's and 0's, for it's most basic unit of information.

there's no reason to assume that something that quantizes voltage levels must necessarily be considered digital. that sort of thing can be done with a purely analog device.

To me, quantized voltage levels are the definition of digital. How do you define a digital?

the common, de-facto definition of digital is a device that uses binary electrical states to internally represent its numeric system. parts of the dictionary definition seem to favor your point of view, although in common usage in at least the last decade or so, digital is almost always used to refer to a computer in the way we normally think of a computer.

Quote:

---

Originally Posted by Elkvis

the common, de-facto definition of digital is a device that uses binary electrical states to internally represent its numeric system. parts of the dictionary definition seem to favor your point of view, although in common usage in at least the last decade or so, digital is almost always used to refer to a computer in the way we normally think of a computer.

---

I don't know how you normally think of a computer, but when I think of it I think of quantized voltages. It's not like there's a "digital life force" that imparts "digitism" to things. It's all in your head (as most things are).

Quote:

---

Originally Posted by brewbuck

It's not like there's a "digital life force" that imparts "digitism" to things. It's all in your head (as most things are).

---

Midi-chlorians man, midi-chlorians!

Quote:

---

Originally Posted by King Mir

You can use a device that's part analog, but to read a value as an integer requires breaking it down into discrete voltage level, a process that would make the device digital, at least in that part. So what you'd have is digital device that uses modulo N instead of 1's and 0's, for it's most basic unit of information.

---

That is called an "analogue to digital converter" (ADC). The reverse is a DAC.

In general, a digital system is just one that uses a discrete (discontinuous) set of values to represent information. An analogue system is one that uses continuous functions to represent information.

Analogue computers existed a long time before digital ones. Look up "Antikythera mechanism".

Add one switch to any analogue system, and it has a digital capability.

Quote:

---

Originally Posted by Elkvis

the common, de-facto definition of digital is a device that uses binary electrical states to internally represent its numeric system. parts of the dictionary definition seem to favor your point of view, although in common usage in at least the last decade or so, digital is almost always used to refer to a computer in the way we normally think of a computer.

---

I would just call what you call a digital device a binary computer, and a device that allows more states than that as an n-ary computer. Ternary computers have existed. Higher n-ary devices have not, but are possible.

I would never call a turnary or n-ary computer an analog device (except in the sense that all computers are analog devices) because, though they are different from binary devices, they are necessarily quite different from analog circuits too.

Quote:

---

Originally Posted by grumpy

That is called an "analogue to digital converter" (ADC). The reverse is a DAC.

In general, a digital system is just one that uses a discrete (discontinuous) set of values to represent information. An analogue system is one that uses continuous functions to represent information.

Analogue computers existed a long time before digital ones. Look up "Antikythera mechanism".

Add one switch to any analogue system, and it has a digital capability.

---

If a device uses ADCs and DACs as part of it's opperation It's not really an analog device. It's a device with analog components. I agree with your definition of digital, but C's (and C++'s) type system is necessarily digital. Being able to assert 1+1=2 requires a digital device. If a computer can perform such arithmetic repeatedly, without errors, such a system has to be called digital. It would need a rounding mechanism that makes all values near to the voltage (or other quantity) representing 1 to be equal to 1, like a digital repeater.

C++ doesn't only strictly have integers, it also has decimals (float/double) where you can represent a number even if you lose some precision. Decimal numbers are a way to represent continuous values. If you write C++ in an analog computer you will just be able to get a better precision and the memory allocated for each variable won't be in bytes.

C++ has trouble asserting 1.345f + 1.123f = 2.468f because of the way decimal floating points are defined in C++. The opposite is not true, you can assert 1+1=2 in an analog computer (three constants, each held in a voltage line with 1V, 1V, 2V respectively). So more or less if you were to use C++ in a computer with an analog memory then the only thing C++ would need to do is leave flexible the representation of decimal types (not necessarily use floating point) and generalize the concept of size (so not in bytes but in an arbitrary unit type).

Quote:

---

Originally Posted by King Mir

If a device uses ADCs and DACs as part of it's opperation It's not really an analog device. It's a device with analog components.

---

By that type of logic, it would not be a digital device either.

It would be composed of both analogue and digital devices, with ADC or DAC being part of the interface between devices.

Quote:

---

Originally Posted by King Mir

Being able to assert 1+1=2 requires a digital device.

---

No it doesn't. As N_ntua said, the assertion could be tested in an analogue computer using three voltage lines.

Quote:

---

Originally Posted by King Mir

If a computer can perform such arithmetic repeatedly, without errors, such a system has to be called digital.

---

That has nothing to do with it being digital.

Firstly, it is possible to have repeatability with combinations of continuous functions (i.e. with an analogue system). In fact, technically, it is easier to achieve repeatability with a combination of continuous functions than it is with discontinuous functions.

Second, technically a transistor (which is the heart of modern digital devices) is an three-terminal analogue device - a voltage applied at one pair of terminals changes the current flowing between another pair of terminals. It just convention that if a voltage (or current) below some threshold is deemed to be "off", a voltage (or current) above that threshold is deemed to be "on". That is actually the physical underpinnings of representing bits within a digital machine. And, technically, the behaviour is statistical - a threshold is chosen so "off" is well below the threshold, and "on" is well above, so the odds of an error is small.

Third, because of the physical nature of modern semiconductor devices (including all those transistors in your CPU) there is actually a non-zero probability than any operation that attempts to turn a bit on/off in a digital device will not give the expected result. Modern devices are engineered so the probabilities are very low, but are non-zero. And some physical phenomena (alpha or beta particles, neutron upset events, electric fields, magnetic fields, .... ) can disturb those probabilities.

Quote:

---

Originally Posted by King Mir

It would need a rounding mechanism that makes all values near to the voltage (or other quantity) representing 1 to be equal to 1, like a digital repeater.

---

Not true. All that is needed is a defined tolerance of uncertainty. Let's say a value of 1 is represented by some voltage in the range [1-delta, 1+delta] volts, with some variation depending on the voltage line used to represent it. Adding 1 + 1 would be expected to give a voltage in the range [2-2*delta, 2+2*delta]. The assertion 1+1 = 2 would be detected as true if the resultant voltage is in that range.