[PATCH v6] sysdeps/x86_64/multiarch/memmem-avx2.c: add memmem-avx2.c

[James]

On Tue, Feb 20, 2024 at 11:14 PM Noah Goldstein <goldstein.w.n@gmail.com>
wrote:

> On Tue, Feb 20, 2024 at 3:16 PM James <tirtajames45@gmail.com> wrote:
> >
> > (Resend because I didn't reply all)
> >
> > On Tue, Feb 20, 2024 at 9:30 PM Adhemerval Zanella Netto <
> adhemerval.zanella@linaro.org> wrote:
> >>
> >>
> >>
> >> On 20/02/24 00:00, James wrote:
> >> > On Tue, Feb 20, 2024 at 12:20 AM Noah Goldstein <
> goldstein.w.n@gmail.com <mailto:goldstein.w.n@gmail.com>> wrote:
> >> >
> >> >     On Mon, Feb 19, 2024 at 2:25 PM Adhemerval Zanella Netto
> >> >     <adhemerval.zanella@linaro.org <mailto:
> adhemerval.zanella@linaro.org>> wrote:
> >> >     >
> >> >     >
> >> >     >
> >> >     > On 19/02/24 05:13, Alexander Monakov wrote:
> >> >     > >
> >> >     > > On Mon, 19 Feb 2024, Noah Goldstein wrote:
> >> >     > >
> >> >     > >> It doesn't seem you have addressed many of the comments from
> your v5 patch.
> >> >     > >> Can it helps if you
> >> >     > >> 1: Reply to the comments indicating they are handled / why
> are choosing not
> >> >     > >> to handle them.
> >> >     > >> 2: Send further versions to the same email chain.
> (`--in-reply-to`
> >> >     > >> with `git send-email`).
> >> >     > >
> >> >     > > Are you ok with the change in worst-case time complexity? The
> existing generic
> >> >     > > implementation is O(n+m), the proposed variants are O(n*m).
> >> >     >
> >> >     > I think we should consider this a regression, we already have a
> bug opened for
> >> >     > wcsstr [1] for a similar issue. We already had another similar
> issue for
> >> >     > PowerPC [2], and we did not have consensus back then because
> the generic
> >> >     > implementation was also O(m*n) (it was before Wilco new
> implementation).
> >> >
> >> >     Think practically this impl would be faster for short needles.
> Maybe
> >> >     limit to `m < ~16`, otherwise fallback to generic?
> >> >
> >> > This implementation is virtually O(n) for m <= VEC_SIZE, so I think
> it should be at least m <= VEC_SIZE, and since generic implementation uses
> O(n+m) for m > 256, it should be m <= 256, unless we want to directly use
> str-two-way.h, which I think would be a waste of code size.
> >>
> >> Afaik s390x do use a similar strategy, so it should be ok to optimize
> for
> >> m <= VEC_SIZE.
> >>
> >> Also, please check why your patch is making aarch64/arm buildbot fails
> to
> >> build [1]. You can bootstrap a toolchain using the build-many-glibcs.py
> >> script it required.
> >
> > It seems that it has to do with the libc_hidden_builtin_def in
> string/memmem.c which I don't really understand.
>
> Instead of adding a new hidden def at the end of `string/memmem.c`,
> just replace the existing
> using of `__memmem` with `MEMMEM`
>
With

#ifndef _LIBC
# define __memmem memmem
#endif

#ifndef MEMMEM
# define MEMMEM __memmem
#endif

void *
MEMMEM (const void *haystack, size_t hs_len,
 const void *needle, size_t ne_len)

libc_hidden_def (MEMMEM)
weak_alias (MEMMEM, memmem)
libc_hidden_weak (memmem)

make test t=string/test-memmem on x86-64 shows

 ./../include/libc-symbols.h:472:33: error: ‘__EI___memmem_generic’ aliased
to undefined symbol ‘__GI___memmem_generic’
  472 |   extern thread __typeof (name) __EI_##name \
      |                                 ^~~~~
./../include/libc-symbols.h:468:3: note: in expansion of macro
‘__hidden_ver2’
  468 |   __hidden_ver2 (, local, internal, name)
      |   ^~~~~~~~~~~~~
./../include/libc-symbols.h:476:41: note: in expansion of macro
‘__hidden_ver1’
  476 | #  define hidden_def(name)              __hidden_ver1(__GI_##name,
name, name);
      |                                         ^~~~~~~~~~~~~
./../include/libc-symbols.h:557:32: note: in expansion of macro ‘hidden_def’
  557 | # define libc_hidden_def(name) hidden_def (name)
      |                                ^~~~~~~~~~
../string/memmem.c:131:1: note: in expansion of macro ‘libc_hidden_def’
  131 | libc_hidden_def (MEMMEM)
      | ^~~~~~~~~~~~~~~
./../include/libc-symbols.h:472:33: error: ‘__EI_memmem’ aliased to
undefined symbol ‘__GI_memmem’
  472 |   extern thread __typeof (name) __EI_##name \
      |                                 ^~~~~
./../include/libc-symbols.h:468:3: note: in expansion of macro
‘__hidden_ver2’
  468 |   __hidden_ver2 (, local, internal, name)
      |   ^~~~~~~~~~~~~
./../include/libc-symbols.h:484:9: note: in expansion of macro
‘__hidden_ver1’
  484 |         __hidden_ver1(__GI_##name, name, name)
__attribute__((weak));
      |         ^~~~~~~~~~~~~
./../include/libc-symbols.h:558:33: note: in expansion of macro
‘hidden_weak’
  558 | # define libc_hidden_weak(name) hidden_weak (name)
      |                                 ^~~~~~~~~~~
../string/memmem.c:133:1: note: in expansion of macro ‘libc_hidden_weak’
  133 | libc_hidden_weak (memmem)
      | ^~~~~~~~~~~~~~~~
make[2]: *** [/home/james/.local/src/glibc/build/sysd-rules:671:
/home/james/.local/src/glibc/build/string/memmem.os] Error 1
make[2]: Leaving directory '/home/james/.local/src/glibc/string'
make[1]: *** [Makefile:759: test] Error 2
make[1]: Leaving directory '/home/james/.local/src/glibc'
make: *** [Makefile:9: test] Error 2
>
> >>
> >>
> >> [1]
> https://patchwork.sourceware.org/project/glibc/patch/20240218082621.131128-1-tirtajames45@gmail.com/
> >>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://sourceware.org/pipermail/libc-alpha/attachments/20240220/979cdb35/attachment.htm>