memmove broken

Hi

I just tried to used memmove in zlib(zlib_inflate_fast) to avoid expensive
byte copies. That didn't work and the reason is that the ppc memmove can handle
overlapping memory it seems.

memmove(dst, dst-x, n) where x is between 1 and 39, n >= x will cause corruption for me.

  Jocke


** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Joakim Tjernlund writes:

I just tried to used memmove in zlib(zlib_inflate_fast) to avoid expensive
byte copies. That didn't work and the reason is that the ppc memmove can handle
overlapping memory it seems.

I assume you mean "can't handle"?

If so, this is interesting because it is supposed to work. :)

memmove(dst, dst-x, n) where x is between 1 and 39, n >= x will cause corruption for me.

Gack.  It should be using backwards_memcpy in arch/ppc/lib/string.S.
I'll have to take a look at it.

Paul.

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Joakim Tjernlund writes:

quoted

I just tried to used memmove in zlib(zlib_inflate_fast) to avoid expensive
byte copies. That didn't work and the reason is that the ppc memmove can handle
overlapping memory it seems.

I assume you mean "can't handle"?

Yes :)

If so, this is interesting because it is supposed to work. :)

quoted

memmove(dst, dst-x, n) where x is between 1 and 39, n >= x will cause corruption for me.

Gack.  It should be using backwards_memcpy in arch/ppc/lib/string.S.
I'll have to take a look at it.

Paul,
I just realized that there is something strange going on in zlib.
zlib_inflate_fast() does a standard byte copy:
do{
  *q++ = *r++;
while(--c); /* c >= 3 */

q is always greater than r and this works. This is something else than a
regular mem copy. I havn't figured out yet what is happening here but I don't
think there is a problem with backwards_memcpy()

    Jocke


** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Joakim Tjernlund writes:

I just realized that there is something strange going on in zlib.
zlib_inflate_fast() does a standard byte copy:
do{
  *q++ = *r++;
while(--c); /* c >= 3 */

q is always greater than r and this works. This is something else than a
regular mem copy. I havn't figured out yet what is happening here but I don't
think there is a problem with backwards_memcpy()

Ah. Yes.  This is actually quite clever.  If you have for example 256
zero bytes to compress, zlib will output a single literal zero byte
and then a block reference of length 255 and offset -1, saying that
the block from 1..255 is the same as the block from 0..254.  So the
fact that it copies forwards byte by byte is essential.  So you
couldn't use memcpy() either since it copies in larger chunks than 1
byte.

Paul.

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Joakim Tjernlund writes:

quoted

I just realized that there is something strange going on in zlib.
zlib_inflate_fast() does a standard byte copy:
do{
  *q++ = *r++;
while(--c); /* c >= 3 */

q is always greater than r and this works. This is something else than a
regular mem copy. I havn't figured out yet what is happening here but I don't
think there is a problem with backwards_memcpy()

Ah. Yes.  This is actually quite clever.  If you have for example 256
zero bytes to compress, zlib will output a single literal zero byte
and then a block reference of length 255 and offset -1, saying that
the block from 1..255 is the same as the block from 0..254.  So the
fact that it copies forwards byte by byte is essential.  So you
couldn't use memcpy() either since it copies in larger chunks than 1
byte.

I see, thanks.

Currenly this works, but it is PPC specific:
static inline void memcpy_update(Byte **dest, Byte **src, size_t *n)
{
  if(*dest - *src <= 8){ /* memcpy on PPC will do 8 bytes in a chunk */
    **dest = **src;
    --(*n);
    do {
      *++(*dest) = *++(*src);
    } while (--(*n));
    (*dest)++;  (*src)++;
  } else {
    memcpy(*dest, *src, *n);
    *dest += *n;
    *src += *n;
    *n = 0;
  }

Jocke


** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Joakim Tjernlund writes:

Currenly this works, but it is PPC specific:
static inline void memcpy_update(Byte **dest, Byte **src, size_t *n)
{
  if(*dest - *src <= 8){ /* memcpy on PPC will do 8 bytes in a chunk */
    **dest = **src;
    --(*n);
    do {
      *++(*dest) = *++(*src);
    } while (--(*n));
    (*dest)++;  (*src)++;
  } else {
    memcpy(*dest, *src, *n);
    *dest += *n;
    *src += *n;
    *n = 0;
  }

Why is it an issue?  Is the performance of the byte-by-byte loop
really a limiting factor for you?

In general the behaviour of memcpy with overlapping regions is very
implementation-dependent.  If we use the code above then that would
place constraints on what we can do in memcpy - and very non-obvious
constraints at that.  For example if we decided to use altivec loads
and stores in memcpy, it would then do 16 or 32 bytes in a chunk and
thus break zlib again.

Paul.

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

On Sat, 5 July 2003 09:38:46 +1000, Paul Mackerras wrote:

Joakim Tjernlund writes:

quoted

Currenly this works, but it is PPC specific:
static inline void memcpy_update(Byte **dest, Byte **src, size_t *n)
{
  if(*dest - *src <= 8){ /* memcpy on PPC will do 8 bytes in a chunk */
    **dest = **src;
    --(*n);
    do {
      *++(*dest) = *++(*src);
    } while (--(*n));
    (*dest)++;  (*src)++;
  } else {
    memcpy(*dest, *src, *n);
    *dest += *n;
    *src += *n;
    *n = 0;
  }

Why is it an issue?  Is the performance of the byte-by-byte loop
really a limiting factor for you?

Not a limiting factor, but it should be noticable.  What is more
important - in my eyes - is that we can replace magic with obvious
code.

In general the behaviour of memcpy with overlapping regions is very
implementation-dependent.  If we use the code above then that would
place constraints on what we can do in memcpy - and very non-obvious
constraints at that.  For example if we decided to use altivec loads
and stores in memcpy, it would then do 16 or 32 bytes in a chunk and
thus break zlib again.

That should not be a problem.  memcpy has a very defined behaviour, as
long as source and destination don't overlap at all or as the sourse
is smaller, than the distination.  Cool.

We should be able to do something like this in the zlib:
if (repeat one byte over and over) /* undefined behaviour for memcpy */
	memset();
else {
	if (copy is wrapped) {
		memcpy(wrapped part);
		tweak pointers;
	}
	memcpy();

With that, source should always be smaller than destination for
memcpy, so the implementation details don't matter, as long as memcpy
doesn't do a reverse memcpy.

Plus, the zlib code is shorter and tells the reader exactly what it
does, without the need for extra comments.

Jörn

--
Don't worry about people stealing your ideas. If your ideas are any good,
you'll have to ram them down people's throats.
-- Howard Aiken quoted by Ken Iverson quoted by Jim Horning quoted by
   Raph Levien, 1979

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

On Sat, 5 Jul 2003, [iso-8859-1] Jörn Engel wrote:

[...]

quoted

Why is it an issue?  Is the performance of the byte-by-byte loop
really a limiting factor for you?

Not a limiting factor, but it should be noticable.  What is more
important - in my eyes - is that we can replace magic with obvious
code.

Doing runlength coding with LZ-style compressors is not magic, it's
actually a fairly old trick.

[...]

memcpy has a very defined behaviour, as
long as source and destination don't overlap at all or as the sourse
is smaller, than the distination.  Cool.

The direction of memcpy is not guaranteed. Non-overlap is the only
situation when memcpy has portable behaviour.

[...]

With that, source should always be smaller than destination for
memcpy, so the implementation details don't matter, as long as memcpy
doesn't do a reverse memcpy.

Not even a guarantee of direction helps, because memcpy might copy in
larger units than single chars. This also breaks the dependency chain of
an originally byte-wise copy. (If you copy in units of 32 bits, the first
char of the source block will definitely not be replicated over the
successive three chars, as a byte copy would do.)

Plus, the zlib code is shorter and tells the reader exactly what it
does, without the need for extra comments.

There is only one portable and correct way to use memcpy in an LZ
decompressor: the source data must be completely within the "past" part of
data (already decompressed, immutable), and the destination address must
be completely within the "future" part (the undefined memory buffer ahead of
the pointer to the current byte).

So you have to check if the ending address of the source block is smaller
than the current address (the "present moment"). In that case, memcpy will
work correctly no matter how it is implemented. Otherwise, you must use a
byte-wise copy, because the semantics of the compressed stream rely on
that.

If you want to optimize further, you can shorten source blocks to the
largest legal size (i.e. up to "present"), and recursively call memcpy
several times. This preserves the data dependencies as expected by the
decompressor, but allows you to call memcpy with exponentially increasing
block sizes.

Another optimization would be to check for a source block that is only a
single byte into the past, and then use memset to replicate it.

Anything else violates the assumptions made by the
compressor/decompressor.

  Holger

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

Jörn Engel writes:

quoted

Why is it an issue?  Is the performance of the byte-by-byte loop
really a limiting factor for you?

Not a limiting factor, but it should be noticable.  What is more
important - in my eyes - is that we can replace magic with obvious
code.

You are proposing to replace simple, working code with considerably
more complex code.  You need to be able to point to a specific real
situation where your change makes a significant difference if you want
to get it accepted.

If the behaviour of the copy loop is non-obvious then the thing to do
is to add a comment rather than make it more complicated.

That should not be a problem.  memcpy has a very defined behaviour, as
long as source and destination don't overlap at all or as the sourse
is smaller, than the distination.  Cool.

The behaviour is defined as long as source and destination don't
overlap.  You get no guarantees from having source < destination.  It
could quite legitimately copy backwards in all situations, or work
exactly the same as memmove.

We should be able to do something like this in the zlib:
if (repeat one byte over and over) /* undefined behaviour for memcpy */
	memset();
else {
	if (copy is wrapped) {
		memcpy(wrapped part);
		tweak pointers;
	}
	memcpy();

With that, source should always be smaller than destination for
memcpy, so the implementation details don't matter, as long as memcpy
doesn't do a reverse memcpy.

Plus, the zlib code is shorter and tells the reader exactly what it
does, without the need for extra comments.

Well no, I think it still isn't right.  What if the length is large
but dst - src == 2 (e.g. if you compress "abababababab") or 3 (e.g. if
you compress "abcabcabcabcabc")?  Or 4 or 5 or ...?  You will end up
with an awfully large number of special cases.

Paul.

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

quoted

We should be able to do something like this in the zlib:
if (repeat one byte over and over) /* undefined behaviour for memcpy */
memset();
else {
if (copy is wrapped) {
memcpy(wrapped part);
tweak pointers;
}
memcpy();

With that, source should always be smaller than destination for
memcpy, so the implementation details don't matter, as long as memcpy
doesn't do a reverse memcpy.

Plus, the zlib code is shorter and tells the reader exactly what it
does, without the need for extra comments.

Well no, I think it still isn't right.  What if the length is large
but dst - src == 2 (e.g. if you compress "abababababab") or 3 (e.g. if
you compress "abcabcabcabcabc")?  Or 4 or 5 or ...?  You will end up
with an awfully large number of special cases.

Hi,
sorry for being a bit late to reply, but as of now I am on vacation.

This works and does not depend on any arch or memcpy/memmove impl. details:

static inline Byte * memmove_update(Byte *dest, Byte *src, size_t n)
{
/* n is always >= 3 and dest > src */
  Byte *ret = dest + n;

  if (dest - src >= n)
      memmove(dest, src, n); /* no overlapping here */
  else if(dest - src == 1)
      memset(dest, *src, n); /* special case of the pattern copy loop below, can be removed  */
  else {
     /* 1 > dest - src < n */
     /* copy patten at *src to *dest, pattern len is dest - src */
     /* one could use 2 byte chunks here, since dest - src is >= 2 */
    *dest = *src;
    --n;
    do {
      *++dest = *++src;
    } while (--n);
  }
  return ret;
}

simple enough?

 Jocke

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

On Sat, 5 July 2003 23:01:15 +1000, Paul Mackerras wrote:

quoted

Not a limiting factor, but it should be noticable.  What is more
important - in my eyes - is that we can replace magic with obvious
code.

You are proposing to replace simple, working code with considerably
more complex code.  You need to be able to point to a specific real
situation where your change makes a significant difference if you want
to get it accepted.

Agreed.  And even then, I don't want to submit it before 2.7.

If the behaviour of the copy loop is non-obvious then the thing to do
is to add a comment rather than make it more complicated.

This may be highly subjective, but I consider the existing code to be
more complicated.

*q++ = *r++; c--;
*q++ = *r++; c--;

Those two lines are found three times in the current code.  Why?  Loop
unrolling, nothing but an optimization, and not a very good one, if
you look at current cpus.

The behaviour is defined as long as source and destination don't
overlap.  You get no guarantees from having source < destination.  It
could quite legitimately copy backwards in all situations, or work
exactly the same as memmove.

Also agreed.  It is hard to imagine a sane implementation that doesn't
give these guarantees, but that doesn't mean much.

Well no, I think it still isn't right.  What if the length is large
but dst - src == 2 (e.g. if you compress "abababababab") or 3 (e.g. if
you compress "abcabcabcabcabc")?  Or 4 or 5 or ...?  You will end up
with an awfully large number of special cases.

That would really make my approach more complicated.  Back to the
drawing board then...

Jörn

--
Fancy algorithms are slow when n is small, and n is usually small.
Fancy algorithms have big constants. Until you know that n is
frequently going to be big, don't get fancy.
-- Rob Pike

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

quoted

You are proposing to replace simple, working code with considerably
more complex code.  You need to be able to point to a specific real
situation where your change makes a significant difference if you want
to get it accepted.

Agreed.  And even then, I don't want to submit it before 2.7.

Why? Just look at 2.4 and you will find much boulder stuff going
in there than this.

  Jocke

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

On Mon, 7 July 2003 12:32:21 +0200, Joakim Tjernlund wrote:

quoted

Agreed.  And even then, I don't want to submit it before 2.7.

Why? Just look at 2.4 and you will find much boulder stuff going
in there than this.

Other people's bad example is no justification for my misbehaviour. ;)

This patch doesn't fix anything that is wrong, and it doesn't add
functionality that isn't there right now.  Performance is the least
important aspect of computing, unless it has an impact on
functionality as well. (audio without glitches and such)

Besides, Marcelo didn't even take my fixes for the zlib yet, so there
is more important stuff in the queue.

Jörn

--
Fancy algorithms are slow when n is small, and n is usually small.
Fancy algorithms have big constants. Until you know that n is
frequently going to be big, don't get fancy.
-- Rob Pike

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

On Mon, 7 July 2003 12:32:21 +0200, Joakim Tjernlund wrote:

quoted

quoted

Agreed.  And even then, I don't want to submit it before 2.7.

Why? Just look at 2.4 and you will find much boulder stuff going
in there than this.

Other people's bad example is no justification for my misbehaviour. ;)

This patch doesn't fix anything that is wrong, and it doesn't add
functionality that isn't there right now.

[SNIP]

Nor does most of you zlib patches either, but most of them are in 2.5.
Point being, this is not a major change(so far). If nothing wrong is found and
it is noticeably faster, I think it should go into 2.5.

 Jocke

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/

On Mon, 7 July 2003 14:58:33 +0200, Joakim Tjernlund wrote:

quoted

This patch doesn't fix anything that is wrong, and it doesn't add
functionality that isn't there right now.

Nor does most of you zlib patches either, but most of them are in 2.5.
Point being, this is not a major change(so far). If nothing wrong is found and
it is noticeably faster, I think it should go into 2.5.

Point taken.  If tests and benchmarks agree, it should go in.

Jörn

--
A defeated army first battles and then seeks victory.
-- Sun Tzu

** Sent via the linuxppc-dev mail list. See http://lists.linuxppc.org/