This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH v2] Improve performance of strstr


Hi Szabolcs,

> in this case a large slowdown is not a real vulnerability.

Absolutely, performance varies quite dramatically with different inputs. That
is true for all algorithms even they are "real-time". Caches and branch
predictors are not going away.

> i think even doing memcmp at every byte position is not a
> denial of service concern if the needle is <= 256 bytes.
> (maybe we should use a lower limit? <= 64?)

It couldn't be since its worst case isn't actually much worse (~2.2 times for
needle size of 256). A simple memcmp at every character is significantly
faster than Two-way on the first bad needle, and about the same performance
on the second.

Also when reducing the size of the needle to 31 from 255 on my algorithm,
there is only a 73% speedup for its worst case (bad needle 2). So reducing the
cutoff doesn't really help the worst case since we're clearly not quadratic.

Wilco
    

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]