Prime Number Calculator

[IntelMole]

The native C++ boolean array was slower because C++ compilers don't normally pack boolean arrays as tightly as we did with the bit twiddling. The compiler will allocate a byte for each element, wasting 7 bits out of each byte. So for the sieve algorithm, you basically get clobbered on memory bandwidth.

Now *THAT* is weird

Now, correct me if I'm wrong, but didn't we use two digits for our clocks to cut down on memory use in the time that B/C was being created?

Memory was at a premium too... using eight times too much space is laughable in that respect

We have a 8th wonder of the world then IMO, :lol
IntelMole

[just brew it!]

It actually makes sense when you realize how heavily C/C++ relies on the concept of pointers. You can take the address of any variable (i.e. create a pointer) and pass it around. That pointer (a memory address, actually) uniquely identifies the variable it points to.

If the native bool data type was allowed to be represented by individual bits within a byte, it would break this fundamental feature of the language. You can't uniquely identify a bit by a memory address; you need a memory address and a bit number (0-7). So the smallest native data type you can have in C/C++ is 1 byte -- the smallest unit of storage that can be uniquely identified by a memory address.

In a sense, this is a side effect of the fact that C/C++ is still very "close to the hardware". The equivalence of pointers and memory addresses is so fundamental to the language, that you can't introduce any new language constructs that run counter to this relationship.

[IntelMole]

That makes sense, and makes the idea of wasting 7 bits a little easier to digest

I'm guessing this will never be addressed because 7 bits are insignificant in today's memory sizes.

Thanks anyways,
IntelMole

[Craig P.]

By "native C++ boolean array", do you mean bool[]?

What happens if you use std::vector<bool> (which, I believe, actually works off of pages of char)? I'm pretty sure it wouldn't waste as much memory, but I'm not sure how much you'd lose in code efficiency.

[just brew it!]

I'm not really all that fluent with STL... but if bool is the base type for the template instantiation, I would expect that it would waste at least as much (if not more) memory than a simple array of bool.

[Craig P.]

std::vector<bool> is explicitly specialized in the standard library so that it behaves differently. This is unfortunate in some respects (I think it makes bool the only type for which you can't use std::vector as a managed buffer), but useful in this case.

[liquidsquid]

A C compiler that I use has a non-ANSI standard ability to make bit-sized elements within a structure (C language extension):

Code: Select all

The ANSI C Standard states that bit fields, no matter what type, are filled in units the size of unsigned integers. Introl-C allows any integral scalar type to be used as a bit field unit. For example, if the bits in a field were defined as type char, they would be stored in a char. You may do this if you want to assign an 8 bit field to some hardware register.

The default fill order for bit fields is from least significant to most significant bit. For example:

        struct tag
                {
                char a : 1;
                char b : 1;
                char c : 1;
                } abc;
the bit field would be stored as follows:

        Bit no: 7 6 5 4 3 2 1 0
        Field :           c b a


So you could access a bit much like a structure in C:

Code: Select all

  myVar.a = B_FALSE;  //Where B_FALSE = 0
  if (myVar.a) { ...   //Tests like any other code.


A bit difficult to use in a loop however since you would need to determine which bit to access on which variable, wich means a MOD calculation (division). With a little CPU work you can reduce the array size by 1/8 with a little code overhead. Otherwise you could write a specialized macro for bit-testing a location in a 1/8 sized array which would work in a similar fashion. Definitly something that would slow the heck out of VB since you would have to have a specialized routine for it, and each bit check would then require quite a bit of code. Save on space at the sacrifice of speed.

-LS