#Raph-Levien lucidly explains how his new #font rasterizer "font-rs" in #Rust is the fastest (≈6× faster than FreeType). Among other things, he uses #SSE #prefix-sum to do the filling, and structures the parser as an iterator to avoid allocation. #graphics #performance
on 02016-08-03getting 7× #performance on #prefix-sum with #SSE in #C++
on 02016-08-03#pdf #paper describing the Viola-Jones #computer-vision #algorithms for rapid object detection combining a number of simple Haar-like features and AdaBoost, using sum tables (aka #prefix-sum or summed-area tables: “We choose a different name here in order to emphasize its use for the analysis of images, rather than for texture mapping.”)
on 02016-01-18out-of-the-box #parallel sorting and #prefix-sum of arrays in #Java 8 for #performance.
on 02015-08-27A survey #paper of #parallel #prefix-sum #algorithms, finding that the Kogge-Stone algorithm is more common in #GPGPU code than Blelloch’s, and with handy diagrams so you can see what they’re talking about! Also they apparently wrote a thing to use #formal-methods to verify different implementations.
on 02015-08-15The Ladner & Fischer 1980 #paper on #parallel #algorithms for #finite-automata using #prefix-sum, with its unnecessary extra N² inefficiency compared to the N lg N in Hillis & Steele 1986. I think, anyway. I haven’t really read the paper.
on 02015-08-15#Algorithms for best #performance on a #parallel #prefix-sum in #CUDA for #GPGPU as of 2007.
on 02015-08-15“Data-Parallel Finite State Machines”: #parallel simulation of #finite-automata that are “up to 3× faster than optimized sequential implementations on a single processor” in #performance due to using #SIMD instructions. Seems to be some tweaks to the #prefix-sum thing Blelloch mentioned in his 1993 #paper, which they call “enumerative computation”? These algorithms are probably crucial to speeding up #CSV parsing.
on 02015-08-15“Prefix Sums and Their Applications”, Blelloch 93. This is the definitive #paper on #prefix-sum #algorithms as of uh 22 years ago. It mentions specifically a #regular-expression #search-engine and #lexing as two of the applications of prefix sum! I think the “parallel solution of recurrence problems” mentioned here can be applied to #DSP IIR filtering. This is just “Chapter 1” (of what, I have no idea), but it promises more meat in chapters 2, 3, and 4, mostly to do with linked lists and trees.
on 02015-08-15