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

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

evaluate a generic swap function

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

Contents

  evaluate a generic swap function Stanley Rice <heconghui@gmail.com> - 2011-09-20 06:51 -0700
    Re: evaluate a generic swap function jacob navia <jacob@spamsink.net> - 2011-09-20 16:01 +0200
      Re: evaluate a generic swap function jt@toerring.de (Jens Thoms Toerring) - 2011-09-20 14:29 +0000
        Re: evaluate a generic swap function jacob navia <jacob@spamsink.net> - 2011-09-20 21:13 +0200
          Re: evaluate a generic swap function jt@toerring.de (Jens Thoms Toerring) - 2011-09-20 20:30 +0000
            Re: evaluate a generic swap function Keith Thompson <kst-u@mib.org> - 2011-09-20 17:05 -0700
              Re: evaluate a generic swap function gazelle@shell.xmission.com (Kenny McCormack) - 2011-09-21 15:45 +0000
                Re: evaluate a generic swap function Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-21 09:33 -0700
                Re: evaluate a generic swap function jacob navia <jacob@spamsink.net> - 2011-09-21 19:17 +0200
                  Re: evaluate a generic swap function gazelle@shell.xmission.com (Kenny McCormack) - 2011-09-21 17:34 +0000
                    Re: evaluate a generic swap function Jack Foot <foot@dev.null.invalid> - 2011-09-21 18:12 +0000
    Re: evaluate a generic swap function Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-20 07:33 -0700
      Re: evaluate a generic swap function ImpalerCore <jadill33@gmail.com> - 2011-09-20 08:26 -0700
        Re: evaluate a generic swap function pete <pfiland@mindspring.com> - 2011-09-20 23:10 -0400
    Re: evaluate a generic swap function "BartC" <bc@freeuk.com> - 2011-09-20 22:20 +0100
      Re: evaluate a generic swap function jacob navia <jacob@spamsink.net> - 2011-09-20 23:23 +0200
        Re: evaluate a generic swap function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-20 23:07 +0100
    Re: evaluate a generic swap function Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-20 21:15 -0400
      Re: evaluate a generic swap function Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-09-21 03:17 -0700
    Re: evaluate a generic swap function Gene <gene.ressler@gmail.com> - 2011-09-21 02:40 -0700
    Re: evaluate a generic swap function Seebs <usenet-nospam@seebs.net> - 2011-09-23 01:46 +0000
      Re: evaluate a generic swap function Nelu <tandauioan@gmail.com> - 2011-09-23 10:26 -0700
        Re: evaluate a generic swap function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-23 18:36 +0100
          Re: evaluate a generic swap function Nelu <tandauioan@gmail.com> - 2011-09-23 10:49 -0700
            Re: evaluate a generic swap function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-23 20:18 +0100
              Re: evaluate a generic swap function Nelu <tandauioan@gmail.com> - 2011-09-23 12:54 -0700
                Re: evaluate a generic swap function James Kuyper <jameskuyper@verizon.net> - 2011-09-23 16:43 -0400
                  Re: evaluate a generic swap function Nelu <tandauioan@gmail.com> - 2011-09-23 13:49 -0700
                    Re: evaluate a generic swap function James Kuyper <jameskuyper@verizon.net> - 2011-09-23 17:44 -0400
                      Re: evaluate a generic swap function Nelu <tandauioan@gmail.com> - 2011-09-23 18:04 -0700
                      Re: evaluate a generic swap function Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-24 13:52 -0800
                Re: evaluate a generic swap function Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-23 21:46 +0100
                  Re: evaluate a generic swap function Nelu <tandauioan@gmail.com> - 2011-09-23 13:59 -0700
                    Re: evaluate a generic swap function Seebs <usenet-nospam@seebs.net> - 2011-09-26 22:59 +0000
            Re: evaluate a generic swap function pete <pfiland@mindspring.com> - 2011-09-23 18:19 -0400
              Re: evaluate a generic swap function Nelu <tandauioan@gmail.com> - 2011-09-23 16:36 -0700

Page 2 of 2 — ← Prev page 1 [2]

#10734

On 2011-09-20, Stanley Rice <heconghui@gmail.com> wrote:
> I wrote a "generic" swap function, which can swap some type, such as
> int, double, long. But I don't know how to evaluate this function, and
> don't know whether it's a good idea to use such a function. I hope you
> can give me some suggestions.

Okay.

>  void swap(void *left, void *right, size_t siz)
> {
>     char *buf;

>     buf = (char *)malloc(sizeof(*buf) * siz);

1.  Don't cast the return of malloc in C.
2.  I wouldn't do this.  I'd just iterate through swapping the bytes
individually.

	{
		unsigned char u;
		unsigned char *l = left;
		unsigned char *r = right;
		for (int i = 0; i < siz; ++i) {
			u = *l;
			*l = *r;
			*r = u;
			++l;
			++r;
		}
	}

Slow?  Maybe.  But:

1.  I don't have any data showing that I need to optimize this function
more.
2.  malloc() is usually VERY expensive compared to most stuff I do.

-s
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

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

#10780

On Thursday, September 22, 2011 9:46:50 PM UTC-4, Seebs wrote:
> On 2011-09-20, Stanley Rice <heco...@gmail.com> wrote:
> > I wrote a "generic" swap function, which can swap some type, such as
> > int, double, long. But I don't know how to evaluate this function, and
> > don't know whether it's a good idea to use such a function. I hope you
> > can give me some suggestions.
> 
<snip>
> 2.  I wouldn't do this.  I'd just iterate through swapping the bytes
> individually.
<snip sample code> 
> Slow?  Maybe.  But:

It could probably be made faster using a static array of unsigned chars to swap blocks if there is no need for thread safety.

It can be made thread safe using a thread local variable but it would work best (avoiding malloc for each operation) if the threads were reused. This is, however, dependent on the threading library and not on topic here.

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

#10784

Nelu <tandauioan@gmail.com> writes:

> On Thursday, September 22, 2011 9:46:50 PM UTC-4, Seebs wrote:
>> On 2011-09-20, Stanley Rice <heco...@gmail.com> wrote:
>> > I wrote a "generic" swap function, which can swap some type, such as
>> > int, double, long. But I don't know how to evaluate this function, and
>> > don't know whether it's a good idea to use such a function. I hope you
>> > can give me some suggestions.
>> 
> <snip>
>> 2.  I wouldn't do this.  I'd just iterate through swapping the bytes
>> individually.
> <snip sample code> 
>> Slow?  Maybe.  But:
>
> It could probably be made faster using a static array of unsigned
> chars to swap blocks if there is no need for thread safety.

I don't understand the static part.  As you say, it introduces a problem
(for threaded code) but surely an automatic array is the way to go
anyway?

> It can be made thread safe using a thread local variable but it would
> work best (avoiding malloc for each operation) if the threads were
> reused. This is, however, dependent on the threading library and not
> on topic here.

I'd "fix" this not with thread local storage but with an automatic
array.  I posted an example of block swapping this way a day or so ago.

-- 
Ben.

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

#10792

On Friday, September 23, 2011 1:36:07 PM UTC-4, Ben Bacarisse wrote:
> Nelu <tanda...@gmail.com> writes:
> 
> > On Thursday, September 22, 2011 9:46:50 PM UTC-4, Seebs wrote:
> >> On 2011-09-20, Stanley Rice <hec...@gmail.com> wrote:
> >> > I wrote a "generic" swap function, which can swap some type, such as
> >> > int, double, long. But I don't know how to evaluate this function, and
> >> > don't know whether it's a good idea to use such a function. I hope you
> >> > can give me some suggestions.
> >> 
> > <snip>
> >> 2.  I wouldn't do this.  I'd just iterate through swapping the bytes
> >> individually.
> > <snip sample code> 
> >> Slow?  Maybe.  But:
> >
> > It could probably be made faster using a static array of unsigned
> > chars to swap blocks if there is no need for thread safety.
> 
> I don't understand the static part.  As you say, it introduces a problem
> (for threaded code) but surely an automatic array is the way to go
> anyway?
> 
> > It can be made thread safe using a thread local variable but it would
> > work best (avoiding malloc for each operation) if the threads were
> > reused. This is, however, dependent on the threading library and not
> > on topic here.
> 
> I'd "fix" this not with thread local storage but with an automatic
> array.  I posted an example of block swapping this way a day or so ago.

Yes, but memory for the tmp variable in your example is allocated/deallocated every time you enter/exit the block of code. The static variable is allocated at the start of the program and successive calls to the function will not need to allocate more memory. Same with the thread local variables as long as you reuse the same threads, no?

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

#10794

Nelu <tandauioan@gmail.com> writes:

> On Friday, September 23, 2011 1:36:07 PM UTC-4, Ben Bacarisse wrote:
>> Nelu <tanda...@gmail.com> writes:
>> 
>> > On Thursday, September 22, 2011 9:46:50 PM UTC-4, Seebs wrote:
>> >> On 2011-09-20, Stanley Rice <hec...@gmail.com> wrote:
>> >> > I wrote a "generic" swap function, which can swap some type, such as
>> >> > int, double, long. But I don't know how to evaluate this function, and
>> >> > don't know whether it's a good idea to use such a function. I hope you
>> >> > can give me some suggestions.
>> >> 
>> > <snip>
>> >> 2.  I wouldn't do this.  I'd just iterate through swapping the bytes
>> >> individually.
>> > <snip sample code> 
>> >> Slow?  Maybe.  But:
>> >
>> > It could probably be made faster using a static array of unsigned
>> > chars to swap blocks if there is no need for thread safety.
>> 
>> I don't understand the static part.  As you say, it introduces a problem
>> (for threaded code) but surely an automatic array is the way to go
>> anyway?
>> 
>> > It can be made thread safe using a thread local variable but it would
>> > work best (avoiding malloc for each operation) if the threads were
>> > reused. This is, however, dependent on the threading library and not
>> > on topic here.
>> 
>> I'd "fix" this not with thread local storage but with an automatic
>> array.  I posted an example of block swapping this way a day or so ago.
>
> Yes, but memory for the tmp variable in your example is
> allocated/deallocated every time you enter/exit the block of code. The
> static variable is allocated at the start of the program and
> successive calls to the function will not need to allocate more
> memory. Same with the thread local variables as long as you reuse the
> same threads, no?

It is a rare program that has to worry about the allocation of an
automatic array.  The CPU cost is often zero.  Since a swap that uses an
auto buffer is entirely portable and is likely as efficient as one that
uses non-portable thread local storage or possibly problematic static
storage, it's the way I'd go every time.

-- 
Ben.

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

#10797

On Friday, September 23, 2011 3:18:20 PM UTC-4, Ben Bacarisse wrote:
> Nelu <tanda...@gmail.com> writes:
> 
> <snip>
> > Yes, but memory for the tmp variable in your example is
> > allocated/deallocated every time you enter/exit the block of code. The
> > static variable is allocated at the start of the program and
> > successive calls to the function will not need to allocate more
> > memory. Same with the thread local variables as long as you reuse the
> > same threads, no?
> 
> It is a rare program that has to worry about the allocation of an
> automatic array.  The CPU cost is often zero.  Since a swap that uses an
> auto buffer is entirely portable and is likely as efficient as one that
> uses non-portable thread local storage or possibly problematic static
> storage, it's the way I'd go every time.

That makes sense. In the DOS days the stack size was a limiting factor, I think. Is the size of the automatic array subject to implementation or are there minimal requirements imposed by the standard?

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

#10801

On 09/23/2011 03:54 PM, Nelu wrote:
> On Friday, September 23, 2011 3:18:20 PM UTC-4, Ben Bacarisse wrote:
...
>> It is a rare program that has to worry about the allocation of an
>> automatic array.  The CPU cost is often zero.  Since a swap that uses an
>> auto buffer is entirely portable and is likely as efficient as one that
>> uses non-portable thread local storage or possibly problematic static
>> storage, it's the way I'd go every time.
> 
> That makes sense. In the DOS days the stack size was a limiting factor, I think. Is the size of the automatic array subject to implementation or are there minimal requirements imposed by the standard?

The C standard never even mentions the stack, and can be implemented on
machines without a hardware stack. Even on platforms where there is a
stack, the C standard imposes no requirements from which you can infer a
minimum size for that stack.

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

#10814

On Friday, September 23, 2011 4:43:36 PM UTC-4, James Kuyper wrote:
> On 09/23/2011 03:54 PM, Nelu wrote:
> > On Friday, September 23, 2011 3:18:20 PM UTC-4, Ben Bacarisse wrote:
> ...
> >> It is a rare program that has to worry about the allocation of an
> >> automatic array.  The CPU cost is often zero.  Since a swap that uses an
> >> auto buffer is entirely portable and is likely as efficient as one that
> >> uses non-portable thread local storage or possibly problematic static
> >> storage, it's the way I'd go every time.
> > 
> > That makes sense. In the DOS days the stack size was a limiting factor, I think. Is the size of the automatic array subject to implementation or are there minimal requirements imposed by the standard?
> 
> The C standard never even mentions the stack, and can be implemented on
> machines without a hardware stack. Even on platforms where there is a
> stack, the C standard imposes no requirements from which you can infer a
> minimum size for that stack.

I know that there is no reference to a stack in the standard. The DOS stack thing was just an example. My question was about the standard and the minimal guarantees for the size of automatic variables. I haven't seen anything in the draft I have but I thought I may have missed it.

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

#10819

On 09/23/2011 04:49 PM, Nelu wrote:
> On Friday, September 23, 2011 4:43:36 PM UTC-4, James Kuyper wrote:
>> On 09/23/2011 03:54 PM, Nelu wrote:
...
>>> That makes sense. In the DOS days the stack size was a limiting factor, I think. Is the size of the automatic array subject to implementation or are there minimal requirements imposed by the standard?
>>
>> The C standard never even mentions the stack, and can be implemented on
>> machines without a hardware stack. Even on platforms where there is a
>> stack, the C standard imposes no requirements from which you can infer a
>> minimum size for that stack.
> 
> I know that there is no reference to a stack in the standard. The DOS stack thing was just an example. My question was about the standard and the minimal guarantees for the size of automatic variables. I haven't seen anything in the draft I have but I thought I may have missed it.

It doesn't. Every implementation of C must include a single program
meeting certain requirements, which it must translate and execute
correctly. A naive examination of those requirements would imply that a
stack based implementation needs to allow sufficient stack space for at
least one call to a function that takes at least 127 arguments. However,
that function call could be written in such a way that it would be
optimized away, so that a much smaller stack would be sufficient. None
of the other limits are applicable.

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

#10837

On Friday, September 23, 2011 5:44:53 PM UTC-4, James Kuyper wrote:
> On 09/23/2011 04:49 PM, Nelu wrote:
> > On Friday, September 23, 2011 4:43:36 PM UTC-4, James Kuyper wrote:
> >> On 09/23/2011 03:54 PM, Nelu wrote:
> ...
> >>> That makes sense. In the DOS days the stack size was a limiting factor, I think. Is the size of the automatic array subject to implementation or are there minimal requirements imposed by the standard?
> >>
> >> The C standard never even mentions the stack, and can be implemented on
> >> machines without a hardware stack. Even on platforms where there is a
> >> stack, the C standard imposes no requirements from which you can infer a
> >> minimum size for that stack.
> > 
> > I know that there is no reference to a stack in the standard. The DOS stack thing was just an example. My question was about the standard and the minimal guarantees for the size of automatic variables. I haven't seen anything in the draft I have but I thought I may have missed it.
> 
> It doesn't. Every implementation of C must include a single program
> meeting certain requirements, which it must translate and execute
> correctly. A naive examination of those requirements would imply that a
> stack based implementation needs to allow sufficient stack space for at
> least one call to a function that takes at least 127 arguments. However,
> that function call could be written in such a way that it would be
> optimized away, so that a much smaller stack would be sufficient. None
> of the other limits are applicable.

Thanks.

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

#16130

James Kuyper <jameskuyper@verizon.net> writes:

> On 09/23/2011 04:49 PM, Nelu wrote:
>> On Friday, September 23, 2011 4:43:36 PM UTC-4, James Kuyper wrote:
>>> On 09/23/2011 03:54 PM, Nelu wrote:
> ...
>>>> That makes sense. In the DOS days the stack size was a limiting factor, I think. Is the size of the automatic array subject to implementation or are there minimal requirements imposed by the standard?
>>>
>>> The C standard never even mentions the stack, and can be implemented on
>>> machines without a hardware stack. Even on platforms where there is a
>>> stack, the C standard imposes no requirements from which you can infer a
>>> minimum size for that stack.
>> 
>> I know that there is no reference to a stack in the standard. The DOS
>> stack thing was just an example. My question was about the standard
>> and the minimal guarantees for the size of automatic variables. I
>> haven't seen anything in the draft I have but I thought I may have
>> missed it.
>
> It doesn't.  Every implementation of C must include a single program
> meeting certain requirements, which it must translate and execute
> correctly.  [snip]

Not exactly right.  There must be such a program, but there
is no obligation for the implementation to include it, or
even say anything about it at all.

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

#10802

Nelu <tandauioan@gmail.com> writes:

> On Friday, September 23, 2011 3:18:20 PM UTC-4, Ben Bacarisse wrote:
>> Nelu <tanda...@gmail.com> writes:
>> 
>> <snip>
>> > Yes, but memory for the tmp variable in your example is
>> > allocated/deallocated every time you enter/exit the block of code. The
>> > static variable is allocated at the start of the program and
>> > successive calls to the function will not need to allocate more
>> > memory. Same with the thread local variables as long as you reuse the
>> > same threads, no?
>> 
>> It is a rare program that has to worry about the allocation of an
>> automatic array.  The CPU cost is often zero.  Since a swap that uses an
>> auto buffer is entirely portable and is likely as efficient as one that
>> uses non-portable thread local storage or possibly problematic static
>> storage, it's the way I'd go every time.
>
> That makes sense. In the DOS days the stack size was a limiting
> factor, I think. Is the size of the automatic array subject to
> implementation or are there minimal requirements imposed by the
> standard?

The standard does not guarantee very much at all about minimum
provision.  It's almost impossible to do so -- you'd have to qualify
everything.  It can't say that you can always make an array of at least
X bytes, because you might be deeply nested in function calls already.

You make a good point, though.  There are cases where resources are very
limited and in these special cases (say some weird embedded system with
very low memory) alternatives are needed (the obvious one being byte by
byte copy until measurement show it to be a bottleneck).  So, yes, I
should have said "every time unless there is some environmental reason
to consider alternatives".

-- 
Ben.

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

#10810

On Friday, September 23, 2011 4:46:52 PM UTC-4, Ben Bacarisse wrote:
> Nelu <tanda...@gmail.com> writes:
> 
> > On Friday, September 23, 2011 3:18:20 PM UTC-4, Ben Bacarisse wrote:
> > That makes sense. In the DOS days the stack size was a limiting
> > factor, I think. Is the size of the automatic array subject to
> > implementation or are there minimal requirements imposed by the
> > standard?
> 
<snip>
> You make a good point, though.  There are cases where resources are very
> limited and in these special cases (say some weird embedded system with
> very low memory) alternatives are needed (the obvious one being byte by
> byte copy until measurement show it to be a bottleneck).  So, yes, I
> should have said "every time unless there is some environmental reason
> to consider alternatives".

I was wondering if this was one consideration behind using statically allocated memory for gmtime().

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

#10974

On 2011-09-23, Nelu <tandauioan@gmail.com> wrote:
> I was wondering if this was one consideration behind using
> statically allocated memory for gmtime().

Probably not.  A lot of functions like that predate threading (no, really!)
and static was an easy way to allow you to return the address of something
without having to alloc it.

-s
-- 
Copyright 2011, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.

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

#10825

Nelu wrote:
 
> Yes, but memory for the tmp variable in your example is allocated/deallocated every time you enter/exit the block of code. The static variable is allocated at the start of the program and successive calls to the function will not need to allocate more memory. Same with the thread local variables as long as you reuse the same threads, no?

If you want instead, to have a single memory reservation
for multiple function calls, and also to have thread safety,
then you could copy the technique used for the renentrant
varieties of strtok, commonly available on many systems
and usually known as either strtok_r or strtokr.
You add another parameter to the swap function 
with the address of the scratch memory.  
The scratch memory is reserved in the calling function
and can have any kind of duration.

-- 
pete

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

#10834

On Friday, September 23, 2011 6:19:10 PM UTC-4, pete wrote:
> Nelu wrote:
>  
> > Yes, but memory for the tmp variable in your example is allocated/deallocated every time you enter/exit the block of code. The static variable is allocated at the start of the program and successive calls to the function will not need to allocate more memory. Same with the thread local variables as long as you reuse the same threads, no?
> 
> If you want instead, to have a single memory reservation
> for multiple function calls, and also to have thread safety,
> then you could copy the technique used for the renentrant
> varieties of strtok, commonly available on many systems
> and usually known as either strtok_r or strtokr.
> You add another parameter to the swap function 
> with the address of the scratch memory.  
> The scratch memory is reserved in the calling function
> and can have any kind of duration.

Yes, that's what I usually do. Here, I was only considering the function prototype that the OP used.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web