Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

3 bit unsigned integer in c

I am setting up a deep neural network to play connect-4 that has to compete against other AI bots on a very limited machine (don't know the specific limitations yet, only that I will only have a couple cores and a small amount of memory). Thus, I am looking to optimize my training set in any way possible. It currently represents the states on the boards as such:

b for blank (no piece present)

x for "x" piece present

o for "o" piece present

win for a won setup

loss for a lost setup

draw for a drawn setup

Essentially I am trying to map it so that my 3 bit integer can take the place of these memory-heavy strings. I thought about using a short, but it comes in as worse than char at 16 bits. I want to map it like such:

000 -> b

001 -> x

010 -> o

011 -> win

100 -> loss

101 -> draw

Since I can represent these states in 3 bits of space instead of chars (8 bits per char, yikes!) I would like to attempt that. However I am not sure how to instantiate a variable like this in c.

The training set is 67557 rows long representing a 6x7 board in each row with an win/loss/draw clause following. So saving 5 bits per char would save (5*6*7)+(5*1) = 215 bits per row and 215*67557 = 14524755 bits overall (1.81 MB of 2.90 MB total, a 62% decrease in overall space).

like image 517
asdf Avatar asked Dec 19 '22 23:12

asdf


1 Answers

And what about if you use bitfields?

struct S {
    unsigned w : 3;
    unsigned x : 3;
    unsigned y : 3;
    unsigned z : 3;
};

On most systems, sizeof(struct S) == 2, but you'ld hold 4 values in it!.

Now, you can do something like...

struct S myS;
s.w = 0; // Okay
s.x = 6; // Okay
s.y = 8; // Will overflow/wrap-around (why do the standards differentiate between those two?)

But, if you do something like...

struct S first;
struct S second;

You'll lose the memory efficiency you're seeking for, because the compiler has to provide an address for both objects, thus they need to be byte-aligned, so they together (usually) hold 32 bits, in which you can hold eight values, but, if you had a single structure holding all eight variables, the memory usage would typically be 24 bits.

Have in mind that a structure that holds bitfields that use all the available space (such as the 8-member one mentioned above: 8 * 3 == 24; 24 % 8 == 0) are better suited for your purposes, as you can have arrays of them, gain the benefits of bitfields, and waste no memory in the process. The first structure is thus inefficient, because it wastes 4 bits for each object of type S.

BTW: Don't try to use &s.x or sizeof(s.x), it simply won't work for obvious reasons.

like image 161
3442 Avatar answered Jan 03 '23 12:01

3442