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

Groups > comp.lang.c > #167955

Re: Idle: C library features wish-list.

Show all headers | View raw

On 10/3/2022 3:40 PM, Kaz Kylheku wrote:
> On 2022-10-03, BGB <cr88192@gmail.com> wrote:
>> On 10/2/2022 10:38 PM, Tim Rentsch wrote:
>>> BGB <cr88192@gmail.com> writes:
>>>
>>>> There are some things that come up often that it might be "useful" if
>>>> they could be supported in a more portable ways.
>>>>
>>>> [ ... ]
>>>>
>>>> Any thoughts?...
>>>
>>> None of these is suitable for inclusion in the ISO C standard.
>>
>> Possibly.
>>
>>
>> As noted, this was more an "idle wish list", based mostly on stuff that
>> comes up a lot in my experience, not really a proposal that this stuff
>> be added (as-is) to the C standard.
> 
> I don't know why you would even wish to have most of that stuff in the
> standard.
> 
> The standard would be objectively worse, even for you, whenever
> you're working on anything but the one program where you need any
> of it.
> 

I didn't originally say anything about wanting to add any of this to the 
C standard in the first place...

I would just prefer if it could be "more portable", which could be 
achieved easily enough in a "de-facto" way.



>> A few of them, such as _msize(), exist in MSVCRT, and is functionally
>> equivalent to malloc_usable_size() in GLIBC.
> 
> _msize doesn't return the size that was passed to malloc; it returns
> some rounded up size. Still that can be useful.
> 

Yes, I mentioned this in the OP.

The proposed behavior *was* that it would return the padded-up size.


> Code which manages a buffer that grows when it becomes full
> tracks the allocated size from the actual filled size. With this
> function, you don't have to waste space storing the allocated
> size and keeping it up-to-date: you just retrieve it. Moreover,
> you use the full underlying size without any waste.
> 
> The function would have to be specified such that if you malloc(42),
> and then malsize(ptr) yields 64, it becomes legitimate for you
> to make use of all the bytes bytes 0 to 63.
> 
> Moreover, it would have to be specified that malsize(ptr) is called, and
> returns some value, then it must always return a value at least as large
> for ptr, regardless of any memory allocations or deallocations that take
> place.. The memory indicated by that size must really belong to the
> allocated object.
> 

All this was already implicit in the original idea.


I wasn't claiming:
   p=malloc(42);
   sz=_msize(p);
Should have sz==42, merely sz>=42 ...


Usually, because the allocator does tend to pad things up internally, 
and also we don't usually want to preserve the exact size of the 
allocation in the first place (it is not usually needed, and has a 
non-zero cost needed to store it).


>> Like, say, for example, what if the C library had not provided
>> "memcpy()" and similar, and nearly every application was left to roll
>> their own, often doing so poorly.
> 
> Sure, but how many need a memcpy that allows overlap, but if the
> overlap is in the wrong direction, it then repeats a byte?
> 

Yes.

In this case:
   _memlzcpy(dst+1, dst, 256);
Would be semantically equivalent to:
   memset(dst+1, *dst, 256);

If the delta is 2 bytes, it will repeat those 2 bytes, or 3 bytes will 
repeat a 3 byte pattern, etc.


> A memcpy that allows overlap, if the second operand has a higher
> address than the first, would be mildly useful. However,
> if we say that the second address must be higher, that can be
> satisfied by it being higher only by a byte.
> 
> The motivation for that function is that a simple loop can perform the
> copy, which sweeps over both operands in order of increasing address.
> However, it can only work reliably if the transfer unit's width
> is no larger than the displacement between the two buffers.
> So in the case of a one byte difference, the loop must transfer
> a byte at a time.
> 

Not necessarily, in a typical implementation, it can be turned into a 
pattern-fill register, which is then written to memory in a single 
larger block.

We don't want to fall back to a "one byte at a time" copy in this case, 
because this is slow; but it is necessary to have the same output 
*as-if* it had been a "byte at a time" copy operation.



> In cases when the address delta can't be deduced at compile time,
> that function would have to switch on the delta size, and say
> handle the 1, 2, 4 and 8 byte cases specially. Plus handle the
> alignment cases and all that.
> 

Yes.


Typically, it needs to specially handle all 1-15 cases, with 16+ bytes 
cases typically able to fall back to the normal SIMD based copy, and 
another (slightly faster) SIMD loop usually at 32 or 64 bytes.



Non-power-of-2 sizes (3/5/7/...) get a little more complicated, but 
would still need to be handled.

Usual options for this are one of:
Pattern fill has a non-power-of-2 stepping, using misaligned memory stores;
Multiple pattern fills are generated, with the fill alternating between 
fill patterns based on a modulo.


The latter case is more limited in scope (doesn't scale very well), so 
the former is typically what is used (say, each store is 128 bits, but 
the destination pointer is advanced by 13 or 15 bytes or similar each time).

Despite typically needing to pay a penalty for misaligned SIMD store, 
this tends to work out faster on-average than the other option (as well 
as being a lot simpler in terms of the required "big blobs of ASM").



> It's not clear that it would end up winning very much over memmove.
> Programmers who want the most performance out of memcpy just
> make it non-overlapping.
> 

memmove has the wrong semantics for cases where one actually needs the 
preceding behavior.

The point of "_memlzcpy()" is partly because:
In some cases, one needs these particular semantics for overlapping 
copies (so paying these costs is unavoidable);
One doesn't want to make normal "memcpy()" slower by asking it to 
detect/handle scenarios that are N/A to most normal uses of memcpy.


So, one ends up with programs needing to implement their own version, 
with it often either being slow or turning into an ugly mess of 
platform-specific code.

As implied by the name, one of the major cases where this comes up tends 
to be things like LZ77 decompressors (such as: LZ4, Deflate, etc).

For some decompressors (such as LZ4, or my own RP2 format), copying 
matches around in the "sliding window" tends to be the majority of the 
clock-cycle budget for these tasks.



> Versions of memcpy and memmove which allow the application to
> specify the alignment (whereby the application ensures that
> the promised alignemnt is true) would be useful:
> 
>    /* array copy, array move */
> 
>    /* non-overlapping operands.
>       both operand pointers aligned to elem_size, else UB. */
> 
>    arrcpy(dest, src, elem_cnt, elem_size)
> 
>    /* Possibly overlapping operands.
>       both operand pointers aligned to elem_size, else UB. */
> 
>    arrmove(dest, src, elem_cnt, elem_size)
> 
> Copy operations that don't have to handle run-time alignment cases, and
> odd leftover sizes, could likely be implemented faster.
> 

Yes, granted.

Possible option is specifying both the size and alignment...

Well, and/or doing the more naive solution and providing functions for 
each (power of 2) combination of size and alignment up to a certain range.

   _arrmcpy_16x8(dst, src, cnt);  //16-byte items with 8-byte alignment
   _arrmcpy_64x16(dst, src, cnt);  //64-byte items with 16-byte alignment
   ...


> The elem_size expression is often a constant expression, in which cases
> the compiler can rewrite the call to use a function which handles that
> transfer unit size (or multiples), without worrying about alignment or
> partial transfer units at the end.
> 
> ISO C (since 99) has something like this, for wchar_t: wmemcpy
> and wmemmove. The above functions would just generalize that.
> 

Granted.

My compiler also does some similar stuff internally for things like 
struct copying, since it statically knows the size and alignment of the 
struct or array.


Otherwise, "memcpy()" is also specialized in some cases as well, since 
the compiler can "see" the types and alignments of the passed in 
pointers, and if the copy size is constant, and so may special case some 
of this (only producing a "true" memcpy call as a fallback case). In 
some other cases, it might turn it into bare loads and stores.

Likewise, "memset()" may also get similar treatment.



Also can note that for a lot of this, I am dealing with a 64-bit VLIW 
architecture clocked at 50 MHz, where "little things" like this can have 
a fairly drastic impact on performance.

Likewise, the performance difference between a SIMD copy loop, and a 
"byte at a time" copy loop, is nearly 2 orders of magnitude.


Where, say (for a 50MHz CPU core):
   Byte-at-a-time copy loop runs at roughly 4.5 MB/s;
   SIMD copy loop can run closer to around 290 MB/s.

Partly as the CPU in this case is pretty much entirely devoid of the 
sorts of OoO cleverness one might expect on x86 and friends.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Idle: C library features wish-list. BGB <cr88192@gmail.com> - 2022-09-30 16:34 -0500
  Re: Idle: C library features wish-list. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-10-02 20:38 -0700
    Re: Idle: C library features wish-list. BGB <cr88192@gmail.com> - 2022-10-03 01:14 -0500
      Re: Idle: C library features wish-list. Kaz Kylheku <864-117-4973@kylheku.com> - 2022-10-03 20:40 +0000
        Re: Idle: C library features wish-list. scott@slp53.sl.home (Scott Lurndal) - 2022-10-03 21:10 +0000
          Re: Idle: C library features wish-list. BGB <cr88192@gmail.com> - 2022-10-03 19:07 -0500
            Re: Idle: C library features wish-list. scott@slp53.sl.home (Scott Lurndal) - 2022-10-04 13:43 +0000
              Re: Idle: C library features wish-list. BGB <cr88192@gmail.com> - 2022-10-04 15:20 -0500
                Re: Idle: C library features wish-list. BGB <cr88192@gmail.com> - 2022-10-05 03:58 -0500
            Re: Idle: C library features wish-list. Kaz Kylheku <864-117-4973@kylheku.com> - 2022-10-04 16:56 +0000
              Re: Idle: C library features wish-list. BGB <cr88192@gmail.com> - 2022-10-04 18:30 -0500
        Re: Idle: C library features wish-list. BGB <cr88192@gmail.com> - 2022-10-03 18:19 -0500
      Re: Idle: C library features wish-list. Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-11-19 06:54 -0800
    Re: Idle: C library features wish-list. gazelle@shell.xmission.com (Kenny McCormack) - 2022-10-03 09:29 +0000

csiph-web