-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 According to jakub at redhat dot com on 12/21/2007 7:00 AM: > ------- Additional Comments From jakub at redhat dot com 2007-12-21 14:00 > ------- >> Can you explain why? > > Because the malloc call makes the function no longer async-signal safe. > While POSIX says nothing about memmem, it is quite desirable to let > the basic mem* and str*/stp* memory/string ops are async-signal safe (of > course > strdup is an exception here).
Jakub raises an interesting point here. While memmem is not standardized, it is similar to strstr, yet POSIX makes no requirements that any of the str* functions be async-signal safe. Is this worth raising with the Austin Group for clarification in the next version of POSIX? Meanwhile, this means that it is likely that glibc's strstr and memmem will NEVER be fixed to be O(n) (the only way to avoid the O(n^2) worst case is to allocate O(n) memory, trading space for time). Perhaps it is worth splitting the memmem module into two - memmem, which provides memmem on systems that lack it or that have non-performance bugs, but can live with glibc's (and other platforms') deficient performance in the worst case, and used by programs that control their use of memmem such that the needle never exceeds the threshold that triggers the O(n^2) behavior; and memmem-fast (or perhaps invent a different interface name, to distinguish the performance improvement at the expense of async-safety) that guarantees the O(n) performance but documents that it is no longer async-safe. And another thought: while mbsstr favors KMP because it is much easier to traverse multibyte characters in forward order, memmem would probably be better off with a variant like turbo-Boyer-Moore; both algorithms have O(n) worst case, but where searching backwards is not prohibitive (remember, memmem searches bytes, not multibyte characters), TBM has the nice property of superlinear speed in the common case. - -- Don't work too hard, make some time for fun as well! Eric Blake [EMAIL PROTECTED] -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.5 (Cygwin) Comment: Public key at home.comcast.net/~ericblake/eblake.gpg Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHfcCr84KuGfSFAYARAgDTAJ41KyE3wZoyimaZwwnD/94VqKHyRACeM5MT XnvaoE2h3YRCBAv1guoSeO8= =Pt6z -----END PGP SIGNATURE-----
