This is the mail archive of the
libc-alpha@sources.redhat.com
mailing list for the glibc project.
strpbrk, strspn, and strcspn optimization suggestion
- From: Hrvoje Niksic <hniksic at xemacs dot org>
- To: libc-alpha at sources dot redhat dot com
- Date: Thu, 23 Jun 2005 22:57:42 +0200
- Subject: strpbrk, strspn, and strcspn optimization suggestion
I stumbled upon an article that describes a fast strspn/strcspn
implementation that would also apply to strpbrk and strtok/strtok_r:
http://tinyurl.com/clynr
Compared to usual table-driver approach, the twist is that table cells
are marked with a different value on each invocation, so that the
entire table needs to be cleared only once in 256 invocations. This
reduces the cost of string traversal to approx. O(n+m) compared to
O(n*m) in the current implementation, or to O(n+m+table_size) for a
table allocated and initialized every time (not counting allocation
costs).
The table and the cycle variable should be in thread-local storage. I
don't know if the addition of a 256-char table per thread is deemed
acceptable for this optimization, but it should be noted that the same
256-char table can be used by all the involved functions.
Do you think this optimization is worth including in glibc?