Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #127645 > unrolled thread

Copy array with small changes

Back to article view | Back to comp.lang.c

Contents

  Copy array with small changes Noob <root@127.0.0.1> - 2018-03-11 22:51 +0100
    Re: Copy array with small changes supercat@casperkitty.com - 2018-03-11 15:11 -0700
    Re: Copy array with small changes Richard Damon <Richard@Damon-Family.org> - 2018-03-11 18:12 -0400
      Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-11 22:35 +0000
        Re: Copy array with small changes Richard Damon <Richard@Damon-Family.org> - 2018-03-13 13:10 -0400
    Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-11 22:13 +0000
      Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 00:04 +0000
      Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 10:35 +0000
        Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 12:37 +0000
          Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 13:10 +0000
          Re: Copy array with small changes Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-03-12 13:34 +0000
            Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:22 -0700
          Re: Copy array with small changes mark.bluemel@gmail.com - 2018-03-12 07:47 -0700
            Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 14:56 +0000
              Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 15:14 +0000
              Re: Copy array with small changes mark.bluemel@gmail.com - 2018-03-12 08:53 -0700
          Re: Copy array with small changes Keith Thompson <kst-u@mib.org> - 2018-03-12 09:08 -0700
            Re: Copy array with small changes supercat@casperkitty.com - 2018-03-12 09:57 -0700
              Re: Copy array with small changes Richard Damon <Richard@Damon-Family.org> - 2018-03-13 13:21 -0400
      Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-12 15:25 +0100
        Re: Copy array with small changes Spiros Bousbouras <spibou@gmail.com> - 2018-03-12 15:09 +0000
    Re: Copy array with small changes Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-03-12 06:59 +0000
      Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-12 15:55 +0100
        Re: Copy array with small changes bartc <bc@freeuk.com> - 2018-03-12 15:07 +0000
        Re: Copy array with small changes mark.bluemel@gmail.com - 2018-03-12 09:03 -0700
        Re: Copy array with small changes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-03-12 17:42 +0000
          Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-12 23:33 +0100
            Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-12 23:44 +0100
            Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:48 -0700
              Re: Copy array with small changes Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-18 03:31 -0700
              Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-22 17:10 +0100
          Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:24 -0700
            Re: Copy array with small changes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-03-17 18:04 +0000
              Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-26 22:55 -0700
                Re: Copy array with small changes Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-03-27 15:28 +0100
                  Re: Copy array with small changes Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-28 14:42 -0700
        Re: Copy array with small changes Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-03-13 12:46 +0000
    Re: Copy array with small changes Anton Shepelev <anton.txt@gmail.com> - 2018-03-12 22:36 +0300
    Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-12 23:32 +0100
      Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-13 10:42 +0100
      Re: Copy array with small changes Noob <root@127.0.0.1> - 2018-03-13 11:37 +0100
        Re: Copy array with small changes Wouter Verhelst <w@uter.be> - 2018-03-13 21:27 +0100
    Re: Copy array with small changes Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-17 09:55 -0700

Page 1 of 3  [1] 2 3  Next page →

#127645 — Copy array with small changes

Hello,

I'm writing a toy program where I have a function that copies
a small sorted array (less than 12 ints) while making two small
changes: remove two elements, insert one element.

The function prototype is:

void update_array(int *arr, int n, int zi, int zj, int val);

arr = the original array, sorted by increasing values
n = number of elements < N = 12
zi = 1st index to remove
zj = 2nd index to remove
val = new value to insert while keeping the array sorted

Here's my current implementation:

void update_array(int *arr, int n, int zi, int zj, int val)
{
    int new_arr[N];
    int i, j = 0, done = 0;

    for (i = 0; i < n; +i)
    {
	if (i == zi || i == zj) continue;
	int tmp = arr[i];
	if (!done && val < tmp) {
	    new_arr[j++] = val;
	    done = 1;
	}
        new_arr[j++] = tmp;
    }
    new_arr[j] = val;
    do_something(new_arr);
}

It's ugly IMO. Do you have suggestions for improvements?
This function is called several billion times, so any performance
improvement will be useful.

Regards.

[toc] | [next] | [standalone]

#127648

On Sunday, March 11, 2018 at 4:51:53 PM UTC-5, Noob wrote:
> I'm writing a toy program where I have a function that copies
> a small sorted array (less than 12 ints) while making two small
> changes: remove two elements, insert one element.

The deletions effectively subdivide the array into three pieces.  I
would suggest comparing the element to be inserted with the two that
are being deleted, so as to identify which piece will contain the new
element.

If the element being inserted is in the first piece, then the second
piece won't move.  Working from the end of the first piece toward the
start, move elements upward until an element is found which should
precede the new one.  Write the new element after that one and copy
the last section forward one element and you're done.

If the element being inserted is in the second piece, then the first
and third pieces won't move.  Working from the start of the second
piece toward the back, copy elements back one position until an
element is found which is greater than the one to be inserted.  Write
the new element before that one and you're done.

If the element being inserted is in the third piece, copy the second
piece to its new location, and then handle the third situation much
like what's described above, except move elements down two spaces as
long as they're less than the new element; move the remaining elements
down one space.

It might be worthwhile to use a function-pointer dispatch to allow
small numbers of elements to be copied without loops, but that would
depend upon the target processor, cache loading issues, and other
factors.

[toc] | [prev] | [next] | [standalone]

#127649

On 3/11/18 5:51 PM, Noob wrote:
> Hello,
> 
> I'm writing a toy program where I have a function that copies
> a small sorted array (less than 12 ints) while making two small
> changes: remove two elements, insert one element.
> 
> The function prototype is:
> 
> void update_array(int *arr, int n, int zi, int zj, int val);
> 
> arr = the original array, sorted by increasing values
> n = number of elements < N = 12
> zi = 1st index to remove
> zj = 2nd index to remove
> val = new value to insert while keeping the array sorted
> 
> Here's my current implementation:
> 
> void update_array(int *arr, int n, int zi, int zj, int val)
> {
>      int new_arr[N];
>      int i, j = 0, done = 0;
> 
>      for (i = 0; i < n; +i)
>      {
> 	if (i == zi || i == zj) continue;
> 	int tmp = arr[i];
> 	if (!done && val < tmp) {
> 	    new_arr[j++] = val;
> 	    done = 1;
> 	}
>          new_arr[j++] = tmp;
>      }
>      new_arr[j] = val;
>      do_something(new_arr);
> }
> 
> It's ugly IMO. Do you have suggestions for improvements?
> This function is called several billion times, so any performance
> improvement will be useful.
> 
> Regards.
> 

For some compilers/processors, rather than using indexing, you could 
just keep a pointer to the 'current' element of the array, and rather 
than bumping the index, bump the pointer (and for the input array, also 
decrement the length, and items to drop).

A second small improvement would be unrolling the done test and using 
two loops, the first only for items less than val, and the second for 
the items after you have copied val.

[toc] | [prev] | [next] | [standalone]

#127652

On Sun, 11 Mar 2018 18:12:41 -0400
Richard Damon <Richard@Damon-Family.org> wrote:
> On 3/11/18 5:51 PM, Noob wrote:
> > Hello,
> > 
> > I'm writing a toy program where I have a function that copies
> > a small sorted array (less than 12 ints) while making two small
> > changes: remove two elements, insert one element.
> > 
> > The function prototype is:
> > 
> > void update_array(int *arr, int n, int zi, int zj, int val);
> > 
> > arr = the original array, sorted by increasing values
> > n = number of elements < N = 12
> > zi = 1st index to remove
> > zj = 2nd index to remove
> > val = new value to insert while keeping the array sorted
> > 
> > Here's my current implementation:
> > 
> > void update_array(int *arr, int n, int zi, int zj, int val)
> > {
> >      int new_arr[N];
> >      int i, j = 0, done = 0;
> > 
> >      for (i = 0; i < n; +i)
> >      {
> > 	if (i == zi || i == zj) continue;
> > 	int tmp = arr[i];
> > 	if (!done && val < tmp) {
> > 	    new_arr[j++] = val;
> > 	    done = 1;
> > 	}
> >          new_arr[j++] = tmp;
> >      }
> >      new_arr[j] = val;
> >      do_something(new_arr);
> > }
> > 
> > It's ugly IMO. Do you have suggestions for improvements?
> > This function is called several billion times, so any performance
> > improvement will be useful.
> > 
> > Regards.
> > 
> 
> For some compilers/processors, rather than using indexing, you could 
> just keep a pointer to the 'current' element of the array, and rather 
> than bumping the index, bump the pointer (and for the input array, also 
> decrement the length, and items to drop).

In this day and age are there really any compilers which won't do on their
own the transformation between  pointer  and  base+index  based on what is
faster ? Regardless , I don't see what the terminating test would be that
would require to increment the pointer and decrement the size of the array.

> A second small improvement would be unrolling the done test and using 
> two loops, the first only for items less than val, and the second for 
> the items after you have copied val.

[toc] | [prev] | [next] | [standalone]

#127758

On 3/11/18 6:35 PM, Spiros Bousbouras wrote:
> On Sun, 11 Mar 2018 18:12:41 -0400
> Richard Damon <Richard@Damon-Family.org> wrote:
>> On 3/11/18 5:51 PM, Noob wrote:
>>> Hello,
>>>
>>> I'm writing a toy program where I have a function that copies
>>> a small sorted array (less than 12 ints) while making two small
>>> changes: remove two elements, insert one element.
>>>
>>> The function prototype is:
>>>
>>> void update_array(int *arr, int n, int zi, int zj, int val);
>>>
>>> arr = the original array, sorted by increasing values
>>> n = number of elements < N = 12
>>> zi = 1st index to remove
>>> zj = 2nd index to remove
>>> val = new value to insert while keeping the array sorted
>>>
>>> Here's my current implementation:
>>>
>>> void update_array(int *arr, int n, int zi, int zj, int val)
>>> {
>>>       int new_arr[N];
>>>       int i, j = 0, done = 0;
>>>
>>>       for (i = 0; i < n; +i)
>>>       {
>>> 	if (i == zi || i == zj) continue;
>>> 	int tmp = arr[i];
>>> 	if (!done && val < tmp) {
>>> 	    new_arr[j++] = val;
>>> 	    done = 1;
>>> 	}
>>>           new_arr[j++] = tmp;
>>>       }
>>>       new_arr[j] = val;
>>>       do_something(new_arr);
>>> }
>>>
>>> It's ugly IMO. Do you have suggestions for improvements?
>>> This function is called several billion times, so any performance
>>> improvement will be useful.
>>>
>>> Regards.
>>>
>>
>> For some compilers/processors, rather than using indexing, you could
>> just keep a pointer to the 'current' element of the array, and rather
>> than bumping the index, bump the pointer (and for the input array, also
>> decrement the length, and items to drop).
> 
> In this day and age are there really any compilers which won't do on their
> own the transformation between  pointer  and  base+index  based on what is
> faster ? Regardless , I don't see what the terminating test would be that
> would require to increment the pointer and decrement the size of the array.

There may not be, I don't know. I suspect that at least most will at a 
high enough optimization level, but it can be better to be explicit 
which makes sure.

For the end condition, why count i up to n, and need an explicit value 
compare, instead of decreasing n down to 0, and perhaps be able to just 
use the results flag of the decrement.
> 
>> A second small improvement would be unrolling the done test and using
>> two loops, the first only for items less than val, and the second for
>> the items after you have copied val.

[toc] | [prev] | [next] | [standalone]

#127650

On Sun, 11 Mar 2018 22:51:40 +0100
Noob <root@127.0.0.1> wrote:
> Hello,
> 
> I'm writing a toy program where I have a function that copies
> a small sorted array (less than 12 ints) while making two small
> changes: remove two elements, insert one element.
> 
> The function prototype is:
> 
> void update_array(int *arr, int n, int zi, int zj, int val);
> 
> arr = the original array, sorted by increasing values
> n = number of elements < N = 12
> zi = 1st index to remove
> zj = 2nd index to remove
> val = new value to insert while keeping the array sorted
> 
> Here's my current implementation:
> 
> void update_array(int *arr, int n, int zi, int zj, int val)

void update_array(const int * const arr , const size_t n ,
                  const size_t zi , const size_t zj , const int val)

Actually something like  arrsz  is a better name than  n .But since the
function is short it doesn't matter that much.

> {
>     int new_arr[N];

Where is  N  defined ?

>     int i, j = 0, done = 0;

size_t i , j ;
int done = 0 ;

>     for (i = 0; i < n; +i)

++i .It seems that you didn't cut and paste your code or you didn't run it
at all. It saves time for all of us if you do both before asking questions.

>     {
> 	if (i == zi || i == zj) continue;
> 	int tmp = arr[i];

It looks nicer to me if you move this declaration outside the loop and just do
an assignment here.

> 	if (!done && val < tmp) {
> 	    new_arr[j++] = val;
> 	    done = 1;
> 	}
>         new_arr[j++] = tmp;
>     }
>     new_arr[j] = val;

if (done == 0) new_arr[j] = val;

>     do_something(new_arr);

How does  do_something()  know the size of  new_arr ?

> }
> 
> It's ugly IMO. Do you have suggestions for improvements?

I don't think it looks ugly but it has bugs.

> This function is called several billion times, so any performance
> improvement will be useful.

You could split it into 2 loops , one before placing  val  into the new
array and one to copy the rest of the array.

-- 
vlaho.ninja/prog

[toc] | [prev] | [next] | [standalone]

#127654

On Sun, 11 Mar 2018 22:13:42 GMT
Spiros Bousbouras <spibou@gmail.com> wrote:
> On Sun, 11 Mar 2018 22:51:40 +0100
> Noob <root@127.0.0.1> wrote:
> > Hello,
> > 
> > I'm writing a toy program where I have a function that copies
> > a small sorted array (less than 12 ints) while making two small
> > changes: remove two elements, insert one element.
> > 
> > The function prototype is:
> > 
> > void update_array(int *arr, int n, int zi, int zj, int val);
> > 
> > arr = the original array, sorted by increasing values
> > n = number of elements < N = 12
> > zi = 1st index to remove
> > zj = 2nd index to remove
> > val = new value to insert while keeping the array sorted
> > 
> > Here's my current implementation:
> > 
> > void update_array(int *arr, int n, int zi, int zj, int val)
> 
> void update_array(const int * const arr , const size_t n ,
>                   const size_t zi , const size_t zj , const int val)
> 
> Actually something like  arrsz  is a better name than  n .But since the
> function is short it doesn't matter that much.
> 
> > {
> >     int new_arr[N];
> 
> Where is  N  defined ?
> 
> >     int i, j = 0, done = 0;
> 
> size_t i , j ;

This ought to be
size_t i , j = 0 ;

[...]

[toc] | [prev] | [next] | [standalone]

#127662

On 11/03/2018 22:13, Spiros Bousbouras wrote:
> On Sun, 11 Mar 2018 22:51:40 +0100
> Noob <root@127.0.0.1> wrote:
>> Hello,
>>
>> I'm writing a toy program where I have a function that copies
>> a small sorted array (less than 12 ints) while making two small
>> changes: remove two elements, insert one element.
>>
>> The function prototype is:
>>
>> void update_array(int *arr, int n, int zi, int zj, int val);
>>
>> arr = the original array, sorted by increasing values
>> n = number of elements < N = 12
>> zi = 1st index to remove
>> zj = 2nd index to remove
>> val = new value to insert while keeping the array sorted
>>
>> Here's my current implementation:
>>
>> void update_array(int *arr, int n, int zi, int zj, int val)
> 
> void update_array(const int * const arr , const size_t n ,
>                    const size_t zi , const size_t zj , const int val)
> 
> Actually something like  arrsz  is a better name than  n.

No, this suggests array size which in C usually means byte-size, not 
number of elements. You might have pointed out that 'update-array' is 
misnamed as the array passed is not modified.

>But since the
> function is short it doesn't matter that much.

Well, it /had/ been short until you introduced all these consts! (Is 
there really a benefit from declaring individual int parameters as const?)

Also, wasn't the OP requesting something less ugly? And something a bit 
faster? Stipulating possible 64-bit types for n, zi and zj, when it was 
stated that all these will be less than 12, probably won't help.

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#127666

On Mon, 12 Mar 2018 10:35:32 +0000
bartc <bc@freeuk.com> wrote:
> On 11/03/2018 22:13, Spiros Bousbouras wrote:
> > On Sun, 11 Mar 2018 22:51:40 +0100
> > Noob <root@127.0.0.1> wrote:
> >> Hello,
> >>
> >> I'm writing a toy program where I have a function that copies
> >> a small sorted array (less than 12 ints) while making two small
> >> changes: remove two elements, insert one element.
> >>
> >> The function prototype is:
> >>
> >> void update_array(int *arr, int n, int zi, int zj, int val);
> >>
> >> arr = the original array, sorted by increasing values
> >> n = number of elements < N = 12
> >> zi = 1st index to remove
> >> zj = 2nd index to remove
> >> val = new value to insert while keeping the array sorted
> >>
> >> Here's my current implementation:
> >>
> >> void update_array(int *arr, int n, int zi, int zj, int val)
> > 
> > void update_array(const int * const arr , const size_t n ,
> >                    const size_t zi , const size_t zj , const int val)
> > 
> > Actually something like  arrsz  is a better name than  n.
> 
> No, this suggests array size which in C usually means byte-size, not 
> number of elements.

You have any statistics to back this up ? I always use it to mean number
of elements.

> You might have pointed out that 'update-array' is 
> misnamed as the array passed is not modified.

Sure.

> >But since the
> > function is short it doesn't matter that much.
> 
> Well, it /had/ been short until you introduced all these consts! (Is 
> there really a benefit from declaring individual int parameters as const?)

It remains short. I thought the  const  declarations might help with
optimisation but the only way to tell is to test.

> Also, wasn't the OP requesting something less ugly? And something a bit 
> faster? Stipulating possible 64-bit types for n, zi and zj, when it was 
> stated that all these will be less than 12, probably won't help.

size_t  is the canonical way to refer to array sizes and array indexes ;
anything else gives one more to think and worry about (like type conversions)
in an area where dangerous errors happen most often. So  size_t  is the
default option unless one has good reasons to do otherwise. If on a machine
size_t  is 64 bit then almost certainly it will be a 64 bit processor so 32
bit integer operations aren't going to be faster than 64 bit. In any case the
opening poster can test ; if using  int  achieves faster speed than using
size_t  and it makes a difference to him then this would be a good reason to
prefer  int  over  size_t .

-- 
vlaho.ninja/prog

[toc] | [prev] | [next] | [standalone]

#127667

On 12/03/2018 12:37, Spiros Bousbouras wrote:
> On Mon, 12 Mar 2018 10:35:32 +0000
> bartc <bc@freeuk.com> wrote:
>> On 11/03/2018 22:13, Spiros Bousbouras wrote:

>>> Actually something like  arrsz  is a better name than  n.
>>
>> No, this suggests array size which in C usually means byte-size, not
>> number of elements.
> 
> You have any statistics to back this up ? I always use it to mean number
> of elements.

If A is a an array like 'int A[10]' then sizeof(A) will the size in 
bytes, not the number of elements.

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#127668

On Mon, 2018-03-12, Spiros Bousbouras wrote:
> On Mon, 12 Mar 2018 10:35:32 +0000
> bartc <bc@freeuk.com> wrote:
>> On 11/03/2018 22:13, Spiros Bousbouras wrote:
...
>> > void update_array(const int * const arr , const size_t n ,
>> >                    const size_t zi , const size_t zj , const int val)
>> > 
>> > Actually something like  arrsz  is a better name than  n.
>> 
>> No, this suggests array size which in C usually means byte-size, not 
>> number of elements.
>
> You have any statistics to back this up ? I always use it to mean number
> of elements.

Me too.  I don't think people tend to count much in bytes at all; IME
you count elements, and convert in the calls to malloc(), memcpy() and
so on.

...
>> >But since the
>> > function is short it doesn't matter that much.
>> 
>> Well, it /had/ been short until you introduced all these consts! (Is 
>> there really a benefit from declaring individual int parameters as const?)
>
> It remains short. I thought the  const  declarations might help with
> optimisation but the only way to tell is to test.

They most likely don't improve optimisation, but they make the function
easier to read and safer to change.

[...]

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [next] | [standalone]

#127944

Jorgen Grahn <grahn+nntp@snipabacken.se> writes:

> On Mon, 2018-03-12, Spiros Bousbouras wrote:
>
>> On Mon, 12 Mar 2018 10:35:32 +0000
>> bartc <bc@freeuk.com> wrote:
>>
>>> On 11/03/2018 22:13, Spiros Bousbouras wrote:
>
> ...
>
>>>> void update_array(const int * const arr , const size_t n ,
>>>>                    const size_t zi , const size_t zj , const int val)
>>>>
>>>> Actually something like  arrsz  is a better name than  n.
>>>
>>> No, this suggests array size which in C usually means byte-size, not
>>> number of elements.
>>
>> You have any statistics to back this up ? I always use it to mean number
>> of elements.
>
> Me too.  I don't think people tend to count much in bytes at all;  IME
> you count elements, and convert in the calls to malloc(), memcpy() and
> so on.

Clearly there is more than one school of thought on this.  When
writing C I try to use "size" as always meaning a size in bytes,
"length" for the number of characters in a string before the
terminating null, and "extent" or "limit" for the number of
elements in (one dimension of) an array.  Of course in talking
informally I might be sloppy and use one of those words in place
of another, but when writing code the result shouldn't ever be
that sloppy.  (Or at least that is what I strive to achieve even
if I don't always succeed.)

[toc] | [prev] | [next] | [standalone]

#127670

On Monday, 12 March 2018 12:37:11 UTC, Spiros Bousbouras  wrote:
> On Mon, 12 Mar 2018 10:35:32 +0000
> bartc <bc@freeuk.com> wrote:
> > On 11/03/2018 22:13, Spiros Bousbouras wrote:

> > > Actually something like  arrsz  is a better name than  n.
> > 
> > No, this suggests array size which in C usually means byte-size, not 
> > number of elements.
> 
> You have any statistics to back this up ? I always use it to mean number
> of elements.

It means byte-size to 100% of 'bartc' which is the important thing.

[toc] | [prev] | [next] | [standalone]

#127672

On 12/03/2018 14:47, mark.bluemel@gmail.com wrote:
> On Monday, 12 March 2018 12:37:11 UTC, Spiros Bousbouras  wrote:
>> On Mon, 12 Mar 2018 10:35:32 +0000
>> bartc <bc@freeuk.com> wrote:
>>> On 11/03/2018 22:13, Spiros Bousbouras wrote:
> 
>>>> Actually something like  arrsz  is a better name than  n.
>>>
>>> No, this suggests array size which in C usually means byte-size, not
>>> number of elements.
>>
>> You have any statistics to back this up ? I always use it to mean number
>> of elements.
> 
> It means byte-size to 100% of 'bartc' which is the important thing.

So referring to the length of the array as its size, even though 
throughout the language 'sizeof(array)' refers to its byte-size not its 
length, is not going to be confusing at all.

OK....

(What would the parameter be named if it /was/ intended to be its 
byte-size?)

[toc] | [prev] | [next] | [standalone]

#127675

On Mon, 12 Mar 2018 14:56:23 +0000
bartc <bc@freeuk.com> wrote:
> On 12/03/2018 14:47, mark.bluemel@gmail.com wrote:
> > On Monday, 12 March 2018 12:37:11 UTC, Spiros Bousbouras  wrote:
> >> On Mon, 12 Mar 2018 10:35:32 +0000
> >> bartc <bc@freeuk.com> wrote:
> >>> On 11/03/2018 22:13, Spiros Bousbouras wrote:
> > 
> >>>> Actually something like  arrsz  is a better name than  n.
> >>>
> >>> No, this suggests array size which in C usually means byte-size, not
> >>> number of elements.
> >>
> >> You have any statistics to back this up ? I always use it to mean number
> >> of elements.
> > 
> > It means byte-size to 100% of 'bartc' which is the important thing.
> 
> So referring to the length of the array as its size, even though 
> throughout the language 'sizeof(array)' refers to its byte-size not its 
> length, is not going to be confusing at all.

It had never occurred to me to look at it this way but I see your point.

> OK....
> 
> (What would the parameter be named if it /was/ intended to be its 
> byte-size?)

I don't know , I've never had a need to give a name to a variable or
parameter to express an array size in bytes. I only use size in bytes
when I use it as an argument to  malloc()  or  realloc() ; in all other
situations , I deal with number of elements.

[toc] | [prev] | [next] | [standalone]

#127678

On Monday, 12 March 2018 14:56:30 UTC, Bart  wrote:
> On 12/03/2018 14:47, mark.bluemel@gmail.com wrote:
> > On Monday, 12 March 2018 12:37:11 UTC, Spiros Bousbouras  wrote:
> >> On Mon, 12 Mar 2018 10:35:32 +0000
> >> bartc <bc@freeuk.com> wrote:
> >>> On 11/03/2018 22:13, Spiros Bousbouras wrote:
> > 
> >>>> Actually something like  arrsz  is a better name than  n.
> >>>
> >>> No, this suggests array size which in C usually means byte-size, not
> >>> number of elements.
> >>
> >> You have any statistics to back this up ? I always use it to mean number
> >> of elements.
> > 
> > It means byte-size to 100% of 'bartc' which is the important thing.
> 
> So referring to the length of the array as its size, even though 
> throughout the language 'sizeof(array)' refers to its byte-size not its 
> length, is not going to be confusing at all.

If someone asks "what size is that array?", I would assume they are interested
in the number of elements it will store, not how many bytes of storage it will
take. But, clearly, YMMV.

To avoid the ambiguity, I may be inclined to call the relevant value n_elements
or something similar. What I would almost never do is use a single letter, but
I'm a working programmer, who spends a lot of time maintaining code, and I like
explicit, expressive naming.

[toc] | [prev] | [next] | [standalone]

#127684

Spiros Bousbouras <spibou@gmail.com> writes:
> On Mon, 12 Mar 2018 10:35:32 +0000
> bartc <bc@freeuk.com> wrote:
>> On 11/03/2018 22:13, Spiros Bousbouras wrote:
[...]
>> > void update_array(const int * const arr , const size_t n ,
>> >                    const size_t zi , const size_t zj , const int val)
>> > 
>> > Actually something like  arrsz  is a better name than  n.
>> 
>> No, this suggests array size which in C usually means byte-size, not 
>> number of elements.
>
> You have any statistics to back this up ? I always use it to mean number
> of elements.

I have no statistics, but since the sizeof operator yields its operand's
size in bytes, I tend to assume that "size" is in bytes.  For the number
of elements in an array, I might use "length" (or "len" if I'm being
terse).

[...]

>> Well, it /had/ been short until you introduced all these consts! (Is 
>> there really a benefit from declaring individual int parameters as const?)
>
> It remains short. I thought the  const  declarations might help with
> optimisation but the only way to tell is to test.

I'd be surprised if adding "const" to an int parameter declaration would
help optimization.  A parameter is a local object, so if the compiler is
doing the analysis necessary for optimization, it should already know
that the object is never modified.

I like to use "const" on (non-parameter) object declarations unless the
object actually needs to be modified, more for the benefit of the reader
than for the benefit of the compiler.  I'm not sure what the best policy
is for parameters.  My own style is admittedly inconsistent.

[...]

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#127689

On Monday, March 12, 2018 at 11:08:09 AM UTC-5, Keith Thompson wrote:
> I'd be surprised if adding "const" to an int parameter declaration would
> help optimization.  A parameter is a local object, so if the compiler is
> doing the analysis necessary for optimization, it should already know
> that the object is never modified.
> 
> I like to use "const" on (non-parameter) object declarations unless the
> object actually needs to be modified, more for the benefit of the reader
> than for the benefit of the compiler.  I'm not sure what the best policy
> is for parameters.  My own style is admittedly inconsistent.

Given the code:

    void foo(const int *p); // Compiler can't see code for this function
    void bar(const int q)
    {
      const int qq = q;
      foo(&qq);
      foo(&qq);
    }
    int boz(int x)
    {
      bar(&x);
      return x;
    }

In the absence of a "const" qualifier on "qq" [in bar()], the code for
"foo" could convert the address of "qq" to an "int*" and use that to
modify qq.  If that happened, behavior would be defined as affecting the
copy of x stored in qq, without modifying x.

Adding the "const" qualifier to qq would allow a compiler to assume that
it could safely pass the address of x directly, rather than having to make
a copy of it first.

I think the same semantics would apply if "q" were declared const and its
address were passed to "foo"; I don't think they would apply if "foo" were
declared as "void foo(int const *restrict p);" since the Standard does not
require that "restrict" qualifiers agree on prototypes and definitions:

   6.7.6.3 p15: ... (In the determination of type compatibility and of a
     composite type, each parameter declared with function or array
     type is taken as having the adjusted type and each parameter
     declared with qualified type is taken as having the unqualified
     version of its declared type.)

Since that appears within the main text, rather than the footnote, I would
interpret that as being normative, suggesting that a prototype

    void foo(const int restrict *p);

would be compatible with a function definition:

    void foo(int *p) { ... }

and I don't see anything that would make the effects of a qualifiers in
a prototype binding upon the function called using it.

[toc] | [prev] | [next] | [standalone]

#127760

On 3/12/18 12:57 PM, supercat@casperkitty.com wrote:
> On Monday, March 12, 2018 at 11:08:09 AM UTC-5, Keith Thompson wrote:
>> I'd be surprised if adding "const" to an int parameter declaration would
>> help optimization.  A parameter is a local object, so if the compiler is
>> doing the analysis necessary for optimization, it should already know
>> that the object is never modified.
>>
>> I like to use "const" on (non-parameter) object declarations unless the
>> object actually needs to be modified, more for the benefit of the reader
>> than for the benefit of the compiler.  I'm not sure what the best policy
>> is for parameters.  My own style is admittedly inconsistent.
> 
> Given the code:
> 
>      void foo(const int *p); // Compiler can't see code for this function
>      void bar(const int q)
>      {
>        const int qq = q;
>        foo(&qq);
>        foo(&qq);
>      }
>      int boz(int x)
>      {
>        bar(&x);
>        return x;
>      }
> 

Constraint error, calling bar with an int* when it is defined as taking 
an int

> In the absence of a "const" qualifier on "qq" [in bar()], the code for
> "foo" could convert the address of "qq" to an "int*" and use that to
> modify qq.  If that happened, behavior would be defined as affecting the
> copy of x stored in qq, without modifying x.
> 
> Adding the "const" qualifier to qq would allow a compiler to assume that
> it could safely pass the address of x directly, rather than having to make
> a copy of it first.
> 
> I think the same semantics would apply if "q" were declared const and its
> address were passed to "foo"; I don't think they would apply if "foo" were
> declared as "void foo(int const *restrict p);" since the Standard does not
> require that "restrict" qualifiers agree on prototypes and definitions:
> 
>     6.7.6.3 p15: ... (In the determination of type compatibility and of a
>       composite type, each parameter declared with function or array
>       type is taken as having the adjusted type and each parameter
>       declared with qualified type is taken as having the unqualified
>       version of its declared type.)
> 
> Since that appears within the main text, rather than the footnote, I would
> interpret that as being normative, suggesting that a prototype
> 
>      void foo(const int restrict *p);
> 
> would be compatible with a function definition:
> 
>      void foo(int *p) { ... }
> 
> and I don't see anything that would make the effects of a qualifiers in
> a prototype binding upon the function called using it.
> 

[toc] | [prev] | [next] | [standalone]

#127669

On 11/03/2018 23:13, Spiros Bousbouras wrote:

> On Sun, 11 Mar 2018, Noob wrote:
>
>> I'm writing a toy program where I have a function that copies
>> a small sorted array (less than 12 ints) while making two small
>> changes: remove two elements, insert one element.
>>
>> The function prototype is:
>>
>> void update_array(int *arr, int n, int zi, int zj, int val);
>>
>> arr = the original array, sorted by increasing values
>> n = number of elements < N = 12
>> zi = 1st index to remove
>> zj = 2nd index to remove
>> val = new value to insert while keeping the array sorted
>>
>> Here's my current implementation:
>>
>> void update_array(int *arr, int n, int zi, int zj, int val)
> 
> void update_array(const int * const arr , const size_t n ,
>                   const size_t zi , const size_t zj , const int val)
> 
> Actually something like  arrsz  is a better name than n. But since the
> function is short it doesn't matter that much.
> 
>> {
>>     int new_arr[N];
> 
> Where is  N  defined ?

N = 12

>>     int i, j = 0, done = 0;
> 
> size_t i , j ;
> int done = 0 ;
> 
>>     for (i = 0; i < n; +i)
> 
> ++i .It seems that you didn't cut and paste your code or you didn't run it
> at all. It saves time for all of us if you do both before asking questions.

You caught me! I wrote the code on a different computer,
and posted it from memory.

>>     {
>> 	if (i == zi || i == zj) continue;
>> 	int tmp = arr[i];
> 
> It looks nicer to me if you move this declaration outside the loop and just do
> an assignment here.

OK, when I said the code looks ugly, I meant the algorithmic
implementation, not the formatting. But point taken.

>> 	if (!done && val < tmp) {
>> 	    new_arr[j++] = val;
>> 	    done = 1;
>> 	}
>>         new_arr[j++] = tmp;
>>     }
>>     new_arr[j] = val;
> 
> if (done == 0) new_arr[j] = val;

In fact, this change makes the code 10% slower!
Kind of like
	if (val != 0) sum += val;
is slower than
	sum += val;

>>     do_something(new_arr);
> 
> How does  do_something()  know the size of  new_arr ?

You're right, it is, in fact

	do_something(new_arr, n-1);

>> It's ugly IMO. Do you have suggestions for improvements?
> 
> I don't think it looks ugly but it has bugs.

What bugs?

>> This function is called several billion times, so any performance
>> improvement will be useful.
> 
> You could split it into 2 loops, one before placing  val  into the new
> array and one to copy the rest of the array.

Yes, I must test that strategy.

Regards.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web