Closed DinkydauSet closed 3 years ago
Because by far the largest amount of memory is used by an array of IterData structs I have looked at if the memory usage can be reduced.
Before even that, I changed the iterationCount value to uint because using int imposes an unnecessary limit of 2^31.
struct IterData {
uint iterationCount; //4 bytes
bool inMinibrot; //1 byte
bool guessed; //1 byte
};
A bool uses 1 byte of memory (8 times as much as strictly needed). Together that's 6 bytes for the struct, but the compiler rounds that to a multiple of 4, making the struct cost 8 bytes.
I can't believe how much memory is being wasted just because I need 2 bits of information along with the iterationcounts.
This class uses the capacity of one integer (4 bytes) to store multiple values as follows: first 30 bits: iterationcount (integer) 31st bit: inMinibrot (boolean) 32nd bit: guessed (boolean)
class IterData {
uint data;
public:
inline void iterationCount(uint iterationCount) {
data = iterationCount << 2;
}
inline uint iterationCount() {
return data >> 2;
}
inline void guessed(bool guessed) {
if (guessed)
data = data | 0b1;
else
data = ((data >> 1) << 1);
}
inline bool guessed() {
return data & 0b1;
}
inline void inMinibrot(bool inMinibrot) {
bool guessed = this->guessed();
if (inMinibrot) {
data = data | 0b10;
}
else {
if (guessed) {
data = ((data >> 2) << 2) | 0b1;
}
else {
data = ((data >> 2) << 2);
}
}
}
inline bool inMinibrot() {
return data & 0b10;
}
};
It works and I don't notice any speed reduction. So by using 2 bits of the data to store the boolean values, memory usage is reduced by half at the cost of 2 bits of precision for the iterationcount, which means the maximum value of the iterationcount is 2^30 = 1,073,741,824.
The iterationcount limit can be easily raised to 2^62 by using a uint64 instead of a uint, providing a much higher limit than the previous version of the struct while using the same amount of memory.
A simpler version by combining all the set-functions into one constructor:
class IterData {
uint data;
public:
IterData(uint iterationCount, bool guessed, bool inMinibrot) {
data = iterationCount << 2;
if (guessed)
data = data | 0b1;
if (inMinibrot) {
data = data | 0b10;
}
}
inline uint iterationCount() {
return data >> 2;
}
inline bool guessed() {
return data & 0b1;
}
inline bool inMinibrot() {
return data & 0b10;
}
};
After construction, the data doesn't have to be changed anyway.
I often use ints when the value is not supposed to be negative. It's better to use unsigned int.
I also ran into a bug when allocating more than 2^31 bytes of memory because of using ints. Allocating a negative amount of memory is meaningless so using unsigned ints would have been better, but would still limit the number of bytes to 2^32, so I should have used long long.
Are there any other unnecessary limits in the program because of this?
Another consideration is memory usage. Memory usage of a single int or long long is so small it doesn't matter, but it does matter when it's used as a type in a vector or array that contains millions of items.
Because the names of these types are ridiculous I use some typedefs to at least shorten "unsigned int" to "uint", but still the names don't make sense. A 1 byte integer is called a char. Apparently there's this header that provides better names http://www.cplusplus.com/reference/cstdint/ . Maybe it's a good idea to use those,