Prime Number Calculator

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

Postposted on Wed Jul 02, 2003 6:47 pm

just brew it! wrote: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 :-D

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
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 6:00 pm
Location: The nearest pub

Postposted on Wed Jul 02, 2003 6:55 pm

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.
just brew it!
Administrator
Gold subscriber
 
 
Posts: 36893
Joined: Tue Aug 20, 2002 9:51 pm
Location: Somewhere, having a beer

Postposted on Thu Jul 03, 2003 11:56 am

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

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

Thanks anyways,
IntelMole
Living proof of John Gabriel's theorem
IntelMole
Grand Gerbil Poohbah
 
Posts: 3529
Joined: Sat Dec 29, 2001 6:00 pm
Location: The nearest pub

Postposted on Tue Jul 08, 2003 9:41 pm

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.
Craig P.
Gerbil Team Leader
 
Posts: 285
Joined: Tue Dec 31, 2002 2:12 am
Location: South Bend, IN

Postposted on Tue Jul 08, 2003 10:00 pm

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.
just brew it!
Administrator
Gold subscriber
 
 
Posts: 36893
Joined: Tue Aug 20, 2002 9:51 pm
Location: Somewhere, having a beer

Postposted on Wed Jul 09, 2003 7:15 am

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.
Craig P.
Gerbil Team Leader
 
Posts: 285
Joined: Tue Dec 31, 2002 2:12 am
Location: South Bend, IN

Postposted on Wed Jul 09, 2003 7:28 am

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
liquidsquid
Minister of Gerbil Affairs
 
Posts: 2437
Joined: Wed May 29, 2002 9:49 am
Location: New York

Previous

Return to Developer's Den

Who is online

Users browsing this forum: No registered users and 2 guests