core.traits?
jmh530
john.michael.hall at gmail.com
Wed Jan 9 18:55:30 UTC 2019
On Wednesday, 9 January 2019 at 17:40:38 UTC, H. S. Teoh wrote:
> [snip]
>
> EXACTLY!!!
>
> Some time ago I took an interest in implementing the equivalent
> of strchr in the most optimized way possible. For that, I wrote
> several of my own algorithms and also perused the glibc
> implementation.
>
> Eventually, I realized that the glibc implementation, which
> uses fancy 64-bit-word scanning with a lot of setup overhead
> and messy starting/trailing cases, is optimizing for very large
> scans, i.e., when the byte being sought occurs only rarely in a
> very large haystack. In those cases it's at the top of
> benchmarks. However, in the arguably more common case where
> the byte being sought occurs relatively frequently in small- to
> medium-sized haystacks, repeatedly searching the haystack
> incurs a ton of overhead setting up all that fancy machinery,
> branch hazards, and what-not, where a plain ole `while (*ptr++
> != needle) {}` works much better.
>
> I suspect many of the C library functions of this sort (incl.
> memcpy + friends) have a tendency to suffer from this sort of
> premature optimization.
>
> Not to mention that often overly-specialized benchmarks of this
> sort fail to account for bias caused by the CPU's branch
> predictor learning the benchmark and the cache hierarchy
> amortizing the cost of repeatedly searching the same haystack
> -- things you rarely do in real-life applications. There's a
> big risk of your "super-optimized" algorithm ending up
> optimizing for an unrealistic use-case, but having only
> mediocre or sometimes even poor performance in real-world
> computations.
One thing I like about libmir's sum function
http://docs.algorithm.dlang.io/latest/mir_math_sum.html
was that the algorithm you use to return the sum can be chosen
with an enum on the template. So it's really a collection of
different sum algorithms all in one. Set the default as something
reasonable and then let the user decide if they want something
else.
More information about the Digitalmars-d
mailing list