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