strpbrk, strspn, and strcspn optimization suggestion
Hrvoje Niksic
hniksic@xemacs.org
Thu Jun 23 20:57:00 GMT 2005
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?
More information about the Libc-alpha
mailing list