https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=288321
Bug ID: 288321
Summary: memrchr function can be very slow
Product: Base System
Version: CURRENT
Hardware: amd64
OS: Any
Status: New
Severity: Affects Many People
Priority: ---
Component: misc
Assignee: [email protected]
Reporter: [email protected]
Attachment #262276 text/plain
mime type:
Created attachment 262276
--> https://bugs.freebsd.org/bugzilla/attachment.cgi?id=262276&action=edit
Naive memrchr implementation in C++.
>From memchr(3):
"The memrchr() function behaves like memchr(), except that it locates the last
occurrence of c in string b."
The amd64 optimized memrchr function always scans the entire buffer, from
beginning to end, before returning the last match:
https://github.com/freebsd/freebsd-src/blob/main/lib/libc/amd64/string/memrchr.S
When there is a match near the end of the buffer, this implementation is O(n)
when it should be close to O(1). In this (common?) case it is easily beaten by
a "naive" memrchr implementation (see attachment). E.g. finding the last line
break in a 1MB buffer where there is a line break 500 bytes from the end, a
naive memrchr is over 200x faster. And if the last byte is a line break the
naive version is ~40000x faster.
--
You are receiving this mail because:
You are the assignee for the bug.
