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