Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > array of bits

Reply
Thread Tools

array of bits

 
 
Keith Thompson
Guest
Posts: n/a
 
      05-13-2010
"Ersek, Laszlo" <(E-Mail Removed)> writes:
> On Thu, 13 May 2010, Eric Sosman wrote:
>> On 5/13/2010 3:48 PM, "" wrote:
>>> Yes, I read the FAQ.
>>>
>>> My doubts are not how to do operations, but how can I choose
>>> the most appropriate type for bitset.
>>> I.e. choose a 32 bits type on a 32 bits machine,
>>> and a 64 bits type on a 64 bits machine.

>>
>> If you can define precisely what you mean by "32 bits machine"
>> and "64 bits machine," perhaps someone will think of a test you can
>> make to tell them apart.

>
> I believe the OP thinks of something like:
>
> "64 bits machine": where uint64_t is supported, and the C compiler
> generates machine instructions (or assembly code) that access such objects
> as single machine words.
>
> "32 bits machine": a machine -- which is not also a "64 bits machine" --
> where uint32_t is supported, and where the C compiler generates machine
> instructions (or assembly code) that access such objects as single machine
> words.


I think that nearly boils down to "64-bit machines have 64-bit machine
words, and 32-bit machines have 32-bit machine words". All that remains
is to define "machine word".

Which you've more or less already done: a machine word can be accessed
by a single instruction. But there's no portable way to detect that in
C.

> I guess he's looking for the widest unsigned integer type that fits into a
> machine register. Yes, I know. There is probably nothing in the standard
> that would help us determine the answer portably. ("What's a register to
> begin with?") The OP seems to ask for a portable guess that will work fast
> on most sensible implemntations. I'd consider
>
> #include <stdint.h> // SIZE_MAX
> #include <limits.h> // UINT_MAX
> #include <stddef.h> // size_t -- perhaps move this after the #if
>
> #if SIZE_MAX > UINT_MAX
> typedef size_t mytype;
> #else
> typedef unsigned mytype;
> #endif


Why not just this?

typedef size_t mytype;

Your version uses unsigned int only when it and size_t are the same
size (so it probably doesn't make any difference) or when unsigned
int is bigger than size_t (which is possible but I've never heard
of it).

Size_t is probably the same size as a machine address register,
which is probably one "word" (whatever that means). It's not
really what size_t is intended for, but it looks like it could be
a reasonable heuristic.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
 
 
 
Ben Pfaff
Guest
Posts: n/a
 
      05-13-2010
Keith Thompson <(E-Mail Removed)> writes:

> Which you've more or less already done: a machine word can be accessed
> by a single instruction. But there's no portable way to detect that in
> C.


I'm not sure that even such a definition is foolproof. For
example, I have heard that the IBM 360 architecture supports
decimal arithmetic of variable-length quantities in a single
instruction, but I doubt that considering such instructions would
give an answer that the OP would be comfortable with.
--
Ben Pfaff
http://benpfaff.org
 
Reply With Quote
 
 
 
 
Ersek, Laszlo
Guest
Posts: n/a
 
      05-13-2010
On Thu, 13 May 2010, Keith Thompson wrote:

> "Ersek, Laszlo" <(E-Mail Removed)> writes:


[snip]

>> I guess he's looking for the widest unsigned integer type that fits
>> into a machine register. Yes, I know. There is probably nothing in the
>> standard that would help us determine the answer portably. ("What's a
>> register to begin with?") The OP seems to ask for a portable guess that
>> will work fast on most sensible implemntations. I'd consider
>>
>> #include <stdint.h> // SIZE_MAX
>> #include <limits.h> // UINT_MAX
>> #include <stddef.h> // size_t -- perhaps move this after the #if
>>
>> #if SIZE_MAX > UINT_MAX
>> typedef size_t mytype;
>> #else
>> typedef unsigned mytype;
>> #endif

>
> Why not just this?
>
> typedef size_t mytype;
>
> Your version uses unsigned int only when it and size_t are the same size
> (so it probably doesn't make any difference) or when unsigned int is
> bigger than size_t (which is possible but I've never heard of it).


Yes, I wanted to protect against a fortuitous "degenerate" case, in which
the size_t elements of the array would be constantly promoted when
manipulated, and then converted back when stored.

Thanks!
lacos
 
Reply With Quote
 
Lew Pitcher
Guest
Posts: n/a
 
      05-13-2010
On May 13, 2010 18:40, in comp.lang.c, (E-Mail Removed) wrote:

> Keith Thompson <(E-Mail Removed)> writes:
>
>> Which you've more or less already done: a machine word can be accessed
>> by a single instruction. But there's no portable way to detect that in
>> C.

>
> I'm not sure that even such a definition is foolproof. For
> example, I have heard that the IBM 360 architecture supports
> decimal arithmetic of variable-length quantities in a single
> instruction,


The AP ("Add Packed") instruction is one of the IBM360 "Storage/Storage"
machine language instructions. Consequently, each of the two operands can
be, independantly, between 1 and 256 bytes in length, representing numbers
with between 1 and 511 decimal digits. With this instruction, it *is*
possible to perform a decimal add between two packed-decimal values with
different lengths.

> but I doubt that considering such instructions would
> give an answer that the OP would be comfortable with.


No, Indeed, the IBM360 would give the OP nightmares, because it is
simultaneously an 8bit, a 16bit, a 32bit and a 64bit machine, which uses
24-bit and 31-bit addresses. Later versions would expand the hardware
address space to 63-bit addresses (note that none of the address types fit
exactly into the C uint*t space).

HTH
--
Lew Pitcher
Master Codewright & JOAT-in-training | Registered Linux User #112576
Me: http://pitcher.digitalfreehold.ca/ | Just Linux: http://justlinux.ca/
---------- Slackware - Because I know what I'm doing. ------


 
Reply With Quote
 
\\
Guest
Posts: n/a
 
      05-13-2010
Ok,
it seems that the question is not simply to define
so I try to put it clear.

I have to use array of bits not only with operations
like set/reset a bit, but also to compare a piece of
an array with a piece of another array, with AND/OR
logical operations, so I would like to use the widest
type available on the machine the code is compiled in.
The widest type naturally supported, obviosly. If I
compile on a 32 bit system, and the compiler could
simulate 64 bit data types through multiple 32 bit
operations, I am not interested in 64, I should
choose 32.

> I guess he's looking for the widest unsigned
> integer type that fits into a machine register.


Yes!!

>(beginner rule: don't do performance optimization;
> advanced rule: don't do it *yet*).


Well, normally I am not interested in the trick of
the month to get faster code, but in this case, I
think that choosing the right type is even a way to
write better code.

I am studying your answers, however, and thank you
very much.
tano

 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      05-14-2010
"\"\"" <(E-Mail Removed)> writes:
> it seems that the question is not simply to define
> so I try to put it clear.
>
> I have to use array of bits not only with operations
> like set/reset a bit, but also to compare a piece of
> an array with a piece of another array, with AND/OR
> logical operations, so I would like to use the widest
> type available on the machine the code is compiled in.
> The widest type naturally supported, obviosly. If I
> compile on a 32 bit system, and the compiler could
> simulate 64 bit data types through multiple 32 bit
> operations, I am not interested in 64, I should
> choose 32.
>
>> I guess he's looking for the widest unsigned
>> integer type that fits into a machine register.

>
> Yes!!
>
>>(beginner rule: don't do performance optimization;
>> advanced rule: don't do it *yet*).

>
> Well, normally I am not interested in the trick of
> the month to get faster code, but in this case, I
> think that choosing the right type is even a way to
> write better code.
>
> I am studying your answers, however, and thank you
> very much.


My advice:

Use a single typedef that defines which unsigned type you want to use.
Other than that single declaration, write all your code so that it
doesn't care which type it's dealing with. It could even be unsigned
char.

Once you've got your code working, then worry about which type is more
efficient on a given system. You can easily tweak the typedef and
rebuild to do performance comparisons.

Don't assume that 32-bit integers are going to be faster than 64-bit
integer, or vice versa, until you've *measured* it.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
robertwessel2@yahoo.com
Guest
Posts: n/a
 
      05-14-2010
On May 13, 6:16*pm, Lew Pitcher <(E-Mail Removed)> wrote:
> On May 13, 2010 18:40, in comp.lang.c, (E-Mail Removed) wrote:
>
> > Keith Thompson <(E-Mail Removed)> writes:

>
> >> Which you've more or less already done: a machine word can be accessed
> >> by a single instruction. *But there's no portable way to detect that in
> >> C.

>
> > I'm not sure that even such a definition is foolproof. *For
> > example, I have heard that the IBM 360 architecture supports
> > decimal arithmetic of variable-length quantities in a single
> > instruction,

>
> The AP ("Add Packed") instruction is one of the IBM360 "Storage/Storage"
> machine language instructions. Consequently, each of the two operands can
> be, independantly, between 1 and 256 bytes in length, representing numbers
> with between 1 and 511 decimal digits. With this instruction, it *is*
> possible to perform a decimal add between two packed-decimal values with
> different lengths.



Actually the decimal instructions allow two four bit lengths, and so
support operands of 1-16 bytes (and 1-31 decimal digits). Other "SS"
format instructions use the same field to represent a single eight bit
length instead.


> > but I doubt that considering such instructions would
> > give an answer that the OP would be comfortable with.

>
> No, Indeed, the IBM360 would give the OP nightmares, because it is
> simultaneously an 8bit, a 16bit, a 32bit and a 64bit machine, which uses
> 24-bit and 31-bit addresses. Later versions would expand the hardware
> address space to 63-bit addresses (note that none of the address types fit
> exactly into the C uint*t space).



zArch extended the address space to 64, not 63 bits. And 24 and 32
bit addresses are almost always handled as a full (32 bit) register
(not that there haven't weren't cases of software taking pains to only
use three bytes to store a 24 bit address). And for the most part, at
the architectural level, and in user mode, the address size impacts
only where the address space wraps around (with the notable exception
of the two original S/360 subroutine call instructions, BAL and BALR,
which require a noteworthy semantic change when moving from 24 bit to
31 bit addressing - although subroutine call instructions without the
oddities of BAL and BALR have been in the ISA since the seventies).
 
Reply With Quote
 
\\
Guest
Posts: n/a
 
      05-14-2010
Wow, it seems that C99 provides something that could help me
(quoted from libc manual):

> If you want an integer with the widest range possible on
> the platform on which it is being used, use one of the
> following. If you use these, you should write code that
> takes into account the variable size and range of the integer.


> intmax_t
> uintmax_t


Tell me if I'm wrong.

 
Reply With Quote
 
bart.c
Guest
Posts: n/a
 
      05-14-2010

"""" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Wow, it seems that C99 provides something that could help me
> (quoted from libc manual):
>
>> If you want an integer with the widest range possible on
>> the platform on which it is being used, use one of the
>> following. If you use these, you should write code that
>> takes into account the variable size and range of the integer.

>
>> intmax_t
>> uintmax_t

>
> Tell me if I'm wrong.


On my machine, these are 64-bits, even though my processor is 32-bits (or
used in 32-bit mode anyway).

--
Bartc

 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      05-14-2010
On 2010-05-14, \"" <(E-Mail Removed)> wrote:
> Wow, it seems that C99 provides something that could help me
> (quoted from libc manual):
>
>> If you want an integer with the widest range possible on
>> the platform on which it is being used, use one of the
>> following. If you use these, you should write code that
>> takes into account the variable size and range of the integer.

>
>> intmax_t
>> uintmax_t

>
> Tell me if I'm wrong.


You're wrong.

See, intmax_t is, on many systems, very inefficient, because it's a larger
type than any of the hardware types.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / (E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
shifting bits, shift 32 bits on 32 bit int GGG C++ 10 07-06-2006 06:09 AM
what about unsigned and signed 8 bits number, 16 bits, etc?? sarmin kho Python 2 06-15-2004 06:40 PM
8 bits/ch vs 16 bits/ch in PS Terry Digital Photography 5 01-21-2004 06:59 PM
8-Bits vs 12 or 16 bits/pixel; When does more than 8 bits count ? Al Dykes Digital Photography 3 12-29-2003 07:08 PM
win XP 32 bits on a 64 bits processor.. Abbyss Computer Support 3 11-13-2003 12:39 AM



Advertisments