This is the mail archive of the glibc-bugs@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]

[Bug libc/5514] memmem is O(n^2), but should be O(n)


------- Additional Comments From bruno at clisp dot org  2007-12-21 13:50 -------
> it is not really feasible to have functions like memmem and strstr
> calling malloc.

When the call to malloc fails, the proposed memmem code falls back to the
O(n^2) code, so degrades gracefully, still returning the correct result
(just slower).

> Such functions have always been simple reentrant code before,
> and we can't go introducing locking and so forth there.

Can you explain why? The locking is done inside malloc(). The performance
will not suffer in most cases, since malloc() is called only when the
algorithm has hints that it is running on one of the worst-case scenarios.

> post the patch to libc-alpha.

Our experience with submissions via bugzilla has been better than with
posts to libc-alpha.

-- 


http://sourceware.org/bugzilla/show_bug.cgi?id=5514

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.


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