Initialization without loop

[caijunfu]

Is there a way to create a new array, and initialise every of them to
0, but maintain the order to this process to O(1)?

(usually, we do initialisation by using for loop. that is of O(n).)

 

[Russell Hanneken]

Is there a way to create a new array, and initialise every of them to
0, but maintain the order to this process to O(1)?

(usually, we do initialisation by using for loop. that is of O(n).)

I don't believe there's any way to do it that's guaranteed to be O(1). You
could do something like this

int array[100] = { 0 };

That would initialize array with 100 zeros (because the initializer list has
fewer elements than the array, the last 99 elements are given the same value
they would get if they were static storage--i.e., 0). With your C
implementation, the initialization process might end up being of the order
O(1), for all I know. But again, there's no guarantee in the C standard.

Regards,

Russell Hanneken
(e-mail address removed)

 

[Tim Prince]

Is there a way to create a new array, and initialise every of them to
0, but maintain the order to this process to O(1)?

(usually, we do initialisation by using for loop. that is of O(n).)

In many implementations, memset() would choose the fastest way of
initialization. Then, it should be better than O(n), up to some size,
perhaps as big as a cache line.
calloc() would be expected to implement the best general algorithm for the
task you have described, if the developers of your library have taken care
to do so. You could test various alternate libraries for your platform. I
don't know whether you mean the speed of the entire process, or just the
speed of the initialization part.

 

[Russell Hanneken]

In many implementations, memset() would choose the fastest way of
initialization. Then, it should be better than O(n), up to some size,
perhaps as big as a cache line.
calloc() would be expected to implement the best general algorithm for the
task you have described, if the developers of your library have taken care
to do so.

memset could give every byte in the array a value of (unsigned char) 0.
That's fine if you have an array of unsigned chars, but if you have an array
of, say, ints, setting every byte to 0 isn't guaranteed to give every
element the value 0.

calloc sets every bit to 0, but again, that may not give every element a
value of 0. The value 0 may or may not be represented by all-bits-zero.
:-\

Regards,

Russell Hanneken
(e-mail address removed)

 

[Martin Dickopp]

memset could give every byte in the array a value of (unsigned char) 0.
That's fine if you have an array of unsigned chars, but if you have an array
of, say, ints, setting every byte to 0 isn't guaranteed to give every
element the value 0.

Actually, all-bits-zero is guaranteed to be a representation of the value
zero for all integer types. See Defect Report #263.

Martin

 

[Glen Herrmannsfeldt]

Is there a way to create a new array, and initialise every of them to
0, but maintain the order to this process to O(1)?

(usually, we do initialisation by using for loop. that is of O(n).)

This doesn't make any sense. Note that O() notation implies the limit as
n --> infinity.

Other than magical initialization, or maybe something like flash RAM that
has the ability to clear blocks using special electronics, it wouldn't be
possible. But even for that, you would still have to initialize the
blocks sequentially, so it would still be O(n), but with a smaller constant.

Well, actually, you didn't say O(n) what. It is common to describe an
algorithm in terms of its space usage and time usage. There is often a
tradeoff where more using more space can speed up an algorithm.

There are also tricks on virtual storage OS where a program may allocate
large amounts of memory, ask the OS to clear it, but never use it. The OS
can map a single page or real memory to many pages of virtual memory, and
only allocate more real pages when they are modified. This effect has
confused some benchmark programs. Note that again it is O(n), but also with
a smaller constant.

In general O(n) is the best you can do for n things, the goal is to get as
close as you can to O(n).

-- glen

 

[Russell Hanneken]

Actually, all-bits-zero is guaranteed to be a representation of the value
zero for all integer types. See Defect Report #263.

Can defect reports guarantee anything? I thought they just described
perceived problems with the standard.

Anyway, even if all-bits-zero is guaranteed to be a representation of the
value zero for all integer types, does that mean we can use memset to zero
an array of ints? As I understand it, if we tell memset to write zeros,
we're telling it to write some valid unsigned char representation of 0 to
each byte. According to what you're saying, all-bits-zero must be *a* valid
representation of unsigned char 0, but it doesn't have to be the only one.
How do we know memset will choose the all-bits-zero representation?

Regards,

Russell Hanneken
(e-mail address removed)

 

[Ben Pfaff]

Can defect reports guarantee anything? I thought they just described
perceived problems with the standard.

The committee's response to a defect report can clarify and/or
correct problems with the standard.

 

[Default User]

The committee's response to a defect report can clarify and/or
correct problems with the standard.

Right, but that's not Martin said. He said that the defect report
guarantees that all-bits is ok now. In fact, while the recommendation is
to modify the Standard, the response from the committee could be,
"tough, live with it."




Brian Rodenborn

 

[Christopher Benson-Manica]

Right, but that's not Martin said. He said that the defect report
guarantees that all-bits is ok now. In fact, while the recommendation is
to modify the Standard, the response from the committee could be,
"tough, live with it."

So what's the official status of all these defect reports? Is a response
still to be determined?

 

[Irrwahn Grausewitz]

So what's the official status of all these defect reports? Is a response
still to be determined?

Take a look at http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/summary.htm .

Irrwahn

 

[Default User]

Take a look at http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/summary.htm .

Hmmm, what does "closed" mean? That the suggested inclusion was
approved? That it was rejected? For the one in question (263), there's
no Technical Corrigendum publication information.



Brian Rodenborn

 

[Martin Dickopp]

Right, but that's not Martin said. He said that the defect report
guarantees that all-bits is ok now. In fact, while the recommendation is
to modify the Standard, the response from the committee could be,
"tough, live with it."

It is my understanding (i.e., I was told in comp.std.c once) that the
Committee's response to Defect Reports is in fact normative.

In this case, I was extremely surprised when first learned about DR#263,
and I still find the situation that the DR created quite unsatisfactory.
From reading the standard, I would have thought that padding bits in
integer types would for example allow an efficient implementation on
hardware where the machine word has an odd parity bit. But with the
requirement that all-bits-zero must be a valid representation of zero,
such a machine couldn't just use its hardware word to store integer types.
Given this requirement, I do in fact wonder why the Committee allowed
padding bits and trap representations of integer types in the first
place.

Martin

 

[Martin Dickopp]

So what's the official status of all these defect reports? Is a response
still to be determined?

See <http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/summary.htm>, which lists
the status of each Defect Report.

Martin

 

[Christian Bau]

It is my understanding (i.e., I was told in comp.std.c once) that the
Committee's response to Defect Reports is in fact normative.

In this case, I was extremely surprised when first learned about DR#263,
and I still find the situation that the DR created quite unsatisfactory.
From reading the standard, I would have thought that padding bits in
integer types would for example allow an efficient implementation on
hardware where the machine word has an odd parity bit. But with the
requirement that all-bits-zero must be a valid representation of zero,
such a machine couldn't just use its hardware word to store integer types.

Such a machine would have to be able to explictely read parity bits by
using a char*. I think that would be highly unusual.

Given this requirement, I do in fact wonder why the Committee allowed
padding bits and trap representations of integer types in the first
place.

There are actually real machines, built and sold today, that have
padding bits in integer types. There is one DSP with 32 bit int and 40
bit long; the 40 bit long is stored in 64 bits including 24 padding
bits. (This machine supports 40 bit integer arithmetic which is slightly
slower than 32 bit, but significantly faster than full 64 bit
arithmetic, so it is quite useful for the intended market).

 

[Default User]

Martin Dickopp wrote:

It is my understanding (i.e., I was told in comp.std.c once) that the
Committee's response to Defect Reports is in fact normative.

I see. So the response is the suggested inclusion into a TC of the
changes, and since it's closed it's effectively approved?



Brian Rodenborn

 

[Irrwahn Grausewitz]

Hmmm, what does "closed" mean? That the suggested inclusion was
approved? That it was rejected? For the one in question (263), there's
no Technical Corrigendum publication information.

Hmmm, I can only assume they made a cut&paste mistake, because otherwise
it would mean that DR263 ends with an IMHO nonsensical repetition of
it's last paragraph. But this is only guessing on my side...

DR263>
DR263> [...]
DR263>
DR263> Suggested Technical Corrigendum
DR263>
DR263> Append to 6.2.6.2#5:
DR263>
DR263> For any integer type, the object representation where all the
DR263> bits are zero shall be a representation of the value zero in
DR263> that type.
DR263>
DR263> ----------------------------------------------------------------
DR263>
DR263> Suggested Technical Corrigendum
^^^^^^^^^
I can only /suppose/ this was intented to read 'Proposed'.
Maybe one of the officials can point it out???

DR263> Append to 6.2.6.2#5:
DR263>
DR263> For any integer type, the object representation where all the
DR263> bits are zero shall be a representation of the value zero in
DR263> that type.
DR263>

Regards

Irrwahn

 

[Kevin Easton]

Can defect reports guarantee anything? I thought they just described
perceived problems with the standard.

Anyway, even if all-bits-zero is guaranteed to be a representation of the
value zero for all integer types, does that mean we can use memset to zero
an array of ints? As I understand it, if we tell memset to write zeros,
we're telling it to write some valid unsigned char representation of 0 to
each byte. According to what you're saying, all-bits-zero must be *a* valid
representation of unsigned char 0, but it doesn't have to be the only one.
How do we know memset will choose the all-bits-zero representation?

unsigned char must be a pure binary representation with no padding bits,
and since it's unsigned no signing issues come into play.

- Kevin.

 

[Christopher Benson-Manica]

See <http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/summary.htm>, which lists
the status of each Defect Report.

Does "closed" equate to "approved" or what? (sorry if I'm being dense...)